S
Also ich hab hier ein gutest Pathfinding tutorial gefunden (und benutze dieses auch in meinem Spiel http://freedune.skaldi.at). Das Tut befindet sich hier http://www.policyalmanac.org/games/aStarTutorial.htm
Und hier ist noch meine Version davon
/*
-------
A* Algorithm by Stefan Waldegger
-------
*/
#include "stdafx.h"
//Creating needed Arrays
int openListCount; //Stores the count of the open List
int closedListCount;
int *openTileList;
int *closedTileList;
unsigned int *whichList; //Is used to know if the current Tile is on the open List or on the closed List
int *parentTileList; //Stores the parenttile of each tile
int *Fcost; //stores Fcost of each tile
int *Gcost; //stores Gcost of each tile
int *Hcost; //stores Hcost of each tile
int aimDistance; //the vertical + horizontal distance to the aim
int wayLength; //Saves the length calculated way.
int *foundWay; //Saves the tiles of the found way
int mapWidth, mapHeight;
unsigned int closedList;
unsigned int openList;
//Here the amount for the different field costs is saved
//@ToDo load the different costs for the different fields and make an array of those
int diagAmount = 14, horizAmount = 10;
//for perfomace optimation this is the integer Version of fabs being in the C++ math.h header file
int fabs(int value)
{
if(value < 0) return -value;
return value;
}
/*
----
Adds an openTile to the List and sorts it by the lowest F cost
----
*/
void addOpenTileToList(int _index, int _parent, int _aimPosx, int _aimPosy)
{
int currentFCost;
int currentHCost;
int currentGCost;
int currentParent = _parent;
int currentIndex = _index;
int counter = openListCount - 1;
int newPosx, newPosy, parentPosx, parentPosy;
int startIndex, endIndex, tempIndex;
parentPosx = currentParent%tilesx;
parentPosy = currentParent/tilesx;
newPosx = _index%tilesx;
newPosy = _index/tilesx;
//calculate the new Fcost Gcost and Hcost for this tile
//There for we have to check if the field is Diagonal, or not.
//When the x or y pos differs by 1 the tile has to be diagonal
if((fabs((int)newPosx - (int)parentPosx) == 1) && (fabs((int)newPosy - (int)parentPosy) == 1))
{
currentGCost = Gcost[currentParent] + diagAmount;
}
else
{
currentGCost = Gcost[currentParent] + horizAmount;
}
currentHCost = (fabs((int)newPosx - (int)_aimPosx) + fabs((int)newPosy - (int)_aimPosy))*10;
currentFCost = currentGCost + currentHCost;
whichList[_index] = openList;
parentTileList[_index] = currentParent;
Gcost[_index] = currentGCost;
Hcost[_index] = currentHCost;
Fcost[_index] = currentFCost;
//going from the last Index (Highest Fcost) forward to the first 1 (lowest Fcost)
//To ensure that the first Index always has the lowest Fcost.
if(currentFCost > Fcost[openTileList[counter]]) //Is the last Item smaller than the new one. The value has to be added at the next Item
{
openTileList[openListCount] = currentIndex;
}
else if(currentFCost < Fcost[openTileList[0]])
{
memmove(&openTileList[1], &openTileList[0], (openListCount)*sizeof(int));
openTileList[0] = currentIndex;
}
else
{
//@Todo add the code for inserting Item to the list here
/*
----
Howto: Insert the item at the right position and move all following back
Therefor the new item is compared with the item in the middle of the list.
if it is greater it is compared with the middle of the middle of the greater list. -> Smaller with the smaller list.
And so on, till the startIndex == endIndex.
Begin:
set the startIndex to 0 and the endIndex to the last item
----
*/
startIndex = 0;
endIndex = counter;
tempIndex = -1;
for(;;)
{
tempIndex = (startIndex + endIndex)/2;
if(tempIndex == startIndex)
break;
if(currentFCost > Fcost[openTileList[tempIndex]])
{
startIndex = tempIndex;
}
else
{
endIndex = tempIndex;
}
}
/*do
{
tempIndex = (startIndex + endIndex)/2;
if(tempIndex == startIndex)
break;
if(currentFCost > Fcost[openTileList[tempIndex]])
{
startIndex = tempIndex;
}
else
{
endIndex = tempIndex;
}
}while(true);*/
//When the current Fcost is smaller than the cost at the calcualted Index
//set it at the position an put the rest back
if(currentFCost > Fcost[openTileList[startIndex]])
{
//When the current Fcost is greater than the Fcost at the calculated Index
//put it at the position after the calculated Index, so we have only add 1 to the startIndex
startIndex++;
}
memmove(&openTileList[startIndex + 1], &openTileList[startIndex], (openListCount - startIndex)*sizeof(int));
openTileList[startIndex] = currentIndex;
}
openListCount++;
}
/*
-----
this function returns the Index for the openTileList of the current tile.
-----
*/
int getTileListIndexByFcost(int _tile)
{
int startIndex = 0;
int endIndex = openListCount - 1;
int tempIndex = -1;
int currentFCost = Fcost[_tile];
//First thing find the index of the fcost
for(;;)
{
tempIndex = (startIndex + endIndex)/2;
if(tempIndex == startIndex)
break;
if(currentFCost > Fcost[openTileList[tempIndex]])
{
startIndex = tempIndex;
}
else
{
endIndex = tempIndex;
}
}
//while(endIndex >= startIndex)
//{
// tempIndex = (startIndex + endIndex) / 2;
//
// /*if(currentFCost == Fcost[openTileList[tempIndex]])
// {
// startIndex = tempIndex;
// break;
// }*/
// if(currentFCost <= Fcost[openTileList[tempIndex]])
// {
// endIndex = tempIndex - 1;
// }
// else
// {
// startIndex = tempIndex + 1;
// }
//}
//now we are at the first position of the _Fcost, so we have to go through the openTileList,
//till we find our wanted tile.
for(int i = startIndex; i < openListCount; i++)
{
if(openTileList[i] == _tile)
{
return i;
}
}
//should never happen, but if the tile isnt found return -1
return -1;
}
/*
-----
this function puts the item at the _openListIndex to the right position int the list.
-----
*/
void reOrderOpenTileList(int _openListIndex)
{
int currentTile = openTileList[_openListIndex];
int currentFCost = Fcost[openTileList[_openListIndex]];
int startIndex = 0, endIndex = openListCount - 1;
int tempIndex = -1;
for(;;)
{
tempIndex = (startIndex + endIndex)/2;
if(tempIndex == startIndex)
break;
if(currentFCost > Fcost[openTileList[tempIndex]])
{
startIndex = tempIndex;
}
else
{
endIndex = tempIndex;
}
}
if(currentFCost > Fcost[openTileList[startIndex]])
{
startIndex++;
}
memmove(&openTileList[startIndex + 1], &openTileList[startIndex], (_openListIndex - startIndex)*sizeof(int));
openTileList[startIndex] = currentTile;
}
/*
-----
this function calcualtes the new FCost from the _oldListPosition to the _newListPosition
-----
*/
void getNewFcost(int _newTileIndex, int _oldTileIndex, bool _horizontal)
{
int newGCost;
int oldGCost;
int currentAmount;
int currentListIndex;
oldGCost = Gcost[_newTileIndex];
if(_horizontal)
{
currentAmount = horizAmount;
}
else
{
currentAmount = diagAmount;
}
newGCost = Gcost[_oldTileIndex] + currentAmount;
//if the newGCost is smaller than the old 1 then the _newTileIndex hast to get the parent of the _oldTileIndex
if(newGCost < oldGCost)
{
//First thing is that we look at which position the old Tile in the list stands
currentListIndex = getTileListIndexByFcost(_newTileIndex);
parentTileList[_newTileIndex] = _oldTileIndex;
//The new Gcost has to be set and the
//FCost has to be recalculated, the HCost will stay the same, so no calculation is needed
Gcost[_newTileIndex] = newGCost;
Fcost[_newTileIndex] = newGCost + Hcost[_newTileIndex];
reOrderOpenTileList(currentListIndex);
}
}
/*
-----
Removes the _index of the openTileList and moves the items behind it forward
and adds it to the closedList
-----
*/
void removeOpenTileFromList(int _index)
{
int currentIndex = _index; //is the item to be removed
//int counter = openListCount - 1; //is the last Index
//first tell the whichList that the item is in the closedTileList
whichList[openTileList[currentIndex]] = closedList;
//next add the item to the closedList, there is no sorting needed.
closedTileList[closedListCount] = openTileList[currentIndex];
//the currentIndex has to be overwritten with the items following in the list
memmove(&openTileList[currentIndex], &openTileList[currentIndex + 1], ((openListCount - 1) - currentIndex)*sizeof(int));
openListCount--;
closedListCount++;
}
/*
-----
Allocates Memory for the AStar Function
-----
*/
void initializeAStar(int _mapWidth, int _mapHeight)
{
openTileList = (int*)malloc(_mapWidth*_mapHeight*sizeof(int));
closedTileList = (int*)malloc(_mapWidth*_mapHeight*sizeof(int));
whichList = (unsigned int*)malloc(_mapWidth*_mapHeight*sizeof(unsigned int));
parentTileList = (int*)malloc(_mapWidth*_mapHeight*sizeof(int));
Gcost = (int*)malloc(_mapWidth*_mapHeight*sizeof(int));
Hcost = (int*)malloc(_mapWidth*_mapHeight*sizeof(int));
Fcost = (int*)malloc(_mapWidth*_mapHeight*sizeof(int));
foundWay = (int*)malloc(_mapWidth*_mapHeight*sizeof(int));
memset(openTileList, 0, _mapWidth*_mapHeight*sizeof(int));
memset(closedTileList, 0, _mapWidth*_mapHeight*sizeof(int));
memset(whichList, 0, _mapWidth*_mapHeight*sizeof(unsigned int));
memset(parentTileList, 0, _mapWidth*_mapHeight*sizeof(int));
memset(Gcost, 0, _mapWidth*_mapHeight*sizeof(int));
memset(Hcost, 0, _mapWidth*_mapHeight*sizeof(int));
memset(Fcost, 0, _mapWidth*_mapHeight*sizeof(int));
mapWidth = _mapWidth;
mapHeight = _mapHeight;
closedList = 0;
openList = 1;
}
/*
-----
Frees Memory for the AStar Function
-----
*/
void unInitializeAStar()
{
free(openTileList);
free(closedTileList);
free(whichList);
free(parentTileList);
free(Gcost);
free(Hcost);
free(Fcost);
free(foundWay);
}
/*
-----
Traces the way from the _endTile back to the _startTile
and wirtes is number into the foundWay array
-----
*/
void traceWay(int _startTile, int _endTile)
{
int currentTile = _endTile;
int startTile = _startTile;
for(wayLength = 0; startTile != currentTile; wayLength++)
{
foundWay[wayLength] = currentTile;
currentTile = parentTileList[currentTile];
}
}
/*
----
Finds the way using the A* Algorithm
may return:
PATH_NOT_WALKABLE
PATH_NOT_FOUND
PATH_FOUND
----
*/
int findPathAStar(int _startIndex, int _aimIndex)
{
int aimPosx, aimPosy;
int startPosx, startPosy;
int tileToCheck;
int currentTile;
bool horizontal;
PTank tempTank;
//1. Calculate the distance to the aimTile using the manhatten method
//Therefor the actual x position and y position of the current tile and of the aim tile is needed
/*
----
The modulo of the aimIndex with the count of tilesx gives the current posx
this means when map is 20 fields high and the currentposition is 35 the posx = 15
----
*/
/*
----
The actual posy can be calculated by index/tilex
So posy of 35 = 1
----
*/
aimPosx = _aimIndex%tilesx;
aimPosy = _aimIndex/tilesx;
/*
----
Same things for the startposition
----
*/
startPosx = _startIndex%tilesx;
startPosy = _startIndex/tilesx;
/*
----
now we have the cell cooridantes of the position
So we can calculate the distance using the manhatten methode
this is the xDistance fabs(startPosx - aimPosx) + yDistance fabs(startPosy - aimPosy)
----
*/
aimDistance = fabs((int)startPosx - (int)aimPosx) + fabs((int)startPosy - (int)aimPosy);
/*
----
there are some cases where no way calculation is needed.
1.) the distance = 0
2.) the tile isn't moveable
----
*/
tempTank = NULL;
if(tiles[_aimIndex].tankIndex >= 0)
{
tempTank = tankPointerList[tiles[_aimIndex].tankIndex];
}
if(tempTank || !tiles[_aimIndex].moveAbleGround)
{
return PATH_NOT_WALKABLE;
}
if((aimDistance == 0))
return PATH_FOUND;
//the whichList has to be set back from time to time
if(closedList > 4294967292)
{
memset(whichList, 0, 256*256*sizeof(unsigned int));
closedList = 0;
openList = 1;
}
closedList += 2;
openList += 2;
/*
----
now we got the guessed distance to the aim and we can start the actual pathfinding
this value is called H cost and has to be calculated for every new cell.
the G cost is calculated by the way to the filed being horizontal (10) or diagonal (14)
the F cost is calculated by adding G cost + H cost
This is done in the addtoopenList Function
----
----____----____----____----
The princip of the A* algorithm:
there are 2 different lists 1 open list and 1 closed list
The first thing is to check the neighbourtiles of the starttile and add them to the openList and add the startfield as parentfield for the
newly opened field.
The next thing is to add the startTile to the open list.
Then check all neighbour cells of the next cell with the lowest F cost and this to the closed list. If those are already open
if the Gcost to this field (G cost of actual field + G cost the "parent") is lower than the actual, when true
change the parent field to the actual field. Else let it be.
----____----____----____----
----
First add the startTile to the openList and check all neighbour tiles of it.
Add those neighbourtiles to the openList, but only if no obstacle is on it.
----
*/
openListCount = 1;
closedListCount = 0;
openTileList[0] = _startIndex;
whichList[_startIndex] = openList;
parentTileList[_startIndex] = -1;
Fcost[_startIndex] = 0;
Gcost[_startIndex] = 0;
Hcost[_startIndex] = 0;
currentTile = _startIndex;
//The startTile was added to the list and is marked as open.
//Now we have to search so long till the openListCount == 0 (no path found)
//or the aimIndex is added to the openList (path Found)
do
{
//First thing is to check the 8 neighbour Tiles of the first tile in the openList (always has the lowest Fcost)
for(int i = 1; i <= 8; i++)
{
tileToCheck = calcNeighbourTile(currentTile, i);
//The item has to be walkable
tempTank = NULL;
if(tiles[tileToCheck].tankIndex >= 0)
{
tempTank = tankPointerList[tiles[tileToCheck].tankIndex];
}
if(tiles[tileToCheck].moveAbleGround && !tempTank)
{
//If this tile isnt already in the openList then add it to it
if(whichList[tileToCheck] != openList && whichList[tileToCheck] != closedList)
{
addOpenTileToList(tileToCheck, currentTile, aimPosx, aimPosy);
//When the item to check is the aim, then the way is found
if(tileToCheck == _aimIndex)
{
//Trace back the way here
traceWay(_startIndex, tileToCheck);
return PATH_FOUND;
}
}
else if(whichList[tileToCheck] == openList)
{ //else look if the Fcost gets smaller when we try to reach the tile from this tile
//Naturally this tile may not be at the right position in the list
//So it has to be reordered.
horizontal = ((i%2) == 0);
getNewFcost(tileToCheck, currentTile, horizontal);
}
}
}
//The next thing is to remove the current tile from the list and add it to the closed List
//@ToDo remove the tile from the openList and add it to the closed List
//this function does both.
removeOpenTileFromList(getTileListIndexByFcost(currentTile));
currentTile = openTileList[0];
}
while(openListCount);
return PATH_NOT_FOUND;
}
/*
----
retunrs the number of fields the way needs to allocate the memory for the patharray
----
*/
int getAStarTileNumber()
{
return wayLength;
}
/*
----
returns the array of the path
----
*/
int *getAStarPathArray()
{
return foundWay;
}
void cleanUpAStar()
{
//This function isnt needed and can be deleted when having time
}
/*
-----
Description: This function searches for the next free tile around the tile given as parameter
Returns: The next free Tile and if no tile is found -1;
-----
*/
int findNextFreeTile(int _tile, int _startPosition)
{
int tilesToCheck = 2;
int pos;
int tempIndex;
int tileCounter = 0;
int freeTiles[24];
int tempx, tempy;
int tempStartx, tempStarty;
int distance;
int oldDistance = -1;
int newTile = 0;
PTank tempTank = NULL;
//First thing is to check if the tile given as parameter is walkable
if(tiles[_tile].tankIndex >= 0)
{
tempTank = tankPointerList[tiles[_tile].tankIndex];
}
if(!tempTank)
{
return _tile;
}
else
{
//Check the surrounding tiles and look if the tiles are walkable
//And save them into an array
tempIndex = _tile;
for(int j = tempIndex - tilesToCheck * tilesx; j <= tempIndex + tilesToCheck * tilesx; j += tilesx)
{
for(int i = j - tilesToCheck; i <= j + tilesToCheck; i++)
{
pos = i;
tempTank = NULL;
if(tiles[pos].tankIndex >= 0)
{
tempTank = tankPointerList[tiles[pos].tankIndex];
}
if(!tempTank)
{
if(findPathAStar(_startPosition, pos) == PATH_FOUND)
{
freeTiles[tileCounter] = pos;
tileCounter++;
}
}
}
}
}
//Having all the tiles in the array, look which tile is the closest one
//and return this 1
tempStartx = _tile%tilesx;
tempStarty = _tile/tilesy;
if(tileCounter > 0)
{
for(int i = 0; i < tileCounter; i++)
{
tempx = freeTiles[i]%tilesx;
tempy = freeTiles[i]/tilesx;
distance = fabs((int)tempStartx - (int)tempx) + fabs((int)tempStarty - (int)tempy);
if(oldDistance == -1 || distance < oldDistance)
{
oldDistance = distance;
newTile = freeTiles[i];
}
}
return newTile;
}
//return -1 when no free tile is found
return -1;
}
//The A* Algorithm is working fine so this function isn't needed anymore
void testAstar()
{
int testSize;
int way[256*256];
if(findPathAStar(2000, 2170) == PATH_FOUND)
{
printf("\nWay found\n");
testSize = getAStarTileNumber();
printf("%i tiles are to drive\n", testSize);
printf("The tiles are:");
memcpy(way, getAStarPathArray(), testSize*sizeof(int));
for(int i = 0; i < testSize; i++)
{
printf("%i, ", way[i]);
}
}
}