astar.cpp File Reference

#include "stratagus.h"
#include "map.h"
#include "settings.h"
#include "tileset.h"
#include "unit.h"
#include "unit_find.h"
#include "pathfinder.h"
#include <stdio.h>

Classes
struct	Node
struct	Open
class	AStarGoalMarker
class	MinMaxRangeVisitor< T >
struct	StatsNode

astar.cpp - The a* path finder routines.
#define	MAX_CLOSE_SET_RATIO   4
#define	MAX_OPEN_SET_RATIO   8
#define	ProfileInit()
#define	ProfileBegin(f)
#define	ProfileEnd(f)
#define	ProfilePrint()
#define	AStarFindMinimum()   (OpenSetSize - 1)
#define	GetIndex(x, y)   (x) + (y) * AStarMapWidth
const int	Heading2X [9] = { 0, +1, +1, +1, 0, -1, -1, -1, 0 }
const int	Heading2Y [9] = { -1, -1, 0, +1, +1, +1, 0, -1, 0 }
int	Heading2O [9]
const int	XY2Heading [3][3] = { {7, 6, 5}, {0, 0, 4}, {1, 2, 3}}
static Node *	AStarMatrix
	cost matrix More...
static int	OpenSetMaxSize
	a list of close nodes, helps to speed up the matrix cleaning More...
static int	AStarMatrixSize
int	AStarFixedUnitCrossingCost
	see pathfinder.h More...
int	AStarMovingUnitCrossingCost = 5
	cost associated to move on a tile occupied by a moving unit More...
int	AStarMaxSearchIterations = INT_MAX
	Maximum number of iterations of A* before giving up. More...
bool	AStarKnowUnseenTerrain = false
	Whether to have knowledge of terrain that we haven't visited yet. More...
int	AStarUnknownTerrainCost = 2
	Cost of using a square we haven't seen before. More...
static bool	AStarFixedEnemyUnitsUnpassable = false
	Used to temporary make enemy units unpassable (needs for correct path lenght calculating for automatic targeting alorithm) More...
static int	AStarMapWidth
static int	AStarMapHeight
static int	AStarMapMax
static int	AStarGoalX
static int	AStarGoalY
static Open *	OpenSet
	The set of Open nodes. More...
static int	OpenSetSize
	The size of the open node set. More...
static int32_t *	CostMoveToCache
static int	CostMoveToCacheSize
static constexpr int	CacheNotSet = -1
int32_t	MyAbs (int32_t x)
static int	AStarCosts (const Vec2i &pos, const Vec2i &goalPos)
	heuristic cost function for a* More...
void	InitAStar (int mapWidth, int mapHeight)
	Init the a* data structures. More...
void	FreeAStar ()
	free the a* data structures More...
static void	AStarPrepare ()
static void	CostMoveToCacheCleanUp ()
static void	AStarCleanUp ()
static void	AStarRemoveMinimum (int pos)
static int	AStarAddNode (const Vec2i &pos, int o, int costs)
static void	AStarReplaceNode (int pos)
static int	AStarFindNode (int eo)
static int	CostMoveToCallBack_Default (unsigned int index, const CUnit &unit)
static int	CostMoveTo (unsigned int index, const CUnit &unit)
static int	AStarMarkGoal (const Vec2i &goal, int gw, int gh, int tilesizex, int tilesizey, int minrange, int maxrange, const CUnit &unit)
static int	AStarSavePath (const Vec2i &startPos, const Vec2i &endPos, char *path, int pathLen)
static int	AStarFindSimplePath (const Vec2i &startPos, const Vec2i &goal, int gw, int gh, int, int, int minrange, int maxrange, char *path, const CUnit &unit)
int	AStarFindPath (const Vec2i &startPos, const Vec2i &goalPos, int gw, int gh, int tilesizex, int tilesizey, int minrange, int maxrange, char *path, int pathlen, const CUnit &unit)
	Find and a* path for a unit. More...
StatsNode *	AStarGetStats ()
void	AStarFreeStats (StatsNode *stats)
void	SetAStarFixedUnitCrossingCost (int cost)
int	GetAStarFixedUnitCrossingCost ()
void	SetAStarMovingUnitCrossingCost (int cost)
int	GetAStarMovingUnitCrossingCost ()
void	SetAStarUnknownTerrainCost (int cost)
int	GetAStarUnknownTerrainCost ()
void	SetAStarFixedEnemyUnitsUnpassable (const bool value)
bool	GetAStarFixedEnemyUnitsUnpassable ()

Macro Definition Documentation

AStarFindMinimum

#define AStarFindMinimum

(

)

(OpenSetSize - 1)

Find the best node in the current open node set Returns the position of this node in the open node set

GetIndex

#define GetIndex	(		x,
			y
	)		(x) + (y) * AStarMapWidth

MAX_CLOSE_SET_RATIO

#define MAX_CLOSE_SET_RATIO   4

MAX_OPEN_SET_RATIO

#define MAX_OPEN_SET_RATIO   8

ProfileBegin

#define ProfileBegin

(

f

)

ProfileEnd

#define ProfileEnd

(

f

)

ProfileInit

#define ProfileInit

(

)

ProfilePrint

#define ProfilePrint

(

)

Function Documentation

AStarAddNode()

static int AStarAddNode ( const Vec2i &  pos, int  o, int  costs  )

inlinestatic

Add a new node to the open set (and update the heap structure)

Returns

0 or PF_FAILED

AStarCleanUp()

static void AStarCleanUp ( )

static

AStarCosts()

static int AStarCosts ( const Vec2i &  pos, const Vec2i &  goalPos  )

inlinestatic

heuristic cost function for a*

AStarFindNode()

static int AStarFindNode ( int  eo )

static

Check if a node is already in the open set.

Returns

