Member Discussions

Hi all,

At the moment, I have the ability for the MOBs to do things, and to react to events...what I'm lacking is a (good) way to let them act independently of outside events.

What I do right now is creation a "tick" action and send it to everything (and their attached logic scripts) in the game. The "thing" can respond to this tick however they want (do damage for, say, a poison effect, or just move around for general AI).

This works ok with the few scripts I have now, but I'm concerned as to how it would scale up to potentially thousands of logic scripts.

This system does let me handle durational effects though. I can simply specify a duration in ticks for the logic module, and when that expires, it deletes itself.

Does anyone have any thoughts on this? Any input is appreciated!

-Kuros

Use an event scheduler and have npcs/objects schedule their own "think" events. Not every npc needs to do something every tick. If you have 1000 npcs that only need to think every four ticks, you can stagger it so 250 npcs get the "think" event every game tick. Another advantage is that if you have scriptable objects/items, you can add a "think" event to them and set it to any frequency, since some objects update slowly (rotting meat) and some objects update quickly (ticking bomb). The objects/npcs with infrequent updates will have little cost, compared to if you had to send them an event every tick whether they need it or not.

Also, when there's no players in the area, nobody's going to see the npcs randomly wandering around, so you can slow it down so they move less often. For things like healing, you can calculate how much to heal based on how many ticks you skipped so they heal the same amount.

Hmm, interesting. I've never worked with an event scheduler, and only have a vague idea of how to go about it. Do you mind expanding on the theory a bit more?

In particular...

When an items/mob is created (via loading or instanced from a template), I should set their update frequency, yes?

Since I don't want to set the frequency manually, I will need some sort of load balancing function, so the game can automatically assign new items/objects to an appropiate "update" group. Is this correct?

It sounds like mobs will need at least two "states"...an idle state, and an "active" state (where they receive ticks every second, like if a player begins moving through the area).

Any more detail or thoughts on this sort of system would be much appreciated. I'm using Twisted, and I think it has its own event scheduler I can use. I'll look into it.

Thanks for your thoughts so far!

-Kuros

Well, an event scheduler allows you to set some event to occur at some point in the future. So you might say "call bomb.explode() at 15 ticks from now". The event scheduler keeps a list of all the events scheduled for a certain time. If you need the bomb to do something for the whole 15 ticks, then an event scheduler doesn't help much. On the other hand, if it's the silent variety and nothing happens in the meantime, then you saved the overhead of calling bomb.countdown() 15 times. You could have 1000 bombs scattered around the city, but since they don't need to "tick" constantly, it's pretty low overhead.

Twisted's scheduler is a bit different in that you schedule using real time units -- seconds and fractions of seconds.

You can actually load balance events reasonably well by making the intervals random. This doesn't work so well for something like bombs, where you need it to explode at a specific time, but for things like mob wandering, it's even better if it happens at random intervals, such as every 4.3-6.6 seconds instead of 5 exactly.

Now, with recurring events, you basically reschedule the event every time it occurs. So after mob.wander() ends, you reschedule it for, say, 6 seconds later. Or if nobody's around, maybe longer. You can have a function to figure it out -- but make sure it's fast, since it'll be called a lot (definitely no scanning the whole area for players; keep track of when players enter and leave the area, assuming you're using an area/zone system.)

You also need to keep track of events so you can delete them later. If someone defuses the bomb, it's really important that you remove the event so the dead bomb doesn't mysteriously explode later. Also, if a mob is killed, you probably want to remove all events that were associated with it.

(Comment added by thyrr on Sun Nov 12 11:03:57 2006)

So, for most cases, you probably don't need the mobs to update every second. Instead of calling mob.wander() every second with a small probability of actually moving, you can call mob.wander() at a random frequency with a moderate probability of moving. You get the same effect for less CPU time. And you save even more if you reduce the frequency when nobody's around.

If you have a decent scripting engine you can do most of this trivially since the script engine willmost likely have its own scheduler. For instance our MUD only fires events for things that have registered a handler. So a tick event is checked against the handler flags. Sure it may check 5000 loaded mobs, but it's just doing a bitwise and on the flags to check for membership. If the onTick even is registered then the thing recieves the event. At this time the script is actually loaded and added to the script scheduler. The script may perform its action immediately, or it may delay until later using a wait (like sleep but called wait since our script syntax allows for direct issuing of in-game commands similar to how a bash shell script works). So then to mimic the bomb described above we might have:

onTick handler...
{
    if( (@countdown = %getVar( @this, lit )) > 0 )
        %setVar( @this, lit, (@countdown -= 1) )
        if( @countdown > 0 )
            TICK
        else
            DO EXPLOSION
        endif
    endif
}

