OpenTTD Source
1.11.0-beta2
|
Go to the documentation of this file.
24 #include "../../stdafx.h"
25 #include "../../core/alloc_func.hpp"
28 #include "../../safeguards.h"
48 PathNode *new_node = MallocT<PathNode>(1);
88 new_node->path.
parent = parent;
89 new_node->path.node = *node;
101 int new_f, new_g, new_h;
109 new_g = this->CalculateG(
this, current, parent);
120 new_h = this->CalculateH(
this, current, parent);
125 new_f = new_g + new_h;
132 if (check !=
nullptr) {
135 if (new_g > check->g)
return;
139 check->path.
parent = closedlist_parent;
141 for (i = 0; i <
lengthof(current->user_data); i++) {
142 check->path.node.user_data[i] = current->user_data[i];
148 this->
OpenListAdd(closedlist_parent, current, new_f, new_g);
171 if (this->EndNodeCheck(
this, current) ==
AYSTAR_FOUND_END_NODE && !CheckIgnoreFirstTile(¤t->path)) {
172 if (this->FoundEndNode !=
nullptr) {
173 this->FoundEndNode(
this, current);
183 this->GetNeighbours(
this, current);
186 for (i = 0; i < this->num_neighbours; i++) {
188 this->
CheckTile(&this->neighbours[i], current);
214 printf(
"[AyStar] Memory free'd\n");
232 printf(
"[AyStar] Cleared AyStar\n");
283 printf(
"[AyStar] Starting A* Algorithm from node (%d, %d, %d)\n",
284 TileX(start_node->tile),
TileY(start_node->tile), start_node->direction);
BinaryHeap openlist_queue
The open queue.
@ AYSTAR_LIMIT_REACHED
The AyStar::max_search_nodes limit has been reached, aborting search.
Hash closedlist_hash
The actual closed list.
void Clear(bool free_values)
Clears the queue, by removing all values from it.
@ AYSTAR_EMPTY_OPENLIST
All items are tested, and no path has been found.
void Delete(bool free_values)
Deletes the hash and cleans up.
PathNode * ClosedListIsInList(const AyStarNode *node)
This looks in the hash whether a node exists in the closed list.
bool Delete(void *item, int priority)
Deletes the item from the queue.
static uint TileY(TileIndex tile)
Get the Y component of a tile.
int Main()
This is the function you call to run AyStar.
OpenListNode * OpenListPop()
Gets the best node from the open list.
static uint TileX(TileIndex tile)
Get the X component of a tile.
void Init(Hash_HashProc hash, uint num_buckets)
Initialize an AyStar.
@ AYSTAR_NO_PATH
No path to the goal was found.
void ClosedListAdd(const PathNode *node)
This adds a node to the closed list.
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.
uint GetSize() const
Gets the current size of the hash.
void Init(Hash_HashProc *hash, uint num_buckets)
Builds a new hash in an existing struct.
byte loops_per_tick
How many loops are there called before Main() gives control back to the caller. 0 = until done.
void * Set(uint key1, uint key2, void *value)
Sets the value associated with the given key pair to the given value.
void * DeleteValue(uint key1, uint key2)
Deletes the value with the specified key pair from the hash and returns that value.
@ 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.
void * Get(uint key1, uint key2) const
Gets the value associated with the given key pair, or nullptr when it is not present.
@ AYSTAR_FOUND_END_NODE
An end node was found.
int Loop()
This function is the core of AyStar.
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.
static const int AYSTAR_INVALID_NODE
Item is not valid (for example, not walkable).
void * Pop()
Pops the first element from the queue.
#define lengthof(x)
Return the length of an fixed size array.
uint max_path_cost
If the g-value goes over this number, it stops searching, 0 = infinite.
void Free(bool free_values)
Frees the queue, by reclaiming all memory allocated by it.
bool Push(void *item, int priority)
Pushes an element into the queue, at the appropriate place for the queue.
static void free(const void *ptr)
Version of the standard free that accepts const pointers.
void AddStartNode(AyStarNode *start_node, uint g)
Adds a node from where to start an algorithm.
void Init(uint max_size)
Initializes a binary heap and allocates internal memory for maximum of max_size elements.
void Clear(bool free_values)
Cleans the hash, but keeps the memory allocated.
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.