22100923347

Committed 17 Feb 2026 01:46PM UTC coverage: 50.81% (+0.001%) from 50.809%

Build # 22100923347

Build Type

Pull #1895

github

Committed by

web-flow

Commit Message

Merge aa19096bb into 6e122731f

Pull Request Pull Request #1895: Ships: Fix crash when doing expedition between adjacent harbor places

Run Details

5 of 9 new or added lines in 2 files covered. (55.56%)

5 existing lines in 1 file now uncovered.

22797 of 44867 relevant lines covered (50.81%)

41762.65 hits per line

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

96.3

/libs/s25main/pathfinding/FreePathFinderImpl.h

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

#pragma once

#include "EventManager.h"
#include "pathfinding/FreePathFinder.h"
#include "pathfinding/NewNode.h"
#include "pathfinding/OpenListBinaryHeap.h"
#include "pathfinding/OpenListPrioQueue.h"
#include "pathfinding/PathfindingPoint.h"
#include "world/GameWorldBase.h"

using FreePathNodes = std::vector<FreePathNode>;
extern FreePathNodes fpNodes;

struct NodePtrCmpGreater
{
    bool operator()(const FreePathNode* const lhs, const FreePathNode* const rhs) const
    {
        if(lhs->estimatedDistance == rhs->estimatedDistance)
        {
            // Enforce strictly monotonic increasing order
            return (lhs > rhs);
        }

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

struct GetEstimatedDistance
{
    unsigned operator()(const FreePathNode& lhs) const { return lhs.estimatedDistance; }
};

// using QueueImpl = OpenListPrioQueue<NewNode2*, NodePtrCmpGreater>;
using QueueImpl = OpenListBinaryHeap<FreePathNode, GetEstimatedDistance>;

template<class TNodeChecker>
bool FreePathFinder::FindPath(const MapPoint start, const MapPoint dest, bool randomRoute, unsigned maxLength,
                              std::vector<Direction>* route, unsigned* length, Direction* firstDir,
                              const TNodeChecker& nodeChecker)
{
    RTTR_Assert(start != dest);

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

    QueueImpl todo;
    const unsigned startId = gwb_.GetIdx(start);
    const unsigned destId = gwb_.GetIdx(dest);
    FreePathNode& startNode = fpNodes[startId];
    FreePathNode& destNode = fpNodes[destId];

    // Anfangsknoten einfügen Und mit entsprechenden Werten füllen
    startNode.targetDistance = gwb_.CalcDistance(start, dest);
    startNode.estimatedDistance = startNode.targetDistance;
    startNode.lastVisited = currentVisit;
    startNode.prev = nullptr;
    startNode.curDistance = 0;

    todo.push(&startNode);

    // Bei Zufälliger Richtung anfangen (damit man nicht immer denselben Weg geht, besonders für die Soldaten wichtig)
    // TODO confirm random: RANDOM.Rand(__FILE__, __LINE__, y_start * GetWidth() + x_start, 6);
    const Direction startDir =
      randomRoute ? convertToDirection(gwb_.GetIdx(start) * gwb_.GetEvMgr().GetCurrentGF()) : Direction::West;

    while(!todo.empty())
    {
        // Knoten mit den geringsten Wegkosten auswählen
        FreePathNode& best = *todo.pop();

        // Ziel schon erreicht?
        if(&best == &destNode)
        {
            // Ziel erreicht!
            // Jeweils die einzelnen Angaben zurückgeben, falls gewünscht (Pointer übergeben)
            if(length)
                *length = best.curDistance;
            if(route)
                route->resize(best.curDistance);

            FreePathNode* curNode = &best;
            // Route rekonstruieren und ggf. die erste Richtung speichern, falls gewünscht
            for(unsigned z = best.curDistance; z > 0; --z)
            {
                if(route)
                    (*route)[z - 1] = curNode->dir;
                if(firstDir && z == 1)
                    *firstDir = curNode->dir;
                curNode = curNode->prev;
            }

            RTTR_Assert(curNode == &startNode);

            // Fertig, es wurde ein Pfad gefunden
            return true;
        }

        // Maximaler Weg schon erreicht? In dem Fall brauchen wir keine weiteren Knoten von diesem aus bilden
        if(best.curDistance >= maxLength)
            continue;

        // Knoten in alle 6 Richtungen bilden
        const auto neighbors = gwb_.GetNeighbours(best.mapPt);
        for(const Direction dir : helpers::enumRange(startDir))
        {
            // Koordinaten des entsprechenden umliegenden Punktes bilden
            MapPoint neighbourPos = neighbors[dir];

            // ID des umliegenden Knotens bilden
            unsigned nbId = gwb_.GetIdx(neighbourPos);
            FreePathNode& neighbour = fpNodes[nbId];

            // Don't try to go back where we came from (would also bail out in the conditions below)
            if(best.prev == &neighbour)
                continue;

            // Knoten schon auf dem Feld gebildet?
            if(neighbour.lastVisited == currentVisit)
            {
                // Dann nur ggf. Weg und Vorgänger korrigieren, falls der Weg kürzer ist
                if(best.curDistance + 1 < neighbour.curDistance)
                {
                    // Check if we can use this transition
                    if(!nodeChecker.IsEdgeOk(best.mapPt, dir))
                        continue;

                    neighbour.curDistance = best.curDistance + 1;
                    neighbour.estimatedDistance = neighbour.curDistance + neighbour.targetDistance;
                    neighbour.prev = &best;
                    neighbour.dir = dir;
                    todo.rearrange(&neighbour);
                }
            } else
            {
                // Check node for all but the goal (goal is assumed to be ok)
                if(&neighbour != &destNode)
                {
                    if(!nodeChecker.IsNodeOk(neighbourPos))
                        continue;
                }

                // Check if we can use this transition
                if(!nodeChecker.IsEdgeOk(best.mapPt, dir))
                    continue;

                // Alles in Ordnung, Knoten kann gebildet werden
                neighbour.lastVisited = currentVisit;
                neighbour.curDistance = best.curDistance + 1;
                neighbour.targetDistance = gwb_.CalcDistance(neighbourPos, dest);
                neighbour.estimatedDistance = neighbour.curDistance + neighbour.targetDistance;
                neighbour.dir = dir;
                neighbour.prev = &best;

                todo.push(&neighbour);
            }
        }
    }

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

/// Ermittelt, ob eine freie Route noch passierbar ist und gibt den Endpunkt der Route zurück
template<class TNodeChecker>
bool FreePathFinder::CheckRoute(const MapPoint start, const std::vector<Direction>& route, unsigned pos,
                                const TNodeChecker& nodeChecker, MapPoint* dest) const
{
    RTTR_Assert(pos < route.size());

    // Empty routes are not considered passable
    if(route.empty())
        return false;

    MapPoint curPt(start);
    // Check all but last step
    unsigned sizeM1 = route.size() - 1;
    for(unsigned i = pos; i < sizeM1; ++i)
    {
        if(!nodeChecker.IsEdgeOk(curPt, route[i]))
            return false;
        curPt = gwb_.GetNeighbour(curPt, route[i]);
        if(!nodeChecker.IsNodeOk(curPt))
            return false;
    }

    // Last step
    if(!nodeChecker.IsEdgeOk(curPt, route.back()))
        return false;

    if(dest)
        *dest = gwb_.GetNeighbour(curPt, route.back());

    return true;
}

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 "EventManager.h"
8	#include "pathfinding/FreePathFinder.h"
9	#include "pathfinding/NewNode.h"
10	#include "pathfinding/OpenListBinaryHeap.h"
11	#include "pathfinding/OpenListPrioQueue.h"
12	#include "pathfinding/PathfindingPoint.h"
13	#include "world/GameWorldBase.h"
14
15	using FreePathNodes = std::vector<FreePathNode>;
16	extern FreePathNodes fpNodes;
17
18	struct NodePtrCmpGreater
19	{
20	bool operator()(const FreePathNode* const lhs, const FreePathNode* const rhs) const
21	{
22	if(lhs->estimatedDistance == rhs->estimatedDistance)
23	{
24	// Enforce strictly monotonic increasing order
25	return (lhs > rhs);
26	}
27
28	return (lhs->estimatedDistance > rhs->estimatedDistance);
29	}
30	};
31
32	struct GetEstimatedDistance
33	{
34	unsigned operator()(const FreePathNode& lhs) const { return lhs.estimatedDistance; }	269,110✔
35	};
36
37	// using QueueImpl = OpenListPrioQueue<NewNode2*, NodePtrCmpGreater>;
38	using QueueImpl = OpenListBinaryHeap<FreePathNode, GetEstimatedDistance>;
39
40	template<class TNodeChecker>
41	bool FreePathFinder::FindPath(const MapPoint start, const MapPoint dest, bool randomRoute, unsigned maxLength,	4,782✔
42	std::vector<Direction>* route, unsigned* length, Direction* firstDir,
43	const TNodeChecker& nodeChecker)
44	{
45	RTTR_Assert(start != dest);	4,782✔
46
47	// increase currentVisit, so we don't have to clear the visited-states at every run
48	IncreaseCurrentVisit();	4,782✔
49
50	QueueImpl todo;	9,564✔
51	const unsigned startId = gwb_.GetIdx(start);	4,782✔
52	const unsigned destId = gwb_.GetIdx(dest);	4,782✔
53	FreePathNode& startNode = fpNodes[startId];	4,782✔
54	FreePathNode& destNode = fpNodes[destId];	4,782✔
55
56	// Anfangsknoten einfügen Und mit entsprechenden Werten füllen
57	startNode.targetDistance = gwb_.CalcDistance(start, dest);	4,782✔
58	startNode.estimatedDistance = startNode.targetDistance;	4,782✔
59	startNode.lastVisited = currentVisit;	4,782✔
60	startNode.prev = nullptr;	4,782✔
61	startNode.curDistance = 0;	4,782✔
62
63	todo.push(&startNode);	4,782✔
64
65	// Bei Zufälliger Richtung anfangen (damit man nicht immer denselben Weg geht, besonders für die Soldaten wichtig)
66	// TODO confirm random: RANDOM.Rand(__FILE__, __LINE__, y_start * GetWidth() + x_start, 6);
67	const Direction startDir =	4,782✔
68	randomRoute ? convertToDirection(gwb_.GetIdx(start) * gwb_.GetEvMgr().GetCurrentGF()) : Direction::West;	4,782✔
69
70	while(!todo.empty())	83,918✔
71	{
72	// Knoten mit den geringsten Wegkosten auswählen
73	FreePathNode& best = *todo.pop();	83,201✔
74
75	// Ziel schon erreicht?
76	if(&best == &destNode)	83,201✔
77	{
78	// Ziel erreicht!
79	// Jeweils die einzelnen Angaben zurückgeben, falls gewünscht (Pointer übergeben)
80	if(length)	4,065✔
81	*length = best.curDistance;	1,257✔
82	if(route)	4,065✔
83	route->resize(best.curDistance);	166✔
84
85	FreePathNode* curNode = &best;	4,065✔
86	// Route rekonstruieren und ggf. die erste Richtung speichern, falls gewünscht
87	for(unsigned z = best.curDistance; z > 0; --z)	22,669✔
88	{
89	if(route)	18,604✔
90	(*route)[z - 1] = curNode->dir;	2,949✔
91	if(firstDir && z == 1)	18,604✔
92	*firstDir = curNode->dir;	3,912✔
93	curNode = curNode->prev;	18,604✔
94	}
95
96	RTTR_Assert(curNode == &startNode);	4,065✔
97
98	// Fertig, es wurde ein Pfad gefunden
99	return true;	4,065✔
100	}
101
102	// Maximaler Weg schon erreicht? In dem Fall brauchen wir keine weiteren Knoten von diesem aus bilden
103	if(best.curDistance >= maxLength)	79,136✔
104	continue;	3,047✔
105
106	// Knoten in alle 6 Richtungen bilden
107	const auto neighbors = gwb_.GetNeighbours(best.mapPt);	76,089✔
108	for(const Direction dir : helpers::enumRange(startDir))	760,890✔
109	{
110	// Koordinaten des entsprechenden umliegenden Punktes bilden
111	MapPoint neighbourPos = neighbors[dir];	456,534✔
112
113	// ID des umliegenden Knotens bilden
114	unsigned nbId = gwb_.GetIdx(neighbourPos);	456,534✔
115	FreePathNode& neighbour = fpNodes[nbId];	456,534✔
116
117	// Don't try to go back where we came from (would also bail out in the conditions below)
118	if(best.prev == &neighbour)	456,534✔
119	continue;	113,491✔
120
121	// Knoten schon auf dem Feld gebildet?
122	if(neighbour.lastVisited == currentVisit)	385,227✔
123	{
124	// Dann nur ggf. Weg und Vorgänger korrigieren, falls der Weg kürzer ist
125	if(best.curDistance + 1 < neighbour.curDistance)	216,264✔
126	{
127	// Check if we can use this transition
128	if(!nodeChecker.IsEdgeOk(best.mapPt, dir))	11,974✔
129	continue;	1✔
130
131	neighbour.curDistance = best.curDistance + 1;	5,986✔
132	neighbour.estimatedDistance = neighbour.curDistance + neighbour.targetDistance;	5,986✔
133	neighbour.prev = &best;	5,986✔
134	neighbour.dir = dir;	5,986✔
135	todo.rearrange(&neighbour);	5,986✔
136	}
137	} else
138	{
139	// Check node for all but the goal (goal is assumed to be ok)
140	if(&neighbour != &destNode)	168,963✔
141	{
142	if(!nodeChecker.IsNodeOk(neighbourPos))	164,815✔
143	continue;	41,630✔
144	}
145
146	// Check if we can use this transition
147	if(!nodeChecker.IsEdgeOk(best.mapPt, dir))	254,666✔
148	continue;	553✔
149
150	// Alles in Ordnung, Knoten kann gebildet werden
151	neighbour.lastVisited = currentVisit;	126,780✔
152	neighbour.curDistance = best.curDistance + 1;	126,780✔
153	neighbour.targetDistance = gwb_.CalcDistance(neighbourPos, dest);	126,780✔
154	neighbour.estimatedDistance = neighbour.curDistance + neighbour.targetDistance;	126,780✔
155	neighbour.dir = dir;	126,780✔
156	neighbour.prev = &best;	126,780✔
157
158	todo.push(&neighbour);	126,780✔
159	}
160	}
161	}
162
163	// Liste leer und kein Ziel erreicht --> kein Weg
164	return false;	717✔
165	}
166
167	/// Ermittelt, ob eine freie Route noch passierbar ist und gibt den Endpunkt der Route zurück
168	template<class TNodeChecker>
169	bool FreePathFinder::CheckRoute(const MapPoint start, const std::vector<Direction>& route, unsigned pos,	524✔
170	const TNodeChecker& nodeChecker, MapPoint* dest) const
171	{
172	RTTR_Assert(pos < route.size());	524✔
173
174	// Empty routes are not considered passable
175	if(route.empty())	524✔
NEW 176	return false;	×
177
178	MapPoint curPt(start);	524✔
179	// Check all but last step
180	unsigned sizeM1 = route.size() - 1;	524✔
181	for(unsigned i = pos; i < sizeM1; ++i)	7,799✔
182	{
183	if(!nodeChecker.IsEdgeOk(curPt, route[i]))	14,558✔
184	return false;	×
185	curPt = gwb_.GetNeighbour(curPt, route[i]);	7,279✔
186	if(!nodeChecker.IsNodeOk(curPt))	7,279✔
187	return false;	4✔
188	}
189
190	// Last step
191	if(!nodeChecker.IsEdgeOk(curPt, route.back()))	1,040✔
192	return false;	×
193
194	if(dest)	520✔
195	*dest = gwb_.GetNeighbour(curPt, route.back());	373✔
196
197	return true;	520✔
198	}

Return-To-The-Roots / s25client / 22100923347

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