$treeview $search $mathjax
Stratagus  2.2.6
$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 <stdlib.h>
#include "map.h"
#include "unit.h"
#include "pathfinder.h"

Classes

struct  Node
struct  Open
struct  StatsNode

astar.cpp - The a* path finder routines.

#define AStarCosts(sx, sy, ex, ey)   std::max<int>(MyAbs(sx - ex), MyAbs(sy - ey))
 heuristic cost function for a*
#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 void * data
static int * CostMoveToCache
static const int CacheNotSet = -5
static int (STDCALL *CostMoveToCallback)(unsigned int index
void InitAStar (int mapWidth, int mapHeight, int(STDCALL *costMoveTo)(unsigned int index, void *data))
 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 (int x, int y, int o, int costs)
static void AStarReplaceNode (int pos, int)
static int AStarFindNode (int eo)
static void AStarAddToClose (int node)
static int CostMoveTo (unsigned int index, void *data)
int square (int v)
static int AStarMarkGoal (int gx, int gy, int gw, int gh, int tilesizex, int tilesizey, int minrange, int maxrange, void *data)
static int AStarSavePath (int startX, int startY, int endX, int endY, char *path, int pathLen)
static int AStarFindSimplePath (int sx, int sy, int gx, int gy, int gw, int gh, int, int, int minrange, int maxrange, char *path, int, void *data)
int AStarFindPath (int sx, int sy, int gx, int gy, int gw, int gh, int tilesizex, int tilesizey, int minrange, int maxrange, char *path, int pathlen, void *data)
 Find and a* path for a 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 AStarCosts ( sx,
sy,
ex,
ey   )     std::max<int>(MyAbs(sx - ex), MyAbs(sy - ey))

heuristic cost function for a*

 
#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 ( int  x,
int  y,
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 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 ( int  sx,
int  sy,
int  gx,
int  gy,
int  gw,
int  gh,
int  tilesizex,
int  tilesizey,
int  minrange,
int  maxrange,
char *  path,
int  pathlen,
void *  data 
)

Find and a* path for a unit.

Find path.

static int AStarFindSimplePath ( int  sx,
int  sy,
int  gx,
int  gy,
int  gw,
int  gh,
int  ,
int  ,
int  minrange,
int  maxrange,
char *  path,
int  ,
void *  data 
) [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 ( int  gx,
int  gy,
int  gw,
int  gh,
int  tilesizex,
int  tilesizey,
int  minrange,
int  maxrange,
void *  data 
) [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 ( int  startX,
int  startY,
int  endX,
int  endY,
char *  path,
int  pathLen 
) [static]

Save the path

Returns:
The length of the path

static int CostMoveTo ( unsigned int  index,
void *  data 
) [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]

void FreeAStar (  ) 

free the a* data structures

Free A* data structure

int GetAStarFixedUnitCrossingCost (  ) 

int GetAStarMovingUnitCrossingCost (  ) 

int GetAStarUnknownTerrainCost (  ) 

void InitAStar ( int  mapWidth,
int  mapHeight,
int(STDCALL *costMoveTo)(unsigned int index, void *data  
)

Init the a* data structures.

Init A* data structures

static int ( STDCALL *  CostMoveToCallback  )  [static]

void SetAStarFixedUnitCrossingCost ( int  cost  ) 

void SetAStarMovingUnitCrossingCost ( int  cost  ) 

void SetAStarUnknownTerrainCost ( int  cost  ) 

int square ( int  v  )  [inline]


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]

void* data

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-2011 by The Stratagus Project under the GNU General Public License.
All trademarks and copyrights on this page are owned by their respective owners.