12732555618

Committed 12 Jan 2025 10:09AM UTC coverage: 50.239%. First build

Build # 12732555618

Build Type

Pull #1734

github

Committed by

web-flow

Commit Message

Merge 83ffe1c84 into da659fca2

Pull Request Pull Request #1734: Improve A* Pathfinding Efficiency by Addressing Final Segment Penalty

Run Details

15 of 16 new or added lines in 1 file covered. (93.75%)

22324 of 44436 relevant lines covered (50.24%)

34857.89 hits per line

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

83.33

/libs/s25main/pathfinding/RoadPathFinder.cpp

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

#include "RoadPathFinder.h"
#include "EventManager.h"
#include "RttrForeachPt.h"
#include "buildings/nobHarborBuilding.h"
#include "pathfinding/OpenListPrioQueue.h"
#include "pathfinding/OpenListVector.h"
#include "world/GameWorldBase.h"
#include "nodeObjs/noRoadNode.h"
#include "gameData/GameConsts.h"
#include "s25util/Log.h"

/// Comparison operator for road nodes that returns true if lhs > rhs (descending order)
struct RoadNodeComperatorGreater
{
    bool operator()(const noRoadNode* const lhs, const noRoadNode* const rhs) const
    {
        if(lhs->estimate == rhs->estimate)
        {
            // Wenn die Wegkosten gleich sind, vergleichen wir die Koordinaten, da wir für std::set eine streng
            // monoton steigende Folge brauchen
            return (lhs->GetObjId() > rhs->GetObjId());
        }

        return (lhs->estimate > rhs->estimate);
    }
};

using QueueImpl = OpenListPrioQueue<const noRoadNode*, RoadNodeComperatorGreater>;
using VecImpl = OpenListVector<const noRoadNode*>;
VecImpl todo;

// Namespace with all functors usable as additional cost functors
namespace AdditonalCosts {
struct None
{
    unsigned operator()(const noRoadNode&, const Direction) const { return 0; }
};

struct Carrier
{
    unsigned operator()(const noRoadNode& curNode, const Direction nextDir) const
    {
        // Add costs for busy carriers to allow alternative routes
        return curNode.GetPunishmentPoints(nextDir);
    }
};
} // namespace AdditonalCosts

// Namespace with all functors usable as segment constraint functors
namespace SegmentConstraints {
struct None
{
    bool operator()(const RoadSegment&) const { return true; }
};

/// Disallows a specific road segment
struct AvoidSegment
{
    const RoadSegment* const forbiddenSeg_;
    AvoidSegment(const RoadSegment* const forbiddenSeg) : forbiddenSeg_(forbiddenSeg) {}

    bool operator()(const RoadSegment& segment) const { return forbiddenSeg_ != &segment; }
};

/// Disallows a specific road type
template<RoadType T_roadType>
struct AvoidRoadType
{
    bool operator()(const RoadSegment& segment) const { return segment.GetRoadType() != T_roadType; }
};

/// Combines 2 functors by returning true only if both of them return true
/// Can be chained
template<class T_Func1, class T_Func2>
struct And : private T_Func1, private T_Func2
{
    using Func1 = T_Func1;
    using Func2 = T_Func2;

    And() : Func1(), Func2() {}

    template<typename T>
    And(const T& p1) : Func1(p1), Func2()
    {}

    template<typename T, typename U>
    And(const T& p1, const U& p2) : Func1(p1), Func2(p2)
    {}

    And(const Func2& f2) : Func1(), Func2(f2) {}

    bool operator()(const RoadSegment& segment) const
    {
        return Func1::operator()(segment) && Func2::operator()(segment);
    }
};
} // namespace SegmentConstraints