Alternatively since this obviously is synchronized with the tick which means the bomb will only countdown on ticks and explode on the tick, we might have the following as an alternative:

customCommand light
{
    for( @countdown = 10; @countdown > 0; @countdown -= 1 )
        wait 10 secs
        TICK
    endfor

    DO EXPLOSION
}

This shows the other style mentioned without having to work with the scheduler itself. In practice, we have a generic event scheduler, and it's not used. The scripting engine uses it's own sheduler and when we have spells or commands needing timed events we just do them in script instead of C.

I have implemented this on a game of mine (non-MUD); although, I do not keep track of the events once they are made. They just get thrown in to a list that gets looked over once a tick and sends out any events that need to be sent. So in the bomb example I can't get rid of the explosion event. Instead if the bomb is defused there is a switch inside the bombs code that tells me that it is defused and when the explosion event is ran it checks to see the value of this switch. How do you keep track of events?

Michael

Well, you could do that a number of ways. One of which would be to traverse the list and remove the reference to the explosion when the bomb was diffused. Otherwise, most reasonable schedulers, I believe, allow the removal of scheduled operations (which they would do in the same way as above, by finding the reference to the "event" and removing it).

Best of Luck,
-Jess

As mann_jess mentioned, you could delete it from the list. You could also just mark it as "cancelled" and remove it when you get to it, which can be more efficient in some cases. So like what you have now, but instead of checking bomb.defused in the bomb code, the code that sends out events would do the check on event.cancelled. This just makes it more general-purpose.

In my game I use these events to talk between all objects, so I have around 20 or more events in my list of events to be sent at a given time. TO traverse this list and find the one event to discard I think would be more time consumming than checking Bomb.disarm for true or false. (To be honest my code wouldn't have a variable for disarm, it would probably have an entire new state disarm and when that state recieved the event it would traverse a switch statement of possible events with the default being ignor the message, and since explode is not an event the disarm state responds to it would ignor it). So thinking about it now, I would do a bunch of if statements to figure out I don't need the event when the bomb recieved it, and that isn't efficent. I just would feel bad traversing the list of events to be sent to find the event I want, but if I could just go to it and cancel or erase it I would feel like it was worth it. I haven't given much thought on how to optimize this code in my game, but I would like to hear your opinon.

Michael

Then you could easily do what thyrr suggested and put the boolean in the object which handles the list... (or the scheduler)... and check that before calling the function. I don't think there are many bad ways to do this, so essentially, if you can come up with a way it works... it's probably fine. Optimization with if statements probably shouldn't be much of a concern right now.

Best of Luck,
-Jess

Tyche's Immediate Temporal System

Here are the two simple laws of TITS:

An event is issued at the point of a state change.

An event is guaranteed to complete.

Events should not be scheduled to occur at some future point in time as events are by their very nature immediate. That is to say a scheduled event is not really an event but a potential event.

Consider the consequences of the TITS-less implementation above. If something should occurred before the scheduled event like an earthquake, flood, or a hole is ripped in the space time continuum that redirects or otherwise voids the destination, then there is no way the event can occur, be completed and will be invalidated. One must handle that. Or consider the consequences of your present TITS-less system. Either way you will be faced with unsatisfactory results unless you embrace and grasp TITS.

There are many others involving causality and logic errors, a few examples:

Inevitable Death scenario:
Bob eats a poisoned apple.
A death event is scheduled to occur in 10 minutes.
Bob takes an antidote to the poison.
Bob dies in ten minutes.

Elves and the Swordmaker scenario:
Bob is crafting a sword
A sword completed event is scheduled to occur in 2 hours
Bob goes to the local pub gets drunk and returns to smithy in time to receive the completed sword

Non-interruptus scenario:
Bob begins casting a fireball
A fireball spell event is scheduled to occured in 2 minutes
Sam knocks Bob unconscious
Bob completes the casting of the spell and a fireball is produced

All of these problems have different solutions depending on how you want the scenario to play out, most involve carefully removing the non-event from the queue or writing additional to carefully check the validity of the assumed
state.

Event removal may also introduces new problems...

Item Eaters and the Swordmaker scenario:
Bob is crafting a sword
A sword completed event is scheduled to occur in 2 hours
Someone knocks on the shop door and Bob goes to answer it.
The sword completed event is removed from the queue.
Bob returns to an empty work bench and has to start all over again.

Expanded definition of TITS theory:

An event is something that happens at a point in time. Now, not in the future!

An event has no duration. No duration!

Two events may be said to precede or follow another or may be unrelated.

Those that are unrelated are said to be concurrent.

An event is a one way transmission of information from one object or subsystem
to another object or subsystem.

It is not like a subroutine, thus there is no return. An object or subsystem may expect a reply, but this reply would be in the form of an event under control of the second object or subsystem.

Objects or subsystems are considered to be innately concurrent.

It certainly quite difficult to test and build a system or even generate meaningful event-state diagrams to test your system when you don't know the state! Scheduling events to occur in the future implies that these aren't really single discrete events as they actually have a duration, but actually pairs of events with some unspecified/undefined state that exists in between.

A Ruby implementation of TITS can be found in TeensyMud available at all fine mud code repositories.

That's a good summary of the issues, Tyche. I might as well elaborate a little about my own implementation dealing with some of them (not using TITS, but basically the same):

- Every scheduled event has a list of objects.
- Every object (npc, item, etc) has a list of scheduled events.
- Scheduled events have a list of flags like cancel-on-combat, cancel-on-leave-room, cancel-on-quit, etc., per object.
- If a person leaves the room, we can easily cancel all scheduled events associated with the person that are flagged cancel-on-leave-room.
- If a person quits, we can save the list of scheduled events and restore them later, while removing them from the global scheduler.
- No resuming/uncanceling scheduled events in the scheduler. I think Tyche(?) mentioned another scenario where the swordmaker hears someone at the door and goes to answer it, and finds that the sword has disappeared upon returning, along with an hour's worth of work.
- Like Tyche's TITS -- or I guess that's redundant -- events have no duration. I have a class called Task (a subclass of ScheduledEvent) that reschedules itself after firing an event for recurring events. I might eventually write a ResumableTask subclass to deal with the problem above.

I might as well elaborate a little about my own implementation dealing with some of them (not using TITS, but basically the same):

Oh no, that's not at all the same. You cannot schedule events in TITS. All events are immediate and guaranteed to complete. A scheduled event has a duration. What you are describing is like the Erwin, Kyndig and Jobo "event system" snippets. They are actually job/task schedulers. What is comparable to TITS is the event programming done in GUI systems like in Swing or Fox.

Okay, right, I have it backwards. So yours is more like a message passing system. How does that fit in with delayed ... things ... happening (to avoid using any confusing terms)? Sitting around ticking?

Job/task schedulers do fire off events/messages though, by proxy. They're just blissfully ignorant of what happens in between unless told otherwise. The opposite of that is constantly checking the state of the world, as with ticking, which makes it less likely you'll miss something, but takes more CPU.

I think his states must have timers in them. So, is an event in TITS basically just a script attached to a state change?

With today's computers, there's no reason for sitting around ticking to use up any significant amount of CPU, even on a large mud. In fact, you can make the ticks happen really quickly, so that it's not very perceptible that there are discrete jumps going on at all, but things (like progress crafting the sword) seem to be happening continuously.

The approach I took was to reference the event with a weak pointer in the scheduler. If the object that owns the event (has the strong pointer) cancels the event (deletes the strong pointer) or is deleted itself (thus deleting its events), then the weak pointer won't resolve when the event is due to fire, effectively marking it as cancelled but without having to keep the event object around.

-Gromble

Just to clarify some terminology here... What is most often referred to as an event scheduler is really a task scheduler, and TITS is really a message passing system. Right?

How does TITS address the "Elven Swordsmith" scenario above?

How is it different from having a task (event) with incremental substates that simply reschedules itself as your work on the sword progresses? When you answer the door, the task is simply suspended until you resume working on the sword (or trash it, thus deleting the task).

-Gromble

Just to clarify some terminology here... What is most often referred to as an event scheduler is really a task scheduler, and TITS is really a message passing system. Right?

Well the formal definition of TITS is "discrete event simulation", but that's not nearly as fun.

How does TITS address the "Elven Swordsmith" scenario above?

How is it different from having a task (event) with incremental substates that simply reschedules itself as your work on the sword progresses? When you answer the door, the task is simply suspended until you resume working on the sword (or trash it, thus deleting the task).

Objects can have multiple timer objects associated with them. A timer object can be named and can have a variable time. The World object holds the list of Timers and processes them sending :timer events to the object. Timers are also persistent.

In a swordsmith scenario, the player(s) would issue the command to forge the sword and would enter the forging state. Either the regular timer associated with player (or a special timer would be set up) to send a timer event. As long as the player is in the forging state they would accumulate work units on the object. Those work units are sent as events from the player to the proto-sword object. Issuing another command would interrupt the work if it were one that changed the state of the player.

With today's computers, there's no reason for sitting around ticking to use up any significant amount of CPU, even on a large mud. In fact, you can make the ticks happen really quickly, so that it's not very perceptible that there are discrete jumps going on at all, but things (like progress crafting the sword) seem to be happening continuously.

That's probably true most of the time, but languages like Python and Ruby are not exactly blazingly fast.

One person sitting around making swords is pretty simple, and even having every player on the MUD cooking a meal by juggling chainsaws while walking on a tightrope over a pit of kangaroos is not that much. On the other hand, having 10,000 NPCs thinking every 1/10th of a second might stress your system. Or at least put you over the quota on a shared hosting account -- although admittedly I don't think I could run my own stuff on a MUD host, just from the memory usage alone.

(Comment added by thyrr on Fri Dec 8 5:32:44 2006)

Of course I'll tack on my standard disclaimer: find out what works best for you. No warranty offered or implied.

Tyche a écrit:
> Inevitable Death scenario:
> Bob eats a poisoned apple.
> A death event is scheduled to occur in 10 minutes.
> Bob takes an antidote to the poison.
> Bob dies in ten minutes.

This is where I actually do use my scheduler, but events have to be carefully written. It would go something like this instead:

Bob eats a poisoned apple.
An effect is applied to Bob indicating this poison.
A death event is scheduled to occur in 10 minutes and, as a member, has a weak reference to the aforementioned effect.
Bob takes an antidote to the poison. The effect is removed.
In 10 minutes, the event fires and attempts to restore the reference to the poison effect. It can't, so nothing happens.

By using this weak reference idiom in all events where some state must be maintained, we can avoid race conditions like this. An event will only trigger if the neccessary references can be restored.

I think there's little difference then between our two systems, other than what you call a timer object I still call an event object and what you call an event is a callback function in my system.

Player objects in my system have what amounts to a parser stack, where each parser models the range of actions available to the player for their given state. There's a parser for login, account management, character management, in play, bulletin board, etc.

With the swordsmith example, I'd likely push a smithing parser that subclassed the event object and pointed to a proto-sword object. Work on the sword would stop if the player stopped smithing (resulting in the parser getting popped).

-Gromble

I think there's little difference then between our two systems, other than what you call a timer object I still call an event object and what you call an event is a callback function in my system.

Well no.
1) You schedule events, I do not.
2) Your events can fail, mine are guaranteed to complete.

