Jump to content
  • Advertisement
Sign in to follow this  
Anand Baumunk

A* polishing - optimising implementation for large map

This topic is 2089 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Well met!

 

I implemented my own A*-algorithm, and thanks to you guys got rid of all of the bottlenecks. So it runs fine now, when used on a medium map and is able to find a path.

However, I need to work fast enough on a 1024*1024 map. At the moment, it manages to stay between 0.001 and 1 sec, depending on the length of the path. If the goal is not reachable, it takes up to 10 seconds, which is obviously not acceptable.

 

I am very inexperienced with speed and optimising, this is in fact the first time I have to think about it. I know the basics, like not new/delete memory in stuff that is frequently called. But that's about it, and I wasn't able to figure out what can be done better for my code.

Therefore I am providing you the implementation, hoping you can point me in the right direction. I'm sorry for having you look through so much code.

class node{
public:
	node *parent;
	int2 pos;
	bool isOpen;


	bool isOnClosedList, isOnOpenList; // not using closedlist, and isOnOpenList lets me skip the sorting through the openlist when I want to see if a node is on it
	int costF, costG, costH;

public:
	node(){
		resetData();
		isOpen = true;
		pos = int2(0, 0);
	}
	node(int2 posIn){
		pos = posIn;
		isOpen = true;
		resetData();
	}
	~node(){}

	// reset for reusing
	void resetData(){
		parent = NULL;
		costF = costG = costH = 0;
		isOnClosedList = false;
		isOnOpenList = false;
	}
};

class pathingDevice{
public:
	visualisePathingDevice *visDev;// don't mind this, it's for rendering the data

	static const int size = 512;
	vector<node*> openList;
	node *map[size][size];
	vector<node*> path;




public:
	pathingDevice(void);
	~pathingDevice(void);

	void init();
	void initVisualisation(ID3D11Device* d3d11DeviceIn, ID3D11DeviceContext* d3d11DevConIn);
	void renderVisualisation(D3DXMATRIX camViewIn, D3DXMATRIX camProjectionIn);

	bool getPath(float startX, float startZ, float goalX, float goalZ);


};


class pathingDevice{
public:
	visualisePathingDevice *visDev;

	static const int size = 512;
	vector<node*> openList;
	node *map[size][size];
	vector<node*> path;




public:
	pathingDevice(void);
	~pathingDevice(void);

	void init();
	void initVisualisation(ID3D11Device* d3d11DeviceIn, ID3D11DeviceContext* d3d11DevConIn);
	void renderVisualisation(D3DXMATRIX camViewIn, D3DXMATRIX camProjectionIn);

	bool getPath(float startX, float startZ, float goalX, float goalZ);


};

class pathingDevice{
public:
	visualisePathingDevice *visDev;

	static const int size = 512;
	vector<node*> openList;
	node *map[size][size];
	vector<node*> path;




public:
	pathingDevice(void);
	~pathingDevice(void);

	void init();
	void initVisualisation(ID3D11Device* d3d11DeviceIn, ID3D11DeviceContext* d3d11DevConIn);
	void renderVisualisation(D3DXMATRIX camViewIn, D3DXMATRIX camProjectionIn);

	bool getPath(float startX, float startZ, float goalX, float goalZ);


};

class pathingDevice{
public:
	visualisePathingDevice *visDev;

	static const int size = 512;
	vector<node*> openList;
	node *map[size][size];
	vector<node*> path;




public:
	pathingDevice(void);
	~pathingDevice(void);

	void init();
	void initVisualisation(ID3D11Device* d3d11DeviceIn, ID3D11DeviceContext* d3d11DevConIn);
	void renderVisualisation(D3DXMATRIX camViewIn, D3DXMATRIX camProjectionIn);

	bool getPath(float startX, float startZ, float goalX, float goalZ);


};

class pathingDevice{
public:
	visualisePathingDevice *visDev;

	static const int size = 512;
	vector<node*> openList;
	node *map[size][size];
	vector<node*> path;




public:
	pathingDevice(void);
	~pathingDevice(void);

	void init();
	void initVisualisation(ID3D11Device* d3d11DeviceIn, ID3D11DeviceContext* d3d11DevConIn);
	void renderVisualisation(D3DXMATRIX camViewIn, D3DXMATRIX camProjectionIn);

	bool getPath(float startX, float startZ, float goalX, float goalZ);


};

class pathingDevice{
public:
	visualisePathingDevice *visDev;

