16 #include "../../stdafx.h"
19 #include "../../safeguards.h"
29 new_node->Set(parent, node->tile, node->td,
true);
30 new_node->estimate = f;
44 int new_g = this->CalculateG(
this, current, parent);
51 new_g += parent->cost;
55 int new_h = this->CalculateH(
this, current, parent);
60 int new_f = new_g + new_h;
67 if (check !=
nullptr) {
69 if (new_g > check->cost)
return;
72 check->estimate = new_f;
74 check->parent = closedlist_parent;
79 this->
OpenListAdd(closedlist_parent, current, new_f, new_g);
101 if (this->FoundEndNode !=
nullptr) {
102 this->FoundEndNode(
this, current);
111 this->GetNeighbours(
this, current);
114 for (
auto &neighbour : this->neighbours) {
171 Debug(misc, 0,
"[AyStar] Starting A* Algorithm from node ({}, {}, {})\n",
172 TileX(start_node->tile),
TileY(start_node->tile), start_node->direction);
This file has the header for AyStar.
static const int AYSTAR_INVALID_NODE
Item is not valid (for example, not walkable).
@ AYSTAR_LIMIT_REACHED
The AyStar::max_search_nodes limit has been reached, aborting search.
@ AYSTAR_FOUND_END_NODE
An end node was found.
@ AYSTAR_NO_PATH
No path to the goal was found.
@ AYSTAR_STILL_BUSY
Some checking was done, but no path found yet, and there are still items left to try.
@ AYSTAR_EMPTY_OPENLIST
All items are tested, and no path has been found.
Titem_ & PopOpenNode(const Key &key)
remove and return the open node specified by a key
void InsertOpenNode(Titem_ &item)
insert given item as open node (into m_open and m_open_queue)
Titem_ * PopBestOpenNode()
remove and return the best open node
Titem_ * FindOpenNode(const Key &key)
return the open node specified by a key or nullptr if not found
void InsertClosedNode(Titem_ &item)
close node
Titem_ * FindClosedNode(const Key &key)
return the closed node specified by a key or nullptr if not found
int ClosedCount()
return number of closed nodes
Titem_ * CreateNewNode()
allocate new data item from items
#define Debug(category, level, format_string,...)
Ouptut a line of debugging information.
static debug_inline uint TileY(TileIndex tile)
Get the Y component of a tile.
static debug_inline uint TileX(TileIndex tile)
Get the X component of a tile.
int max_search_nodes
The maximum number of nodes that will be expanded, 0 = infinite.
void OpenListAdd(PathNode *parent, const AyStarNode *node, int f, int g)
Adds a node to the open list.
int Loop()
This function is the core of AyStar.
int max_path_cost
If the g-value goes over this number, it stops searching, 0 = infinite.
void CheckTile(AyStarNode *current, PathNode *parent)
Checks one tile and calculate its f-value.
void AddStartNode(AyStarNode *start_node, int g)
Adds a node from where to start an algorithm.
int Main()
This is the function you call to run AyStar.
uint8_t loops_per_tick
How many loops are there called before Main() gives control back to the caller. 0 = until done.