This is a big difference in the way one thinks about programming events.

Timer objects and event objects are essential stateless. That is they carry no state information that belongs to the receiver or target objects.

Now your's and Kaz's sound similar. The weak reference failure avoids the search and cleanup of the event queue, which in turn is different than the Erwin snippet which requires the event to be removed from the queue.

The similarity is we both avoid the search and cleanup of the event queue. You and Kaz by handling event failure, me by never placing an event on the queue that can fail.

I assume since your are scheduling events, that you both use a priority queue, no?

On the other hand, having 10,000 NPCs thinking every 1/10th of a second might stress your system.

One way to minimize this, is only proximate NPC's actively think, and others are put to sleep. An NPC upon wakening do to the proximity of someone or something interesting, will have the results of their past decisions simulated (or summarized).

Another way to minimize this is to group NPCs into population objects. Where thinking is done for the whole group. This is particularly useful for non-sentient/mob type creatures like 100 rats, crowds at a Madonna concert, etc.

I do actually have about 10,000 NPCs "thinking" every quarter of a second, and it doesn't produce any noticeable load. Of course, on most of these intervals they actually do very little, and I am careful not to put anything CPU-intensive into that code. Most of the actual decision-making is done at longer intervals; I think 1/2 second if the NPC is having a conversation, 1 second if he's in a fight, and 5 seconds otherwise.

As long as I avoid searches over everything-in-the-world (every character or every room, for example) I don't have speed issues even without any fancy structures to support it. At one point many years ago we experimented with removing unoccupied regions from memory (and thus shutting down all of the NPCs there) but that was for memory reasons rather than speed reasons, and thankfully memory gut cheaper so we don't have to do that any more. It was a real pain - I recommend avoiding it.

I do actually have about 10,000 NPCs "thinking" every quarter of a second, and it doesn't produce any noticeable load. Of course, on most of these intervals they actually do very little, and I am careful not to put anything CPU-intensive into that code.

It wouldn't. Then again the definition of "thinking" is a rather slippery thing. The more "thinking" that is done, the more CPU intensive it will be. For instance, a procedural reasoning system is going to be more CPU intensive.

An existing Diku-Mercish tick system's performance can be improved quite a bit simply by using a subscribe/publish pattern for tick events, instead of checking every living thing in the system at every tick. Of course there is no need for improving performance, if the sort of "thinking" you are doing ain't sucking the wind out of your account's quota anyway. It's just better to design the pieces to be flexible enough to change.