hi, I use the stl priority queue in a game to hold game events (event with smallest timestamp on the top of the queue). But when I have many Objects (about 200-300) that send events at different times, the delivery of the events gets slow. On the other hand, when all Objects send events at the same time, the speed is ok. Is a Priority Queue inefficient when used in that way, should I use a normal queue instead? Any experience or suggestions? bye chris

This sounds like the exact reason why you''d want to use a priority queue, so I can''t see why it would be slow unless you''re doing something wrong or inefficient. The rate of additions to the queue shouldn''t make much difference. What type of object do you store in the queue?

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

hi, maybe I have another problem.
I store event Objects in the Queue (no pointers to event Objects). Don''t know if it would be better to store pointers, cause I don''t know how it''s implementet in the STL.

Your''re maybe right Wildfire, I should try to store pointers in the queue.

A normal queue won''t work for me, cause you can add a message to the queue with a timestamp in the future. So it remains in the queue until the right time comes to handle it.

If you are storing events themselves and not pointers to events then you are most likely suffering from a copy operations each time you put an object in and take it out. Also, depending on the implementation of the queue, it may be copying each event when one gets added or one gets removed. This is implementation dependent.

I am also unsure of what you mean by ''events at different times''. Are you putting events into the queue that are going to be posted much later? If so, then you must be sorting the queue every time something is added. This invokes the copy constructor as well. The larger your structure, the longer the copy takes.

In contrast, if you are using pointers then the copy is only a (on win2k) 32 bit copy, which is very quick.

You might also want to think about two queues, one that is ''immediate'' or close to that - messages that are to be passed next frame and don''t need to be sorted, and those that are further in the future, which do need to be sorted. In this way you are sorting only a subset of all messages in the game.

Alternatively, it might not be sensible to put messages for the future in a queue at all. In my system I have an event manager that is only responsible for collecting events from the current frame, and sending them out at the end of the frame so that next frame they can be acted on. Anything that takes place in the future is tied to a clock manager that will fire off an event once the clock expires.

Not sure if you really need so many events, but then you havn''t describe the kind of game system you are working on.

Nonetheless, pointers should give you a speed increase. What I would do is, on game start, allocate an array of, say, 200 events, and then put the address of each of these into a list. When you need a new event, get it from the ''free list'' and put it''s address into the priority queue. Once it comes out of the queue, put it back into the list. This should be speedy and avoids dynamic allocations during run time - it also lets you put a cap on the events so that, if suddenly you need 300 events, you''re aware of this and can decide if allocating more is the right thing to do, or revisiting your various subsystems is better.

Best of luck.

thanks for the reply Sphet. It''s a very interesting idea to put only the future events into a priority queue.
about the game: it''s a rpg game. there are to types of events: events that are posted by the player. these events should normaly be handled very quickly. The other events are from npcs. the idea was to let every non player character post a TICK event to itsself in a short intervals, so there can be npcs with different reaction speed, when posting TICK events in different intervals.
Do you have any idea how efficient this system is, or how to improve it?

The priority_queue contains Event objects. Every Event object saves a timestamp. So when the queue looks at its top and sees an object with a timestamp "in two hours", and the current gametime timestamp is "now", no event is handled, until the gametime reaches the "in two hours" timestamp or an event with an earlier timestamp is added to the queue.

Personally, I''d just say store pointers (or smart pointers) to your objects, make sure that you alter the sorting function to take this into account, and leave it. Your slowdown is almost certainly due to the time involved in copying events, and moving to pointers will eliminate this.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]