/// Wegfinden ( A* ), O(v lg v) --> Wegfindung auf Stra�en
template<class T_AdditionalCosts, class T_SegmentConstraints>
bool RoadPathFinder::FindPathImpl(const noRoadNode& start, const noRoadNode& goal, const unsigned max,
                                  const T_AdditionalCosts addCosts, const T_SegmentConstraints isSegmentAllowed,
                                  unsigned* const length, RoadPathDirection* const firstDir,
                                  MapPoint* const firstNodePos)
{
    if(&start == &goal)
    {
        // Path where start==goal should never happen
        RTTR_Assert(false);
        LOG.write("WARNING: Bug detected (GF: %u). Please report this with the savegame and replay (Start==Goal in "
                  "pathfinding %u,%u)\n")
          % gwb_.GetEvMgr().GetCurrentGF() % unsigned(start.GetX()) % unsigned(start.GetY());
        // But for now we assume it to be valid and return (kind of) correct values
        if(length)
            *length = 0;
        if(firstDir)
            *firstDir = RoadPathDirection::None;
        if(firstNodePos)
            *firstNodePos = start.GetPos();
        return true;
    }

    // increase current_visit_on_roads, so we don't have to clear the visited-states at every run
    currentVisit++;

    // if the counter reaches its maximum, tidy up
    if(currentVisit == std::numeric_limits<unsigned>::max())
    {
        RTTR_FOREACH_PT(MapPoint, gwb_.GetSize())
        {
            auto* const node = gwb_.GetSpecObj<noRoadNode>(pt);
            if(node)
                node->last_visit = 0;
        }
        currentVisit = 1;
    }

    // Add start node
    todo.clear();

    const MapPoint goalPos = goal.GetPos();
    start.targetDistance = gwb_.CalcDistance(start.GetPos(), goalPos);
    start.estimate = start.targetDistance;
    start.last_visit = currentVisit;
    start.prev = nullptr;
    start.cost = 0;
    start.dir_ = RoadPathDirection::None;

    todo.push(&start);

    bool reachingDestViaAttachedFlag = false;

    while(!todo.empty())
    {
        // Get node with current least estimate
        const noRoadNode& best = *todo.pop();

        // Reached goal
        if(&best == &goal)
        {
            if(length)
            {
                *length = best.cost;
                if(reachingDestViaAttachedFlag)
                    *length += 500;
                if(*length > max)
                    return false;
            }

            // Backtrace to get the last node that is not the start node (has a prev node) --> Next node from start on
            // path
            const noRoadNode* firstNode = &best;
            while(firstNode->prev != &start)
            {
                firstNode = firstNode->prev;
            }

            if(firstDir)
                *firstDir = firstNode->dir_;

            if(firstNodePos)
                *firstNodePos = firstNode->GetPos();

            // Done, path found
            return true;
        }

        const helpers::EnumArray<RoadSegment*, Direction> routes = best.getRoutes();
        const noRoadNode* prevNode = best.prev;

        // Nachbarflagge bzw. Wege in allen 6 Richtungen verfolgen
        for(const auto dir : helpers::EnumRange<Direction>{})
        {
            const auto* route = routes[dir];
            if(!route)
                continue;

            // Check the 2 flags, one is the current node, so we need the other
            noRoadNode* neighbour = route->GetF1();
            if(neighbour == &best)
                neighbour = route->GetF2();

            // this eliminates 1/6 of all nodes and avoids cost calculation and further checks,
            if(neighbour == prevNode)
                continue;

            // No paths over buildings
            if(dir == Direction::NorthWest && neighbour != &goal)
            {
                // Flags and harbors are allowed
                const GO_Type got = neighbour->GetGOT();
                if(got != GO_Type::Flag && got != GO_Type::NobHarborbuilding)
                    continue;
            }

            // evtl verboten?
            if(!isSegmentAllowed(*route))
                continue;

            unsigned cost = best.cost + route->GetLength();
            unsigned add_cost = addCosts(best, dir);

            // special case: the road from a building to its flag does not need a carrier
            if(dir == Direction::NorthWest && add_cost >= 500)
            {
                noBase* no = gwb_.GetNO(gwb_.GetNeighbour(best.GetPos(), dir));
                if(no == &goal)
                {
                    if(no->GetType() == NodalObjectType::Buildingsite || no->GetType() == NodalObjectType::Building)
                    {
                        if((cost + add_cost) > max)
                            return false;
                        reachingDestViaAttachedFlag = true;
                        RTTR_Assert(add_cost >= 500);
                        add_cost -= 500;
                    }
                }
            }
            cost += add_cost;

            if(cost > max)
                continue;

            // Was node already visited?
            if(neighbour->last_visit == currentVisit)
            {
                // Update node if costs are lower
                if(cost < neighbour->cost)
                {
                    neighbour->cost = cost;
                    neighbour->estimate = neighbour->targetDistance + cost;
                    neighbour->prev = &best;
                    neighbour->dir_ = toRoadPathDirection(dir);
                    todo.rearrange(neighbour);
                }
            } else
            {
                // Not visited yet -> Add to list
                neighbour->cost = cost;
                neighbour->targetDistance = gwb_.CalcDistance(neighbour->GetPos(), goalPos);
                neighbour->estimate = neighbour->targetDistance + cost;
                neighbour->last_visit = currentVisit;
                neighbour->prev = &best;
                neighbour->dir_ = toRoadPathDirection(dir);

                todo.push(neighbour);
            }
        }

        // For harbors also consider ship connections
        if(best.GetGOT() != GO_Type::NobHarborbuilding)
            continue;
        for(const auto& sc : static_cast<const nobHarborBuilding&>(best).GetShipConnections())
        {
            unsigned cost = best.cost + sc.way_costs;

            if(cost > max)
                continue;

            noRoadNode& dest = *sc.dest;
            // Was node already visited?
            if(dest.last_visit == currentVisit)
            {
                // Update node if costs are lower
                if(cost < dest.cost)
                {
                    dest.cost = cost;
                    dest.estimate = dest.targetDistance + cost;
                    dest.prev = &best;
                    dest.dir_ = RoadPathDirection::Ship;
                    todo.rearrange(&dest);
                }
            } else
            {
                // Not visited yet -> Add to list
                dest.cost = cost;
                dest.targetDistance = gwb_.CalcDistance(dest.GetPos(), goalPos);
                dest.estimate = dest.targetDistance + cost;
                dest.last_visit = currentVisit;
                dest.prev = &best;
                dest.dir_ = RoadPathDirection::Ship;

                todo.push(&dest);
            }
        }
    }

    // Liste leer und kein Ziel erreicht --> kein Weg
    return false;
}

