Archived

This topic is now archived and is closed to further replies.

A better priority queue for Dijkstra's?

This topic is 4943 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

Hello, I'm developing my pathfinding algorithm, using Dijstra's single-source shortest distance algorithm, for a simple Pac-Man like game. However, I'm seeing some terrible perfomance drops using a STL based priority queue, primarily the make_heap operation. Here is my code so far. I know its not pretty, but I would appreciate any feedback.
// the current Tile being visited by the algorithm

Tile *currentTile = NULL;
	
// initialize all of the Tile pointers for the algorithm and add them to V

for (int panel = 0; panel < NUMBER_OF_PANELS; panel++)
{
        for (int column = 0; column < NUMBER_OF_COLUMNS; column++)
	{
		for (int row = 0; row < NUMBER_OF_ROWS; row++)
		{					
			Tile *node = getTileAt(panel, column, row);
			
			node->parent = NULL;
			
			if (node->equals(inSourceTile))
			{
				node->distanceCost = 0;
			}
			else 
			{
				node->distanceCost = INT_MAX;
			}
			
			V.push_back(node);
		}
	}
}
	
// make a heap out of V

make_heap(V.begin(), V.end(), cmp());

// run dijksta's algorithm until we have found the destination Tile

while (currentTile != inDestinationTile)
{
	// get the smallest Tile pointer from the front of the heap

	currentTile = V.front();		
			
	// Relax all of the current Tile's valid neighbors

	Tile *tileUp, *tileDown, *tileLeft, *tileRight;
	if (currentTile->getUp())
	{
		tileUp = getTileAt (currentTile->getUp());
		relaxEdge (currentTile, tileUp);
	}
	if (currentTile->getDown())
	{
		tileDown = getTileAt (currentTile->getDown());
		relaxEdge (currentTile, tileDown);
	}
	if (currentTile->getLeft())
	{
		tileLeft = getTileAt (currentTile->getLeft());
		relaxEdge (currentTile, tileLeft);
	}
	if (currentTile->getRight())
	{
		tileRight = getTileAt (currentTile->getRight());
		relaxEdge (currentTile, tileRight);
	}

	// remove the Tile pointer from the front of the head

	vector<Tile *>::iterator startIterator;
	startIterator = V.begin();
	V.erase( startIterator );
 
	// heapify V

	make_heap(V.begin(), V.end(), cmp());
}
{Ed. Sorry for the crappy alignment.) [edited by - ryansobol on May 28, 2004 9:45:42 PM]

Share this post


Link to post
Share on other sites
I''m no AI expert but as far as I know, Dijkstra''s algorithm is pretty inefficient. A* can minimize the amount of things you need to check every time you need to find a path. And if it''s for a Pac-Man clone (you said Pac-Man like though so it might not be a Pac-Man clone) I wouldn''t use any pathfinding, I''d probably just make the ghosts move up and down and left and right based on where you are in relation to them.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The STL heap functions are very unintuitive unless you already know how a heap works, and the way you are using the heap functions is incorrect. make_heap is an O(n) operation that usually only needs to be done once, when starting with a group of numbers that are not already a heap.

You are treating your entire vector of panels as a heap, which is completely unnecessary since most of them have not even been discovered. This makes the heap much larger than it has to be.

The STL heap functions also do not include functions for updating item already in the heap. I guess this is why you were remaking the heap every time. Updating an item in the heap can actually be done in O(log(n)) time. Adding and removing items also takes O(log(n)) time. Updating an item in the heap also requires knowledge of where in the heap the item is, which is once again something that can''t really be done using the STL heap functions.

To really implement the algorithm efficiently with a heap, you need to know how a heap works and possibly implement your own heap code. Or maybe just not use a heap, if that''s easier.

Without the heap the algorithm isn''t as efficient, but for small graphs (maps, number of tiles, whatever) maintaining a sorted linked list shouldn''t be too bad. You give each tile a pointer to the previous and next item in the list, and you keep the list sorted by inserting items in the correct position and update items by removing them from the list and looking backwards or forwards in the list to find where they should now go. Actually this is similiar to how you would maintain a heap, it is just that heaps are slightly more complicated so many people are more comfortable working with linked lists. Also note that the list or heap should only contain tiles that are in the open set (tiles that are adjacent to a visited tile but have not yet been visited). Initially only the starting tile is in the open set, then it is removed and the adjecent tiles are placed in it, and so on.

