OpenTTD Source
1.11.0-beta2
|
Go to the documentation of this file.
20 #include "../../tile_type.h"
21 #include "../../track_type.h"
60 bool CheckIgnoreFirstTile(
const PathNode *node);
BinaryHeap openlist_queue
The open queue.
uint32 TileIndex
The index/ID of a Tile.
@ AYSTAR_DONE
Not an end-tile, or wrong direction.
@ AYSTAR_LIMIT_REACHED
The AyStar::max_search_nodes limit has been reached, aborting search.
Hash closedlist_hash
The actual closed list.
@ AYSTAR_EMPTY_OPENLIST
All items are tested, and no path has been found.
PathNode * ClosedListIsInList(const AyStarNode *node)
This looks in the hash whether a node exists in the closed list.
int32 AyStar_EndNodeCheck(const AyStar *aystar, const OpenListNode *current)
Check whether the end-tile is found.
int Main()
This is the function you call to run AyStar.
OpenListNode * OpenListPop()
Gets the best node from the open list.
void Init(Hash_HashProc hash, uint num_buckets)
Initialize an AyStar.
@ AYSTAR_NO_PATH
No path to the goal was found.
void AyStar_GetNeighbours(AyStar *aystar, OpenListNode *current)
This function requests the tiles around the current tile and put them in #neighbours.
void ClosedListAdd(const PathNode *node)
This adds a node to the closed list.
int32 AyStar_CalculateG(AyStar *aystar, AyStarNode *current, OpenListNode *parent)
Calculate the G-value for the AyStar algorithm.
void Free()
This function frees the memory it allocated.
Hash openlist_hash
An extra hash to speed up the process of looking up an element in the open list.
byte loops_per_tick
How many loops are there called before Main() gives control back to the caller. 0 = until done.
AystarStatus
Return status of AyStar methods.
@ AYSTAR_STILL_BUSY
Some checking was done, but no path found yet, and there are still items left to try.
OpenListNode * OpenListIsInList(const AyStarNode *node)
Check whether a node is in the open list.
void Clear()
This function make the memory go back to zero.
@ AYSTAR_FOUND_END_NODE
An end node was found.
int Loop()
This function is the core of AyStar.
AyStar search algorithm struct.
PathNode * parent
The parent of this item.
void OpenListAdd(PathNode *parent, const AyStarNode *node, int f, int g)
Adds a node to the open list.
void AyStar_FoundEndNode(AyStar *aystar, OpenListNode *current)
If the End Node is found, this function is called.
static const int AYSTAR_INVALID_NODE
Item is not valid (for example, not walkable).
uint max_path_cost
If the g-value goes over this number, it stops searching, 0 = infinite.
Trackdir
Enumeration for tracks and directions.
int32 AyStar_CalculateH(AyStar *aystar, AyStarNode *current, OpenListNode *parent)
Calculate the H-value for the AyStar algorithm.
void AddStartNode(AyStarNode *start_node, uint g)
Adds a node from where to start an algorithm.
uint Hash_HashProc(uint key1, uint key2)
Generates a hash code from the given key pair.
uint max_search_nodes
The maximum number of nodes that will be expanded, 0 = infinite.
void CheckTile(AyStarNode *current, OpenListNode *parent)
Checks one tile and calculate its f-value.