_________ __ __ / _____// |_____________ _/ |______ ____ __ __ ______ \_____ \\ __\_ __ \__ \\ __\__ \ / ___\| | \/ ___/ / \| | | | \// __ \| | / __ \_/ /_/ > | /\___ \ /_______ /|__| |__| (____ /__| (____ /\___ /|____//____ > \/ \/ \//_____/ \/ ______________________ ______________________ T H E W A R B E G I N S Stratagus - A free fantasy real time strategy game engine
#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 () |
#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, | |
y | |||
) | (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 | ( | ) |
|
inlinestatic |
Add a new node to the open set (and update the heap structure)
|
static |
heuristic cost function for a*
|
static |
Check if a node is already in the open set.
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 |
Optimization to find a simple path Check if we're at the goal or if it's 1 tile away
StatsNode* AStarGetStats | ( | ) |
|
static |
MarkAStarGoal
|
static |
Prepare pathfinder.
|
static |
Remove the minimum from the open node set
|
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 |
Save the path
|
inlinestatic |
Compute the cost of crossing tile (x,y)
x | X tile where to move. |
y | Y tile where to move. |
data | user data. |
|
static |
Clean up A*
|
static |
void FreeAStar | ( | ) |
free the a* data structures
Free A* data structure
bool GetAStarFixedEnemyUnitsUnpassable | ( | ) |
int GetAStarFixedUnitCrossingCost | ( | ) |
int GetAStarMovingUnitCrossingCost | ( | ) |
int GetAStarUnknownTerrainCost | ( | ) |
void InitAStar | ( | int | mapWidth, |
int | mapHeight | ||
) |
Init the a* data structures.
Init A* data structures
|
inline |
void SetAStarFixedEnemyUnitsUnpassable | ( | const bool | value | ) |
void SetAStarFixedUnitCrossingCost | ( | int | cost | ) |
void SetAStarMovingUnitCrossingCost | ( | int | cost | ) |
void SetAStarUnknownTerrainCost | ( | int | cost | ) |
|
static |
Used to temporary make enemy units unpassable (needs for correct path lenght calculating for automatic targeting alorithm)
int AStarFixedUnitCrossingCost |
see pathfinder.h
cost associated to move on a tile occupied by a fixed unit
|
static |
|
static |
bool AStarKnowUnseenTerrain = false |
Whether to have knowledge of terrain that we haven't visited yet.
|
static |
|
static |
|
static |
|
static |
cost matrix
|
static |
int AStarMaxSearchIterations = INT_MAX |
Maximum number of iterations of A* before giving up.
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.
|
staticconstexpr |
|
static |
|
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 } |
|
static |
|
static |
a list of close nodes, helps to speed up the matrix cleaning
|
static |
The size of the open node set.
const int XY2Heading[3][3] = { {7, 6, 5}, {0, 0, 4}, {1, 2, 3}} |