Jump to content
  • Advertisement
Sign in to follow this  
fooman_69

Queue q

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

hiya, I asked in the AI forum about what kinda list to use for A* algorithm and was told to use a priority queue. I have a few questions about this. (the ppl in the AI forum are slow to respond sometimes hehe) 1. What is the difference between a queue and PRIORITY Queue?? 2. Since I need to sort the queue, is it still a queue... since it won't really be FIFO.

Share this post


Link to post
Share on other sites
Advertisement
A priority queue isn't FIFO, it is sorted by the priority you give the data. In C++ in the STL, they use a -edit- vector as the underlying structure.

Queue works like a line, FIFO. Priority queue doesn't matter about what was first in, the first out is the one with the highest priority (-edit- What you use for the Compare function is what determines highest priority).

SGI's info on the priority queue here

-edit- My mistake, SGI's p-queue uses a vector, not a rb-tree.

Share this post


Link to post
Share on other sites
Can you explain a bit about this Red-Black tree structure? I've heard of it, but never have had to deal with it before. Guess I'll look around.

Share this post


Link to post
Share on other sites
Priority-queue
wiki
Also read about heaps, because that is a way to make a priority queue.


(For RB-Trees)
Googling is probably you quickest bet, it is well known and documented.

A java version of how it works
here

wiki for RB-tree

Share this post


Link to post
Share on other sites
a priority queue is definately not a FIFO ... but it's a queue in the sense that items are added through one end and pulled out through the other (as opposed to a stack where the are (logically) pushed in and pulled out through the same opening.

A priority is RELATED to a queue because each item in it WITH THE SAME PRIORITY should act as if it is in a queue (there are no line jumpers allowed between items of equal priority).

So here's a Queue

ENTRY POINT - ITEM 4 - ITEM 3 - ITEM 2 - ITEM 1 - EXIT POINT

Here's a Priority Queue (letter represents an item's priority, number it's insertion order)

ENTRY POINT
C ENTRY POINT - ITEM C10 - ITEM C7 - ITEM C5 - ITEM C4
B ENTRY POINT - ITEM B11 - ITEM B6 - ITEM B1
A ENTRY POINT - ITEM A9 - ITEM A8 - ITEM A3 - ITEM A2
- EXIT POINT

I hope the way I drew that shows ok ... it's meant to be both 3 seperate lines (queues) and the meta / overall queue ...

the orders of the individual queues are (10,7,5,4) (11,6,1) (9,8,3,2) [notice these ARE in normal FIFO order] and the current order of the meta queue is (10,7,5,4,11,6,1,9,8,3,2) [pririty order first, FIFO second]

Share this post


Link to post
Share on other sites
I am very confused. Apparently I should read up on heaps as well to properly use the priority queue... correct?
Also, I need to get the smallest element, not the largest. Is this what the priority queue's .top() method returns? I have seen an websites that it returns the largest element, while others say smallest.
If I want to store structs in the queue, what must I do for the queue to know what to prioritize? Should I override < operator?
Finally, do I need to write a sorting routine for these things at all, or do they sort themselves everytime I call .push()?
Ah, so many questions. haha

If anyone can write some basic priority queue code in which the queue contains structs, that would be beyond great.

Share this post


Link to post
Share on other sites
You don't need to really know how heaps work to use a priority queue. The basic thing to keep in mind is that the top of the priority queue is either the max or min value you've pushed in, depending on how you specify the sorting function.

Overriding operator<() is probably the easiest way to work with a priority queue, but you can work with stand alone functions if that's what you want. Example:


#include <vector>
#include <queue>
#include <iostream>

struct SomeStruct {
int x;
int y;
};

bool compare_x_lessthan(const SomeStruct & lhs, const SomeStruct & rhs) {
return lhs.x < rhs.x;
}

bool compare_x_greaterthan(const SomeStruct & lhs, const SomeStruct & rhs) {
return lhs.x > rhs.x;
}


int main(int, char **) {
typedef std::priority_queue<SomeStruct, std::vector<SomeStruct>, bool (*)(const SomeStruct &, const SomeStruct &)> MyPriorityQueue;

MyPriorityQueue queue_1(&compare_x_lessthan);
MyPriorityQueue queue_2(&compare_x_greaterthan);

SomeStruct some_structs[] = { { 0, 0}, {-1, -1}, {1, 1}, {0, 2}, {5, - 3} };

queue_1.push(some_structs[0]);
queue_1.push(some_structs[1]);
queue_1.push(some_structs[2]);
queue_1.push(some_structs[3]);
queue_1.push(some_structs[4]);

std::cout << "less than priority queue:" << std::endl;
while (!queue_1.empty()) {
std::cout << queue_1.top().x << "," << queue_1.top().y << std::endl;
queue_1.pop();
}

queue_2.push(some_structs[0]);
queue_2.push(some_structs[1]);
queue_2.push(some_structs[2]);
queue_2.push(some_structs[3]);
queue_2.push(some_structs[4]);

std::cout << "greater than priority queue:" << std::endl;
while (!queue_2.empty()) {
std::cout << queue_2.top().x << "," << queue_2.top().y << std::endl;
queue_2.pop();
}


return 0;
}


In this case MyPriorityQueue stores SomeStructs, is implemented in terms of std::vector, and uses function pointers to determine the order of elements. When I create the priority queues, I pass which function

Share this post


Link to post
Share on other sites
SiCrane and everyone else: THANK YOU!!!!!!!!!!!!!!! I have read up on heaps, and those have branched off into more things which I now am familiar with. So thank you very much for the links and info!
I have one question for SiCrane tho, why the typedef? I used it, but I'm not sure why you did it like that. Is there a way you could have told the priority_queue what function to use in the declaration??

actually, I do have a problem. I am getting an error on this code:
#ifndef EG_GHOST
#define EG_GHOST

#include <queue>
#include <vector>
#include <windows.h>
using namespace std;

struct sLocation
{
int posX;
int posY;
int sum;
int totalDistance;
int heuristic;
};

typedef priority_queue<sLocation, vector<sLocation>, bool (*)(const sLocation &s1, const sLocation &s2)> PriorityQueue;

class Ghost
{
public:
Ghost(CHAR_INFO mapIn);
void SetGoal(int x, int y); //Sets the goal position
void SetStart(int x, int y); //Sets the starting point position
bool FindPaths();
private:
CHAR_INFO map;

sLocation *goalNode;
sLocation *startNode;
vector<sLocation> closedNodes; //Priority Queue to hold closed nodes
PriorityQueue openNodes(&CompareSumLessThan); //Priority Queue to hold open nodes
int index; //Counter for nodes

//Methods
void SetHeuristic(sLocation *current, sLocation goal);
void SetDistance(sLocation *node);

bool CompareSumLessThan(const sLocation &s1, const sLocation &s2);
};

#endif


The error has a prob with the PriorityQueue openNodes(&CompareSumLessThan); line at the '&'. I am missing something here...
PS. This class is not finished. So don't worry about unfinished business other than the priority_queue set up.

[Edited by - fooman_69 on January 8, 2005 1:23:27 PM]

Share this post


Link to post
Share on other sites
I think the error you are getting is because you are calling CompareSumLessThan before you declare it 7 lines later.

move "bool CompareSumLessThan(const sLocation &s1, const sLocation &s2);" above the line "PriorityQueue openNodes(&CompareSumLessThan);" and it should fix that problem. Make sure you actually code the CompareSumLess function as well.
You probably don't need that function as part of that class as well because I don't think it has to do with your Ghost class specifically.

Good luck.

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!