OpenTTD Source  20241108-master-g80f628063a
aystar.h
Go to the documentation of this file.
1 /*
2  * This file is part of OpenTTD.
3  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
4  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
5  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
6  */
7 
16 #ifndef AYSTAR_H
17 #define AYSTAR_H
18 
19 #include "../track_func.h"
20 
21 #include "../misc/hashtable.hpp"
22 #include "../misc/binaryheap.hpp"
23 #include "../misc/dbg_helpers.h"
24 
25 #include "yapf/nodelist.hpp"
26 #include "yapf/yapf_node.hpp"
27 
28 static const int AYSTAR_DEF_MAX_SEARCH_NODES = 10000;
29 
38 };
39 
40 static const int AYSTAR_INVALID_NODE = -1;
41 
43 
44 struct PathNode : CYapfNodeT<AyStarNode, PathNode> {
45 };
46 
47 bool CheckIgnoreFirstTile(const PathNode *node);
48 
49 struct AyStar;
50 
65 typedef int32_t AyStar_EndNodeCheck(const AyStar *aystar, const PathNode *current);
66 
73 typedef int32_t AyStar_CalculateG(AyStar *aystar, AyStarNode *current, PathNode *parent);
74 
80 typedef int32_t AyStar_CalculateH(AyStar *aystar, AyStarNode *current, PathNode *parent);
81 
87 typedef void AyStar_GetNeighbours(AyStar *aystar, PathNode *current);
88 
93 typedef void AyStar_FoundEndNode(AyStar *aystar, PathNode *current);
94 
103 struct AyStar {
104 /* These fields should be filled before initing the AyStar, but not changed
105  * afterwards (except for user_data)! (free and init again to change them) */
106 
107  /* These should point to the application specific routines that do the
108  * actual work */
109  AyStar_CalculateG *CalculateG;
110  AyStar_CalculateH *CalculateH;
111  AyStar_GetNeighbours *GetNeighbours;
112  AyStar_EndNodeCheck *EndNodeCheck;
113  AyStar_FoundEndNode *FoundEndNode;
114 
115  /* These are completely untouched by AyStar, they can be accessed by
116  * the application specific routines to input and output data.
117  * user_path should typically contain data about the resulting path
118  * afterwards, user_target should typically contain information about
119  * what you where looking for, and user_data can contain just about
120  * everything */
121  void *user_target;
122  void *user_data;
123 
124  uint8_t loops_per_tick;
127 
128  /* These should be filled with the neighbours of a tile by GetNeighbours */
129  std::vector<AyStarNode> neighbours;
130 
131  /* These will contain the methods for manipulating the AyStar. Only
132  * Main() should be called externally */
133  void AddStartNode(AyStarNode *start_node, int g);
134  int Main();
135  int Loop();
136  void CheckTile(AyStarNode *current, PathNode *parent);
137 
138 protected:
140 
141  void OpenListAdd(PathNode *parent, const AyStarNode *node, int f, int g);
142 };
143 
144 #endif /* AYSTAR_H */
int32_t AyStar_CalculateG(AyStar *aystar, AyStarNode *current, PathNode *parent)
Calculate the G-value for the AyStar algorithm.
Definition: aystar.h:73
static const int AYSTAR_INVALID_NODE
Item is not valid (for example, not walkable).
Definition: aystar.h:40
int32_t AyStar_CalculateH(AyStar *aystar, AyStarNode *current, PathNode *parent)
Calculate the H-value for the AyStar algorithm.
Definition: aystar.h:80
AystarStatus
Return status of AyStar methods.
Definition: aystar.h:31
@ AYSTAR_DONE
Not an end-tile, or wrong direction.
Definition: aystar.h:37
@ AYSTAR_LIMIT_REACHED
The AyStar::max_search_nodes limit has been reached, aborting search.
Definition: aystar.h:36
@ AYSTAR_FOUND_END_NODE
An end node was found.
Definition: aystar.h:32
@ AYSTAR_NO_PATH
No path to the goal was found.
Definition: aystar.h:35
@ AYSTAR_STILL_BUSY
Some checking was done, but no path found yet, and there are still items left to try.
Definition: aystar.h:34
@ AYSTAR_EMPTY_OPENLIST
All items are tested, and no path has been found.
Definition: aystar.h:33
void AyStar_GetNeighbours(AyStar *aystar, PathNode *current)
This function requests the tiles around the current tile and put them in #neighbours.
Definition: aystar.h:87
static const int AYSTAR_DEF_MAX_SEARCH_NODES
Reference limit for AyStar::max_search_nodes.
Definition: aystar.h:28
int32_t AyStar_EndNodeCheck(const AyStar *aystar, const PathNode *current)
Check whether the end-tile is found.
Definition: aystar.h:65
void AyStar_FoundEndNode(AyStar *aystar, PathNode *current)
If the End Node is found, this function is called.
Definition: aystar.h:93
List of nodes used for the A-star pathfinder.
AyStar search algorithm struct.
Definition: aystar.h:103
int max_search_nodes
The maximum number of nodes that will be expanded, 0 = infinite.
Definition: aystar.h:126
void OpenListAdd(PathNode *parent, const AyStarNode *node, int f, int g)
Adds a node to the open list.
Definition: aystar.cpp:25
int Loop()
This function is the core of AyStar.
Definition: aystar.cpp:92
int max_path_cost
If the g-value goes over this number, it stops searching, 0 = infinite.
Definition: aystar.h:125
void CheckTile(AyStarNode *current, PathNode *parent)
Checks one tile and calculate its f-value.
Definition: aystar.cpp:38
void AddStartNode(AyStarNode *start_node, int g)
Adds a node from where to start an algorithm.
Definition: aystar.cpp:168
int Main()
This is the function you call to run AyStar.
Definition: aystar.cpp:137
uint8_t loops_per_tick
How many loops are there called before Main() gives control back to the caller. 0 = until done.
Definition: aystar.h:124
Yapf Node base.
Definition: yapf_node.hpp:62
Node in the pathfinder's graph.