25985372463

Committed 17 May 2026 08:03AM UTC coverage: 50.362% (+0.08%) from 50.284%

Build # 25985372463

Build Type

Pull #1917

github

Committed by

web-flow

Commit Message

Merge 5d7afa219 into 57b082981

Pull Request Pull Request #1917: Fix sea path finding (for ships)

Coverage Stats

118 of 166 new or added lines in 13 files covered. (71.08%)

5 existing lines in 3 files now uncovered.

23215 of 46096 relevant lines covered (50.36%)

47651.7 hits per line

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

97.06

/libs/s25main/Pathfinding.cpp

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

#include "GamePlayer.h"
#include "helpers/EnumRange.h"
#include "helpers/IdRange.h"
#include "pathfinding/FreePathFinder.h"
#include "pathfinding/FreePathFinderImpl.h"
#include "pathfinding/PathConditionHuman.h"
#include "pathfinding/PathConditionShip.h"
#include "pathfinding/PathConditionTrade.h"
#include "pathfinding/RoadPathFinder.h"
#include "pathfinding/ShipPathData.h"
#include "world/GameWorld.h"
#include "gameTypes/ShipDirection.h"
#include "gameData/GameConsts.h"

/// Findet einen Weg für Figuren
helpers::OptionalEnum<Direction> GameWorldBase::FindHumanPath(const MapPoint start, const MapPoint dest,
                                                              const unsigned max_route, const bool random_route,
                                                              unsigned* length, std::vector<Direction>* route) const
{
    Direction first_dir{};
    if(GetFreePathFinder().FindPath(start, dest, random_route, max_route, route, length, &first_dir,
                                    PathConditionHuman(*this)))
        return first_dir;
    else
        return boost::none;
}

/// Wegfindung für Menschen im Straßennetz
RoadPathDirection GameWorld::FindHumanPathOnRoads(const noRoadNode& start, const noRoadNode& goal, unsigned* length,
                                                  MapPoint* firstPt, const RoadSegment* const forbidden)
{
    RoadPathDirection first_dir;
    if(GetRoadPathFinder().FindPath(start, goal, false, std::numeric_limits<unsigned>::max(), forbidden, length,
                                    &first_dir, firstPt))
        return first_dir;
    else
        return RoadPathDirection::None;
}

/// Wegfindung für Waren im Straßennetz
RoadPathDirection GameWorld::FindPathForWareOnRoads(const noRoadNode& start, const noRoadNode& goal, unsigned* length,
                                                    MapPoint* firstPt, unsigned max)
{
    RoadPathDirection first_dir;
    if(GetRoadPathFinder().FindPath(start, goal, true, max, nullptr, length, &first_dir, firstPt))
        return first_dir;
    else
        return RoadPathDirection::None;
}

bool GameWorldBase::FindShipPathToHarbor(const MapPoint start, HarborId harborId, SeaId seaId,
                                         std::vector<Direction>* route, unsigned* length) const
{
    const MapPoint coastalPoint = GetCoastalPoint(harborId, seaId);
    RTTR_Assert(coastalPoint.isValid());

    // already arrived?
    if(start == coastalPoint)
    {
        if(length)
            *length = 0;
        if(route)
            route->clear();
        return true;
    }
    auto& shipPathData = GetShipPathData();
    // If we start from a harbor we can get the route directly w/o the costly pathfinding
    for(const auto startHbId : helpers::idRange<HarborId>(GetNumHarborPoints()))
    {
        if(GetCoastalPoint(startHbId, seaId) == start)
        {
            auto hbRoute = shipPathData.getHarborConnection(startHbId, harborId, seaId);
            if(length)
                *length = hbRoute.size();
            if(route)
                *route = std::move(hbRoute);
        }
    }

    // Try cache first
    bool reversed = false;
    if(const auto* cachedPath = shipPathData.findCachedPath(start, coastalPoint, reversed))
    {
        if(route)
        {
            *route = *cachedPath;
            if(reversed)
            {
                std::reverse(route->begin(), route->end());
                for(auto& d : *route)
                    d = d + 3u; // reverse direction
            }
        }
        if(length)
            *length = cachedPath->size();
        return true;
    }

    // Not in cache -> compute full path and add
    std::vector<Direction> newRoute;
    if(!FindShipPath(start, coastalPoint, std::numeric_limits<unsigned>::max(), &newRoute, length))
        return false;
    shipPathData.addToCache(start, coastalPoint, newRoute);
    if(route)
        *route = std::move(newRoute);

    return true;
}

bool GameWorldBase::FindShipPath(const MapPoint start, const MapPoint dest, unsigned maxDistance,
                                 std::vector<Direction>* route, unsigned* length) const
{
    return GetFreePathFinder().FindPath(start, dest, true, maxDistance, route, length, nullptr,
                                        PathConditionShip(*this));
}

/// Prüft, ob eine Schiffsroute noch Gültigkeit hat
bool GameWorld::CheckShipRoute(const MapPoint start, const std::vector<Direction>& route, const unsigned pos,
                               MapPoint* dest) const
{
    return GetFreePathFinder().CheckRoute(start, route, pos, PathConditionShip(*this), dest);
}

/// Find a route for trade caravanes
helpers::OptionalEnum<Direction> GameWorld::FindTradePath(const MapPoint start, const MapPoint dest,
                                                          unsigned char player, unsigned max_route, bool random_route,
                                                          std::vector<Direction>* route, unsigned* length) const
{
    unsigned char owner = GetNode(dest).owner;
    if(owner != 0 && !GetPlayer(player).IsAlly(owner - 1))
        return boost::none;

    RTTR_Assert(GetNO(dest)->GetType() == NodalObjectType::Flag); // Goal should be the flag of a wh

    if(!PathConditionHuman(*this).IsNodeOk(dest))
        return boost::none;

    Direction first_dir{};
    if(GetFreePathFinder().FindPath(start, dest, random_route, max_route, route, length, &first_dir,
                                    PathConditionTrade(*this, player)))
        return first_dir;
    else
        return boost::none;
}

bool GameWorld::CheckTradeRoute(const MapPoint start, const std::vector<Direction>& route, unsigned pos,
                                unsigned char player, MapPoint* dest) const
{
    return GetFreePathFinder().CheckRoute(start, route, pos, PathConditionTrade(*this, player), dest);
}

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 "GamePlayer.h"
6	#include "helpers/EnumRange.h"
7	#include "helpers/IdRange.h"
8	#include "pathfinding/FreePathFinder.h"
9	#include "pathfinding/FreePathFinderImpl.h"
10	#include "pathfinding/PathConditionHuman.h"
11	#include "pathfinding/PathConditionShip.h"
12	#include "pathfinding/PathConditionTrade.h"
13	#include "pathfinding/RoadPathFinder.h"
14	#include "pathfinding/ShipPathData.h"
15	#include "world/GameWorld.h"
16	#include "gameTypes/ShipDirection.h"
17	#include "gameData/GameConsts.h"
18
19	/// Findet einen Weg für Figuren
20	helpers::OptionalEnum<Direction> GameWorldBase::FindHumanPath(const MapPoint start, const MapPoint dest,	5,441✔
21	const unsigned max_route, const bool random_route,
22	unsigned* length, std::vector<Direction>* route) const
23	{
24	Direction first_dir{};	5,441✔
25	if(GetFreePathFinder().FindPath(start, dest, random_route, max_route, route, length, &first_dir,	10,882✔
26	PathConditionHuman(*this)))	10,882✔
27	return first_dir;	4,737✔
28	else
29	return boost::none;	704✔
30	}
31
32	/// Wegfindung für Menschen im Straßennetz
33	RoadPathDirection GameWorld::FindHumanPathOnRoads(const noRoadNode& start, const noRoadNode& goal, unsigned* length,	285✔
34	MapPoint* firstPt, const RoadSegment* const forbidden)
35	{
36	RoadPathDirection first_dir;
37	if(GetRoadPathFinder().FindPath(start, goal, false, std::numeric_limits<unsigned>::max(), forbidden, length,	285✔
38	&first_dir, firstPt))
39	return first_dir;	283✔
40	else
41	return RoadPathDirection::None;	2✔
42	}
43
44	/// Wegfindung für Waren im Straßennetz
45	RoadPathDirection GameWorld::FindPathForWareOnRoads(const noRoadNode& start, const noRoadNode& goal, unsigned* length,	267✔
46	MapPoint* firstPt, unsigned max)
47	{
48	RoadPathDirection first_dir;
49	if(GetRoadPathFinder().FindPath(start, goal, true, max, nullptr, length, &first_dir, firstPt))	267✔
50	return first_dir;	263✔
51	else
52	return RoadPathDirection::None;	4✔
53	}
54
55	bool GameWorldBase::FindShipPathToHarbor(const MapPoint start, HarborId harborId, SeaId seaId,	38✔
56	std::vector<Direction>* route, unsigned* length) const
57	{
58	const MapPoint coastalPoint = GetCoastalPoint(harborId, seaId);	38✔
59	RTTR_Assert(coastalPoint.isValid());	38✔
60
61	// already arrived?
62	if(start == coastalPoint)	38✔
63	{
64	if(length)	10✔
65	*length = 0;	9✔
66	if(route)	10✔
67	route->clear();	10✔
68	return true;	10✔
69	}
70	auto& shipPathData = GetShipPathData();	28✔
71	// If we start from a harbor we can get the route directly w/o the costly pathfinding
72	for(const auto startHbId : helpers::idRange<HarborId>(GetNumHarborPoints()))	229✔
73	{
74	if(GetCoastalPoint(startHbId, seaId) == start)	201✔
75	{
76	auto hbRoute = shipPathData.getHarborConnection(startHbId, harborId, seaId);	32✔
77	if(length)	16✔
78	*length = hbRoute.size();	1✔
79	if(route)	16✔
80	*route = std::move(hbRoute);	16✔
81	}
82	}
83
84	// Try cache first
85	bool reversed = false;	28✔
86	if(const auto* cachedPath = shipPathData.findCachedPath(start, coastalPoint, reversed))	28✔
87	{
88	if(route)	4✔
89	{
90	route = cachedPath;	4✔
91	if(reversed)	4✔
92	{
93	std::reverse(route->begin(), route->end());	3✔
94	for(auto& d : *route)	47✔
95	d = d + 3u; // reverse direction	44✔
96	}
97	}
98	if(length)	4✔
99	*length = cachedPath->size();	1✔
100	return true;	4✔
101	}
102
103	// Not in cache -> compute full path and add
104	std::vector<Direction> newRoute;	48✔
105	if(!FindShipPath(start, coastalPoint, std::numeric_limits<unsigned>::max(), &newRoute, length))	24✔
NEW 106	return false;	×
107	shipPathData.addToCache(start, coastalPoint, newRoute);	24✔
108	if(route)	24✔
109	*route = std::move(newRoute);	24✔
110
111	return true;	24✔
112	}
113
114	bool GameWorldBase::FindShipPath(const MapPoint start, const MapPoint dest, unsigned maxDistance,	363✔
115	std::vector<Direction>* route, unsigned* length) const
116	{
117	return GetFreePathFinder().FindPath(start, dest, true, maxDistance, route, length, nullptr,	726✔
118	PathConditionShip(*this));	726✔
119	}
120
121	/// Prüft, ob eine Schiffsroute noch Gültigkeit hat
122	bool GameWorld::CheckShipRoute(const MapPoint start, const std::vector<Direction>& route, const unsigned pos,	471✔
123	MapPoint* dest) const
124	{
125	return GetFreePathFinder().CheckRoute(start, route, pos, PathConditionShip(*this), dest);	471✔
126	}
127
128	/// Find a route for trade caravanes
129	helpers::OptionalEnum<Direction> GameWorld::FindTradePath(const MapPoint start, const MapPoint dest,	36✔
130	unsigned char player, unsigned max_route, bool random_route,
131	std::vector<Direction>* route, unsigned* length) const
132	{
133	unsigned char owner = GetNode(dest).owner;	36✔
134	if(owner != 0 && !GetPlayer(player).IsAlly(owner - 1))	36✔
135	return boost::none;	14✔
136
137	RTTR_Assert(GetNO(dest)->GetType() == NodalObjectType::Flag); // Goal should be the flag of a wh	22✔
138
139	if(!PathConditionHuman(*this).IsNodeOk(dest))	44✔
140	return boost::none;	×
141
142	Direction first_dir{};	22✔
143	if(GetFreePathFinder().FindPath(start, dest, random_route, max_route, route, length, &first_dir,	44✔
144	PathConditionTrade(*this, player)))	44✔
145	return first_dir;	18✔
146	else
147	return boost::none;	4✔
148	}
149
150	bool GameWorld::CheckTradeRoute(const MapPoint start, const std::vector<Direction>& route, unsigned pos,	190✔
151	unsigned char player, MapPoint* dest) const
152	{
153	return GetFreePathFinder().CheckRoute(start, route, pos, PathConditionTrade(*this, player), dest);	190✔
154	}

Return-To-The-Roots / s25client / 25985372463

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