13520962205

Committed 25 Feb 2025 12:14PM UTC coverage: 50.351% (+0.02%) from 50.335%

Build # 13520962205

Build Type

Pull #1745

github

Committed by

web-flow

Commit Message

Merge 8c44f5bf8 into 26465f26c

Pull Request Pull Request #1745: Don't draw content of ship window if minimized

Run Details

24 of 73 new or added lines in 9 files covered. (32.88%)

16 existing lines in 8 files now uncovered.

22383 of 44454 relevant lines covered (50.35%)

37105.2 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.19

/libs/s25main/mapGenerator/Algorithms.h

// Copyright (C) 2005 - 2021 Settlers Freaks (sf-team at siedler25.org)
//
// SPDX-License-Identifier: GPL-2.0-or-later

#pragma once

#include "RttrForeachPt.h"
#include "helpers/containerUtils.h"
#include "mapGenerator/NodeMapUtilities.h"
#include "world/NodeMapBase.h"
#include <cmath>
#include <queue>
#include <set>
#include <stdexcept>

namespace rttr::mapGenerator {

template<typename T>
auto join(const T& container)
{
    using E = typename T::value_type::value_type;
    std::vector<E> joined;
    for(const auto& el : container)
    {
        joined.insert(joined.end(), el.begin(), el.end());
    }
    return joined;
}

/**
 * Smoothes the specified nodes with a smoothing kernel of the specified extent (radius).
 *
 * @param iteration number of times to apply smoothing kernel to every node
 * @param radius extent of the smoothing kernel
 * @param nodes map of node values
 */
template<typename T>
void Smooth(unsigned iterations, unsigned radius, NodeMapBase<T>& nodes)
{
    const MapExtent& size = nodes.GetSize();
    std::vector<std::vector<MapPoint>> neighbors(size.x * size.y);

    RTTR_FOREACH_PT(MapPoint, size)
    {
        neighbors[nodes.GetIdx(pt)] = nodes.GetPointsInRadius(pt, radius);
    }

    for(unsigned i = 0; i < iterations; ++i)
    {
        RTTR_FOREACH_PT(MapPoint, size)
        {
            int sum = static_cast<int>(nodes[pt]);
            const auto& neighborPoints = neighbors[nodes.GetIdx(pt)];

            for(const MapPoint& p : neighborPoints)
            {
                sum += static_cast<int>(nodes[p]);
            }

            nodes[pt] = static_cast<T>(round(static_cast<double>(sum) / (neighborPoints.size() + 1)));
        }
    }
}

/// Flatten the height map so a castle sized building can be placed at pos
void FlattenForCastleBuilding(NodeMapBase<uint8_t>& heightMap, MapPoint pos);

/**
 * Maps the values to the specified range [minimum, maximum].
 *
 * @param values map of  comparable values
 * @param minimum minimum value to map any values to
 * @param maximum maximum value to map any values to
 */
template<typename T>
void Scale(NodeMapBase<T>& values, T minimum, T maximum)
{
    auto range = GetRange(values);
    auto actualRange = range.GetDifference();
    auto actualMinimum = range.minimum;

    if(actualRange == 0)
    {
        return;
    }

    auto scaledRange = maximum - minimum;

    RTTR_FOREACH_PT(MapPoint, values.GetSize())
    {
        auto normalizer = static_cast<double>(values[pt] - actualMinimum) / actualRange;
        auto offset = round(normalizer * scaledRange);

        values[pt] = static_cast<T>(minimum + offset);
    }
}

/**
 * Collects all map points around the specified point for which the evaluator returns 'true'. The function
 * recursively checks neighbors of neighbors but only collects positively evaluated points. Whenever it hits a
 * negative value is stops searching the neighborhood of this specific point. The underlying implementation is
 * breadth-first search.
 *
 * @param map reference to the map to collect map points from
 * @param pt starting point which has to be evaluated with 'true' or and empty vector will be returned
 * @param evaluator evaluator function which returns 'true' or 'false' for any map point
 *
 * @returns a list of map points where every point is connected to at least one other point of the least which
 * has also been evaluated positively.
 */
template<typename T>
std::vector<MapPoint> Collect(const MapBase& map, const MapPoint& pt, T&& evaluator)
{
    std::set<MapPoint, MapPointLess> visited;
    std::vector<MapPoint> body;
    std::queue<MapPoint> searchSpace;

    searchSpace.push(pt);

    while(!searchSpace.empty())
    {
        MapPoint currentPoint = searchSpace.front();
        searchSpace.pop();

        if(evaluator(currentPoint))
        {
            if(visited.insert(currentPoint).second)
            {
                body.push_back(currentPoint);

                const auto& neighbors = map.GetNeighbours(currentPoint);
                for(MapPoint neighbor : neighbors)
                {
                    searchSpace.push(neighbor);
                }
            }
        }
    }

    return body;
}

/**
 * Updates the specified distance values to the values initially contained by the queue. The queue is being
 * modified throughout the process for performance reasons.
 *
 * @param distances distance map which is being updated
 * @param queue queue with initial elements to used for distance computation
 */
void UpdateDistances(NodeMapBase<unsigned>& distances, std::queue<MapPoint>& queue);

/**
 * Computes a map of distance values describing the distance of each grid position to the closest flagged point.
 *
 * @param flaggedPoints contains all flagged points
 * @param size size of  the map
 *
 * @return distance of each grid position to closest flagged point.
 */
template<class T_Container>
NodeMapBase<unsigned> DistancesTo(const T_Container& flaggedPoints, const MapExtent& size)
{
    std::queue<MapPoint> queue;
    NodeMapBase<unsigned> distances;
    distances.Resize(size, unsigned(-1));

    for(const MapPoint& pt : flaggedPoints)
    {
        distances[pt] = 0;
        queue.push(pt);
    }

    UpdateDistances(distances, queue);

    return distances;
}

template<typename T>
NodeMapBase<unsigned> DistancesTo(const MapExtent& size, T&& evaluator)
{
    return DistancesTo(SelectPoints(evaluator, size), size);
}

/**
 * Computes a map of distance values describing the distance of each grid position to the closest position for
 * which the evaluator returned `true`. The computation takes place only within the specified area - points outside
 * the area are set to a maximum value of width + height of the map.
 *
 * @param size size of  the map
 * @param area area to compute distance values for
 * @param defaultValue default distance value applied to points outside of the specified area
 * @param evaluator evaluator function takes a MapPoint as input and returns `true` or `false`
 *
 * @return distance of each grid position to closest point which has been evaluted with `true`.
 */
template<typename T, class T_Container>
NodeMapBase<unsigned> Distances(const MapExtent& size, const T_Container& area, const unsigned defaultValue,
                                T&& evaluator)
{
    std::queue<MapPoint> queue;
    NodeMapBase<unsigned> distances;
    distances.Resize(size, defaultValue);

    for(const MapPoint& pt : area)
    {
        if(evaluator(pt))
        {
            distances[pt] = 0;
            queue.push(pt);
        } else
        {
            distances[pt] = unsigned(-1);
        }
    }

    UpdateDistances(distances, queue);

    return distances;
}

/**
 * Computes an upper limit for the specified values. The number of values between the specified minimum and the
 * computed limit is at least as high as the specified coverage of the map.
 *
 * @param values map of comparable values
 * @param coverage percentage of expected map coverage (value between 0 and 1)
 * @param minimum minimum value to consider
 *
 * @returns a value between the specified minimum and the maximum value of the map.
 */
template<typename T>
T LimitFor(const NodeMapBase<T>& values, double coverage, T minimum)
{
    if(coverage < 0 || coverage > 1)
    {
        throw std::invalid_argument("coverage must be between 0 and 1");
    }

    const T maximum = *std::max_element(values.begin(), values.end());

    if(minimum == maximum)
    {
        return maximum;
    }

    const auto nodes = values.GetWidth() * values.GetHeight();
    const auto expectedNodes = static_cast<unsigned>(coverage * nodes);

    unsigned currentNodes = 0;
    unsigned previousNodes = 0;

    T limit = minimum;

    while(currentNodes < expectedNodes && limit <= maximum)
    {
        previousNodes = currentNodes;
        currentNodes =
          helpers::count_if(values, [minimum, limit](const T value) { return value >= minimum && value <= limit; });
        limit++;
    }

    if(expectedNodes - previousNodes < currentNodes - expectedNodes)
    {
        return limit - 2;
    }

    return limit - 1;
}

/**
 * Computes an upper limit for the specified values. The number of values between the specified minimum and the
 * computed limit is at least as high as the specified coverage of the map.
 *
 * @param values map of comparable values
 * @param area area of nodes to consider
 * @param coverage percentage of expected map coverage (value between 0 and 1)
 * @param minimum minimum value to consider
 *
 * @returns a value between the specified minimum and the maximum value of the map.
 */
template<typename T, class T_Area>
T LimitFor(const NodeMapBase<T>& values, const T_Area& area, double coverage, T minimum)
{
    if(coverage < 0 || coverage > 1)
    {
        throw std::invalid_argument("coverage must be between 0 and 1");
    }

    const T maximum = GetMaximum(values, area);

    if(minimum >= maximum)
    {
        return maximum;
    }

    const auto nodes = area.empty() ? values.GetWidth() * values.GetHeight() : area.size();
    const auto expectedNodes = static_cast<unsigned>(coverage * nodes);

    unsigned currentNodes = 0;
    unsigned previousNodes = 0;

    T limit = minimum;

    while(currentNodes < expectedNodes && limit <= maximum)
    {
        previousNodes = currentNodes;
        currentNodes = helpers::count_if(
          area, [&values, minimum, limit](const MapPoint& pt) { return values[pt] >= minimum && values[pt] <= limit; });
        limit++;
    }

    if(expectedNodes - previousNodes < currentNodes - expectedNodes)
    {
        return limit - 2;
    }

    return limit - 1;
}

} // namespace rttr::mapGenerator

1	// Copyright (C) 2005 - 2021 Settlers Freaks (sf-team at siedler25.org)
2	//
3	// SPDX-License-Identifier: GPL-2.0-or-later
4
5	#pragma once
6
7	#include "RttrForeachPt.h"
8	#include "helpers/containerUtils.h"
9	#include "mapGenerator/NodeMapUtilities.h"
10	#include "world/NodeMapBase.h"
11	#include <cmath>
12	#include <queue>
13	#include <set>
14	#include <stdexcept>
15
16	namespace rttr::mapGenerator {
17
18	template<typename T>
19	auto join(const T& container)	8✔
20	{
21	using E = typename T::value_type::value_type;
22	std::vector<E> joined;	8✔
23	for(const auto& el : container)	19✔
24	{
25	joined.insert(joined.end(), el.begin(), el.end());	11✔
26	}
27	return joined;	8✔
28	}
29
30	/**
31	* Smoothes the specified nodes with a smoothing kernel of the specified extent (radius).
32	*
33	* @param iteration number of times to apply smoothing kernel to every node
34	* @param radius extent of the smoothing kernel
35	* @param nodes map of node values
36	*/
37	template<typename T>
38	void Smooth(unsigned iterations, unsigned radius, NodeMapBase<T>& nodes)	8✔
39	{
40	const MapExtent& size = nodes.GetSize();	8✔
41	std::vector<std::vector<MapPoint>> neighbors(size.x * size.y);	16✔
42
43	RTTR_FOREACH_PT(MapPoint, size)	25,738✔
44	{
45	neighbors[nodes.GetIdx(pt)] = nodes.GetPointsInRadius(pt, radius);	25,356✔
46	}
47
48	for(unsigned i = 0; i < iterations; ++i)	75✔
49	{
50	RTTR_FOREACH_PT(MapPoint, size)	271,383✔
51	{
52	int sum = static_cast<int>(nodes[pt]);	267,496✔
53	const auto& neighborPoints = neighbors[nodes.GetIdx(pt)];	267,496✔
54
55	for(const MapPoint& p : neighborPoints)	5,103,928✔
56	{
57	sum += static_cast<int>(nodes[p]);	4,836,432✔
58	}
59
60	nodes[pt] = static_cast<T>(round(static_cast<double>(sum) / (neighborPoints.size() + 1)));	267,496✔
61	}
62	}
63	}	8✔
64
65	/// Flatten the height map so a castle sized building can be placed at pos
66	void FlattenForCastleBuilding(NodeMapBase<uint8_t>& heightMap, MapPoint pos);
67
68	/**
69	* Maps the values to the specified range [minimum, maximum].
70	*
71	* @param values map of comparable values
72	* @param minimum minimum value to map any values to
73	* @param maximum maximum value to map any values to
74	*/
75	template<typename T>
76	void Scale(NodeMapBase<T>& values, T minimum, T maximum)	17✔
77	{
78	auto range = GetRange(values);	17✔
79	auto actualRange = range.GetDifference();	17✔
80	auto actualMinimum = range.minimum;	17✔
81
82	if(actualRange == 0)	17✔
83	{
84	return;	1✔
85	}
86
87	auto scaledRange = maximum - minimum;	16✔
88
89	RTTR_FOREACH_PT(MapPoint, values.GetSize())	51,236✔
90	{
91	auto normalizer = static_cast<double>(values[pt] - actualMinimum) / actualRange;	50,472✔
92	auto offset = round(normalizer * scaledRange);	50,472✔
93
94	values[pt] = static_cast<T>(minimum + offset);	50,472✔
95	}
96	}
97
98	/**
99	* Collects all map points around the specified point for which the evaluator returns 'true'. The function
100	* recursively checks neighbors of neighbors but only collects positively evaluated points. Whenever it hits a
101	* negative value is stops searching the neighborhood of this specific point. The underlying implementation is
102	* breadth-first search.
103	*
104	* @param map reference to the map to collect map points from
105	* @param pt starting point which has to be evaluated with 'true' or and empty vector will be returned
106	* @param evaluator evaluator function which returns 'true' or 'false' for any map point
107	*
108	* @returns a list of map points where every point is connected to at least one other point of the least which
109	* has also been evaluated positively.
110	*/
111	template<typename T>
112	std::vector<MapPoint> Collect(const MapBase& map, const MapPoint& pt, T&& evaluator)	8,529✔
113	{
114	std::set<MapPoint, MapPointLess> visited;	17,058✔
115	std::vector<MapPoint> body;	8,529✔
116	std::queue<MapPoint> searchSpace;	17,058✔
117
118	searchSpace.push(pt);	8,529✔
119
120	while(!searchSpace.empty())	99,408✔
121	{
122	MapPoint currentPoint = searchSpace.front();	90,879✔
123	searchSpace.pop();	90,879✔
124
125	if(evaluator(currentPoint))	90,879✔
126	{
127	if(visited.insert(currentPoint).second)	75,202✔
128	{
129	body.push_back(currentPoint);	13,725✔
130
131	const auto& neighbors = map.GetNeighbours(currentPoint);	13,725✔
132	for(MapPoint neighbor : neighbors)	96,075✔
133	{
134	searchSpace.push(neighbor);	82,350✔
135	}
136	}
137	}
138	}
139
140	return body;	17,058✔
141	}
142
143	/**
144	* Updates the specified distance values to the values initially contained by the queue. The queue is being
145	* modified throughout the process for performance reasons.
146	*
147	* @param distances distance map which is being updated
148	* @param queue queue with initial elements to used for distance computation
149	*/
150	void UpdateDistances(NodeMapBase<unsigned>& distances, std::queue<MapPoint>& queue);
151
152	/**
153	* Computes a map of distance values describing the distance of each grid position to the closest flagged point.
154	*
155	* @param flaggedPoints contains all flagged points
156	* @param size size of the map
157	*
158	* @return distance of each grid position to closest flagged point.
159	*/
160	template<class T_Container>
161	NodeMapBase<unsigned> DistancesTo(const T_Container& flaggedPoints, const MapExtent& size)	190✔
162	{
163	std::queue<MapPoint> queue;	380✔
164	NodeMapBase<unsigned> distances;	190✔
165	distances.Resize(size, unsigned(-1));	190✔
166
167	for(const MapPoint& pt : flaggedPoints)	154,032✔
168	{
169	distances[pt] = 0;	153,842✔
170	queue.push(pt);	153,842✔
171	}
172
173	UpdateDistances(distances, queue);	190✔
174
175	return distances;	380✔
176	}
177
178	template<typename T>
179	NodeMapBase<unsigned> DistancesTo(const MapExtent& size, T&& evaluator)	133✔
180	{
181	return DistancesTo(SelectPoints(evaluator, size), size);	133✔
182	}
183
184	/**
185	* Computes a map of distance values describing the distance of each grid position to the closest position for
186	* which the evaluator returned `true`. The computation takes place only within the specified area - points outside
187	* the area are set to a maximum value of width + height of the map.
188	*
189	* @param size size of the map
190	* @param area area to compute distance values for
191	* @param defaultValue default distance value applied to points outside of the specified area
192	* @param evaluator evaluator function takes a MapPoint as input and returns `true` or `false`
193	*
194	* @return distance of each grid position to closest point which has been evaluted with `true`.
195	*/
196	template<typename T, class T_Container>
197	NodeMapBase<unsigned> Distances(const MapExtent& size, const T_Container& area, const unsigned defaultValue,	6✔
198	T&& evaluator)
199	{
200	std::queue<MapPoint> queue;	12✔
201	NodeMapBase<unsigned> distances;	6✔
202	distances.Resize(size, defaultValue);	6✔
203
204	for(const MapPoint& pt : area)	2,589✔
205	{
206	if(evaluator(pt))	2,583✔
207	{
208	distances[pt] = 0;	425✔
209	queue.push(pt);	425✔
210	} else
211	{
212	distances[pt] = unsigned(-1);	2,158✔
213	}
214	}
215
216	UpdateDistances(distances, queue);	6✔
217
218	return distances;	12✔
219	}
220
221	/**
222	* Computes an upper limit for the specified values. The number of values between the specified minimum and the
223	* computed limit is at least as high as the specified coverage of the map.
224	*
225	* @param values map of comparable values
226	* @param coverage percentage of expected map coverage (value between 0 and 1)
227	* @param minimum minimum value to consider
228	*
229	* @returns a value between the specified minimum and the maximum value of the map.
230	*/
231	template<typename T>
232	T LimitFor(const NodeMapBase<T>& values, double coverage, T minimum)	15✔
233	{
234	if(coverage < 0 \|\| coverage > 1)	15✔
235	{
236	throw std::invalid_argument("coverage must be between 0 and 1");	×
237	}
238
239	const T maximum = *std::max_element(values.begin(), values.end());	15✔
240
241	if(minimum == maximum)	15✔
242	{
243	return maximum;	×
244	}
245
246	const auto nodes = values.GetWidth() * values.GetHeight();	15✔
247	const auto expectedNodes = static_cast<unsigned>(coverage * nodes);	15✔
248
249	unsigned currentNodes = 0;	15✔
250	unsigned previousNodes = 0;	15✔
251
252	T limit = minimum;	15✔
253
254	while(currentNodes < expectedNodes && limit <= maximum)	284✔
255	{
256	previousNodes = currentNodes;	269✔
257	currentNodes =	269✔
258	helpers::count_if(values, [minimum, limit](const T value) { return value >= minimum && value <= limit; });	1,198,077✔
259	limit++;	269✔
260	}
261
262	if(expectedNodes - previousNodes < currentNodes - expectedNodes)	15✔
263	{
264	return limit - 2;	7✔
265	}
266
267	return limit - 1;	8✔
268	}
269
270	/**
271	* Computes an upper limit for the specified values. The number of values between the specified minimum and the
272	* computed limit is at least as high as the specified coverage of the map.
273	*
274	* @param values map of comparable values
275	* @param area area of nodes to consider
276	* @param coverage percentage of expected map coverage (value between 0 and 1)
277	* @param minimum minimum value to consider
278	*
279	* @returns a value between the specified minimum and the maximum value of the map.
280	*/
281	template<typename T, class T_Area>
282	T LimitFor(const NodeMapBase<T>& values, const T_Area& area, double coverage, T minimum)	7✔
283	{
284	if(coverage < 0 \|\| coverage > 1)	7✔
285	{
286	throw std::invalid_argument("coverage must be between 0 and 1");	×
287	}
288
289	const T maximum = GetMaximum(values, area);	7✔
290
291	if(minimum >= maximum)	7✔
292	{
293	return maximum;	×
294	}
295
296	const auto nodes = area.empty() ? values.GetWidth() * values.GetHeight() : area.size();	7✔
297	const auto expectedNodes = static_cast<unsigned>(coverage * nodes);	7✔
298
299	unsigned currentNodes = 0;	7✔
300	unsigned previousNodes = 0;	7✔
301
302	T limit = minimum;	7✔
303
304	while(currentNodes < expectedNodes && limit <= maximum)	63✔
305	{
306	previousNodes = currentNodes;	56✔
307	currentNodes = helpers::count_if(	56✔
308	area, [&values, minimum, limit](const MapPoint& pt) { return values[pt] >= minimum && values[pt] <= limit; });	22,523✔
309	limit++;	56✔
310	}
311
312	if(expectedNodes - previousNodes < currentNodes - expectedNodes)	7✔
313	{
UNCOV 314	return limit - 2;	×
315	}
316
317	return limit - 1;	7✔
318	}
319
320	} // namespace rttr::mapGenerator

Return-To-The-Roots / s25client / 13520962205

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous