OpenTTD Source  1.11.0-beta2
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 "queue.h"
20 #include "../../tile_type.h"
21 #include "../../track_type.h"
22 
23 //#define AYSTAR_DEBUG
24 
33 };
34 
35 static const int AYSTAR_INVALID_NODE = -1;
36 
38 struct AyStarNode {
39  TileIndex tile;
40  Trackdir direction;
41  uint user_data[2];
42 };
43 
45 struct PathNode {
46  AyStarNode node;
48 };
49 
55 struct OpenListNode {
56  int g;
57  PathNode path;
58 };
59 
60 bool CheckIgnoreFirstTile(const PathNode *node);
61 
62 struct AyStar;
63 
78 typedef int32 AyStar_EndNodeCheck(const AyStar *aystar, const OpenListNode *current);
79 
86 typedef int32 AyStar_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
87 
93 typedef int32 AyStar_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
94 
100 typedef void AyStar_GetNeighbours(AyStar *aystar, OpenListNode *current);
101 
106 typedef void AyStar_FoundEndNode(AyStar *aystar, OpenListNode *current);
107 
116 struct AyStar {
117 /* These fields should be filled before initing the AyStar, but not changed
118  * afterwards (except for user_data and user_path)! (free and init again to change them) */
119 
120  /* These should point to the application specific routines that do the
121  * actual work */
122  AyStar_CalculateG *CalculateG;
123  AyStar_CalculateH *CalculateH;
124  AyStar_GetNeighbours *GetNeighbours;
125  AyStar_EndNodeCheck *EndNodeCheck;
126  AyStar_FoundEndNode *FoundEndNode;
127 
128  /* These are completely untouched by AyStar, they can be accessed by
129  * the application specific routines to input and output data.
130  * user_path should typically contain data about the resulting path
131  * afterwards, user_target should typically contain information about
132  * what you where looking for, and user_data can contain just about
133  * everything */
134  void *user_path;
135  void *user_target;
136  void *user_data;
137 
141 
142  /* These should be filled with the neighbours of a tile by
143  * GetNeighbours */
144  AyStarNode neighbours[12];
145  byte num_neighbours;
146 
147  void Init(Hash_HashProc hash, uint num_buckets);
148 
149  /* These will contain the methods for manipulating the AyStar. Only
150  * Main() should be called externally */
151  void AddStartNode(AyStarNode *start_node, uint g);
152  int Main();
153  int Loop();
154  void Free();
155  void Clear();
156  void CheckTile(AyStarNode *current, OpenListNode *parent);
157 
158 protected:
162 
163  void OpenListAdd(PathNode *parent, const AyStarNode *node, int f, int g);
166 
167  void ClosedListAdd(const PathNode *node);
168  PathNode *ClosedListIsInList(const AyStarNode *node);
169 };
170 
171 #endif /* AYSTAR_H */
AyStar::openlist_queue
BinaryHeap openlist_queue
The open queue.
Definition: aystar.h:160
TileIndex
uint32 TileIndex
The index/ID of a Tile.
Definition: tile_type.h:78
AYSTAR_DONE
@ AYSTAR_DONE
Not an end-tile, or wrong direction.
Definition: aystar.h:32
AYSTAR_LIMIT_REACHED
@ AYSTAR_LIMIT_REACHED
The AyStar::max_search_nodes limit has been reached, aborting search.
Definition: aystar.h:31
AyStar::closedlist_hash
Hash closedlist_hash
The actual closed list.
Definition: aystar.h:159
AYSTAR_EMPTY_OPENLIST
@ AYSTAR_EMPTY_OPENLIST
All items are tested, and no path has been found.
Definition: aystar.h:28
AyStar::ClosedListIsInList
PathNode * ClosedListIsInList(const AyStarNode *node)
This looks in the hash whether a node exists in the closed list.
Definition: aystar.cpp:35
AyStar_EndNodeCheck
int32 AyStar_EndNodeCheck(const AyStar *aystar, const OpenListNode *current)
Check whether the end-tile is found.
Definition: aystar.h:78
BinaryHeap
Binary Heap.
Definition: queue.h:26
AyStar::Main
int Main()
This is the function you call to run AyStar.
Definition: aystar.cpp:245
AyStar::OpenListPop
OpenListNode * OpenListPop()
Gets the best node from the open list.
Definition: aystar.cpp:68
AyStar::Init
void Init(Hash_HashProc hash, uint num_buckets)
Initialize an AyStar.
Definition: aystar.cpp:293
AYSTAR_NO_PATH
@ AYSTAR_NO_PATH
No path to the goal was found.
Definition: aystar.h:30
AyStar_GetNeighbours
void AyStar_GetNeighbours(AyStar *aystar, OpenListNode *current)
This function requests the tiles around the current tile and put them in #neighbours.
Definition: aystar.h:100
AyStar::ClosedListAdd
void ClosedListAdd(const PathNode *node)
This adds a node to the closed list.
Definition: aystar.cpp:45
AyStar_CalculateG
int32 AyStar_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent)
Calculate the G-value for the AyStar algorithm.
Definition: aystar.h:86
AyStar::Free
void Free()
This function frees the memory it allocated.
Definition: aystar.cpp:206
AyStar::openlist_hash
Hash openlist_hash
An extra hash to speed up the process of looking up an element in the open list.
Definition: aystar.h:161
PathNode
A path of nodes.
Definition: aystar.h:45
AyStar::loops_per_tick
byte loops_per_tick
How many loops are there called before Main() gives control back to the caller. 0 = until done.
Definition: aystar.h:138
AystarStatus
AystarStatus
Return status of AyStar methods.
Definition: aystar.h:26
AYSTAR_STILL_BUSY
@ AYSTAR_STILL_BUSY
Some checking was done, but no path found yet, and there are still items left to try.
Definition: aystar.h:29
AyStar::OpenListIsInList
OpenListNode * OpenListIsInList(const AyStarNode *node)
Check whether a node is in the open list.
Definition: aystar.cpp:58
AyStarNode
Node in the search.
Definition: aystar.h:38
queue.h
OpenListNode
Internal node.
Definition: aystar.h:55
AyStar::Clear
void Clear()
This function make the memory go back to zero.
Definition: aystar.cpp:222
AYSTAR_FOUND_END_NODE
@ AYSTAR_FOUND_END_NODE
An end node was found.
Definition: aystar.h:27
AyStar::Loop
int Loop()
This function is the core of AyStar.
Definition: aystar.cpp:161
AyStar
AyStar search algorithm struct.
Definition: aystar.h:116
PathNode::parent
PathNode * parent
The parent of this item.
Definition: aystar.h:47
AyStar::OpenListAdd
void OpenListAdd(PathNode *parent, const AyStarNode *node, int f, int g)
Adds a node to the open list.
Definition: aystar.cpp:83
AyStar_FoundEndNode
void AyStar_FoundEndNode(AyStar *aystar, OpenListNode *current)
If the End Node is found, this function is called.
Definition: aystar.h:106
AYSTAR_INVALID_NODE
static const int AYSTAR_INVALID_NODE
Item is not valid (for example, not walkable).
Definition: aystar.h:35
AyStar::max_path_cost
uint max_path_cost
If the g-value goes over this number, it stops searching, 0 = infinite.
Definition: aystar.h:139
Trackdir
Trackdir
Enumeration for tracks and directions.
Definition: track_type.h:70
AyStar_CalculateH
int32 AyStar_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent)
Calculate the H-value for the AyStar algorithm.
Definition: aystar.h:93
AyStar::AddStartNode
void AddStartNode(AyStarNode *start_node, uint g)
Adds a node from where to start an algorithm.
Definition: aystar.cpp:280
Hash
Definition: queue.h:71
Hash_HashProc
uint Hash_HashProc(uint key1, uint key2)
Generates a hash code from the given key pair.
Definition: queue.h:70
AyStar::max_search_nodes
uint max_search_nodes
The maximum number of nodes that will be expanded, 0 = infinite.
Definition: aystar.h:140
AyStar::CheckTile
void CheckTile(AyStarNode *current, OpenListNode *parent)
Checks one tile and calculate its f-value.
Definition: aystar.cpp:99