bool RoadPathFinder::FindPath(const noRoadNode& start, const noRoadNode& goal, const bool wareMode, const unsigned max,
                              const RoadSegment* const forbidden, unsigned* const length,
                              RoadPathDirection* const firstDir, MapPoint* const firstNodePos)
{
    RTTR_Assert(length || firstDir || firstNodePos); // If none of them is set use the \ref PathExist function!

    if(wareMode)
    {
        if(forbidden)
            return FindPathImpl(start, goal, max, AdditonalCosts::Carrier(),
                                SegmentConstraints::AvoidSegment(forbidden), length, firstDir, firstNodePos);
        else
            return FindPathImpl(start, goal, max, AdditonalCosts::Carrier(), SegmentConstraints::None(), length,
                                firstDir, firstNodePos);
    } else
    {
        if(forbidden)
            return FindPathImpl(start, goal, max, AdditonalCosts::None(),
                                SegmentConstraints::And<SegmentConstraints::AvoidSegment,
                                                        SegmentConstraints::AvoidRoadType<RoadType::Water>>(forbidden),
                                length, firstDir, firstNodePos);
        else
            return FindPathImpl(start, goal, max, AdditonalCosts::None(),
                                SegmentConstraints::AvoidRoadType<RoadType::Water>(), length, firstDir, firstNodePos);
    }
}

