OpenTTD
Public Member Functions | Data Fields | Protected Member Functions | Protected Attributes
AyStar Struct Reference

AyStar search algorithm struct. More...

#include <aystar.h>

Public Member Functions

void Init (Hash_HashProc hash, uint num_buckets)
 Initialize an AyStar. More...
 
void AddStartNode (AyStarNode *start_node, uint 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 Free ()
 This function frees the memory it allocated.
 
void Clear ()
 This function make the memory go back to zero. More...
 
void CheckTile (AyStarNode *current, OpenListNode *parent)
 Checks one tile and calculate its f-value.
 

Data Fields

AyStar_CalculateGCalculateG
 
AyStar_CalculateHCalculateH
 
AyStar_GetNeighboursGetNeighbours
 
AyStar_EndNodeCheckEndNodeCheck
 
AyStar_FoundEndNodeFoundEndNode
 
void * user_path
 
void * user_target
 
void * user_data
 
byte loops_per_tick
 How many loops are there called before Main() gives control back to the caller. 0 = until done.
 
uint max_path_cost
 If the g-value goes over this number, it stops searching, 0 = infinite.
 
uint max_search_nodes
 The maximum number of nodes that will be expanded, 0 = infinite.
 
AyStarNode neighbours [12]
 
byte num_neighbours
 

Protected Member Functions

void OpenListAdd (PathNode *parent, const AyStarNode *node, int f, int g)
 Adds a node to the open list. More...
 
OpenListNodeOpenListIsInList (const AyStarNode *node)
 Check whether a node is in the open list. More...
 
OpenListNodeOpenListPop ()
 Gets the best node from the open list. More...
 
void ClosedListAdd (const PathNode *node)
 This adds a node to the closed list. More...
 
PathNodeClosedListIsInList (const AyStarNode *node)
 This looks in the hash whether a node exists in the closed list. More...
 

Protected Attributes

Hash closedlist_hash
 The actual closed list.
 
BinaryHeap openlist_queue
 The open queue.
 
Hash openlist_hash
 An extra hash to speed up the process of looking up an element in the open list.
 

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 116 of file aystar.h.

Member Function Documentation

◆ AddStartNode()

void AyStar::AddStartNode ( AyStarNode start_node,
uint  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 282 of file aystar.cpp.

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

◆ Clear()

void AyStar::Clear ( )

This function make the memory go back to zero.

This function should be called when you are using the same instance again.

Definition at line 224 of file aystar.cpp.

References BinaryHeap::Clear(), Hash::Clear(), closedlist_hash, openlist_hash, and openlist_queue.

Referenced by Main().

◆ ClosedListAdd()

void AyStar::ClosedListAdd ( const PathNode node)
protected

This adds a node to the closed list.

It makes a copy of the data.

Parameters
nodeNode to add to the closed list.

Definition at line 47 of file aystar.cpp.

References closedlist_hash, and Hash::Set().

Referenced by Loop().

◆ ClosedListIsInList()

PathNode * AyStar::ClosedListIsInList ( const AyStarNode node)
protected

This looks in the hash whether a node exists in the closed list.

Parameters
nodeNode to search.
Returns
The PathNode if it is available, else NULL

Definition at line 37 of file aystar.cpp.

References closedlist_hash, and Hash::Get().

Referenced by CheckTile().

◆ Init()

void AyStar::Init ( Hash_HashProc  hash,
uint  num_buckets 
)

Initialize an AyStar.

You should fill all appropriate fields before calling Init (see the declaration of AyStar for which fields are internal).

Definition at line 295 of file aystar.cpp.

References closedlist_hash, BinaryHeap::Init(), Hash::Init(), openlist_hash, and openlist_queue.

◆ Loop()

int AyStar::Loop ( )

This function is the core of AyStar.

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

Returns
Possible values:

Definition at line 163 of file aystar.cpp.

References AYSTAR_EMPTY_OPENLIST, AYSTAR_FOUND_END_NODE, AYSTAR_LIMIT_REACHED, AYSTAR_STILL_BUSY, CheckTile(), closedlist_hash, ClosedListAdd(), free(), Hash::GetSize(), max_search_nodes, and OpenListPop().

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 247 of file aystar.cpp.

References AYSTAR_EMPTY_OPENLIST, AYSTAR_FOUND_END_NODE, AYSTAR_LIMIT_REACHED, AYSTAR_NO_PATH, AYSTAR_STILL_BUSY, Clear(), 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 85 of file aystar.cpp.

References openlist_hash, openlist_queue, PathNode::parent, BinaryHeap::Push(), and Hash::Set().

Referenced by AddStartNode().

◆ OpenListIsInList()

OpenListNode * AyStar::OpenListIsInList ( const AyStarNode node)
protected

Check whether a node is in the open list.

Parameters
nodeNode to search.
Returns
If the node is available, it is returned, else NULL is returned.

Definition at line 60 of file aystar.cpp.

References Hash::Get(), and openlist_hash.

◆ OpenListPop()

OpenListNode * AyStar::OpenListPop ( )
protected

Gets the best node from the open list.

It deletes the returned node from the open list.

Returns
the best node available, or NULL of none is found.

Definition at line 70 of file aystar.cpp.

References Hash::DeleteValue(), openlist_hash, openlist_queue, and BinaryHeap::Pop().

Referenced by Loop().


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