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

93.75

/libs/s25main/pathfinding/ShipPathData.cpp

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

#include "ShipPathData.h"
#include "EventManager.h"
#include "helpers/IdRange.h"
#include "helpers/containerUtils.h"
#include "pathfinding/FreePathFinder.h"
#include "pathfinding/PathConditionShip.h"
#include "world/GameWorldBase.h"
#include <algorithm>
#include <set>

struct ShipPathData::HarborConnection::Matcher
{
    HarborId harbor;
    SeaId sea;
    constexpr bool operator()(const ShipPathData::HarborConnection& con) const
    {
        return con.destHarbor == harbor && con.sea == sea;
    }
};

std::vector<Direction> ShipPathData::getHarborConnection(HarborId startHarbor, HarborId destHarbor, SeaId seaId)
{
    if(harborConnections_.empty())
        initHarborConnections();
    const auto it = helpers::find_if(harborConnections_[startHarbor], HarborConnection::Matcher{destHarbor, seaId});
    RTTR_Assert(it != harborConnections_[startHarbor].end());
    return it->route;
}

const std::vector<Direction>* ShipPathData::findCachedPath(MapPoint start, MapPoint dest, bool& reversed) const
{
    for(const PathEntry& e : cachedPaths_)
    {
        if(e.start == start && e.dest == dest)
        {
            const_cast<PathEntry&>(e).lastUse = world_.GetEvMgr().GetCurrentGF();
            reversed = false;
            return &e.route;
        }
        if(e.start == dest && e.dest == start)
        {
            const_cast<PathEntry&>(e).lastUse = world_.GetEvMgr().GetCurrentGF();
            reversed = true;
            return &e.route;
        }
    }
    return nullptr;
}

void ShipPathData::addToCache(MapPoint start, MapPoint dest, std::vector<Direction> route)
{
    PathEntry entry{start, dest, world_.GetEvMgr().GetCurrentGF(), std::move(route)};
    if(cachedPaths_.size() < cachedPaths_.max_size())
        cachedPaths_.emplace_back(std::move(entry));
    else
    {
        const auto itOldest =
          std::min_element(cachedPaths_.begin(), cachedPaths_.end(),
                           [](const PathEntry& a, const PathEntry& b) { return a.lastUse < b.lastUse; });
        *itOldest = std::move(entry);
    }
}

void ShipPathData::initHarborConnections()
{
    harborConnections_.resize(world_.GetNumHarborPoints());
    for(const auto startHbId : helpers::idRange<HarborId>(world_.GetNumHarborPoints()))
    {
        auto& curConnections = harborConnections_[startHbId];
        std::vector<HarborPos::Neighbor> neighbors;
        for(const auto dir : helpers::EnumRange<ShipDirection>{})
        {
            const auto& curNbs = world_.GetHarborNeighbors(startHbId, dir);
            neighbors.insert(neighbors.end(), curNbs.begin(), curNbs.end());
        }
        for(const auto& nb : neighbors)
        {
            RTTR_Assert(startHbId != nb.id);
            RTTR_Assert(nb.sea);
            // Connections are unique
            RTTR_Assert(!helpers::contains_if(curConnections, HarborConnection::Matcher{nb.id, nb.sea}));
            curConnections.push_back(HarborConnection{nb.id, nb.sea, {}});
            unsigned len = 0;
            const auto startPoint = world_.GetCoastalPoint(startHbId, nb.sea);
            const auto nbPoint = world_.GetCoastalPoint(nb.id, nb.sea);
            const bool found =
              (startPoint == nbPoint)
              || world_.FindShipPath(startPoint, nbPoint, nb.distance, &curConnections.back().route, &len);
            RTTR_Assert(found);
            RTTR_Assert(len == nb.distance);
        }
    }
}

