AyStar search algorithm struct. More...

#include <aystar.h>

Inheritance diagram for AyStar:

Protected Member Functions
virtual int32_t	CalculateG (const AyStarNode &current, const PathNode &parent) const =0
	Calculate the G-value for the AyStar algorithm.

virtual int32_t	CalculateH (const AyStarNode &current, const PathNode &parent) const =0
	Calculate the H-value for the AyStar algorithm.

virtual void	GetNeighbours (const PathNode &current, std::vector< AyStarNode > &neighours) const =0
	This function requests the tiles around the current tile.

virtual AyStarStatus	EndNodeCheck (const PathNode &current) const =0
	Check whether the end-tile is found.

virtual void	FoundEndNode (const PathNode &current)=0
	If the End Node is found, this function is called.

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.

Private Member Functions
AyStarStatus	Loop ()
	This function is the core of AyStar.

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

void	CheckTile (AyStarNode current, PathNode parent)
	Checks one tile and calculate its f-value.

Private Attributes
NodeList< PathNode, 8, 10 >	nodes

std::vector< AyStarNode >	neighbours

Detailed Description

AyStar search algorithm struct.

Definition at line 44 of file aystar.h.

Member Function Documentation

◆ AddStartNode()

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

protected

Adds a node from where to start an algorithm.

Multiple nodes can be added if wanted.

Parameters

start_node	Node to start with.
g	the cost for starting with this node.

Definition at line 161 of file aystar.cpp.

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

Referenced by RiverBuilder::Exec().

◆ CalculateG()

virtual int32_t AyStar::CalculateG	(	const AyStarNode &	current,
		const PathNode &	parent
	)		const

protectedpure virtual

Calculate the G-value for the AyStar algorithm.

Returns

G value of the node:

AYSTAR_INVALID_NODE : indicates an item is not valid (e.g.: unwalkable)
Any value >= 0 : the g-value for this tile

Implemented in RiverBuilder.

Referenced by CheckTile().

◆ CalculateH()

virtual int32_t AyStar::CalculateH	(	const AyStarNode &	current,
		const PathNode &	parent
	)		const

protectedpure virtual

Calculate the H-value for the AyStar algorithm.

Mostly, this must return the distance (Manhattan way) between the current point and the end point.

Returns: The h-value for this tile (any value >= 0)

Implemented in RiverBuilder.

Referenced by CheckTile().

◆ CheckTile()

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

private

Checks one tile and calculate its f-value.

Definition at line 38 of file aystar.cpp.

References AYSTAR_INVALID_NODE, CalculateG(), CalculateH(), 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(), OpenListAdd(), and NodeList< Titem, Thash_bits_open, Thash_bits_closed >::PopOpenNode().

Referenced by Loop().

◆ EndNodeCheck()

virtual AyStarStatus AyStar::EndNodeCheck ( const PathNode & current ) const

protectedpure virtual

Check whether the end-tile is found.

Parameters

current Node to exam.

Returns

Status of the node:

AyStarStatus::FoundEndNode : indicates this is the end tile
AyStarStatus::Done : indicates this is not the end tile (or direction was wrong)

Implemented in RiverBuilder.

Referenced by Loop().

◆ FoundEndNode()

virtual void AyStar::FoundEndNode ( const PathNode & current )

protectedpure virtual

If the End Node is found, this function is called.

It can do, for example, calculate the route and put that in an array.

Implemented in RiverBuilder.

◆ GetNeighbours()

virtual void AyStar::GetNeighbours	(	const PathNode &	current,
		std::vector< AyStarNode > &	neighours
	)		const

protectedpure virtual

This function requests the tiles around the current tile.

neighbours is never reset, so if you are not using directions, just leave it alone.

Implemented in RiverBuilder.

Referenced by Loop().

◆ Loop()

AyStarStatus AyStar::Loop ( )

private

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

References AYSTAR_DEF_MAX_SEARCH_NODES, CheckTile(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::ClosedCount(), EmptyOpenList, EndNodeCheck(), FoundEndNode, GetNeighbours(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::InsertClosedNode(), LimitReached, NodeList< Titem, Thash_bits_open, Thash_bits_closed >::PopBestOpenNode(), and StillBusy.

Referenced by Main().

◆ Main()

AyStarStatus AyStar::Main ( )

protected

This is the function you call to run AyStar.

Returns

Possible values:

Definition at line 132 of file aystar.cpp.

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

Referenced by RiverBuilder::Exec().

◆ OpenListAdd()

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

private

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

◆ neighbours

std::vector<AyStarNode> AyStar::neighbours

mutableprivate

Definition at line 91 of file aystar.h.

◆ nodes

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

private

Definition at line 90 of file aystar.h.

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

src/pathfinder/aystar.h
src/pathfinder/aystar.cpp

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Function Documentation

◆ AddStartNode()

◆ CalculateG()

◆ CalculateH()

◆ CheckTile()

◆ EndNodeCheck()

◆ FoundEndNode()

◆ GetNeighbours()

◆ Loop()

◆ Main()

◆ OpenListAdd()

Field Documentation

◆ neighbours

◆ nodes