Share this post


Link to post
Share on other sites
Erasing out of the middle of a vector is also inefficient. It causes all elements after the erased element to be copied as they are shifted to fill in the hole.

I am also a bit confused about your comment about using a priority_queue. Are you using a vector and creating a heap, or are you using priority_queue?

Before changing algorithms, I would suggest for looking up information on how priority_queue and make_heap work, as they are both useful (and easy to misuse).

Share this post


Link to post
Share on other sites
Thanks for all of your prompt replies.

BrianL: You may be right about the copying issue. However, my profiler reports that the make_heap operation hogs 25 - 40% of my CPU cycles. Obviously, I should focus my optimization here.

I am using a vector and the push_heap and make_heap operations from the STL. The reason I choose this is because I could not figure out how to modify OBJECTS POINTERS within a priority_queue. My experiements with priority_queues led me to believe that the container cannot use the operator< correctly when dealing with object pointers. After modifying the priorty variable of an object pointer inside the priority_queue, the container tried to maintain the heap property. However, it compared memory addresses of the object pointers instead of the priority variable. My real problem is that I''m not as familar with the STL as I should be.

AP: I''m familiar with the pseudo-code and running time of heaps, priority queues, and dijkstra''s algorithm. My implementation lacks the same familiarity.

You have correctly discovered my graph uses a large number of nodes. Unlike Pac-Man''s single maze, my game has six mazes during the game. I agree that my heap is large, but not excessively large that Dijkstra''s becomes inefficient. I would like to keep the benefit of exploring onto adjacent mazes derived from Dijkstra''s.

Actually, the STL priority_queue and heap operations do allow you to modify the elements inside the container class and maintain the heap property. I''m passing in an functor, which is a object function, to the push_heap and make_heap operation. The heap and priority_queue order the elements based on the functor argument. The default argument is less, which works great for primitives and objects. If T is an object pointer then the functor only compares memory addresses, like I mentioned before. That is why I had to create a homebrew functor. My apologies for not posting the this sooner.


struct cmp {
bool operator()(Tile *t1, Tile *t2) const
{
return t1->distanceCost > t2->distanceCost;
}
};


If anyone knows how to use and modify object pointers in the priority_queue class please let me know. As I mentioned before, I''m still new to the STL.

Samith: Dijkstra''s algorithm is used to route data across many network protocols. If used properly, I don''t understand why it wouldn''t be efficient in games.

Hopefully, from this post, you realize that my game is not a Pac-man clone.

Share this post


Link to post
Share on other sites
quote:

"Actually, the STL priority_queue and heap operations do allow you to modify the elements inside the container class and maintain the heap property."



If I understand what you mean, you may be incorrect. I think the idea of a heap is to do a sort on insertion to avoid sorting the entire heap every time you add a new element. To do this, it expects the heaps ordering to not change.

If you need to modify elements which the heap sorts on, then you probably need to remove them from the heap, make the modification, then re-insert them.

On the priority queue side, this works for me:


#include <stdafx.h>
#include <queue>

struct Tile
{
int m_iPriority;
};

struct TileCompare
{
bool operator()(const Tile* plhs, const Tile* prhs)
{
return plhs->m_iPriority < prhs->m_iPriority;
}
};

Tile* MakeTile(int i)
{
Tile* pTile = new Tile;
pTile->m_iPriority = i;
return pTile;
}
int main(int, char*)
{
typedef std::priority_queue<Tile*, std::vector< Tile* >, TileCompare > TileQueue;

TileQueue queue;
queue.push(MakeTile(3));
queue.push(MakeTile(10));
queue.push(MakeTile(1));
queue.push(MakeTile(8));

while (!queue.empty())
{
Tile* pTile = queue.top();
queue.pop();
delete pTile;
}

return 0;
}


(Take all of this with a grain of salt, as I haven''t spent much time with the priority_queue class or the heap functions in a while.)

Share this post


Link to post
Share on other sites
quote:

If you need to modify elements which the heap sorts on, then you probably need to remove them from the heap, make the modification, then re-insert them.



You are correct. I see some significant time savings by removing nodes with adjacent edges from the heap, modifying their distance cost, and reinserting them back into the heap. However, I think priority_queue only has an operation to pop from the top of the heap. Can you think of another way to remove any node from a heap, while maintaining the heap property, without creating my own homebrew container class? I'm not as familiar making template classes as I am using them.

Also, perhaps I'm looking at this from the wrong angle. Is there a better container to implement Dijkstra's than a priority queue?

[edited by - ryansobol on May 29, 2004 5:58:30 PM]

Share this post


Link to post
Share on other sites
What you probably want to do is use a set instead of priority_queue if you really want to stick with the base STL structures. This way you can have log(n) removals and insertions and O(1) access to the top element.

priority_queue is in fact simply a vector that uses make_heap, push_heap and pop_heap (see reference [2] here).

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
A set would be easier to use in this case than the STL heap functions, or the STL priority queue which is most likely a wrapper for the heap functions.

For the best performance, you''d want to use a binary heap, and use it the way it is meant to be used, since it has lower overhead than a set. I think I implemented this once before for A*, and I ended up using a binary heap stored in a vector and coding some simple bubble up and bubble down functions and having each node keep track of its current index in the vector/heap.

When I say your heap is big, I don''t mean that heaps aren''t practical for large numbers of nodes, what I mean is the way it is coded your heap is always maintained as if it was the entire vector of tiles. Tiles that haven''t been visited yet don''t need to be counted as part of the heap, so there is no reason to do something like make_heap(V.begin(), V.end(), cmp()); when only the first 50 tiles have been visited. This is why make_heap is using up so much time. You might have 10,000 tiles, and if only 100 of them have been visited, the heap only needs to contain those 100 (minus any that have already been expanded).

Share this post


Link to post
Share on other sites
You may want to check astar.h, as written by my (soon to be) collegue Thaddaeus Frogley. push_heap and pop_heap from the <algorithm> header may be what you are looking for.

Alex

[edited by - alexjc on May 30, 2004 5:54:39 AM]

Share this post


Link to post
Share on other sites
alexjc: Thanks for the astar implementation. Eventhough I still want to use Dijkstra's algorithm, this will definitely benefit the community.

AP: I'm not familiar with the STL set class. I'll check it out. However, I would love to use the priority_queue class if I could efficiently change the priority variable of any element already inside the container.

What is the difference between a bineary heap and a regular heap? I assume its a heap with a binary search operation. If so, this would be a good way to search for and remove any element inside the priority queue. However, I was hoping I wouldn't have to write my own container class.

I totally agree with you; I would love to only maintain a heap of 50 discovered Tile pointer objects rather than 1000. I'll investigate that possibility.

Premandrake: A set that has O(log n) time insertions and removals and O(1) time access to the top-most element sounds awefully similar to a priority_queue. Would you care to elaborate a little more?

ALL: Once I've solved my dilemma, I'd like to post my findings back to this thread. Please check back here often so we can all reap the benefits.