	static const int size = 512;
	vector<node*> openList;
	node *map[size][size];
	vector<node*> path;




public:
	pathingDevice(void);
	~pathingDevice(void);

	void init();
	void initVisualisation(ID3D11Device* d3d11DeviceIn, ID3D11DeviceContext* d3d11DevConIn);
	void renderVisualisation(D3DXMATRIX camViewIn, D3DXMATRIX camProjectionIn);

	bool getPath(float startX, float startZ, float goalX, float goalZ);


};

class pathingDevice{
public:
	visualisePathingDevice *visDev;

	static const int size = 512;
	vector<node*> openList;
	node *map[size][size];
	vector<node*> path;




public:
	pathingDevice(void);
	~pathingDevice(void);

	void init();
	void initVisualisation(ID3D11Device* d3d11DeviceIn, ID3D11DeviceContext* d3d11DevConIn);
	void renderVisualisation(D3DXMATRIX camViewIn, D3DXMATRIX camProjectionIn);

	bool getPath(float startX, float startZ, float goalX, float goalZ);


};

class pathingDevice{
public:
	visualisePathingDevice *visDev;

	static const int size = 512;
	vector<node*> openList;
	node *map[size][size];
	vector<node*> path;




public:
	pathingDevice(void);
	~pathingDevice(void);

	void init();
	void initVisualisation(ID3D11Device* d3d11DeviceIn, ID3D11DeviceContext* d3d11DevConIn);
	void renderVisualisation(D3DXMATRIX camViewIn, D3DXMATRIX camProjectionIn);

	bool getPath(float startX, float startZ, float goalX, float goalZ);


};

class pathingDevice{
public:
	visualisePathingDevice *visDev;

	static const int size = 512;
	vector<node*> openList;
	node *map[size][size];
	vector<node*> path;




public:
	pathingDevice(void);
	~pathingDevice(void);

	void init();
	void initVisualisation(ID3D11Device* d3d11DeviceIn, ID3D11DeviceContext* d3d11DevConIn);
	void renderVisualisation(D3DXMATRIX camViewIn, D3DXMATRIX camProjectionIn);

	bool getPath(float startX, float startZ, float goalX, float goalZ);


};

#include "pathingDevice.h"


pathingDevice::pathingDevice(void){
}

pathingDevice::~pathingDevice(void){
}


void pathingDevice::init(){
	
	//example data for blocked nodes
	for(int y=0; y<size; y++){
		for(int x=0; x<size; x++){
			map[x][y] = new node(int2(x, y));
			if(x == 5 && y != 1){map[x][y]->isOpen = false;}
			if(x == 11 && y != 63){map[x][y]->isOpen = false;}
			if(x == 22 && y != 44){map[x][y]->isOpen = false;}
			if(x == 34 && y != 22){map[x][y]->isOpen = false;}
			if(x == 55 && y != 11){map[x][y]->isOpen = false;}
		}
	}

}


void pathingDevice::initVisualisation(ID3D11Device* d3d11DeviceIn, ID3D11DeviceContext* d3d11DevConIn){
	visDev = new visualisePathingDevice(d3d11DeviceIn, d3d11DevConIn, map);
}


void pathingDevice::renderVisualisation(D3DXMATRIX camViewIn, D3DXMATRIX camProjectionIn){
	visDev->render(D3DXVECTOR2(size, size), camViewIn, camProjectionIn);
}



