   A better priority queue for Dijkstra's?
  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 algorithmTile *currentTile = NULL;// initialize all of the Tile pointers for the algorithm and add them to Vfor (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 Vmake_heap(V.begin(), V.end(), cmp());// run dijksta's algorithm until we have found the destination Tilewhile (currentTile != inDestinationTile){// get the smallest Tile pointer from the front of the heapcurrentTile = V.front();// Relax all of the current Tile's valid neighborsTile *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 headvector<Tile *>::iterator startIterator;startIterator = V.begin();V.erase( startIterator ); // heapify Vmake_heap(V.begin(), V.end(), cmp());}{Ed.  Sorry for the crappy alignment.)[edited by - ryansobol on May 28, 2004 9:45:42 PM]
  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. ;  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. ;  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). ;  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.  ;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.) ;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];  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). ;  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). ;  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]