1	// Copyright (C) 2005 - 2026 Settlers Freaks (sf-team at siedler25.org)
2	//
3	// SPDX-License-Identifier: GPL-2.0-or-later
4
5	#include "ShipPathData.h"
6	#include "EventManager.h"
7	#include "helpers/IdRange.h"
8	#include "helpers/containerUtils.h"
9	#include "pathfinding/FreePathFinder.h"
10	#include "pathfinding/PathConditionShip.h"
11	#include "world/GameWorldBase.h"
12	#include <algorithm>
13	#include <set>
14
15	struct ShipPathData::HarborConnection::Matcher
16	{
17	HarborId harbor;
18	SeaId sea;
19	constexpr bool operator()(const ShipPathData::HarborConnection& con) const	347✔
20	{
21	return con.destHarbor == harbor && con.sea == sea;	347✔
22	}
23	};
24
25	std::vector<Direction> ShipPathData::getHarborConnection(HarborId startHarbor, HarborId destHarbor, SeaId seaId)	25✔
26	{
27	if(harborConnections_.empty())	25✔
28	initHarborConnections();	9✔
29	const auto it = helpers::find_if(harborConnections_[startHarbor], HarborConnection::Matcher{destHarbor, seaId});	25✔
30	RTTR_Assert(it != harborConnections_[startHarbor].end());	50✔
31	return it->route;	50✔
32	}
33
34	const std::vector<Direction>* ShipPathData::findCachedPath(MapPoint start, MapPoint dest, bool& reversed) const	28✔
35	{
36	for(const PathEntry& e : cachedPaths_)	138✔
37	{
38	if(e.start == start && e.dest == dest)	31✔
39	{
40	const_cast<PathEntry&>(e).lastUse = world_.GetEvMgr().GetCurrentGF();	1✔
41	reversed = false;	1✔
42	return &e.route;	4✔
43	}
44	if(e.start == dest && e.dest == start)	30✔
45	{
46	const_cast<PathEntry&>(e).lastUse = world_.GetEvMgr().GetCurrentGF();	3✔
47	reversed = true;	3✔
48	return &e.route;	3✔
49	}
50	}
51	return nullptr;	24✔
52	}
53
54	void ShipPathData::addToCache(MapPoint start, MapPoint dest, std::vector<Direction> route)	24✔
55	{
56	PathEntry entry{start, dest, world_.GetEvMgr().GetCurrentGF(), std::move(route)};	48✔
57	if(cachedPaths_.size() < cachedPaths_.max_size())	72✔
58	cachedPaths_.emplace_back(std::move(entry));	24✔
59	else
60	{
61	const auto itOldest =
NEW 62	std::min_element(cachedPaths_.begin(), cachedPaths_.end(),	×
NEW 63	[](const PathEntry& a, const PathEntry& b) { return a.lastUse < b.lastUse; });	×
NEW 64	*itOldest = std::move(entry);	×
65	}
66	}	24✔
67
68	void ShipPathData::initHarborConnections()	9✔
69	{
70	harborConnections_.resize(world_.GetNumHarborPoints());	9✔
71	for(const auto startHbId : helpers::idRange<HarborId>(world_.GetNumHarborPoints()))	80✔
72	{
73	auto& curConnections = harborConnections_[startHbId];	71✔
74	std::vector<HarborPos::Neighbor> neighbors;	142✔
75	for(const auto dir : helpers::EnumRange<ShipDirection>{})	1,136✔
76	{
77	const auto& curNbs = world_.GetHarborNeighbors(startHbId, dir);	426✔
78	neighbors.insert(neighbors.end(), curNbs.begin(), curNbs.end());	426✔
79	}
80	for(const auto& nb : neighbors)	305✔
81	{
82	RTTR_Assert(startHbId != nb.id);	234✔
83	RTTR_Assert(nb.sea);	234✔
84	// Connections are unique
85	RTTR_Assert(!helpers::contains_if(curConnections, HarborConnection::Matcher{nb.id, nb.sea}));	234✔
86	curConnections.push_back(HarborConnection{nb.id, nb.sea, {}});	468✔
87	unsigned len = 0;	234✔
88	const auto startPoint = world_.GetCoastalPoint(startHbId, nb.sea);	234✔
89	const auto nbPoint = world_.GetCoastalPoint(nb.id, nb.sea);	234✔
90	const bool found =
91	(startPoint == nbPoint)	234✔
92	\|\| world_.FindShipPath(startPoint, nbPoint, nb.distance, &curConnections.back().route, &len);	466✔
93	RTTR_Assert(found);	234✔
94	RTTR_Assert(len == nb.distance);	234✔
95	}
96	}
97	}	9✔

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