bool RoadPathFinder::PathExists(const noRoadNode& start, const noRoadNode& goal, const bool allowWaterRoads,
                                const unsigned max, const RoadSegment* const forbidden)
{
    if(allowWaterRoads)
    {
        if(forbidden)
            return FindPathImpl(start, goal, max, AdditonalCosts::None(), SegmentConstraints::AvoidSegment(forbidden));
        else
            return FindPathImpl(start, goal, max, AdditonalCosts::None(), SegmentConstraints::None());
    } else
    {
        if(forbidden)
            return FindPathImpl(start, goal, max, AdditonalCosts::None(),
                                SegmentConstraints::And<SegmentConstraints::AvoidSegment,
                                                        SegmentConstraints::AvoidRoadType<RoadType::Water>>(forbidden));
        else
            return FindPathImpl(start, goal, max, AdditonalCosts::None(),
                                SegmentConstraints::AvoidRoadType<RoadType::Water>());
    }
}

1	// Copyright (C) 2005 - 2021 Settlers Freaks (sf-team at siedler25.org)
2	//
3	// SPDX-License-Identifier: GPL-2.0-or-later
4
5	#include "RoadPathFinder.h"
6	#include "EventManager.h"
7	#include "RttrForeachPt.h"
8	#include "buildings/nobHarborBuilding.h"
9	#include "pathfinding/OpenListPrioQueue.h"
10	#include "pathfinding/OpenListVector.h"
11	#include "world/GameWorldBase.h"
12	#include "nodeObjs/noRoadNode.h"
13	#include "gameData/GameConsts.h"
14	#include "s25util/Log.h"
15
16	/// Comparison operator for road nodes that returns true if lhs > rhs (descending order)
17	struct RoadNodeComperatorGreater
18	{
19	bool operator()(const noRoadNode* const lhs, const noRoadNode* const rhs) const
20	{
21	if(lhs->estimate == rhs->estimate)
22	{
23	// Wenn die Wegkosten gleich sind, vergleichen wir die Koordinaten, da wir für std::set eine streng
24	// monoton steigende Folge brauchen
25	return (lhs->GetObjId() > rhs->GetObjId());
26	}
27
28	return (lhs->estimate > rhs->estimate);
29	}
30	};
31
32	using QueueImpl = OpenListPrioQueue<const noRoadNode*, RoadNodeComperatorGreater>;
33	using VecImpl = OpenListVector<const noRoadNode*>;
34	VecImpl todo;
35
36	// Namespace with all functors usable as additional cost functors
37	namespace AdditonalCosts {
38	struct None
39	{
40	unsigned operator()(const noRoadNode&, const Direction) const { return 0; }	1,893✔
41	};
42
43	struct Carrier
44	{
45	unsigned operator()(const noRoadNode& curNode, const Direction nextDir) const	1,230✔
46	{
47	// Add costs for busy carriers to allow alternative routes
48	return curNode.GetPunishmentPoints(nextDir);	1,230✔
49	}
50	};
51	} // namespace AdditonalCosts
52
53	// Namespace with all functors usable as segment constraint functors
54	namespace SegmentConstraints {
55	struct None
56	{
57	bool operator()(const RoadSegment&) const { return true; }	1,249✔
58	};
59
60	/// Disallows a specific road segment
61	struct AvoidSegment
62	{
63	const RoadSegment* const forbiddenSeg_;
64	AvoidSegment(const RoadSegment* const forbiddenSeg) : forbiddenSeg_(forbiddenSeg) {}	372✔
65
66	bool operator()(const RoadSegment& segment) const { return forbiddenSeg_ != &segment; }	583✔
67	};
68
69	/// Disallows a specific road type
70	template<RoadType T_roadType>
71	struct AvoidRoadType
72	{
73	bool operator()(const RoadSegment& segment) const { return segment.GetRoadType() != T_roadType; }	1,874✔
74	};
75
76	/// Combines 2 functors by returning true only if both of them return true
77	/// Can be chained
78	template<class T_Func1, class T_Func2>
79	struct And : private T_Func1, private T_Func2
80	{
81	using Func1 = T_Func1;
82	using Func2 = T_Func2;
83
84	And() : Func1(), Func2() {}
85
86	template<typename T>
87	And(const T& p1) : Func1(p1), Func2()	372✔
88	{}	372✔
89
90	template<typename T, typename U>
91	And(const T& p1, const U& p2) : Func1(p1), Func2(p2)
92	{}
93
94	And(const Func2& f2) : Func1(), Func2(f2) {}
95
96	bool operator()(const RoadSegment& segment) const	583✔
97	{
98	return Func1::operator()(segment) && Func2::operator()(segment);	583✔
99	}
100	};
101	} // namespace SegmentConstraints
102
103	/// Wegfinden ( A* ), O(v lg v) --> Wegfindung auf Stra�en
104	template<class T_AdditionalCosts, class T_SegmentConstraints>
105	bool RoadPathFinder::FindPathImpl(const noRoadNode& start, const noRoadNode& goal, const unsigned max,	1,441✔
106	const T_AdditionalCosts addCosts, const T_SegmentConstraints isSegmentAllowed,
107	unsigned* const length, RoadPathDirection* const firstDir,
108	MapPoint* const firstNodePos)
109	{
110	if(&start == &goal)	1,441✔
111	{
112	// Path where start==goal should never happen
113	RTTR_Assert(false);	×
114	LOG.write("WARNING: Bug detected (GF: %u). Please report this with the savegame and replay (Start==Goal in "
115	"pathfinding %u,%u)\n")
116	% gwb_.GetEvMgr().GetCurrentGF() % unsigned(start.GetX()) % unsigned(start.GetY());
117	// But for now we assume it to be valid and return (kind of) correct values
118	if(length)
119	*length = 0;
120	if(firstDir)
121	*firstDir = RoadPathDirection::None;
122	if(firstNodePos)
123	*firstNodePos = start.GetPos();
124	return true;
125	}
126
127	// increase current_visit_on_roads, so we don't have to clear the visited-states at every run
128	currentVisit++;	1,441✔
129
130	// if the counter reaches its maximum, tidy up
131	if(currentVisit == std::numeric_limits<unsigned>::max())	1,441✔
132	{
133	RTTR_FOREACH_PT(MapPoint, gwb_.GetSize())	×
134	{
135	auto* const node = gwb_.GetSpecObj<noRoadNode>(pt);	×
136	if(node)	×
137	node->last_visit = 0;	×
138	}
139	currentVisit = 1;	×
140	}
141
142	// Add start node
143	todo.clear();	1,441✔
144
145	const MapPoint goalPos = goal.GetPos();	1,441✔
146	start.targetDistance = gwb_.CalcDistance(start.GetPos(), goalPos);	1,441✔
147	start.estimate = start.targetDistance;	1,441✔
148	start.last_visit = currentVisit;	1,441✔
149	start.prev = nullptr;	1,441✔
150	start.cost = 0;	1,441✔
151	start.dir_ = RoadPathDirection::None;	1,441✔
152
153	todo.push(&start);	1,441✔
154
155	bool reachingDestViaAttachedFlag = false;	1,441✔
156
157	while(!todo.empty())	4,692✔
158	{
159	// Get node with current least estimate
160	const noRoadNode& best = *todo.pop();	4,180✔
161
162	// Reached goal
163	if(&best == &goal)	4,180✔
164	{
165	if(length)	929✔
166	{
167	*length = best.cost;	390✔
168	if(reachingDestViaAttachedFlag)	390✔
169	*length += 500;	117✔
170	if(*length > max)	390✔
171	return false;	929✔
172	}
173
174	// Backtrace to get the last node that is not the start node (has a prev node) --> Next node from start on
175	// path
176	const noRoadNode* firstNode = &best;	929✔
177	while(firstNode->prev != &start)	1,860✔
178	{
179	firstNode = firstNode->prev;	931✔
180	}
181
182	if(firstDir)	929✔
183	*firstDir = firstNode->dir_;	515✔
184
185	if(firstNodePos)	929✔
186	*firstNodePos = firstNode->GetPos();	515✔
187
188	// Done, path found
189	return true;	929✔
190	}
191
192	const helpers::EnumArray<RoadSegment*, Direction> routes = best.getRoutes();	3,251✔
193	const noRoadNode* prevNode = best.prev;	3,251✔
194
195	// Nachbarflagge bzw. Wege in allen 6 Richtungen verfolgen
196	for(const auto dir : helpers::EnumRange<Direction>{})	32,510✔
197	{
198	const auto* route = routes[dir];	19,506✔
199	if(!route)	19,506✔
200	continue;	16,383✔
201
202	// Check the 2 flags, one is the current node, so we need the other
203	noRoadNode* neighbour = route->GetF1();	5,557✔
204	if(neighbour == &best)	5,557✔
205	neighbour = route->GetF2();	3,318✔
206
207	// this eliminates 1/6 of all nodes and avoids cost calculation and further checks,
208	if(neighbour == prevNode)	5,557✔
209	continue;	1,794✔
210
211	// No paths over buildings
212	if(dir == Direction::NorthWest && neighbour != &goal)	3,763✔
213	{
214	// Flags and harbors are allowed
215	const GO_Type got = neighbour->GetGOT();	666✔
216	if(got != GO_Type::Flag && got != GO_Type::NobHarborbuilding)	666✔
217	continue;	532✔
218	}
219
220	// evtl verboten?
221	if(!isSegmentAllowed(*route))	3,231✔
222	continue;	108✔
223
224	unsigned cost = best.cost + route->GetLength();	3,123✔
225	unsigned add_cost = addCosts(best, dir);	3,123✔
226
227	// special case: the road from a building to its flag does not need a carrier
228	if(dir == Direction::NorthWest && add_cost >= 500)	3,123✔
229	{
230	noBase* no = gwb_.GetNO(gwb_.GetNeighbour(best.GetPos(), dir));	367✔
231	if(no == &goal)	367✔
232	{
233	if(no->GetType() == NodalObjectType::Buildingsite \|\| no->GetType() == NodalObjectType::Building)	340✔
234	{
235	if((cost + add_cost) > max)	340✔
NEW 236	return false;	×
237	reachingDestViaAttachedFlag = true;	340✔
238	RTTR_Assert(add_cost >= 500);	340✔
239	add_cost -= 500;	340✔
240	}
241	}
242	}
243	cost += add_cost;	3,123✔
244
245	if(cost > max)	3,123✔
246	continue;	×
247
248	// Was node already visited?
249	if(neighbour->last_visit == currentVisit)	3,123✔
250	{
251	// Update node if costs are lower
252	if(cost < neighbour->cost)	7✔
253	{
254	neighbour->cost = cost;	×
255	neighbour->estimate = neighbour->targetDistance + cost;	×
256	neighbour->prev = &best;	×
257	neighbour->dir_ = toRoadPathDirection(dir);	×
258	todo.rearrange(neighbour);	×
259	}
260	} else
261	{
262	// Not visited yet -> Add to list
263	neighbour->cost = cost;	3,116✔
264	neighbour->targetDistance = gwb_.CalcDistance(neighbour->GetPos(), goalPos);	3,116✔
265	neighbour->estimate = neighbour->targetDistance + cost;	3,116✔
266	neighbour->last_visit = currentVisit;	3,116✔
267	neighbour->prev = &best;	3,116✔
268	neighbour->dir_ = toRoadPathDirection(dir);	3,116✔
269
270	todo.push(neighbour);	3,116✔
271	}
272	}
273
274	// For harbors also consider ship connections
275	if(best.GetGOT() != GO_Type::NobHarborbuilding)	3,251✔
276	continue;	3,173✔
277	for(const auto& sc : static_cast<const nobHarborBuilding&>(best).GetShipConnections())	253✔
278	{
279	unsigned cost = best.cost + sc.way_costs;	175✔
280
281	if(cost > max)	175✔
282	continue;	4✔
283
284	noRoadNode& dest = *sc.dest;	171✔
285	// Was node already visited?
286	if(dest.last_visit == currentVisit)	171✔
287	{
288	// Update node if costs are lower
289	if(cost < dest.cost)	106✔
290	{
291	dest.cost = cost;	×
292	dest.estimate = dest.targetDistance + cost;	×
293	dest.prev = &best;	×
294	dest.dir_ = RoadPathDirection::Ship;	×
295	todo.rearrange(&dest);	×
296	}
297	} else
298	{
299	// Not visited yet -> Add to list
300	dest.cost = cost;	65✔
301	dest.targetDistance = gwb_.CalcDistance(dest.GetPos(), goalPos);	65✔
302	dest.estimate = dest.targetDistance + cost;	65✔
303	dest.last_visit = currentVisit;	65✔
304	dest.prev = &best;	65✔
305	dest.dir_ = RoadPathDirection::Ship;	65✔
306
307	todo.push(&dest);	65✔
308	}
309	}
310	}
311
312	// Liste leer und kein Ziel erreicht --> kein Weg
313	return false;	512✔
314	}
315
316	bool RoadPathFinder::FindPath(const noRoadNode& start, const noRoadNode& goal, const bool wareMode, const unsigned max,	1,380✔
317	const RoadSegment* const forbidden, unsigned* const length,
318	RoadPathDirection* const firstDir, MapPoint* const firstNodePos)
319	{
320	RTTR_Assert(length \|\| firstDir \|\| firstNodePos); // If none of them is set use the \ref PathExist function!	1,380✔
321
322	if(wareMode)	1,380✔
323	{
324	if(forbidden)	390✔
325	return FindPathImpl(start, goal, max, AdditonalCosts::Carrier(),	×
326	SegmentConstraints::AvoidSegment(forbidden), length, firstDir, firstNodePos);	×
327	else
328	return FindPathImpl(start, goal, max, AdditonalCosts::Carrier(), SegmentConstraints::None(), length,	390✔
329	firstDir, firstNodePos);	390✔
330	} else
331	{
332	if(forbidden)	990✔
333	return FindPathImpl(start, goal, max, AdditonalCosts::None(),	744✔
334	SegmentConstraints::And<SegmentConstraints::AvoidSegment,
335	SegmentConstraints::AvoidRoadType<RoadType::Water>>(forbidden),
336	length, firstDir, firstNodePos);	372✔
337	else
338	return FindPathImpl(start, goal, max, AdditonalCosts::None(),	618✔
339	SegmentConstraints::AvoidRoadType<RoadType::Water>(), length, firstDir, firstNodePos);	618✔
340	}
341	}
342
343	bool RoadPathFinder::PathExists(const noRoadNode& start, const noRoadNode& goal, const bool allowWaterRoads,	61✔
344	const unsigned max, const RoadSegment* const forbidden)
345	{
346	if(allowWaterRoads)	61✔
347	{
348	if(forbidden)	15✔
349	return FindPathImpl(start, goal, max, AdditonalCosts::None(), SegmentConstraints::AvoidSegment(forbidden));	×
350	else
351	return FindPathImpl(start, goal, max, AdditonalCosts::None(), SegmentConstraints::None());	15✔
352	} else
353	{
354	if(forbidden)	46✔
355	return FindPathImpl(start, goal, max, AdditonalCosts::None(),	×
356	SegmentConstraints::And<SegmentConstraints::AvoidSegment,
357	SegmentConstraints::AvoidRoadType<RoadType::Water>>(forbidden));	×
358	else
359	return FindPathImpl(start, goal, max, AdditonalCosts::None(),	46✔
360	SegmentConstraints::AvoidRoadType<RoadType::Water>());	46✔
361	}
362	}

Return-To-The-Roots / s25client / 12732555618

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