[edited by - ryansobol on May 30, 2004 1:13:00 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by ryansobol
Eventhough I still want to use Dijkstra''s algorithm, this will definitely benefit the community.



heh, it should benefit YOU directly. What A* does here is almost exactly what your inner loop of Dijkstra will be doing (at least as far as the priority queue pushing and popping is concerned).

Alex

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The code linked by alexjc uses push_heap and pop_heap to maintain a vector of indexes into the actual vector of nodes. A functor is passed to the operations to make them properly compare the nodes instead of comparing the indexes directly.

A binary heap is what is implemented by push_heap and pop_heap. it is a heap where each node of the heap has two children (except the nodes towards the bottom of the heap). It is very efficient because the entire heap can be kept in an array and the children and parents of a node can be found based on the node''s index, meaning that no extra storage is required for pointers to children and parent nodes. Other types of heaps are more complicated and require extra pointers to be stored, but these heaps are useful only for special cases where special operations are used frequently. For general use binary heaps are generally faster because of the lower overhead.

Looking at the code, it seems someone found a non-obvious way to use the push_heap function to update values in the heap when the value is increased, by realizing that any part of the top of a binary heap is also a binary heap.

Share this post


Link to post
Share on other sites
ryansobol: set is one of the standard containers used in the STL. It is very similar to priority_queue, but does not have the same space guarantee (in fact it is usually implemented with a red-black tree, so there is usually a decent overhead per node).

To use it as you use your priority queue here you would do something like this:


#include <set>

int main() {
std::set<int> q;
while (!q.empty()) {
// Grab the first element in the set (the smallest element)

int cur = *q.begin();
// Remove it from the set

q.erase(q.begin());

if (cur == endval) break;

for (all children) {
q.insert(child);
}
}
}

Share this post


Link to post
Share on other sites
I conducted an experiment to verify whether or not priority_queue's push and pop methods maintain heap property while elements in the queue are modified. This code is a modification of BrianL's example.


#include <iostream.h>
#include <queue>

struct Tile
{
int m_iPriority;
};

struct TileCompare
{
bool operator()(const Tile* plhs, const Tile* prhs)
{
return plhs->m_iPriority > prhs->m_iPriority;
}
};

int main(int, char*)
{
typedef std::Priority_queue<Tile*, std::vector< Tile* >, TileCompare > TileQueue;

TileQueue queue;

Tile* tile1 = new Tile;
tile1->m_iPriority = 2;
queue.push(tile1);

Tile* tile2 = new Tile;
tile2->m_iPriority = 4;
queue.push(tile2);

Tile* tile3 = new Tile;
tile3->m_iPriority = 6;
queue.push(tile3);

Tile* tile4 = new Tile;
tile4->m_iPriority = 8;
queue.push(tile4);

Tile* tile5 = new Tile;
tile5->m_iPriority = 10;
queue.push(tile5);


Tile* pTile = queue.top();
cout << pTile->m_iPriority << " ";

tile5->m_iPriority = 7;

queue.pop();


pTile = queue.top();
cout << pTile->m_iPriority << " ";

tile3->m_iPriority = INT_MAX;

queue.pop();

pTile = queue.top();
cout << pTile->m_iPriority << " ";
queue.pop();

pTile = queue.top();
cout << pTile->m_iPriority << " ";
queue.pop();

pTile = queue.top();
cout << pTile->m_iPriority << " ";
queue.pop();

delete tile1;
delete tile2;
delete tile3;
delete tile4;
delete tile5;

return 0;
}


My results were "2 4 7 8 2147483647 ". From the results of the experiment, it appears that the pop method maintains heap property even if elements inside the priority_queue are modified. Also note that the elements of the priority_queue are object pointers.

[edited by - ryansobol on May 30, 2004 6:02:53 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The fact that the heap property was apparently maintained in your test is a mere coincidence. Popping an element from a binary heap involves swapping the first and last elements, decreasing the size of the heap by 1 (so that the heap no longer includes the last element, which is the one that was just popped off), and then bubbling the first element in the heap down to maintain the heap property. As the heap grows, it becomes increasingly unlikely that this will maintain the heap property in the face of outside changes that the heap is not aware of.

Here''s a step by step of what happened in your heap that caused it to still maintain proper order:

First all the elements are popped on, and they are put on in heap order, so nothing needs to be bubbled up:

2 4 6 8 10

Tile 5 is changed from 10 to 7:

2 4 6 8 7

An element is popped off. First it is swapped with the last element, then the vector is shrunk and the first element is bubbled down:

7 4 6 8 2
7 4 6 8
4 7 6 8

Tile 3 is changed from 6 to INT_MAX:

4 7 INT_MAX 8

and then everything is popped off...the last change didn''t even cause the heap order to be violated, so clearly nothing can go wrong from here.

Try another experiment. Generate 1000 tiles with random values and pop them into a priority queue. Then change a few of them to a different random value. Then pop the values from the priority queue while verifying that they are in order. Remember to seed the number generator. In fact, maybe automatically run a bunch of trials, and have it report how many trials the numbers came out in the wrong order.

Share this post


Link to post
Share on other sites