aystar.h File Reference

This file has the header for AyStar. More...

#include "../track_func.h"
#include "../misc/hashtable.hpp"
#include "../misc/binaryheap.hpp"
#include "../misc/dbg_helpers.h"
#include "yapf/nodelist.hpp"
#include "yapf/yapf_node.hpp"

Go to the source code of this file.

Data Structures
struct	PathNode
struct	AyStar
	AyStar search algorithm struct. More...

Typedefs
using	AyStarNode = CYapfNodeKeyTrackDir
typedef AyStarStatus	AyStar_EndNodeCheck(const AyStar *aystar, const PathNode *current)
	Check whether the end-tile is found.
typedef int32_t	AyStar_CalculateG(AyStar *aystar, AyStarNode *current, PathNode *parent)
	Calculate the G-value for the AyStar algorithm.
typedef int32_t	AyStar_CalculateH(AyStar *aystar, AyStarNode *current, PathNode *parent)
	Calculate the H-value for the AyStar algorithm.
typedef void	AyStar_GetNeighbours(AyStar *aystar, PathNode *current)
	This function requests the tiles around the current tile and put them in #neighbours.
typedef void	AyStar_FoundEndNode(AyStar *aystar, PathNode *current)
	If the End Node is found, this function is called.

Enumerations
enum class	AyStarStatus : uint8_t {   FoundEndNode , EmptyOpenList , StillBusy , NoPath ,   LimitReached , Done }
	Return status of AyStar methods. More...

Functions
bool	CheckIgnoreFirstTile (const PathNode *node)

Variables
static const int	AYSTAR_DEF_MAX_SEARCH_NODES = 10000
	Reference limit for AyStar::max_search_nodes.
static const int	AYSTAR_INVALID_NODE = -1
	Item is not valid (for example, not walkable).

Detailed Description

This file has the header for AyStar.

AyStar is a fast path finding routine and is used for things like AI path finding and Train path finding. For more information about AyStar (A* Algorithm), you can look at http://en.wikipedia.org/wiki/A-star_search_algorithm.

Definition in file aystar.h.

Typedef Documentation

AyStar_CalculateG

typedef int32_t AyStar_CalculateG(AyStar *aystar, AyStarNode *current, PathNode *parent)

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

Definition at line 73 of file aystar.h.

AyStar_CalculateH

typedef int32_t AyStar_CalculateH(AyStar *aystar, AyStarNode *current, PathNode *parent)

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)

Definition at line 80 of file aystar.h.

AyStar_EndNodeCheck

typedef AyStarStatus AyStar_EndNodeCheck(const AyStar *aystar, const PathNode *current)

Check whether the end-tile is found.

Parameters

aystar	AyStar search algorithm data.
current	Node to exam one.

Note

The 2nd parameter should be #OpenListNode, and not AyStarNode. AyStarNode is part of #OpenListNode and so it could be accessed without any problems. The good part about #OpenListNode is, and how AIs use it, that you can access the parent of the current node, and so check if you, for example don't try to enter the file tile with a 90-degree curve. So please, leave this an #OpenListNode, it works just fine.

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)

Definition at line 65 of file aystar.h.

AyStar_FoundEndNode

typedef void AyStar_FoundEndNode(AyStar *aystar, PathNode *current)

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

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

Definition at line 93 of file aystar.h.

AyStar_GetNeighbours

typedef void AyStar_GetNeighbours(AyStar *aystar, PathNode *current)

This function requests the tiles around the current tile and put them in #neighbours.

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

Warning

Never add more #neighbours than memory allocated for it.

Definition at line 87 of file aystar.h.

AyStarNode

using AyStarNode = CYapfNodeKeyTrackDir

Definition at line 42 of file aystar.h.

Enumeration Type Documentation

AyStarStatus

enum class AyStarStatus : uint8_t

strong

Return status of AyStar methods.

Enumerator
FoundEndNode	An end node was found.
EmptyOpenList	All items are tested, and no path has been found.
StillBusy	Some checking was done, but no path found yet, and there are still items left to try.
NoPath	No path to the goal was found.
LimitReached	The AyStar::max_search_nodes limit has been reached, aborting search.
Done	Not an end-tile, or wrong direction.

Definition at line 31 of file aystar.h.

Variable Documentation

AYSTAR_DEF_MAX_SEARCH_NODES

const int AYSTAR_DEF_MAX_SEARCH_NODES = 10000

static

Reference limit for AyStar::max_search_nodes.

Definition at line 28 of file aystar.h.

AYSTAR_INVALID_NODE

const int AYSTAR_INVALID_NODE = -1

static

Item is not valid (for example, not walkable).

Definition at line 40 of file aystar.h.

Referenced by AyStar::CheckTile().