Delayed effects

Thanks for the response, Lorenzo. After I posted, I searched this group
for older posts on the same topic, and found some great descriptions of
how a priority queue works. I had the wrong idea of what a queue like
this actually was--it's perfect! The best I found is:
Find the lowest 'energy' in the queue(or have previously sorted it)->
Subtract that value from all in the queue->
Give that actor/event its turn(because its 'energy' is now 0)->
Repeat. Right now, I'm learning what I need to do to:
1. Make the queue. I could use a list as my queue, right? Do I want
to?(i.e. is it efficient?)
2. Either (a) have the queue accept normal actors AND events, giving
actors their normal turn when their time comes, or (b) have the queue
accept only events, and simply make one event 'this actor gets a turn'.
I thought of (b) as I was typing, so I guess I'll use that one. =d
I think this looks promising. Any opinions?
 >> Stay informed about: Delayed effects 

ds_creamer wrote:
> Thanks for the response, Lorenzo. After I posted, I searched this group
> for older posts on the same topic, and found some great descriptions of
> how a priority queue works. I had the wrong idea of what a queue like
> this actually was--it's perfect! The best I found is:
> Find the lowest 'energy' in the queue(or have previously sorted it)->
> Subtract that value from all in the queue->
> Give that actor/event its turn(because its 'energy' is now 0)->
> Repeat.


Or equivalently in logic but at lower CPU costs:
Find the thing that has the lowest "next action" time.
Update the system time to match its "next action" time.
Let it perform its action.
Update its "next action" time by adding the amount of time
its action takes.
Repeat.

If you are clever you can code this to take sublinear
time w/r/t the number of things that act. If you don't
feel clever, you can code it in linear time and then
replace it later if it becomes a performance bottleneck.

Bear
 >> Stay informed about: Delayed effects 

On Fri, 24 Mar 2006 14:57:55 +0100, ds_creamer
<dcreamer0001.RemoveThis@email.vccs.edu> wrote:

> Thanks for the response, Lorenzo. After I posted, I searched this group
> for older posts on the same topic, and found some great descriptions of
> how a priority queue works. I had the wrong idea of what a queue like
> this actually was--it's perfect! The best I found is:
> Find the lowest 'energy' in the queue(or have previously sorted it)->
> Subtract that value from all in the queue->

As long as there aren't too many things in the queue I guess that's ok.
In my RL I have a time variable that stores the current time and when I
add an Item that should happen after 100 ticks I add it with (time + 100)
as the key, that way I don't have to update the entire queue every time.

> Give that actor/event its turn(because its 'energy' is now 0)->
> Repeat. Right now, I'm learning what I need to do to:
> 1. Make the queue. I could use a list as my queue, right? Do I want
> to?(i.e. is it efficient?)
Depending on which programming language there might be something even
better included, Java has the PriorityQueue class and I'm pretty sure
there is something similar in c++'s STL.

> 2. Either (a) have the queue accept normal actors AND events, giving
> actors their normal turn when their time comes, or (b) have the queue
> accept only events, and simply make one event 'this actor gets a turn'.
> I thought of (b) as I was typing, so I guess I'll use that one. =d
> I think this looks promising. Any opinions?
>

(b) sounds like pretty much exactly what I have in my project. I have a
abstract class Event with a method called execute() that is called when
it's that events to happen, then I extend that class for every type of
event. Some events I have now are PlayerMoveEvent MonsterMoveEvent
FireSpreadEvent, TimedExplosiveEvent (that one is fun. ),
PlayerRegenHealthEvent and so on.
 >> Stay informed about: Delayed effects 

Colin MacIntyre wrote:
> "Ray Dillinger" <bear.TakeThisOut@sonic.net> wrote in message
> news:44242f4c$0$58064$742ec2ed@news.sonic.net...


>>If you are clever you can code this to take sublinear
>>time w/r/t the number of things that act. If you don't
>>feel clever, you can code it in linear time and then
>>replace it later if it becomes a performance bottleneck.
>
>
> Sorry, what is w/r/t?

With respect to. I mean to say that you can make the
process take time less than proportional to the number
of things that have a "next action" coming up.

The implementation ds_creamer mentioned would take
linear time. That is, there's an element where you
update everybody's "time left" that takes twice as
long if you have twice as many actors, and there's
nothing that grows with number of actors at a rate
worse than that.

A "classic algorithms" priority queue can take
logarithmic time -- that is, there's an element
that grows such that with twice as many actors it
would take one step longer.

But with dungeon movement in particular there are
regularities about the problem that allow you, for
very few restrictions, to code something that's
*not* a classic priority queue and lets you do things
in constant time or very close to it.

Bear
 >> Stay informed about: Delayed effects