A better priority queue for Dijkstra's?

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.

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).

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]

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]

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

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

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]