-1 if not found and the position of the node in the table if found.

AStarFindPath()

int AStarFindPath	(	const Vec2i &	startPos,
		const Vec2i &	goalPos,
		int	gw,
		int	gh,
		int	tilesizex,
		int	tilesizey,
		int	minrange,
		int	maxrange,
		char *	path,
		int	pathlen,
		const CUnit &	unit
	)

Find and a* path for a unit.

Find path.

AStarFindSimplePath()

static int AStarFindSimplePath ( const Vec2i &  startPos, const Vec2i &  goal, int  gw, int  gh, int  , int  , int  minrange, int  maxrange, char *  path, const CUnit &  unit  )

static

Optimization to find a simple path Check if we're at the goal or if it's 1 tile away

AStarFreeStats()

void AStarFreeStats

(

StatsNode *

stats

)

AStarGetStats()

StatsNode* AStarGetStats

(

)

AStarMarkGoal()

static int AStarMarkGoal ( const Vec2i &  goal, int  gw, int  gh, int  tilesizex, int  tilesizey, int  minrange, int  maxrange, const CUnit &  unit  )

static

MarkAStarGoal

AStarPrepare()

static void AStarPrepare ( )

static

Prepare pathfinder.

AStarRemoveMinimum()

static void AStarRemoveMinimum ( int  pos )

static

Remove the minimum from the open node set

AStarReplaceNode()

static void AStarReplaceNode ( int  pos )

static

Change the cost associated to an open node. Can be further optimised knowing that the new cost MUST BE LOWER than the old one.

AStarSavePath()

static int AStarSavePath ( const Vec2i &  startPos, const Vec2i &  endPos, char *  path, int  pathLen  )

static

Save the path

Returns

The length of the path

CostMoveTo()

static int CostMoveTo ( unsigned int  index, const CUnit &  unit  )

inlinestatic

Compute the cost of crossing tile (x,y)

Parameters

x	X tile where to move.
y	Y tile where to move.
data	user data.

Returns

-1 -> impossible to cross. 0 -> no induced cost, except move >0 -> costly tile

CostMoveToCacheCleanUp()

static void CostMoveToCacheCleanUp ( )

static

Clean up A*

CostMoveToCallBack_Default()

static int CostMoveToCallBack_Default ( unsigned int  index, const CUnit &  unit  )

static

FreeAStar()

void FreeAStar

(

)

free the a* data structures

Free A* data structure

GetAStarFixedEnemyUnitsUnpassable()

bool GetAStarFixedEnemyUnitsUnpassable

(

)

GetAStarFixedUnitCrossingCost()

int GetAStarFixedUnitCrossingCost

(

)

GetAStarMovingUnitCrossingCost()

int GetAStarMovingUnitCrossingCost

(

)

GetAStarUnknownTerrainCost()

int GetAStarUnknownTerrainCost

(

)

InitAStar()

void InitAStar	(	int	mapWidth,
		int	mapHeight
	)

Init the a* data structures.

Init A* data structures

MyAbs()

int32_t MyAbs ( int32_t  x )

inline

SetAStarFixedEnemyUnitsUnpassable()

void SetAStarFixedEnemyUnitsUnpassable

(

const bool

value

)

SetAStarFixedUnitCrossingCost()

void SetAStarFixedUnitCrossingCost

(

int

cost

)

SetAStarMovingUnitCrossingCost()

void SetAStarMovingUnitCrossingCost

(

int

cost

)

SetAStarUnknownTerrainCost()

void SetAStarUnknownTerrainCost

(

int

cost

)

Variable Documentation

AStarFixedEnemyUnitsUnpassable

bool AStarFixedEnemyUnitsUnpassable = false

static

Used to temporary make enemy units unpassable (needs for correct path lenght calculating for automatic targeting alorithm)

AStarFixedUnitCrossingCost

int AStarFixedUnitCrossingCost

see pathfinder.h

cost associated to move on a tile occupied by a fixed unit

AStarGoalX

int AStarGoalX

static

AStarGoalY

int AStarGoalY

static

AStarKnowUnseenTerrain

bool AStarKnowUnseenTerrain = false

Whether to have knowledge of terrain that we haven't visited yet.

AStarMapHeight

int AStarMapHeight

static

AStarMapMax

int AStarMapMax

static

AStarMapWidth

int AStarMapWidth

static

AStarMatrix

Node* AStarMatrix

static

cost matrix

AStarMatrixSize

int AStarMatrixSize

static

AStarMaxSearchIterations

int AStarMaxSearchIterations = INT_MAX

Maximum number of iterations of A* before giving up.

AStarMovingUnitCrossingCost

int AStarMovingUnitCrossingCost = 5

cost associated to move on a tile occupied by a moving unit

AStarUnknownTerrainCost

int AStarUnknownTerrainCost = 2

Cost of using a square we haven't seen before.

CacheNotSet

constexpr int CacheNotSet = -1

staticconstexpr

CostMoveToCache

int32_t* CostMoveToCache

static

CostMoveToCacheSize

int CostMoveToCacheSize

static

Heading2O

int Heading2O[9]

Heading2X

const int Heading2X[9] = { 0, +1, +1, +1, 0, -1, -1, -1, 0 }

Heading2Y

const int Heading2Y[9] = { -1, -1, 0, +1, +1, +1, 0, -1, 0 }

OpenSet

Open* OpenSet

static

The set of Open nodes.

The Open set is handled by a stored array the end of the array holds the item with the smallest cost.

OpenSetMaxSize

int OpenSetMaxSize

static

a list of close nodes, helps to speed up the matrix cleaning

OpenSetSize

int OpenSetSize

static

The size of the open node set.

XY2Heading

const int XY2Heading[3][3] = { {7, 6, 5}, {0, 0, 4}, {1, 2, 3}}