OpenTTD
aystar.h
Go to the documentation of this file.
1 /* $Id$ */
2 
3 /*
4  * This file is part of OpenTTD.
5  * 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.
6  * 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.
7  * 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/>.
8  */
9 
18 #ifndef AYSTAR_H
19 #define AYSTAR_H
20 
21 #include "queue.h"
22 #include "../../tile_type.h"
23 #include "../../track_type.h"
24 
25 //#define AYSTAR_DEBUG
26 
35 };
36 
37 static const int AYSTAR_INVALID_NODE = -1;
38 
40 struct AyStarNode {
41  TileIndex tile;
42  Trackdir direction;
43  uint user_data[2];
44 };
45 
47 struct PathNode {
48  AyStarNode node;
50 };
51 
57 struct OpenListNode {
58  int g;
59  PathNode path;
60 };
61 
62 bool CheckIgnoreFirstTile(const PathNode *node);
63 
64 struct AyStar;
65 
80 typedef int32 AyStar_EndNodeCheck(const AyStar *aystar, const OpenListNode *current);
81 
88 typedef int32 AyStar_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
89 
95 typedef int32 AyStar_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent);
96 
102 typedef void AyStar_GetNeighbours(AyStar *aystar, OpenListNode *current);
103 
108 typedef void AyStar_FoundEndNode(AyStar *aystar, OpenListNode *current);
109 
118 struct AyStar {
119 /* These fields should be filled before initing the AyStar, but not changed
120  * afterwards (except for user_data and user_path)! (free and init again to change them) */
121 
122  /* These should point to the application specific routines that do the
123  * actual work */
124  AyStar_CalculateG *CalculateG;
125  AyStar_CalculateH *CalculateH;
126  AyStar_GetNeighbours *GetNeighbours;
127  AyStar_EndNodeCheck *EndNodeCheck;
128  AyStar_FoundEndNode *FoundEndNode;
129 
130  /* These are completely untouched by AyStar, they can be accessed by
131  * the application specific routines to input and output data.
132  * user_path should typically contain data about the resulting path
133  * afterwards, user_target should typically contain information about
134  * what you where looking for, and user_data can contain just about
135  * everything */
136  void *user_path;
137  void *user_target;
138  void *user_data;
139 
143 
144  /* These should be filled with the neighbours of a tile by
145  * GetNeighbours */
146  AyStarNode neighbours[12];
147  byte num_neighbours;
148 
149  void Init(Hash_HashProc hash, uint num_buckets);
150 
151  /* These will contain the methods for manipulating the AyStar. Only
152  * Main() should be called externally */
153  void AddStartNode(AyStarNode *start_node, uint g);
154  int Main();
155  int Loop();
156  void Free();
157  void Clear();
158  void CheckTile(AyStarNode *current, OpenListNode *parent);
159 
160 protected:
164 
165  void OpenListAdd(PathNode *parent, const AyStarNode *node, int f, int g);
166  OpenListNode *OpenListIsInList(const AyStarNode *node);
167  OpenListNode *OpenListPop();
168 
169  void ClosedListAdd(const PathNode *node);
170  PathNode *ClosedListIsInList(const AyStarNode *node);
171 };
172 
173 #endif /* AYSTAR_H */
void AyStar_FoundEndNode(AyStar *aystar, OpenListNode *current)
If the End Node is found, this function is called.
Definition: aystar.h:108
Binary Heap.
Definition: queue.h:28
Internal node.
Definition: aystar.h:57
static const int AYSTAR_INVALID_NODE
Item is not valid (for example, not walkable).
Definition: aystar.h:37
No path to the goal was found.
Definition: aystar.h:32
Definition: queue.h:73
byte loops_per_tick
How many loops are there called before Main() gives control back to the caller. 0 = until done...
Definition: aystar.h:140
uint max_path_cost
If the g-value goes over this number, it stops searching, 0 = infinite.
Definition: aystar.h:141
Not an end-tile, or wrong direction.
Definition: aystar.h:34
The AyStar::max_search_nodes limit has been reached, aborting search.
Definition: aystar.h:33
BinaryHeap openlist_queue
The open queue.
Definition: aystar.h:162
AyStar search algorithm struct.
Definition: aystar.h:118
Binary heap implementation, hash implementation.
A path of nodes.
Definition: aystar.h:47
uint max_search_nodes
The maximum number of nodes that will be expanded, 0 = infinite.
Definition: aystar.h:142
Trackdir
Enumeration for tracks and directions.
Definition: track_type.h:74
All items are tested, and no path has been found.
Definition: aystar.h:30
uint Hash_HashProc(uint key1, uint key2)
Generates a hash code from the given key pair.
Definition: queue.h:72
int32 AyStar_EndNodeCheck(const AyStar *aystar, const OpenListNode *current)
Check whether the end-tile is found.
Definition: aystar.h:80
PathNode * parent
The parent of this item.
Definition: aystar.h:49
Node in the search.
Definition: aystar.h:40
int32 AyStar_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent)
Calculate the H-value for the AyStar algorithm.
Definition: aystar.h:95
Hash closedlist_hash
The actual closed list.
Definition: aystar.h:161
Some checking was done, but no path found yet, and there are still items left to try.
Definition: aystar.h:31
void AyStar_GetNeighbours(AyStar *aystar, OpenListNode *current)
This function requests the tiles around the current tile and put them in #neighbours.
Definition: aystar.h:102
int32 AyStar_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent)
Calculate the G-value for the AyStar algorithm.
Definition: aystar.h:88
uint32 TileIndex
The index/ID of a Tile.
Definition: tile_type.h:80
AystarStatus
Return status of AyStar methods.
Definition: aystar.h:28
Hash openlist_hash
An extra hash to speed up the process of looking up an element in the open list.
Definition: aystar.h:163
An end node was found.
Definition: aystar.h:29