OpenTTD Source  20241121-master-g67a0fccfad
AyStar Struct Reference

AyStar search algorithm struct. More...

#include <aystar.h>

Public Member Functions

void AddStartNode (AyStarNode *start_node, int g)
 Adds a node from where to start an algorithm. More...
 
int Main ()
 This is the function you call to run AyStar. More...
 
int Loop ()
 This function is the core of AyStar. More...
 
void CheckTile (AyStarNode *current, PathNode *parent)
 Checks one tile and calculate its f-value.
 

Data Fields

AyStar_CalculateGCalculateG
 
AyStar_CalculateHCalculateH
 
AyStar_GetNeighboursGetNeighbours
 
AyStar_EndNodeCheckEndNodeCheck
 
AyStar_FoundEndNodeFoundEndNode
 
void * user_target
 
void * user_data
 
uint8_t loops_per_tick
 How many loops are there called before Main() gives control back to the caller. 0 = until done.
 
int max_path_cost
 If the g-value goes over this number, it stops searching, 0 = infinite.
 
int max_search_nodes = AYSTAR_DEF_MAX_SEARCH_NODES
 The maximum number of nodes that will be expanded, 0 = infinite.
 
std::vector< AyStarNodeneighbours
 

Protected Member Functions

void OpenListAdd (PathNode *parent, const AyStarNode *node, int f, int g)
 Adds a node to the open list. More...
 

Protected Attributes

NodeList< PathNode, 8, 10 > nodes
 

Detailed Description

AyStar search algorithm struct.

Before calling #Init(), fill #CalculateG, #CalculateH, #GetNeighbours, #EndNodeCheck, and #FoundEndNode. If you want to change them after calling #Init(), first call #Free() !

The #user_path, #user_target, and #user_data[10] are intended to be used by the user routines. The data not accessed by the AyStar code itself. The user routines can change any moment they like.

Definition at line 103 of file aystar.h.

Member Function Documentation

◆ AddStartNode()

void AyStar::AddStartNode ( AyStarNode start_node,
int  g 
)

Adds a node from where to start an algorithm.

Multiple nodes can be added if wanted. You should make sure that #Clear() is called before adding nodes if the AyStar has been used before (though the normal main loop calls #Clear() automatically when the algorithm finishes.

Parameters
start_nodeNode to start with.
gthe cost for starting with this node.

Definition at line 168 of file aystar.cpp.

References Debug, OpenListAdd(), TileX(), and TileY().

◆ Loop()

int AyStar::Loop ( )

This function is the core of AyStar.

It handles one item and checks its neighbour items. If they are valid, they are added to be checked too.

Returns
Possible values:

Definition at line 92 of file aystar.cpp.

References AYSTAR_EMPTY_OPENLIST, AYSTAR_FOUND_END_NODE, AYSTAR_LIMIT_REACHED, AYSTAR_STILL_BUSY, CheckTile(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::ClosedCount(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::InsertClosedNode(), max_search_nodes, and NodeList< Titem, Thash_bits_open, Thash_bits_closed >::PopBestOpenNode().

Referenced by Main().

◆ Main()

int AyStar::Main ( )

This is the function you call to run AyStar.

Returns
Possible values:
Note
When the algorithm is done (when the return value is not AYSTAR_STILL_BUSY) #Clear() is called automatically. When you stop the algorithm halfway, you should call #Clear() yourself!

Definition at line 137 of file aystar.cpp.

References AYSTAR_EMPTY_OPENLIST, AYSTAR_FOUND_END_NODE, AYSTAR_LIMIT_REACHED, AYSTAR_NO_PATH, AYSTAR_STILL_BUSY, Debug, Loop(), and loops_per_tick.

◆ OpenListAdd()

void AyStar::OpenListAdd ( PathNode parent,
const AyStarNode node,
int  f,
int  g 
)
protected

Adds a node to the open list.

It makes a copy of node, and puts the pointer of parent in the struct.

Definition at line 25 of file aystar.cpp.

References NodeList< Titem, Thash_bits_open, Thash_bits_closed >::CreateNewNode(), and NodeList< Titem, Thash_bits_open, Thash_bits_closed >::InsertOpenNode().

Referenced by AddStartNode(), and CheckTile().


The documentation for this struct was generated from the following files: