Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

DarkBASIC Professional Discussion / Ingame Events System

Author
Message
BlackChaos
16
Years of Service
User Offline
Joined: 2nd May 2010
Location: London
Posted: 8th Sep 2012 20:25 Edited at: 8th Sep 2012 20:31
Link
Ello EveEryoNE

I'm close to finishing my 3d Side-Scroller engine and game.
I need help with an in-game events system that does not! eat frame rate.

I've been thinking and writing down ideas but most of them involve For-Next Loop which when large enough EATS! frame rates leaving a 3d game with below 50 frames per-second.

Any help, adVice or food would be nice!

//My current idea goes like this (Please note this is just a rough idea that I've not even tested in DBP).



Thanks,

AEngine 2012 Ameadus Project Feedback or Food o0
Back to top
Profile PM Email
BatVink
Moderator
23
Years of Service
User Offline
Joined: 4th Apr 2003
Location: Gods own County, UK
Posted: 8th Sep 2012 20:43
Link
I would suggest reading about Finite State Machine logic. I could try to explain here but there is a lot of information already out there.

Once you get the grasp of FSM, work out how to embed one within another, so that you vastly reduce the number of checks you are making each cycle.

Back to top
Profile PM Email
BlackChaos
16
Years of Service
User Offline
Joined: 2nd May 2010
Location: London
Posted: 8th Sep 2012 21:24 Edited at: 8th Sep 2012 21:24
Link
Thank
This is interesting stuff.

Heres a link to the info I found on FSM when used in computer games.
http://blog.manuvra.com/modeling-a-simple-ai-behavior-using-a-finite-state-machine/

AEngine 2012 Ameadus Project Feedback or Food o0
Back to top
Profile PM Email
TheComet
18
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 8th Sep 2012 22:52 Edited at: 8th Sep 2012 22:53
Link
Another tip: Instead of looping through all possible events and checking if it's active, you should use an event list. Something like this:



AddEvent( cmd$ ) to add events to the list
RemoveEvent( index ) to remove events from the list
ProcessEvents() will process all events currently in the list

This way you're only looping through the events that actually have to be processed.

TheComet

"Why geeks like computers: unzip, strip, touch, finger, grep, mount, fsck, more, yes, fsck, fsck, fsck, umount, sleep." - Unknown
Back to top
Profile PM Email Website
Mage
Valued Member
19
Years of Service
User Offline
Joined: 3rd Feb 2007
Location:
Posted: 8th Sep 2012 23:01 Edited at: 9th Sep 2012 04:31
Link
He's right, being efficient is really important.
I would suggest a few simple techniques to improve performance.

1. Cheat.
Do everything you can to fake checks, cut workload corners, etc. Don't check a circle radius use a box it's close enough. Don't use square root, compare squared values instead. Process anything you can in advance. If stuff is too far away, ignore it. It's all about getting the result you want.

2. Don't do it all, every frame.
What's wrong with taking an extra 10ms or whatever. You can program the game to simply take like 2ms on processing the list, then leave and handle other things like drawing the screen, then on the next frame simply pickup where it left off. You can convert lost frames into fewer checks, and you probably won't care.

3. Don't run checks every frame.
If you arranged checks to only occur every half or quarter of a second, that makes checking 500 times faster on average. A massive speed increase. If checking is too big of a hit and you get lag spikes, suggestion #2 should be applied also.

4. Make checking easier.
Simply store information in better ways to make it easier and faster to do the checking. String Tokenizers are bad. Just store stuff in a string array instead.

Also realize something important about frame rate. Time is more significant at higher frame rates. At 400fps taking a teeny weeny 1ms more will drop you down to about 300fps. However at 60fps 1ms more will only drop you down to about 56fps. So if you are seeing a huge drop, it might not be that abnormal.

Back to top
Profile PM
Mage
Valued Member
19
Years of Service
User Offline
Joined: 3rd Feb 2007
Location:
Posted: 8th Sep 2012 23:18 Edited at: 8th Sep 2012 23:21
Link
Quote: "Another tip: Instead of looping through all possible events and checking if it's active, you should use an event list. Something like this:"


I upgraded your code to support a processing time limit.



Then you can make it only run every quarter of a second by calling it for processing like this:




I set it up as a max 2ms processing time, only processing every quarter of a second (250ms). You'll have to explore whats actually most appropriate.

