_________ __                 __
        /   _____//  |_____________ _/  |______     ____  __ __  ______
        \_____  \\   __\_  __ \__  \\   __\__  \   / ___\|  |  \/  ___/
        /        \|  |  |  | \// __ \|  |  / __ \_/ /_/  >  |  /\___ \
       /_______  /|__|  |__|  (____  /__| (____  /\___  /|____//____  >
               \/                  \/          \//_____/            \/
    ______________________                           ______________________
                          T H E   W A R   B E G I N S
                   Stratagus - A free fantasy real time strategy game engine

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Classes
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 NodeAStarMatrix
 cost matrix More...
 
static int * CloseSet
 a list of close nodes, helps to speed up the matrix cleaning More...
 
static int CloseSetSize
 
static int Threshold
 
static int OpenSetMaxSize
 
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...
 
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 int AStarMapWidth
 
static int AStarMapHeight
 
static int AStarGoalX
 
static int AStarGoalY
 
static OpenOpenSet
 The set of Open nodes. More...
 
static int OpenSetSize
 The size of the open node set. More...
 
static int * CostMoveToCache
 
static const int CacheNotSet = -5
 
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 AStarCleanUp ()
 
static void CostMoveToCacheCleanUp ()
 
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 void AStarAddToClose (int node)
 
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...
 
StatsNodeAStarGetStats ()
 
void AStarFreeStats (StatsNode *stats)
 
void SetAStarFixedUnitCrossingCost (int cost)
 
int GetAStarFixedUnitCrossingCost ()
 
void SetAStarMovingUnitCrossingCost (int cost)
 
int GetAStarMovingUnitCrossingCost ()
 
void SetAStarUnknownTerrainCost (int cost)
 
int GetAStarUnknownTerrainCost ()
 

Macro Definition Documentation

#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

#define GetIndex (   x,
 
)    (x) + (y) * AStarMapWidth
#define MAX_CLOSE_SET_RATIO   4
#define MAX_OPEN_SET_RATIO   8
#define ProfileBegin (   f)
#define ProfileEnd (   f)
#define ProfileInit ( )
#define ProfilePrint ( )

Function Documentation

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
static void AStarAddToClose ( int  node)
static

Add a node to the closed set

static void AStarCleanUp ( )
static

Clean up A*

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

heuristic cost function for a*

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.
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.

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

void AStarFreeStats ( StatsNode stats)
StatsNode* AStarGetStats ( )
static int AStarMarkGoal ( const Vec2i goal,
int  gw,
int  gh,
int  tilesizex,
int  tilesizey,
int  minrange,
int  maxrange,
const CUnit unit 
)
static

MarkAStarGoal

static void AStarPrepare ( )
static

Prepare pathfinder.

static void AStarRemoveMinimum ( int  pos)
static

Remove the minimum from the open node set

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.

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

Save the path

Returns
The length of the path
static int CostMoveTo ( unsigned int  index,
const CUnit unit 
)
inlinestatic

Compute the cost of crossing tile (x,y)

Parameters
xX tile where to move.
yY tile where to move.
datauser data.
Returns
-1 -> impossible to cross. 0 -> no induced cost, except move >0 -> costly tile
static void CostMoveToCacheCleanUp ( )
static
static int CostMoveToCallBack_Default ( unsigned int  index,
const CUnit unit 
)
static
void FreeAStar ( )

free the a* data structures

Free A* data structure

int GetAStarFixedUnitCrossingCost ( )
int GetAStarMovingUnitCrossingCost ( )
int GetAStarUnknownTerrainCost ( )
void InitAStar ( int  mapWidth,
int  mapHeight 
)

Init the a* data structures.

Init A* data structures

int32_t MyAbs ( int32_t  x)
inline
void SetAStarFixedUnitCrossingCost ( int  cost)
void SetAStarMovingUnitCrossingCost ( int  cost)
void SetAStarUnknownTerrainCost ( int  cost)

Variable Documentation

int AStarFixedUnitCrossingCost

see pathfinder.h

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

int AStarGoalX
static
int AStarGoalY
static
bool AStarKnowUnseenTerrain = false

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

int AStarMapHeight
static
int AStarMapWidth
static
Node* AStarMatrix
static

cost matrix

int AStarMatrixSize
static
int AStarMovingUnitCrossingCost = 5

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

int AStarUnknownTerrainCost = 2

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

const int CacheNotSet = -5
static
int* CloseSet
static

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

int CloseSetSize
static
int* CostMoveToCache
static
int Heading2O[9]
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 }
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.

int OpenSetMaxSize
static
int OpenSetSize
static

The size of the open node set.

int Threshold
static
const int XY2Heading[3][3] = { {7, 6, 5}, {0, 0, 4}, {1, 2, 3}}
(C) Copyright 1998-2012 by The Stratagus Project under the GNU General Public License.
All trademarks and copyrights on this page are owned by their respective owners.