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

src/pathfinder/astar.cpp File Reference

#include "stratagus.h"
#include "map.h"
#include "unit.h"
#include "unit_find.h"
#include "pathfinder.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
static int * CloseSet
 a list of close nodes, helps to speed up the matrix cleaning
static int CloseSetSize
static int Threshold
static int OpenSetMaxSize
static int AStarMatrixSize
int AStarFixedUnitCrossingCost
 see pathfinder.h
int AStarMovingUnitCrossingCost = 5
 cost associated to move on a tile occupied by a moving unit
bool AStarKnowUnseenTerrain = false
 Whether to have knowledge of terrain that we haven't visited yet.
int AStarUnknownTerrainCost = 2
 Cost of using a square we haven't seen before.
static int AStarMapWidth
static int AStarMapHeight
static int AStarGoalX
static int AStarGoalY
static OpenOpenSet
 The set of Open nodes.
static int OpenSetSize
 The size of the open node set.
static int * CostMoveToCache
static const int CacheNotSet = -5
int MyAbs (int x)
static int AStarCosts (const Vec2i &pos, const Vec2i &goalPos)
 heuristic cost function for a*
void InitAStar (int mapWidth, int mapHeight)
 Init the a* data structures.
void FreeAStar ()
 free the a* data structures
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, int)
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, int, 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)
StatsNodeAStarGetStats ()
void AStarFreeStats (StatsNode *stats)
void SetAStarFixedUnitCrossingCost (int cost)
int GetAStarFixedUnitCrossingCost ()
void SetAStarMovingUnitCrossingCost (int cost)
int GetAStarMovingUnitCrossingCost ()
void SetAStarUnknownTerrainCost (int cost)
int GetAStarUnknownTerrainCost ()

Define 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 (  ) 

#define ProfileEnd (  ) 

 
#define ProfileInit (  ) 

 
#define ProfilePrint (  ) 


Function Documentation

static int AStarAddNode ( const Vec2i pos,
int  o,
int  costs 
) [inline, static]

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 
) [inline, static]

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

static int AStarFindSimplePath ( const Vec2i startPos,
const Vec2i goal,
int  gw,
int  gh,
int  ,
int  ,
int  minrange,
int  maxrange,
char *  path,
int  ,
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,
int   
) [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 
) [inline, static]

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

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

int MyAbs ( int  x  )  [inline]

void SetAStarFixedUnitCrossingCost ( int  cost  ) 

void SetAStarMovingUnitCrossingCost ( int  cost  ) 

void SetAStarUnknownTerrainCost ( int  cost  ) 


Variable Documentation

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]

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

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.