Back to top
Profile PM
Sasuke
20
Years of Service
User Offline
Joined: 2nd Dec 2005
Location: Milton Keynes UK
Posted: 9th Sep 2012 15:59
Link
Constantly changing the size of an array is slow (especially if it's big). I would suggest changing it to linked lists instead. Plus some event's may need to be processed faster than others. So you should just add a 'WarmUpTime' variable to the events that tells the system how much time can pass till the event needs to be processed.
Back to top
Profile PM Email
TheComet
18
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 9th Sep 2012 16:44
Link
Well, you don't necessarily have to resize the array, you could leave it how it is when removing events, and only expand it when there are no more free slots.

TheComet

"Why geeks like computers: unzip, strip, touch, finger, grep, mount, fsck, more, yes, fsck, fsck, fsck, umount, sleep." - Unknown
Back to top
Profile PM Email Website
Mage
Valued Member
19
Years of Service
User Offline
Joined: 3rd Feb 2007
Location:
Posted: 9th Sep 2012 22:47 Edited at: 9th Sep 2012 22:50
Link
Who says you need to expand it at all. Take the cheap way out and simply ignore events when there are too many. Certainly you need to be smart about it. Major game breaking things like oh... passing a finish line and not having the race end, would need some special care, but not much. If this happens at all beyond an extrmely rare occaision then the array should simply be bigger. Tottally an exceptional case.

Quote: "... Plus some event's may need to be processed faster than others. So you should just add a 'WarmUpTime' variable to the events that tells the system how much time can pass till the event needs to be processed. "


This may be true, but it's rarer than most people think. What type of an event noticeable to a human player can't wait 1-10ms. The fact that another event somehow slipped in beforehand probably doesn't matter.

Now If you are saying well some events should be processed at different rates. That maybe some at 250ms intervals and some at 1000ms intervals, then 'WarmUpTime' could help. However that means every event tracking both 'WarmUpTime' and something you didn't mention but required 'LastTimeOfOperation'. Then you end up scanning potentially huge lists of events that aren't being processed. You can cut the workload by simply adding a second faster/slower event queue (cause that's what these are) operating at a different rate. That way you do minimum work, you don't need to check every event every frame, and you don't need to fumble around with event timing when coding the game.

Back to top
Profile PM
New World Order
21
Years of Service
User Offline
Joined: 31st Oct 2004
Location:
Posted: 10th Sep 2012 10:59
Link
About the "warm up time":
Wouldn't the following work just fine?

- Player hits a button. This triggers two events:
Event 1: Open door immediately.
Event 2: Close door again in 5 seconds.

These IDs of these events (1 and 2) are added to the handle-event-list (which has a finite number of slots, containing only the Events ID (reference to the array where all events are stored with their effects, default warmup times etc.) and the actual warmup-coundown of this particular instance of the event.)

The handle-event-list is checked every frame (or every x ms) and all events in it are executed. Therefore the program enters the handle-events-function and sees:
Event 1 is supposed to be triggered right now - check the array of Events for what Event 1 does and execute that. Then delete Event 1 from the handle-events-list.
Event 2 is supposed to be triggered in 5 seconds - do nothing for now except reducing the wwarm-up-countdown. Keep Event 2 in the handle-events-list.

After 5 seconds, when the program enters the handle-events-list, it sees that the countdown has reached zero, executes the effect of event 2 and deletes it from the handle-events-list.


Now, this would only take care of the EFFECTS of events.. the Conditions would need to be handled differently :/
Back to top
Profile PM
Mage
Valued Member
19
Years of Service
User Offline
Joined: 3rd Feb 2007
Location:
Posted: 11th Sep 2012 00:18 Edited at: 11th Sep 2012 01:53
Link
Quote: "About the "warm up time":
Wouldn't the following work just fine? ..."


Yeah that would work, everything mentioned by people so far would work. It's just that some methods are way better than others.


Lets compare your method with mine from a workload perspective:
You:
Check all events every frame. So lets say at 60fps thats 61 event processing operations in the first second (1 open door + 60 close door) and 240 more processing operations (for remaining seconds of close door). That's 301 event processing operations.

Me:
Make 2 queues, one fast (250ms) and one slow (1000ms). So in the first second fast queue has 1 operation and then no other operations at all (open door). Slow queue has 1 operation a second for 5 seconds. The total is 6 event processing operations.

The result is my method is only a little more inaccurate for timing, but is an insane 1.9% of the workload.
That's a massive 50x speed increase.

If you are opening a door it doesn't matter if it takes 16ms or 250ms to begin opening. Nobody cares my door closes after 5-6 seconds instead of 5 seconds.

Here we're merely talking about an event that doesn't really process each time (waiting for a door to trigger closed), unlike if the player was taking damage or something else.
Sometimes processing events each frame really drops frame rate. You just need to find an appropriate time interval.

Also I would put a counter in the 250ms event queue code and when it reached 4 it would trigger the 1000ms event handler (not as an event itself)(faster queue drives the slower one). For simplicity. So then I only need to time and call the one queue. And if you absolutely needed a 'per frame' event queue (like events handling object animation frames manually) have that 'per frame' queue simply 'drive' the other time based queues. That way you're keeping code complexity down.

Back to top
Profile PM
New World Order
21
Years of Service
User Offline
Joined: 31st Oct 2004
Location:
Posted: 11th Sep 2012 09:25
Link
this is proving to be extremely insightful for me, so pardon any dumb questions please
For your two queues, you would still need to check every frame whether they should be handled or not, right? (check if the last execution was more than 250ms / 1000 ms ago)
Isn't that also 60 checks in the first second (or rather 120, because 2 queues^^? In addition to decreasing the countdown variables of the queues)? This would make the two queues profitable only if there are more than 1 events in them, right (which is probably the case most of the time)? Or am I missing something?
Hmm, but I'm beginning to see the point of having different "resolution" queues... thanks, Mage!
Back to top
Profile PM
Broken_Code
15
Years of Service
User Offline
Joined: 20th Aug 2010
Location: Bremen, Germany
Posted: 11th Sep 2012 11:40
Link
Have you thought about using an 'event code' instead of a string? As numbers are evaluated faster than strings, especially if you're checking 60 of them. Also a simple 'Process Event' flag to say when there are any events to process would help, as you don't always have an event running so even checking that any are active is a waste.

Apart from that I think Mage and The Comet pretty much hit the nail on the head.
Back to top
Profile PM
Sasuke
20
Years of Service
User Offline
Joined: 2nd Dec 2005
Location: Milton Keynes UK
Posted: 11th Sep 2012 18:43
Link
Quote: "Also a simple 'Process Event' flag to say when there are any events to process would help, as you don't always have an event running so even checking that any are active is a waste."


Actually this would waste more time because for the process flag you'd need to check if there are events that need to be processed first before updating the flag every time. Instead we just use the event queue to tell us if there's an events that needs processing.

One thing I forgot to mention was what I use the WarmUpTime for. It's not simply to lessen checks, it's 'also' used to WarmUp so to speak variables and assets required for the event so that when the event is triggered all the calculations and etc are not done at an instance for a massive performance hit. Instead I pre-calc what is needed spread over the course of the WarmUpTime.

Think of creating and calculating every velocity of 1000 particles in a single frame = massive slow down or even a pause. But if you pre-calc all this for use over the course of average frames with in say 500 ms, far less of a noticeable performance hit.
Back to top
Profile PM Email
Mage
Valued Member
19
Years of Service
User Offline
Joined: 3rd Feb 2007
Location:
Posted: 11th Sep 2012 20:12 Edited at: 12th Sep 2012 02:00
Link
Quote: "this is proving to be extremely insightful for me For your two queues, you would still need to ch execution was more than 250ms / 1000 ms ago Isn't that also 60 checks in the first second (or of the queues)? "
No and i'll tell you why. 1. I'm running just one time check every frame no matter the number of events. Imagine our example had a million events. Checking one variable evey frame is not significant. 2. His method is scaling up workload per frame, and his method isn't doing the same kind of checks. He's waiting for a door close event. Imagine if you had to be far from the door for it to close too, now he's running distance checks every frame too and i'm not. The volume of his checks scale with the number of events each frame and he might not even be doing featherweight time checks. So it's not the same at all. Because my timing code doesn't scale it's not mathematically significant.


Quote: "One thing I forgot to mention was what WarmUpTime for. It's not simply to less 'also' used to WarmUp so to speak varia required for the event so that when the triggered all the calculations and etc ar an instance for a massive performance pre-calc what is needed spread over th WarmUpTime. Think of... "
That's more complicated then it needs to be, just have the code stop processing entries when too much time passes and pickup where it left off next tme. Also not all events are time bombs, some require constant checking and then constant action like making lava hurt players if they're too close. You need a system that handles more than one type of event.

Quote: " This would make the two queues profitable only if there are more than 1 events in them, right (which is probably the case most of the time)? "

If there's nothing in the queue, then you won't even notice its there. If you wanted to feel better about it, you could always have the queue track it's size and simply abort early if it was empty. You wouldn't see any performance gain unless you did something bad with the programming.

Back to top
Profile PM
GIDustin
18
Years of Service
User Offline
Joined: 30th May 2008
Location:
Posted: 12th Sep 2012 02:58
Link
I really haven't read much of this thread, so feel free to ignore me if my response is way out in left field here.

If you have a list of items that need to fire off at a set time, and you do not want to loop the entire list every <interval>, then could you not sort it by the "fire time" in ascending order, start looping at the beginning, and stop once you reach the first item that is not ready to fire yet? As long as you only re-sort the list when items are added, I could see a performance gain there...
Back to top
Profile PM Email Website
Sasuke
20
Years of Service
User Offline
Joined: 2nd Dec 2005
Location: Milton Keynes UK
Posted: 12th Sep 2012 12:05 Edited at: 12th Sep 2012 12:06
Link
Quote: "If you have a list of items that need to fire off at a set time, and you do not want to loop the entire list every <interval>, then could you not sort it by the "fire time" in ascending order, start looping at the beginning, and stop once you reach the first item that is not ready to fire yet? As long as you only re-sort the list when items are added, I could see a performance gain there..."


Also you only ever need to check the first item in that list if it's sorted.


Mage Quoting me:
Quote: ""One thing I forgot to mention was what WarmUpTime for. It's not simply to less 'also' used to WarmUp so to speak varia required for the event so that when the triggered all the calculations and etc ar an instance for a massive performance pre-calc what is needed spread over th WarmUpTime. Think of... ""


Mage! What the hell happened to this quote?
Back to top
Profile PM Email
BlackChaos
16
Years of Service
User Offline
Joined: 2nd May 2010
Location: London
Posted: 12th Sep 2012 14:49
Link
Even though it might take a bit of time to implement; would it be easier or even possible if I was to code a sever type application that runs in the background?

The server application will run on a local netwrk IP and manage all even processing, giving the main application back some well needed frames.

AEngine 2012 Ameadus Project Feedback or Food o0
Back to top
Profile PM Email
Broken_Code
15
Years of Service
User Offline
Joined: 20th Aug 2010
Location: Bremen, Germany
Posted: 12th Sep 2012 22:55
Link
@Sasuke:
Quote: "
Actually this would waste more time because for the process flag you'd need to check if there are events that need to be processed first before updating the flag every time. Instead we just use the event queue to tell us if there's an events that needs processing.
"

Why would you set the flag by checking the array every frame? Why not set the flag to 1 in the 'Event_Add' function and set the flag to 0 when all the events are cleared?

Can you give me an example of how you'd do this:
Quote: "
Instead we just use the event queue to tell us if there's an events that needs processing.
"

Because I always use flags for this and if there's a better/faster/easier way I'd like to hear it!


Thanks.
Back to top
Profile PM
Sasuke
20
Years of Service
User Offline
Joined: 2nd Dec 2005
Location: Milton Keynes UK
Posted: 13th Sep 2012 00:06
Link
Quote: "Why would you set the flag by checking the array every frame? Why not set the flag to 1 in the 'Event_Add' function and set the flag to 0 when all the events are cleared?"


I never said every frame, but I was mistaken it what I said. But I'll get to what I was saying.

Quote: "Can you give me an example of how you'd do this:"


In the functions posted above you see this uEvent.Count, so if it's greater than -1 then there's something to process. Pretty much this is your flag, so there's no need to make another variable that does the same thing. I use linked lists so I just check the header of the list to see if it has a child, pretty similar to checking if uEvent.Count > -1.

Another thing no one has mentioned is how long an event could remain in the list and then you see the issue with Mage's code. Because if something is moving it would only update the position every quarter of a second. Though obviously that was just pseudo code. So the handling of slow queue's or warm ups needs to be done separate to the update process.
Back to top
Profile PM Email
Mage
Valued Member
19
Years of Service
User Offline
Joined: 3rd Feb 2007
Location:
Posted: 13th Sep 2012 01:48 Edited at: 13th Sep 2012 02:00
Link
People seem to be concerned with one type of event, an event that waits for a set time then triggers. Some events like animation need to be run every frame no matter what. Some events like checking if a player is standing in fire are looping and periodic. it's not all about checking a 'time' to see if an event plays yet, that's just one type of possible event.


Concerning Sorted Event Lists:

Quote: "Also you only ever need to check the first item in that list if it's sorted."

That's not true. If you have multiple ready events you need to check all those and even with just one ready event, you need to check the next one just to be certain it's not ready too. That mean's you might process the whole list.

Quote: "Mage! What the hell happened to this quote?"

It was too long to copy and my mobile phone truncated it. When you see a quote that ends in "..." it means the quote was shortened. The risk when this done is that the person will be taken out of context. But i don't believe this was the case here.


Okay so lets deconstruct the sorted list method...
Worst Case Scenario:

You check the first entries of the sorted events list until an event is found to not be scheduled yet and can ignore the rest because you can safely assume they don't run yet. Potentially this means checking the entire list if all the times are the same and ready. Now for any events that need to be processed, some need to be removed from the list. If you are using an array instead of a linked list then means moving the entire array down if that event is at the front for each removal, potentially all of them. If events are looping, then they need to be rescheduled. So that means even with a linked list, traversing potentially the entire list.

The worst case scenario for a 'Sorted List' is worse than just running all events every frame. The worst case has you running all events every frame + sorting them.

In my method the worst case scenario was all events processing only every second, or quarter of a second, or whatever. It's still faster at a tenth of a second interval. Taking my second suggestion of a max processing time (as I demonstrated above) makes this entire comparison trivial. Max processing time beats every other method.

Then there's the Timer Problem: 'What do you mean timer problem?'

Whenever someone pauses your game, you need to correct the entire sorted list otherwise all the timestamps are wrong. Annoying but not that big a deal right? What about the Timer Rollover Bug. You know when the timer gets so high it doesn't get to the end instead it suddenly becomes negative counting in reverse... This would cause events to freeze and become permanently stuck to the event queue, filling it. Or it would fire off all events in the crossover. Using a sorted list means you need to pay attention to these problems.

Balancing simplicity and speed.


Quote: "Another thing no one has mentioned is how long an event could remain in the list and then you see the issue with Mage's code. Because if something is moving it would only update the position every quarter of a second. Though obviously that was just pseudo code. So the handling of slow queue's or warm ups needs to be done separate to the update process. "

The example above was rather quick. In practice I suggested having a per frame queue for the things that need to be done per frame, like handling object movement and animation. These things are always running. Not waiting and then poof teleporting it, but actual constant onscreen action. If the player is taking lava damage, you can cheat and make damage into quarter second bursts. A lot of people seem focused on events where you wait for long periods of time doing nothing then suddenly do one thing and the event ends. What about when a projectile is fired, handling it's movement MUST be done every frame no matter what method you use. Secondly have that 'per frame' queue drive the next fastest queue like a 250ms queue. Then in the 250ms queue have a counter that reaches 4 and fires the 1 second queue. Then have a counter for something larger in there. If you want to talk about an event that does nothing for 30 minutes and then suddenly does one thing and ends, who cares if its late by 10 or 20 seconds because it was in a slow queue. If there's an on screen timer and it needs to be exact then the same event driving the timer can trigger the 30 minute event.

My whole point here is you can cut a few corners, drop a lot of the workload, things don't need to be exact, and the system doesn't need to be overly complicated. Or you could break your back squeezing out performance, but you get diminishing returns.

Back to top
Profile PM
Sasuke
20
Years of Service
User Offline
Joined: 2nd Dec 2005
Location: Milton Keynes UK
Posted: 13th Sep 2012 03:12 Edited at: 13th Sep 2012 03:21
Link
Quote: "It was too long to copy and my mobile phone truncated it. When you see a quote that ends in "..." it means the quote was shortened. The risk when this done is that the person will be taken out of context. But i don't believe this was the case here."


Aha, I've got ya now.

Quote: "So that means even with a linked list, traversing potentially the entire list."


You missed my 's'. I said I use linked lists (plural), more than one to manage events. Since there are so many types of events, one, two, even three list wasn't going to cut. What I use is dynamic linked lists that are controlled/allocated by their header, or _subEventDirector as I call it. The first list is the processing list and anything in it is considered active. Any other lists is for warmUps, pausing/holding or special cases. Then I've got event type lists which is in another linked list, which is the _eventDirector.

I see no point in checking bullet detection if no bullet has been fired. So I split each event up into types and they get added to the _eventDirector list and if an event in that type needs updating, it gets pushed to the _eventDirector list.

So _eventDirector > _subEventDirector0(handle bullets bla bla) > _processConstantEventList etc (the actual names you wouldn't understand so made these up)

One further is my entire engine runs on a list which I call _director. Just like the bullet example, there no point checking or updating sound if you know no sound is going to be played or is needed at that point in time. So the _soundDirector is removed from the _director list.

This might sound mad. I only update/check the things that require it. Everything else isn't even skip because by the _director it doesn't even exist. I've found this incredible efficient over the standard method of a list of function calls to things that don't even need checking/updating.

Quote: "My whole point here is you can cut a few corners, drop a lot of the workload, things don't need to be exact, and the system doesn't need to be overly complicated. Or you could break your back squeezing out performance, but you get diminishing returns."


Damn, if only I read this before coming up with my engine design

But I've got to hand it to you Mage, you really do put a lot of effort and knowledge in your posts. Really great to see

I would like to add one thing. For timing don't use DBP's stock timer, use Ian M matrix plugin hitimer as it's far more accurate and look into timer based movement and use frame ticks for timing.
Back to top
Profile PM Email
Mage
Valued Member
19
Years of Service
User Offline
Joined: 3rd Feb 2007
Location:
Posted: 13th Sep 2012 04:32
Link
Quote: "I see no point in checking bullet detection if no bullet has been fired. So I split each event up into types and they get added to the _eventDirector list and if an event in that type needs updating, it gets pushed to the _eventDirector list.

So _eventDirector > _subEventDirector0(handle bullets bla bla) > _processConstantEventList etc (the actual names you wouldn't understand so made these up)

One further is my entire engine runs on a list which I call _director. Just like the bullet example, there no point checking or updating sound if you know no sound is going to be played or is needed at that point in time. So the _soundDirector is removed from the _director list.

This might sound mad. I only update/check the things that require it. Everything else isn't even skip because by the _director it doesn't even exist. I've found this incredible efficient over the standard method of a list of function calls to things that don't even need checking/updating."


Agreed. Should be the case no matter what method you are using.

Quote: "I would like to add one thing. For timing don't use DBP's stock timer, use Ian M matrix plugin hitimer as it's far more accurate and look into timer based movement and use frame ticks for timing. "

I sort of assumed the use of Timer Based Movement without mentioning it. Although I get the impression that many people only see it as something useful for movement, and not everything that scales with frame rate. I was thinking of "Ian M's hitimer" but I decided to avoid mentioning/using/suggesting it. I favor solutions that will work for everyone, without the need to add plugins. I try to avoid the need for plugins. It's a great plugin, and it would help a lot especially with my "Max Processing Time" suggestion. I wanted the example to be as clean, clear, and as approachable as possible.

Back to top
Profile PM
Sasuke
20
Years of Service
User Offline
Joined: 2nd Dec 2005
Location: Milton Keynes UK
Posted: 13th Sep 2012 04:55 Edited at: 13th Sep 2012 05:03
Link
Quote: "I sort of assumed the use of Timer Based Movement without mentioning it. Although I get the impression that many people only see it as something useful for movement, and not everything that scales with frame rate. I was thinking of "Ian M's hitimer" but I decided to avoid mentioning/using/suggesting it. I favor solutions that will work for everyone, without the need to add plugins. I try to avoid the need for plugins. It's a great plugin, and it would help a lot especially with my "Max Processing Time" suggestion. I wanted the example to be as clean, clear, and as approachable as possible."


I usually have the same thought. But with the hundreds of work arounds we face using DBP when a plugin becomes necessary I've started to mention them. Because things in vanilla DBP just can't be done or would be ridiculous attempting. For instance like any meaningful collision system, advanced rotation (unless you make your own classes matrix/quaternion and insane trig(LowerLogic's work is floating round here)), lots of 2D etc. Saying you can make any game in just DBP is a down right lie, there's not even a simple way to check if an object is in the screen (why we still have those two useless commands is beyond me) but this is another old old topic. Plugin's, especially Ian M's I would say is a standard for DBP just like Sparky's collision is (though wasn't that created by a member of TGC?).
Back to top
Profile PM Email
Mage
Valued Member
19
Years of Service
User Offline
Joined: 3rd Feb 2007
Location:
Posted: 13th Sep 2012 05:07 Edited at: 13th Sep 2012 05:14
Link
Quote: "
I usually have the same thought. But with the hundreds of work arounds we face using DBP when a plugin becomes necessary I've started to mention them. Because things in vanilla DBP just can't be done or would be ridiculous attempting. For instance like any meaningful collision system, advanced rotation (unless you make your own classes matrix/quaternion and insane trig), lots of 2D etc. Saying you can make any game in just DBP is a down right lie, there's not even a simple way to check if an object is in the screen (why we still have those two useless commands is beyond me) but this is another old old topic. Plugin's, especially Ian M's I would say is a standard for DBP just like Sparky's collision is (though wasn't that created by a member of TGC?)."


Oh I agree completely. I just mean I try not to cloud an example I give people with adding things I don't particularly need.

If this was a discussion about collision I'd be recommending Sparky's plugin. I'm not against plugins, I just make an effort to give clear examples.

Back to top
Profile PM
Diggsey
20
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 14th Sep 2012 21:51
Link
Also, here's an easy way to always avoid the timer roll-over problem: make sure you clearly distinguish between absolute time and time differences. Comparing time differences will always be fine but comparing absolute times is doomed to fail.

For example, instead of this:




This works because even if the time has rolled over, so currentTime is negative but startTime is positive, when you subtract the two it will give you the correct time difference because computer arithmetic is modular.

[b]
Back to top
Profile PM Email Website
Mage
Valued Member
19
Years of Service
User Offline
Joined: 3rd Feb 2007
Location:
Posted: 15th Sep 2012 06:57 Edited at: 15th Sep 2012 08:00
Link
Quote: "Also, here's an easy way to always avoid the timer roll-over problem: make sure you clearly distinguish between absolute time and time differences. Comparing time differences will always be fine but comparing absolute times is doomed to fail.

For example, instead of this:

+ Code Snippet

if (currentTime - startTime) > duration
...
endif"


I hate to do this to you bud, but you need an ABS operation and an equal sign in there.



I agree that using relative time is a great way to avoid the Timer Rollover Problem... But it makes creating the Sorted Event Queue difficult. Just think how that would be created. Every event's timestamp would not be the time in which said event is processed, but instead the relative time since the previous event.

So inserting events is more complicated since you need to correct the timestamp of the next event. Ok big deal.

Quote: "Comparing time differences will always be fine but comparing absolute times is doomed to fail."


There's also the Time Drift Problem...
You will be late processing every event by at least a little bit of time. If something takes too long then maybe a lot of time. For example, the next event is in 2ms but the game takes 20ms to cycle and begin processing it. Each time this happens more and more delay is built up. Long term events that have had many events occur since they were scheduled can experience potentially wild drifts from intended timing. This system is unstable.

Also The Timer Precision Problem:
I should add that any method where you are using any form of relative time will also suffer from a -/+ 3.6 seconds per minute range of time drift at 60 frames per second, unless a more accurate Timer plugin is used. This is because the built-in timer can't register anything under 1ms. For example, you measure a duration of 2ms when you really took 2.9ms. For per frame events like motion, bursty periodic events like fire damage, and short events like a door closing this is meaningless. However If you want to go nuts with long term events that MUST be on time (not as common as people think) then get a timer plugin.

Back to top
Profile PM
TheComet
18
Years of Service
User Offline
Joined: 18th Oct 2007
Location: I`m under ur bridge eating ur goatz.
Posted: 15th Sep 2012 11:12
Link
There's a lot of thought going into this... I should mention that maybe we should all just stick to KISS, shouldn't we?

TheComet

"Why geeks like computers: unzip, strip, touch, finger, grep, mount, fsck, more, yes, fsck, fsck, fsck, umount, sleep." - Unknown
Back to top
Profile PM Email Website
Mage
Valued Member
19
Years of Service
User Offline
Joined: 3rd Feb 2007
Location:
Posted: 15th Sep 2012 17:37
Link
That's what i was saying.

Back to top
Profile PM
Diggsey
20
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 15th Sep 2012 17:42 Edited at: 16th Sep 2012 22:21
Link
Quote: "I hate to do this to you bud, but you need an ABS operation and an equal sign in there."


No you don't, that's the whole point of my post An abs will actually break the system.



Also I wasn't specifically talking about using this for the events system but for use in general, although I see no reason why it cannot be used for an events system...

Quote: "There's also the Time Drift Problem..."


That has nothing to do with my example, I said not to COMPARE absolute times. Storing them is fine. In the case of the events system I would store the absolute time of when each event should fire, but always subtract the current time before doing any comparisons.

Quote: "The Timer Precision Problem:"


Again, doesn't apply.

[b]
Back to top
Profile PM Email Website
Mage
Valued Member
19
Years of Service
User Offline
Joined: 3rd Feb 2007
Location:
Posted: 17th Sep 2012 01:12 Edited at: 17th Sep 2012 01:22
Link
I've taken a second look at your example and I see that you are not only storing the duration, but are also storing the original start time.

I think this is an improvement over the other method which was to just to store the duration, as yes it eliminates some of the long-term problems I discussed. Bravo.


Quote: "Quote: "There's also the Time Drift Problem..."

That has nothing to do with my example, I said not to COMPARE absolute times. Storing them is fine. In the case of the events system I would store the absolute time of when each event should fire, but always subtract the current time before doing any comparisons.

Quote: "The Timer Precision Problem:"

Again, doesn't apply."


Agreed.


Quote: "Quote: "I hate to do this to you bud, but you need an ABS operation and an equal sign in there."

No you don't, that's the whole point of my post An abs will actually break the system.

+ Code Snippet

` Simulate a timer roll-over of 10ms
startTime = 2147483640
currentTime = -2147483646

timeDifference = currentTime - startTime

` It prints 10
print timeDifference
sync
wait key"


I disagree. I believe you've made a serious error here. The timer rollover is a binary problem. Timer in binary looks something like 01010101010111000 and when it reaches something like 011111111111 it rolls over to 1000000000000 (-0). Then it counts to 1000000000001 (-1). Then there's a second roll over at 1111111111111 to 0, 1, 2, 3. The error is that that first digit actually controls whether the number is negative or positive. So the timer doesn't roll over from a number like 2147483640 to -2147483641. It rolls over from a number like 2147483640 to -0 counting backwards.

Your example appears to forget time is counting backwards from 0 because of this bug. Therefore your method is fundamentally broken and cannot work under this condition.

As soon as the roll over occurs current time is -0, the duration is a massive incorrect number and all events are triggered.

For events triggered after the rollover where currentTime and startTime are both negative, because time is counting backwards (the bug)
timeDifference = currentTime - startTime is a negative expanding number. So timeDifference > duration is never true.

Then again on the second rollover from a number like -99999999 to +0 you get a ridiculously big Negative duration. This time instead of the events all firing prematurely they never fire at all.

So it just isn't going to work in this way.

Edit:
Also I still disagree with you, there should be an "=" sign in there. If timeDifference = duration, the event should occur. '>' should be '=>'.

Back to top
Profile PM
Dar13
18
Years of Service
User Offline
Joined: 12th May 2008
Location: Microsoft VisualStudio 2010 Professional
Posted: 17th Sep 2012 03:20
Link
Mage, you're incorrect about how integers rollover.

This code works as how Diggsey explained it:


Follow WTLD's progress on Twitter
Git repository for WasTeLanD
Back to top
Profile PM Email
Mage
Valued Member
19
Years of Service
User Offline
Joined: 3rd Feb 2007
Location:
Posted: 17th Sep 2012 04:29 Edited at: 17th Sep 2012 04:49
Link
Quote: "Mage, you're incorrect about how integers rollover.

This code works as how Diggsey explained it:"


I apologize I am in error. I have forgotten something about 2's compliment. The timer doesn't rollover as badly as I described. **If you use the default Data Type to store the time.**

His code will work well. The best overall method is to use his suggestion for storing both duration and start time. You will still have to correct all event times if the game is paused. However his method won't have a runaway timer precision problem. It's best to merge this with my view on making events occur less often. Also my Max Processing Time method.

All of that together will ensure you have accurately timed long term events, with low workload short term events. It allows you to skip almost anything that doesn't need to be processed. Also you can cap workload per frame, to prevent slow downs.

Efficiency:
I'm still worried all that sorting would kill performance. I would only ever use this method with a linked list instead of an array. Worst case is still O(n*n) vs. O(n/60). Which is still potentially slower than just running all events every frame. Since you could potentially be stuck sorting everything.

Good job.

Back to top
Profile PM
Dar13
18
Years of Service
User Offline
Joined: 12th May 2008
Location: Microsoft VisualStudio 2010 Professional
Posted: 17th Sep 2012 04:48 Edited at: 17th Sep 2012 04:57
Link
Quote: "I'm still worried all that sorting would kill performance"

You'd be better off dealing with the constant O(n) performance cost of accessing all the elements in the array versus the possible O(n log n) best case and O(n^2) worst case(assuming the sort is done using quicksort).

Of course, the array might be small enough that n^2 isn't too bad but that's not exactly something to count on.

Follow WTLD's progress on Twitter
Git repository for WasTeLanD
Back to top
Profile PM Email
Mage
Valued Member
19
Years of Service
User Offline
Joined: 3rd Feb 2007
Location:
Posted: 17th Sep 2012 04:51
Link
Quote: "You'd be better off dealing with the constant O(n) performance cost of accessing all the elements in the array versus the possible O(n log n) best case and O(n^2) worst case(assuming the sort is done use quicksort).

Of course, the array might be small enough that n^2 isn't too bad but that's not exactly something to count on."


Yeah.

Back to top
Profile PM
Diggsey
20
Years of Service
User Offline
Joined: 24th Apr 2006
Location: On this web page.
Posted: 17th Sep 2012 05:13 Edited at: 17th Sep 2012 05:20
Link
Quote: "**If you use the default Data Type to store the time.**"


Actually, this is a property of all binary data types on the computer. Since the timer returns a 32-bit integer extending it to 64-bits will break it, but truncating it to a 16-bit or 8-bit value will still give the correct roll-over behaviour, although the maximum delay times you can use will be smaller.

Quote: "The best overall method is to use his suggestion for storing both duration and start time."


You only need to store the time the event is to be fired. However, whenever you would compare two times to see which comes first:
if timeA < timeB
...
endif

Instead, you would do this:
currentTime = timer()
if (timeA - currentTime) < (timeB - currentTime)
...
endif

This ensures that the wrap-around position is always as far away as possible from the current time. Normally one of the times you are comparing would already be the current time, in which case it's as simple as this:

if (timeA - currentTime) < 0
...
endif

The important part is that both sides of the '<' operator are time differences rather than absolute times.

Quote: "I'm still worried all that sorting would kill performance. I would only ever use this method with a linked list instead of an array. Worst case is still O(n*n) vs. O(n/60). Which is still potentially slower than just running all events every frame. Since you could potentially be stuck sorting everything."


There's no need to sort the array - as long as you insert elements at the correct positions the array will always be in the correct order. Finding the correct position is O(log n) or O(n) if done the easy way. Resizing the array is also O(n). Using a linked list instead would provide no performance gain at the cost of memory and code complexity, since although resizing is now amortized constant time, finding the correct position will now be at least O(n) so the overall complexity of an insertion is still O(n).

However you can do better: arranging the events in a binary min-heap inside the array will allow you to get O(log n) time for both insertion and removal of events, and constant time checking for events each frame. Plus, a binary heap is very easy to implement using an array.

[b]
Back to top
Profile PM Email Website
Mage
Valued Member
19
Years of Service
User Offline
Joined: 3rd Feb 2007
Location:
Posted: 18th Sep 2012 05:08 Edited at: 18th Sep 2012 05:12
Link
Quote: "
Actually, this is a property of all binary data types on the computer. Since the timer returns a 32-bit integer extending it to 64-bits will break it, but truncating it to a 16-bit or 8-bit value will still give the correct roll-over behaviour, although the maximum delay times you can use will be smaller."


Yes it is. I was specifically talking about the code you posted. Of course other data types roll over, but just not at that same value. So using that same value with another data type would change the effect. I think we're in agreement.


Quote: "You only need to store the time the event is to be fired. However, whenever you would compare two times to see which comes first:
if timeA < timeB
...
endif

Instead, you would do this:
currentTime = timer()
if (timeA - currentTime) < (timeB - currentTime)
...
endif

This ensures that the wrap-around position is always as far away as possible from the current time. Normally one of the times you are comparing would already be the current time, in which case it's as simple as this:

if (timeA - currentTime) < 0
...
endif

The important part is that both sides of the '<' operator are time differences rather than absolute times."


Sure. That will work too.

Quote: "There's no need to sort the array - as long as you insert elements at the correct positions the array will always be in the correct order. Finding the correct position is O(log n) or O(n) if done the easy way. Resizing the array is also O(n). Using a linked list instead would provide no performance gain at the cost of memory and code complexity, since although resizing is now amortized constant time, finding the correct position will now be at least O(n) so the overall complexity of an insertion is still O(n)."


Yeah, and worst case is running O(n) or O(logn) inserts on all n entries, like if they were repeating. The so called 'perfect storm' worst cast scenario. And I should add that they didn't mention any kind of quick searching capability. That sort of evolved in the discussion afterwards.

Quote: "
However you can do better: arranging the events in a binary min-heap inside the array will allow you to get O(log n) time for both insertion and removal of events, and constant time checking for events each frame. Plus, a binary heap is very easy to implement using an array."


Well there you go you can squeeze more performance out of there. Still I wasn't looking to to build the absolute perfect system, seems I've been sucked into this none the less.

This approach to Sorting Events, is a lot better than the first one that was proposed. The fact that you can Binary sort and search in O(logn) time means it's fast. It's a bit more in depth then I was thinking of going with this, with mindset of a simple approach. Relatively speaking, it's the most complicated of the suggestions, but I think it's the most rewarding.

Worst case... I'm starting to wrack my brain here... still has you running all the events... every frame... so that's n, insertion is O(logn)... insertion on every event looping to the end... O(nlogn) I'm thinking.

It's a bit rough working with worst case scenarios, I think that as a matter of practicality your method would work really well. In some special case situations it would be worse.

Now I don't think my suggestion is the absolute mathematical best solution that exists. I thought of it more as a lazy man approach, simple but effective. But hell, I'm in this deep might as well provoke you further, in all good fun. O(n) is still better than O(nlogn).

On a side note:
I suggested a few other things like making things periodic instead of 'per frame'. I think that still stands. If you were simply running everything every frame before, then adding the best event system isn't going to help if you're still running all those events per frame. That would be the same workload plus overhead.

Also the suggestion of capping the event processing time per frame, to something like 1 or 2ms and picking up where you left off on the next frame. I think that could also be applied to any suggestion here. This suggestion in most cases ends the debate. Realistically speaking for any typical game. You pretty much cap any slow down, even if you are reasonably inefficient. Don't be like that be efficient too, at least a little.

Back to top
Profile PM
Back to top

Login to post a reply

Server time is: 2026-07-07 17:26:26
Your offset time is: 2026-07-07 17:26:26