pathfinder/EvePathfinder.cpp at main · carbonengine/pathfinder · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
// Copyright © 2014 CCP ehf.

#include "stdafx.h"
#include <functional>

BLUE_REGISTER_GLOBAL_AS_MODULE_OBJECT( "classes", BeClasses );
BLUE_STANDARD_MODULE_INIT( _pyevepathfinder );

#include <memory>
#include "EvePathfinder.h"
#include "EveMapPathfinderCache.h"
#include "Include/IEvePathfinderGoal.h"
#include "EveMap.h"

typedef EveMapNode const * const constEveMapNodePtr;

void RunPathfinder( const EveMap* universeMap, const IEvePathfinderGoal* goal, EveMapPathfinderCache* cache )
{
	if( universeMap == nullptr || goal == nullptr || cache == nullptr )
	{
		return;
	}

	std::vector<EveMapNodeID> neighbours;
	neighbours.reserve(5);

	std::vector<EveMapNodeID> origins;
	goal->GetOriginSystems( origins );

	// Add all origin systems
	for( std::vector<EveMapNodeID>::iterator originIt = origins.begin(); originIt !=  origins.end(); ++originIt )
	{
		constEveMapNodePtr o = universeMap->GetSolarSystem( *originIt );
		ClosedListNode& originInClosedList = cache->GetCurrentPath( o->m_closedListID );

		originInClosedList.m_jumpCountFromOrigin = 0;
		originInClosedList.m_visited = true;
		originInClosedList.m_mapNodeID = *originIt;
	}

	// Populate open list with the neighbours of the origin systems.
	for( std::vector<EveMapNodeID>::iterator originIt = origins.begin(); originIt !=  origins.end(); ++originIt )
	{
		constEveMapNodePtr originSystem = universeMap->GetSolarSystem( *originIt );
		EveMapNodeID origin = *originIt;
		ClosedListNode& originPath = cache->GetCurrentPath( originSystem->m_closedListID );

		if( originSystem )
		{
			goal->GetNeighbours( *universeMap, origin, neighbours );

			for( std::vector<EveMapNodeID>::iterator neighbourIt = neighbours.begin(); neighbourIt != neighbours.end(); ++neighbourIt )
			{
				constEveMapNodePtr candidateSystem = universeMap->GetSolarSystem( *neighbourIt );
				ClosedListNode& candidatePath = cache->GetCurrentPath( candidateSystem->m_closedListID );

				if( candidatePath.m_jumpCountFromOrigin != 0 )
				{
					cache->AddCandidate(
						*neighbourIt,
						*originIt,
						goal->GetTraversalCost( *originSystem,*candidateSystem ),
						goal->GetHeuristicEstimate(*candidateSystem),
						originPath,
						candidatePath);
				}
			}
		}
	}

	// While there are still candidates in the cache
	while( !cache->IsComplete() && !cache->AreAllOptionsExhausted() )
	{
		// delete when done
		std::unique_ptr<const OpenListNode> candidate( cache->GetBestCandidate() );

		if( !candidate.get() )
		{
			return;
		}

		EveMapNodeID candidateSystemID = candidate->m_toNode;
		constEveMapNodePtr candidateSystemNode = universeMap->GetSolarSystem( candidateSystemID );

		if( !candidateSystemNode )
		{
			return;
		}

		// Find the current path to the given node
		ClosedListNode& currentPath = cache->GetCurrentPath( candidateSystemNode->m_closedListID );

		if( currentPath.m_jumpCountFromOrigin == 0 )
		{
			// No point in revisiting an origin node
			continue;
		}
		else if( currentPath.m_visited && currentPath.m_costToNode <= candidate->m_costToNodeFromOrigin )
		{
			// the candidate path is longer than an existing path
			continue;
		}

		// Either the new path is shorter, or we haven't visited the node before
		// Set it into the closed list
		cache->SetPathToSystem( *universeMap, candidateSystemID, candidate->m_fromNode, candidate->m_costToNodeFromOrigin );

		if( goal->IsGoal( *universeMap, candidateSystemID ) )
		{
			// We are done
			cache->SetSolutionSystem( *universeMap, candidateSystemID );
			return;
		}

		// Now we explore the neighbours and add them to the open list
		goal->GetNeighbours( *universeMap, candidateSystemID, neighbours );

		for( std::vector<EveMapNodeID>::iterator neighbourIt = neighbours.begin(); neighbourIt != neighbours.end(); ++neighbourIt )
		{
			EveMapNodeID neighbourID = *neighbourIt;

			if( neighbourID == candidateSystemID )
			{
				// This is where we just came from. Skip It.
				continue;
			}

			// Generate new open list candidates
			constEveMapNodePtr neighbour = universeMap->GetSolarSystem( neighbourID );

			if( !neighbour )
			{
				continue;
			}

			// Find the current path to the given node
			ClosedListNode& neighbourPath = cache->GetCurrentPath( neighbour->m_closedListID );

			cache->AddCandidate(
				neighbourID,
				candidate->m_toNode,
				candidate->m_costToNodeFromOrigin + goal->GetTraversalCost( *candidateSystemNode, *neighbour ),
				goal->GetHeuristicEstimate( *neighbour ),
				currentPath,
				neighbourPath
			);
		}
	}
}


MAP_FUNCTION_AND_WRAP( "FindRoute", RunPathfinder, "TODO: Docstring");