OpenTTD Source 20241224-master-gee860a5c8e
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 AddStartNode (AyStarNode *start_node, int g)
 Adds a node from where to start an algorithm.
 
AyStarStatus Main ()
 This is the function you call to run AyStar.
 
AyStarStatus Loop ()
 This function is the core of AyStar.
 
void CheckTile (AyStarNode *current, PathNode *parent)
 Checks one tile and calculate its f-value.
 

Data Fields

AyStar_CalculateG * CalculateG
 
AyStar_CalculateH * CalculateH
 
AyStar_GetNeighbours * GetNeighbours
 
AyStar_EndNodeCheck * EndNodeCheck
 
AyStar_FoundEndNode * FoundEndNode
 
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< AyStarNode > neighbours
 

Protected Member Functions

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

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

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

Referenced by BuildRiver().

◆ CheckTile()

void AyStar::CheckTile ( AyStarNode *  current,
PathNode *  parent 
)

Checks one tile and calculate its f-value.

Definition at line 38 of file aystar.cpp.

References AYSTAR_INVALID_NODE, NodeList< Titem, Thash_bits_open, Thash_bits_closed >::FindClosedNode(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::FindOpenNode(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::InsertOpenNode(), max_path_cost, OpenListAdd(), and NodeList< Titem, Thash_bits_open, Thash_bits_closed >::PopOpenNode().

Referenced by Loop().

◆ Loop()

AyStarStatus 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 CheckTile(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::ClosedCount(), EmptyOpenList, FoundEndNode, NodeList< Titem, Thash_bits_open, Thash_bits_closed >::InsertClosedNode(), LimitReached, max_search_nodes, NodeList< Titem, Thash_bits_open, Thash_bits_closed >::PopBestOpenNode(), and StillBusy.

Referenced by Main().

◆ Main()

AyStarStatus 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 AyStarStatus::StillBusy) #Clear() is called automatically. When you stop the algorithm halfway, you should call #Clear() yourself!

Definition at line 137 of file aystar.cpp.

References Debug, EmptyOpenList, FoundEndNode, LimitReached, Loop(), loops_per_tick, NoPath, and StillBusy.

Referenced by BuildRiver().

◆ 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().

Field Documentation

◆ CalculateG

AyStar_CalculateG* AyStar::CalculateG

Definition at line 109 of file aystar.h.

◆ CalculateH

AyStar_CalculateH* AyStar::CalculateH

Definition at line 110 of file aystar.h.

◆ EndNodeCheck

AyStar_EndNodeCheck* AyStar::EndNodeCheck

Definition at line 112 of file aystar.h.

◆ FoundEndNode

AyStar_FoundEndNode* AyStar::FoundEndNode

Definition at line 113 of file aystar.h.

◆ GetNeighbours

AyStar_GetNeighbours* AyStar::GetNeighbours

Definition at line 111 of file aystar.h.

◆ loops_per_tick

uint8_t AyStar::loops_per_tick

How many loops are there called before Main() gives control back to the caller. 0 = until done.

Definition at line 124 of file aystar.h.

Referenced by Main().

◆ max_path_cost

int AyStar::max_path_cost

If the g-value goes over this number, it stops searching, 0 = infinite.

Definition at line 125 of file aystar.h.

Referenced by CheckTile().

◆ max_search_nodes

int AyStar::max_search_nodes = AYSTAR_DEF_MAX_SEARCH_NODES

The maximum number of nodes that will be expanded, 0 = infinite.

Definition at line 126 of file aystar.h.

Referenced by Loop().

◆ neighbours

std::vector<AyStarNode> AyStar::neighbours

Definition at line 129 of file aystar.h.

◆ nodes

NodeList<PathNode, 8, 10> AyStar::nodes
protected

Definition at line 139 of file aystar.h.

◆ user_data

void* AyStar::user_data

Definition at line 122 of file aystar.h.

◆ user_target

void* AyStar::user_target

Definition at line 121 of file aystar.h.

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