GLLib: GLLibPathFinding Class Reference

GLLib

GLLibPathFinding Class Reference
[GLLibPathFinding]

A* (A star) Pathfinding class. More...

List of all members.


Public Member Functions

 GLLibPathFinding ()
 Empty constructor.
void PathFinding_Exec (int start_x, int start_y, int start_dir, int end_x, int end_y)
 PathFinding_Exec is the heart of the engine, the search is done in this function.
void PathFinding_Free (boolean bKeepLastPath)
 PathFinding_Free will free all of the internal buffers and arrays.
int PathFinding_GetPathLength ()
 PathFinding_GetPathLength will give you the path length that was found by the previous call to PathFinding_Exec.
int PathFinding_GetPathPosition (int nIndex)
 PathFinding_GetPathPosition will give you the position of the path node in array index i.e.
int PathFinding_GetPathPositionX (int nIndex)
 PathFinding_GetPathPositionX will give you the x position of the path node you are querying.
int PathFinding_GetPathPositionY (int nIndex)
 PathFinding_GetPathPositionY will give you the y position of the path node you are querying.
void PathFinding_Init (int nMapWidth, int nMapHeight, byte[] pPhysicalMap, int nCostMove, int nCostMoveDiag, int nCostChangeDir, int nDirCount, int nCollisionMask)
 PathFinding_Init must be used once to initialize the PathFinding engine, or if you want to change the parameters of the search.
void PathFinding_Init (int nMapWidth, int nMapHeight, byte[] pPhysicalMap, int nCostMove, int nCostMoveDiag, int nCostChangeDir, int nDirCount)
 PathFinding_Init must be used once to initialize the PathFinding engine, or if you want to change the parameters of the search.

Static Public Attributes

static final int kDirDown = 1
static final int kDirDownLeft = 6
static final int kDirDownRight = 7
static final int kDirLeft = 2
static final int kDirRight = 3
static final int kDirUp = 0
static final int kDirUpLeft = 4
static final int kDirUpRight = 5

Detailed Description

A* (A star) Pathfinding class.

A* incrementally searches all routes leading from the starting point until it finds the shortest path to a goal. Like all informed search algorithms, it searches first the routes that appear to be most likely to lead towards the goal. What sets A* apart from a greedy best-first search is that it also takes the distance already traveled into account (the g(x) part of the heuristic is the cost from the start, and not simply the local cost from the previously expanded node).

If you want to have more information about the algorythm used in this class, see http://www.policyalmanac.org/games/aStarTutorial.htm or http://en.wikipedia.org/wiki/A%2A


Constructor & Destructor Documentation

Empty constructor.

Note:
Call PathFinding_Init to initialize the class.


Member Function Documentation

void PathFinding_Exec ( int  start_x,
int  start_y,
int  start_dir,
int  end_x,
int  end_y 
)

PathFinding_Exec is the heart of the engine, the search is done in this function.

The search will be completed with one call.

Parameters:
start_x Starting tile's x coordinate.
start_y Starting tile's y coordinate.
start_dir Starting direction of the entity that will be moving.
end_x Ending tile's x coordinate.
end_y Ending tile's y coordinate.

void PathFinding_Free ( boolean  bKeepLastPath  ) 

PathFinding_Free will free all of the internal buffers and arrays.

Parameters:
bKeepLastPath If true, will keep the last path found array. If false, it will be freed also, and calls to query path results will fail.

int PathFinding_GetPathLength (  ) 

PathFinding_GetPathLength will give you the path length that was found by the previous call to PathFinding_Exec.

Returns:
The current path length. 0 if no path was found.
Note:
You need to call PathFinding_Exec once before calling this fonction.

int PathFinding_GetPathPosition ( int  nIndex  ) 

PathFinding_GetPathPosition will give you the position of the path node in array index i.e.

((y*width) + x) so that you can access you array without computing the array pos.

Parameters:
nIndex The path node you want to query.
Returns:
The path node position in your collision map.
Note:
You need to call PathFinding_Exec once before calling this fonction.

The result will be backward, going from the end to the bening, so PathFinding_GetPathPosition(0) start from the end.

int PathFinding_GetPathPositionX ( int  nIndex  ) 

PathFinding_GetPathPositionX will give you the x position of the path node you are querying.

Parameters:
nIndex The path node you want to query.
Returns:
The X position your collision map.
Note:
You need to call PathFinding_Exec once before calling this fonction.

int PathFinding_GetPathPositionY ( int  nIndex  ) 

PathFinding_GetPathPositionY will give you the y position of the path node you are querying.

Parameters:
nIndex The path node you want to query.
Returns:
The Y position your collision map.
Note:
You need to call PathFinding_Exec once before calling this fonction.

void PathFinding_Init ( int  nMapWidth,
int  nMapHeight,
byte[]  pPhysicalMap,
int  nCostMove,
int  nCostMoveDiag,
int  nCostChangeDir,
int  nDirCount,
int  nCollisionMask 
)

PathFinding_Init must be used once to initialize the PathFinding engine, or if you want to change the parameters of the search.

Parameters:
nMapWidth The witdh of your collision map grid.
nMapHeight The height of your collision map grid.
pPhysicalMap The coolision map, single dimension byte array. The format is the same as a pixel array, a cell is found by cell=((y*width)+x). For the moment, the internal format of this array is 0=freecell anything else is blocked.
nCostMove is the cost of moving verticaly or horizontaly (but not both). Usually you should use 10.
nCostMoveDiag is the cost of moving verticaly and horizontaly at the same time. Usually you should use 14. Its not used if nDirCount is 4.
nCostChangeDir is the cost of changing direction. Use 0 if there is no cost involve in changing direction. Usually you should use 10.
nDirCount is used to specify if the algo should look at diagonals possibilities (8) or only the minimal ones (4).
nCollisionMask is a mask applied to your Physical Map to find collision. Usefull if you want to store more info in you map. By default the mask should be 0xFFFFFFFF.

void PathFinding_Init ( int  nMapWidth,
int  nMapHeight,
byte[]  pPhysicalMap,
int  nCostMove,
int  nCostMoveDiag,
int  nCostChangeDir,
int  nDirCount 
)

PathFinding_Init must be used once to initialize the PathFinding engine, or if you want to change the parameters of the search.

Parameters:
nMapWidth The witdh of your collision map grid.
nMapHeight The height of your collision map grid.
pPhysicalMap The coolision map, single dimension byte array. The format is the same as a pixel array, a cell is found by cell=((y*width)+x). For the moment, the internal format of this array is 0=freecell anything else is blocked.
nCostMove is the cost of moving verticaly or horizontaly (but not both). Usually you should use 10.
nCostMoveDiag is the cost of moving verticaly and horizontaly at the same time. Usually you should use 14. Its not used if nDirCount is 4.
nCostChangeDir is the cost of changing direction. Use 0 if there is no cost involve in changing direction. Usually you should use 10.
nDirCount is used to specify if the algo should look at diagonals possibilities (8) or only the minimal ones (4).


Member Data Documentation

final int kDirDown = 1 [static]

final int kDirDownLeft = 6 [static]

final int kDirDownRight = 7 [static]

final int kDirLeft = 2 [static]

final int kDirRight = 3 [static]

final int kDirUp = 0 [static]

final int kDirUpLeft = 4 [static]

final int kDirUpRight = 5 [static]


Generated on Tue Sep 23 23:05:32 2008 for GLLib by  doxygen 1.5.2