bool pathingDevice::getPath(float startX, float startZ, float goalX, float goalZ){

	int directionsX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
	int directionsY[8] = {0, 1, 0, -1, -1, 1, -1, 1};
	int numDirections = 8;



	clock_t begin = clock();

	path.clear();

	// just the conversion from real space to map indices, ignore it
	int sX = (int)(startX/10);
	int sY = (int)(startZ/10);
	int gX = (int)(goalX/10);
	int gY = (int)(goalZ/10);

	if(map[gX][gY]->isOpen == false){printf("Unpassable terrain at goal!\n");return false;}

	bool failedToFindPath = false;


	node *goal = new node(int2(gX, gY));
	node *currentNode = map[sX][sY];
	openList.push_back(currentNode);
	currentNode->isOnOpenList = true;

	

	while(true){

		//if no more nodes, no path 
		if(openList.empty()){
			failedToFindPath = true;
			break;		
		}

		//search for lowest F-Cost node on openList
		//add anti-corner-crossing here
		long lowestCost = openList[0]->costF;
		int lowestID = 0;
		for(int i=0; i<openList.size(); i++){
			if(openList[i]->costF < lowestCost){
				lowestCost = openList[i]->costF;
				lowestID = i;
			}
		}
		

		//move it to closedList
		currentNode = openList[lowestID];

		//if found goal, we are done
		if(currentNode->pos == goal->pos){
			break;
		}
		currentNode->isOnClosedList = true;
		currentNode->isOnOpenList = false;
		openList.erase(openList.begin()+lowestID);


		// check adjacent squares
		for(int r=0; r<numDirections; r++){
			int2 checkNodeId; 
			checkNodeId.x = currentNode->pos.x + directionsX[r];
			checkNodeId.y = currentNode->pos.y + directionsY[r];


			//if node out of bounds, ignore it
			if(checkNodeId.x < 0 || checkNodeId.x > size-1 || checkNodeId.y < 0 || checkNodeId.y > size-1){
				continue;
			}


			//if on closed list or updassable, ignore
			if(!map[checkNodeId.x][checkNodeId.y]->isOpen || map[checkNodeId.x][checkNodeId.y]->isOnClosedList){
				continue;
			}

			if(map[checkNodeId.x][checkNodeId.y]->isOnOpenList){
				

				int costToGetThere;
				if(r > 3){
					costToGetThere = 14;
				}else{
					costToGetThere = 10;
				}

				//If new path is shorter, use it
				if(map[checkNodeId.x][checkNodeId.y]->costG > currentNode->costG + costToGetThere){
					map[checkNodeId.x][checkNodeId.y]->parent = currentNode;
					map[checkNodeId.x][checkNodeId.y]->costG = currentNode->costG + costToGetThere;
					map[checkNodeId.x][checkNodeId.y]->costF = map[checkNodeId.x][checkNodeId.y]->costG +  map[checkNodeId.x][checkNodeId.y]->costH;
				}

			}else{
				openList.push_back(map[checkNodeId.x][checkNodeId.y]);
				map[checkNodeId.x][checkNodeId.y]->isOnOpenList = true;
				map[checkNodeId.x][checkNodeId.y]->parent = currentNode;

				//calculate cost of node
				//if diagonal
				if(r > 3){
					map[checkNodeId.x][checkNodeId.y]->costG = currentNode->costG + 14;
				}else{
					map[checkNodeId.x][checkNodeId.y]->costG = currentNode->costG + 10;
				}

				
				int h;
				int dx = abs(map[checkNodeId.x][checkNodeId.y]->pos.x - goal->pos.x);
				int dy = abs(map[checkNodeId.x][checkNodeId.y]->pos.y - goal->pos.y);
				h = 10 * (dx + dy) + (14 - 2 * 10) * min(dx, dy);

				map[checkNodeId.x][checkNodeId.y]->costH = h;//10*(sqrt((map[checkNodeId.x][checkNodeId.y]->pos.x - goal->pos.x) ^2 + (map[checkNodeId.x][checkNodeId.y]->pos.y - goal->pos.y) ^2));
				map[checkNodeId.x][checkNodeId.y]->costF = map[checkNodeId.x][checkNodeId.y]->costG + map[checkNodeId.x][checkNodeId.y]->costH;
			}

		}
	
	}




	if(!failedToFindPath){

		path.clear();
		
		
		while(currentNode->pos != map[sX][sY]->pos){
			path.push_back(currentNode);
			currentNode = currentNode->parent;
		}
		path.push_back(currentNode);
		
	}else{
		printf("No Path!\n");
	}

	reverse(path.begin(),path.end());
	//reset everything
	openList.clear();

	for(int z=0; z<size; z++){
		for(int x=0; x<size; x++){
			map[x][z]->resetData();
		}
	}

	//delete currentNode;
	//delete goal;


	clock_t end = clock();
	double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
	printf("Time in secs: %f\n", elapsed_secs);
	


	return !failedToFindPath;
}
So, that's it. I'm happy about any other things that suck in my code beeing pointed out as well.
If anyone wants to use my implementation for himself, just go ahead, I don't mind.
 
Greetings
-gnomgrol

Share this post


Link to post
Share on other sites
Advertisement

I spotted one way you can improve your code: use an ordered queue instead of a vector. Deleting items in the middle of a vector is known to be slow in comparison to other std container operations. Here's the definition of such a container, straight off my A* implementation, it orders nodes inserted into it by its F value:

struct PathfinderNode : public Point
{
	int G_Score, H_Score, F_Score, Parent;

	PathfinderNode() { F_Score = DN_NODE_UNSCANNED; }
};

class mycomparison
{
public:
	mycomparison() {}
	bool operator() (const PathfinderNode& lhs, const PathfinderNode& rhs) const
	{
		return lhs.F_Score > rhs.F_Score;
	}
};

typedef std::priority_queue<PathfinderNode,
		std::vector<PathfinderNode>, mycomparison>
		PathfinderNodeOrderedList;

Does your game use a fixed map? If so then you can pre-calculate every path at the start of the game, or even better, do it the first time the game is ran and then save the data to a cache file.

 

If your map isn't fixed and there's no way around having to calculate paths in real time (for example, if moving foes are considered inpassable walls), then don't expect it to get much better than what you have now. 1024x1024 pathing is going to take up a lot of resources no matter how hard you optimize the code. My program is designed to handle grids of up to 64k by 64k, but it is a simulation as opposed to a real-time game so it's acceptable to take time pathing (although my objects seldomly need to path anything longer than 100 tiles or so).

 

Good luck!

Edited by Nüb?ek Pænus

Share this post


Link to post
Share on other sites

A* is as fast as it comes, but huge maps are huge maps and simply exploring them with A* will inevitably at some point become too expensive. If the map is enclosed, like a city or the inside of a building, there is a lot you can do to simplyfy A*'s workload, the map is not likely to change and going from A to B will always require the same path. When you edit and save the map, you can precalculate paths between key points and store it along with the map data, so when someone wants to go from A to B it simply loads the saved path.

 

On an open map, there should always be choke points, natural barriers that split the map in zones, like a bridge over a river, a slope that climbs a cliff sided mountain, stuff like that, the path to cross an entire area from one chokepoint to another will always be more or less the same, and can be precalculated, you then use A* for more short range adaptations.

Share this post


Link to post
Share on other sites

Correct me if I am wrong (I am not a C++ programmer), but I don't think you can use a priority queue because you need to update the values.

Share this post


Link to post
Share on other sites

A min-heap priority queue is essential for an efficient implementation. In order to update the values in the queue, you just remove the ones that need updating and re-insert them.

Share this post


Link to post
Share on other sites

Correct me if I am wrong (I am not a C++ programmer), but I don't think you can use a priority queue because you need to update the values.

 

Sure you can.  The STL heap functions don't provide an update function, but you don't exactly need one in the context of A* if you keep enough extra state.  A properly written heap update performs in O(log n) time, but the only way to perform an update using the STL provided functions is to modify the contents directly yourself and then call make_heap() which runs in O(n) time.  This is not desirable.  However, you don't need to do a full heap rebuild; as long as you keep flags to know when a node is opened or closed, you can simply keep throwing on the updated node cost values into your heap and every time you pop off the heap you should check if the node you retrieved is open or not.  If it isn't open, just skip it!

 

This is how I've implemented my A* function.  You may be concerned that you'll have multiple instances of a node in the heap with different costs, but this doesn't actually affect the correctness of the algorithm as long as you have a flag (or some other structure) to determine if the node is in the open list or not.  The heap serves only to keep track of the next min cost node to explore, not to actually tell you if a node is open or not.  And due to the relaxation process of edges inherent in shortest path algorithms, you will always be popping off the most current cost estimates to a node if you have multiple copies.

 

Using a good structure to retrieve the min cost node is critical to good performance in cases where you have a large map to path through, but possibly just as important is the initialization time.  I haven't looked thoroughly at your code but I also suspect your graph initialization can be a bottleneck.  You should profile or instrument your code so you know exactly which parts take the most time.  If your main loop takes up a lot of time, chances are you need a faster structure to retrieve your min cost nodes.  Currently, I'm inclined to believe that most of your performance is dependent the open list data structure, simply because you stated earlier that the performance depends heavily on the length of the path.

Share this post


Link to post
Share on other sites


If the goal is not reachable, it takes up to 10 seconds, which is obviously not acceptable.

 

You should make an effort to never try to find an A* path that is impossible. For a simple static data set, this is pretty straightforward, you can just keep doing flood fills on your graph and assign each node an 'island number'. You can then know in advance that navigating from island 1 to island 2 is impossible and don't even bother trying.

 

If your data is more dynamic then it's trickier, but it might be worth thinking about possible solutions. e.g. If the only way your data is dynamic is with predefined doors opening/closing then you could integrate that information into the islanding system.

 

The other thing to do, if you haven't already done so, is to make sure your pathfinding system can run asynchronously, so you don't stall the game while paths are being calculated.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!