• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

Return-To-The-Roots / s25client / 44076625557

17 Nov 2026 11:43AM UTC coverage: 51.803% (-0.002%) from 51.805%
44076625557

push

github

web-flow
Merge pull request #2018 from Return-To-The-Roots/refactor/lowerCamelCase-methods

Rename Msg_* handlers to lowerCamelCase

8121 of 16693 new or added lines in 565 files covered. (48.65%)

323 existing lines in 133 files now uncovered.

24236 of 46785 relevant lines covered (51.8%)

49647.74 hits per line

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

83.06
/libs/s25main/pathfinding/RoadPathFinder.cpp
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 "helpers/EnumArray.h"
10
#include "pathfinding/OpenListPrioQueue.h"
11
#include "pathfinding/OpenListVector.h"
12
#include "world/GameWorldBase.h"
13
#include "nodeObjs/noRoadNode.h"
14
#include "s25util/Log.h"
15
#include <limits>
16

17
/// Comparison operator for road nodes that returns true if lhs > rhs (descending order)
18
struct RoadNodeComperatorGreater
19
{
20
    bool operator()(const noRoadNode* const lhs, const noRoadNode* const rhs) const
21
    {
22
        if(lhs->estimate == rhs->estimate)
23
        {
24
            // Use a tie-breaker to get strict ordering
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,390 ✔
41
};
42

43
struct Carrier
44
{
45
    unsigned operator()(const noRoadNode& curNode, const Direction nextDir) const
1,283 ✔
46
    {
47
        // Add costs for busy carriers to allow alternative routes
48
        return curNode.getPunishmentPoints(nextDir);
1,283 ✔
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,929 ✔
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) {}
199 ✔
65

66
    bool operator()(const RoadSegment& segment) const { return forbiddenSeg_ != &segment; }
406 ✔
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,804 ✔
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()
199 ✔
88
    {}
199 ✔
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
406 ✔
97
    {
98
        return Func1::operator()(segment) && Func2::operator()(segment);
406 ✔
99
    }
100
};
101
} // namespace SegmentConstraints
102

103
/// Path finding on roads using A* O(n lg n)
104
/// \tparam T_AdditionalCosts Cost for each road segment but the one to the goal building
105
/// \tparam T_SegmentConstraints Predicate whether a road is allowed
106
template<class T_AdditionalCosts, class T_SegmentConstraints>
107
bool RoadPathFinder::findPathImpl(const noRoadNode& start, const noRoadNode& goal, const unsigned max,
1,482 ✔
108
                                  const T_AdditionalCosts addCosts, const T_SegmentConstraints isSegmentAllowed,
109
                                  unsigned* const length, RoadPathDirection* const firstDir,
110
                                  MapPoint* const firstNodePos)
111
{
112
    if(&start == &goal)
1,482 ✔
113
    {
114
        // Path where start==goal should never happen
115
        RTTR_Assert(false);
×
116
        LOG.write("WARNING: Bug detected (GF: %u). Please report this with the savegame and replay (Start==Goal in "
117
                  "pathfinding %u,%u)\n")
118
          % gwb_.getEvMgr().getCurrentGF() % unsigned(start.getX()) % unsigned(start.getY());
119
        // But for now we assume it to be valid and return (kind of) correct values
120
        if(length)
121
            *length = 0;
122
        if(firstDir)
123
            *firstDir = RoadPathDirection::None;
124
        if(firstNodePos)
125
            *firstNodePos = start.getPos();
126
        return true;
127
    }
128

129
    // If the goal is a flag (unlikely) we have no goal building
130
    // TODO(Replay): Change RoadPathFinder::FindPath to target flag instead of building for wares
131
    const noRoadNode* goalBld = (goal.getGOT() == GO_Type::Flag) ? nullptr : &goal;
1,482 ✔
132

133
    // Use a counter for the visited-states so we don't have to reset them on every invocation
134
    currentVisit++;
1,482 ✔
135
    // if the counter reaches its maximum, tidy up
136
    if(currentVisit == std::numeric_limits<unsigned>::max())
1,482 ✔
137
    {
NEW
138
        RTTR_FOREACH_PT(MapPoint, gwb_.getSize())
×
139
        {
NEW
140
            auto* const node = gwb_.getSpecObj<noRoadNode>(pt);
×
141
            if(node)
×
142
                node->last_visit = 0;
×
143
        }
144
        currentVisit = 1;
×
145
    }
146

147
    // Add start node
148
    todo.clear();
1,482 ✔
149

150
    const MapPoint goalPos = goal.getPos();
1,482 ✔
151
    start.targetDistance = gwb_.calcDistance(start.getPos(), goalPos);
1,482 ✔
152
    start.estimate = start.targetDistance;
1,482 ✔
153
    start.last_visit = currentVisit;
1,482 ✔
154
    start.prev = nullptr;
1,482 ✔
155
    start.cost = 0;
1,482 ✔
156
    start.dir_ = RoadPathDirection::None;
1,482 ✔
157

158
    todo.push(&start);
1,482 ✔
159

160
    while(!todo.empty())
4,863 ✔
161
    {
162
        // Get node with current least estimate
163
        const noRoadNode& best = *todo.pop();
4,703 ✔
164

165
        // Reached goal
166
        if(&best == &goal)
4,703 ✔
167
        {
168
            if(length)
1,322 ✔
169
                *length = best.cost;
581 ✔
170

171
            // Backtrack to get the last node that is not the start node (has a prev node)
172
            // --> Next node from start on path
173
            if(firstDir || firstNodePos)
1,322 ✔
174
            {
175
                const noRoadNode* firstNode = &best;
712 ✔
176
                while(firstNode->prev != &start)
1,148 ✔
177
                    firstNode = firstNode->prev;
436 ✔
178

179
                if(firstDir)
712 ✔
180
                    *firstDir = firstNode->dir_;
712 ✔
181

182
                if(firstNodePos)
712 ✔
183
                    *firstNodePos = firstNode->getPos();
712 ✔
184
            }
185

186
            // Done, path found
187
            return true;
1,322 ✔
188
        }
189

190
        const helpers::EnumArray<RoadSegment*, Direction> routes = best.getRoutes();
3,381 ✔
191
        const noRoadNode* prevNode = best.prev;
3,381 ✔
192

193
        // Check paths in all directions
194
        for(const auto dir : helpers::EnumRange<Direction>{})
33,810 ✔
195
        {
196
            const auto* route = routes[dir];
20,286 ✔
197
            if(!route)
20,286 ✔
198
                continue;
16,554 ✔
199

200
            // Check the 2 flags, one is the current node, so we need the other
201
            noRoadNode* neighbour = route->getF1();
6,228 ✔
202
            if(neighbour == &best)
6,228 ✔
203
                neighbour = route->getF2();
3,747 ✔
204

205
            // this eliminates 1/6 of all nodes and avoids cost calculation and further checks,
206
            if(neighbour == prevNode)
6,228 ✔
207
                continue;
1,869 ✔
208

209
            // No paths over buildings
210
            if(dir == Direction::NorthWest && neighbour != &goal)
4,359 ✔
211
            {
212
                // Flags and harbors are allowed
213
                const GO_Type got = neighbour->getGOT();
722 ✔
214
                if(got != GO_Type::Flag && got != GO_Type::NobHarborbuilding)
722 ✔
215
                    continue;
540 ✔
216
            }
217

218
            // Check if route is forbidden
219
            if(!isSegmentAllowed(*route))
3,819 ✔
220
                continue;
86 ✔
221

222
            const unsigned cost = best.cost + route->getLength() + (neighbour != goalBld ? addCosts(best, dir) : 0);
3,733 ✔
223

224
            if(cost > max)
3,733 ✔
225
                continue;
1 ✔
226

227
            // Was node already visited?
228
            if(neighbour->last_visit == currentVisit)
3,732 ✔
229
            {
230
                // Update node if costs are lower
231
                if(cost < neighbour->cost)
11 ✔
232
                {
233
                    neighbour->cost = cost;
×
234
                    neighbour->estimate = neighbour->targetDistance + cost;
×
235
                    neighbour->prev = &best;
×
236
                    neighbour->dir_ = toRoadPathDirection(dir);
×
237
                    todo.rearrange(neighbour);
×
238
                }
239
            } else
240
            {
241
                // Not visited yet -> Add to list
242
                neighbour->cost = cost;
3,721 ✔
243
                neighbour->targetDistance = gwb_.calcDistance(neighbour->getPos(), goalPos);
3,721 ✔
244
                neighbour->estimate = neighbour->targetDistance + cost;
3,721 ✔
245
                neighbour->last_visit = currentVisit;
3,721 ✔
246
                neighbour->prev = &best;
3,721 ✔
247
                neighbour->dir_ = toRoadPathDirection(dir);
3,721 ✔
248

249
                todo.push(neighbour);
3,721 ✔
250
            }
251
        }
252

253
        // For harbors also consider ship connections
254
        if(best.getGOT() != GO_Type::NobHarborbuilding)
3,381 ✔
255
            continue;
3,216 ✔
256
        for(const auto& sc : static_cast<const nobHarborBuilding&>(best).getShipConnections())
322 ✔
257
        {
258
            unsigned cost = best.cost + sc.way_costs;
157 ✔
259

260
            if(cost > max)
157 ✔
261
                continue;
5 ✔
262

263
            noRoadNode& dest = *sc.dest;
152 ✔
264
            // Was node already visited?
265
            if(dest.last_visit == currentVisit)
152 ✔
266
            {
267
                // Update node if costs are lower
268
                if(cost < dest.cost)
43 ✔
269
                {
270
                    dest.cost = cost;
×
271
                    dest.estimate = dest.targetDistance + cost;
×
272
                    dest.prev = &best;
×
273
                    dest.dir_ = RoadPathDirection::Ship;
×
274
                    todo.rearrange(&dest);
×
275
                }
276
            } else
277
            {
278
                // Not visited yet -> Add to list
279
                dest.cost = cost;
109 ✔
280
                dest.targetDistance = gwb_.calcDistance(dest.getPos(), goalPos);
109 ✔
281
                dest.estimate = dest.targetDistance + cost;
109 ✔
282
                dest.last_visit = currentVisit;
109 ✔
283
                dest.prev = &best;
109 ✔
284
                dest.dir_ = RoadPathDirection::Ship;
109 ✔
285

286
                todo.push(&dest);
109 ✔
287
            }
288
        }
289
    }
290

291
    // Queue is empty without reaching the goal --> No allowed, existing path
292
    return false;
160 ✔
293
}
294

295
bool RoadPathFinder::findPath(const noRoadNode& start, const noRoadNode& goal, const bool wareMode, const unsigned max,
1,421 ✔
296
                              const RoadSegment* const forbidden, unsigned* const length,
297
                              RoadPathDirection* const firstDir, MapPoint* const firstNodePos)
298
{
299
    RTTR_Assert_Msg(length || firstDir || firstNodePos, "Use PathExists instead!");
1,421 ✔
300

301
    if(wareMode)
1,421 ✔
302
    {
303
        // TODO(Replay): Change to target flag instead of its attached building
304
        if(forbidden)
631 ✔
NEW
305
            return findPathImpl(start, goal, max, AdditonalCosts::Carrier(),
×
306
                                SegmentConstraints::AvoidSegment(forbidden), length, firstDir, firstNodePos);
×
307
        else
308
            return findPathImpl(start, goal, max, AdditonalCosts::Carrier(), SegmentConstraints::None(), length,
631 ✔
309
                                firstDir, firstNodePos);
631 ✔
310
    } else
311
    {
312
        if(forbidden)
790 ✔
313
            return findPathImpl(start, goal, max, AdditonalCosts::None(),
398 ✔
314
                                SegmentConstraints::And<SegmentConstraints::AvoidSegment,
315
                                                        SegmentConstraints::AvoidRoadType<RoadType::Water>>(forbidden),
316
                                length, firstDir, firstNodePos);
199 ✔
317
        else
318
            return findPathImpl(start, goal, max, AdditonalCosts::None(),
591 ✔
319
                                SegmentConstraints::AvoidRoadType<RoadType::Water>(), length, firstDir, firstNodePos);
591 ✔
320
    }
321
}
322

323
bool RoadPathFinder::pathExists(const noRoadNode& start, const noRoadNode& goal, const bool allowWaterRoads,
61 ✔
324
                                const unsigned max, const RoadSegment* const forbidden)
325
{
326
    if(allowWaterRoads)
61 ✔
327
    {
328
        // TODO(Replay): Change to target flag instead of its attached building.
329
        // Likely combine with RoadPathFinder::FindPath
330
        if(forbidden)
23 ✔
NEW
331
            return findPathImpl(start, goal, max, AdditonalCosts::None(), SegmentConstraints::AvoidSegment(forbidden));
×
332
        else
333
            return findPathImpl(start, goal, max, AdditonalCosts::None(), SegmentConstraints::None());
23 ✔
334
    } else
335
    {
336
        if(forbidden)
38 ✔
NEW
337
            return findPathImpl(start, goal, max, AdditonalCosts::None(),
×
338
                                SegmentConstraints::And<SegmentConstraints::AvoidSegment,
339
                                                        SegmentConstraints::AvoidRoadType<RoadType::Water>>(forbidden));
×
340
        else
341
            return findPathImpl(start, goal, max, AdditonalCosts::None(),
38 ✔
342
                                SegmentConstraints::AvoidRoadType<RoadType::Water>());
38 ✔
343
    }
344
}
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE TRIAL · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc