Pathfinding

[xindon]

Hey,

ich hab ein kleines Spiel gemacht (Idee und Anfänge von nem Kumpel und mir auf der letzten LAN :))

Bevor ich hier lange erkläre, einfach ein Screenshot:
http://bloody-blades.de/gbm/gbm_screenshot.jpg

Die blauen Steine kann man wegsprengen, die grauen nicht. Die Karte wird zufällig generiert.
Da es selten, aber doch ab und zu mal vorkommt, dass sich die Spieler nicht treffen können, weil sie durch eine Mauer getrennt werden, habe ich mir überlegt bei jeder neuen Map zu testen, ob sie in Ordnung ist.

Jetzt meine Frage: Wie kann ich das am besten realiseren und zwar auch entsprechend schnell, dass es nicht stört. Merci

----

zum Antesten
http://bloody-blades.de/gbm/GBM.zip

In der config.ini kann man Auflösung ändern, Fullscreen an und aus etc...

Wir hatten es auf der Netzwerksession die GANZE Zeit gespielt, war richtig geil. (aber andere Grafiken und vorallem lustigere Skins *g*)

[toast]

das schreit nach einer guten Rekursionsanwedung (übrigens Minesweeperprinzip beim Aufdecken Feldern ohne Miene):

schreib eine Funktion isHart( pos Axy ), um zu überprüfen ob feld xy nicht leer und nicht sprengbar
schreib eine Funktion _isConnected( pos Axy, pos Bxy ), die enthält:

bool controlled[3000][3000];
bool _isConnected( pos Axy, pos Bxy )
{
controlled[Axy.x][Axy.y] = true;
for( int x=Axy.x-1; x<=Axy.x+1; i++)
  for( int y=Axy.y-1; y<=Axy.y+1; i++)
    if( x != Axy.x && y != Ayx.y )
    {
      if( pos(x,y) == Bxy )        return true;
      if( isHart( pos(x,y) )       continue;
      if( !controlled[x][y] )
        if( _isConnected(pos(x,y) ) return true;
    }
}

jetzt noch eine übergeordnete Funktion:

bool isConnected( pos Axy, pos Bxy )
{
// clear controlled
return _isConnected(pos(x,y);
}

da wärs :p

[edit]n paar typos, kein Bock weiter zu korrigiern ^^[/edit]

[toast]

haltma, das testet so wie es jetz steht alle 8 Felder um ein mittleres, kann man schräg laufen? Ansonsten musste noch n bischen mehr ändern ...

[xindon]

Man kann nicht diagonal laufen; kannst es ja mal antesten.

---

Okay, also erstmal wie würde denn dann eine Anwendung deines Codes aussehen? Also wo und wie soll er aufgerufen werden und was soll als Ergebnis geliefert werden?
----
edit:
ich glaube, ich habe deinen Code verstanden, aber eine Frage:
du definierst

bool _isConnected( pos Axy, pos Bxy )

, aber dann rufst du es nur mit einem Parameter auf?

----

Ich habe mir überlegt, dass getestet wird, ob man einen Weg zwischen Spieler Rot und Spieler Blau herstellen kann. Wenn nicht, wird eine neue Karte erstellt.
Aber wie genau würde da die Logik dahinter aussehen?

Und bitte kein Code, sondern einfach in Worte fassen. Ich würde es gerne selbst programmieren. Trotzdem vielen Dank toast für die Mühe

---------------------------------

Okay, hab mich von deinem Vorschlag inspirieren lassen und habs jetzt selbst hingekriegt. Vielen Dank!

[TGGC]

Schau dir doch mal den InChains Source an, Da gibts auch'n Pathfinding drin.

Bye, TGGC(War, bin, sein.)

[Skaldi]

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]);
		}
	}
}