Game Main Loop Timing (desiring feedback) (solved)

Game development specific discussions.
leopardpm
Posts: 1791
Joined: Feb 28, 2009 20:58

Game Main Loop Timing (desiring feedback) (solved)

Postby leopardpm » Dec 09, 2018 18:14

Thinking about a good method for designing my Main Game Loop. I notice that virtually all the things going on in a game revolve around timings - Screen Updates at a desired speed (ie: 60 FPS), Sprite Animations have variable # of Frames as well as timing between frames,World Updates occur at certain intervals, Character Updates occur at different intervals (for instance, no need to check every millisecond to see if any enemies nearby - checking 1 per second might be fine), different Agent Actions might take different times (the time to walk one grid space would probably take much less time than the time to Chop down a Tree...), etc

Objectives:
(1) Do not do unnecessary work: if you want 60 FPS, then any additional screen updates are worthless
(2) Do not check every timing to see if any is due to execute

So my thought is to maintain a Sorted Event Timing Array. Here is a quick example:

Code: Select all

const TILEW = 5
const TILEH = 5

const SCRW = 1280
const SCRH = 600

    dim shared as integer map(100,100,5)
    dim shared as double starttime, endtime


    ' PQ_TE = Sorted Array/Stack for Timer Event Stack
    dim shared as double PQ_TE(1000,2)
    ' #0 = Event Time
    ' #1 = Event Type
    ' #2 = Event Info (not used in this example...)
   
    ' TE_pntr = Timer Event stack pointer
    dim shared as integer TE_pntr

declare sub Refreshscreen
declare sub DrawGrid
declare function PQ_TE_Add(ByVal newtime as double, byval event as double) as integer
declare function PQ_TE_Del(ByVal thisOne as integer) as integer

    screenres SCRW,SCRH,32,2 'set up 2 video pages (#0 visible, #1 working)
   
    dim shared as integer FPS, LPS, desiredFPS, Loops, Frames
    dim shared as double TimeStart, OldTime, RefreshTime, EstRefreshdelay, Lastframe

' Initialize Main Loop
    locate 50,20 : input "Desired FPS :";desiredFPS
    RefreshTime = 1/desiredFPS
    TE_pntr = 0 ' no events in stack
    Loops = 0 : Frames = 0
    ScreenSet 1, 0 ' working page #1, visible page #0
    DrawGrid
    PQ_TE_Add(timer+RefreshTime,100) ' add the next screen refresh to Timer Event Stack (100 = refresh screen event)

' Main Loop
do
    Loops = Loops + 1
   
    if timer > PQ_TE(TE_pntr,0) then 'check timer against the next event time
        select case PQ_TE(TE_pntr,1) ' figure out what Event needs to be dealt with
            case 100 ' this is the code for RefreshScreen Event
                Refreshscreen
            case 200 ' could be an action or world update or even animation frame change...
               
        end select
    end if
loop until inkey = "q"

end


' some subroutines....
sub Refreshscreen
    dim as double t1

    t1 = timer
   
    'PQ_TE_Del(TE_pntr) ' remove the Event
    TE_pntr -= 1 ' Quick n Dirty remove this event
    PQ_TE_Add(t1+RefreshTime,100) ' add a new Scren Refresh Event to Timer Event Stack

    ' FPS stuff
    FPS = 1/(t1 - OldTime) ' time between frames
    OldTime = t1 'reset OldTime

    locate 3,70 : print "Main Loops per Frame =";Loops;"    "
    locate 5,70 : print "Display FPS =";FPS;"       "
    locate 7,70 : print "Timer =";t1;"      "
    locate 9,70 : print "Refresh Time = ";RefreshTime
    ScreenCopy
    Loops = 0 'reset Loop counter
end sub

sub DrawGrid
        dim as integer x1, y1
        dim as ulong c1

    cls
    ' draw grid
    for i as integer = 1 to 100
        x1 = i*TILEW
        for j as integer = 1 to 100
            y1 = j*TILEH
            c1 = rgb(200,200,200)
            select case map(i,j,0)
                case 1
                    c1 = rgb(0,255,0)
                case 2
                    c1 = rgb(255,0,0)
                case 3
                    c1 = rgb(0,0,255)
                case 4
                    c1 = rgb(255,255,0)
            end select
            line(x1,y1)- step(TILEW-2,TILEH-2),c1,BF
        next j
    next i
end sub

'
'   this is a Sorted Array which maintains an array in sorted order
'
'
function PQ_TE_Add(ByVal newtime as double, byval event as double) as integer
    ' Adds an event to the Timer Event Stack Sorted Array
    ' this function uses and alters the shared variables: PQ_TE() & TE_pntr

' ... add it to the end then bubble sort it down...
    dim as integer bub, addHere
    TE_pntr = TE_pntr + 1
    addHere = TE_pntr
    PQ_TE(TE_pntr,0) = newtime
    PQ_TE(TE_pntr,1) = event
    if TE_pntr > 1 then
        bub = TE_pntr
        do
            if PQ_TE(bub,0) > PQ_TE(bub-1,0) then
                swap PQ_TE(bub,0) , PQ_TE(bub-1,0)
                swap PQ_TE(bub,1) , PQ_TE(bub-1,1)
                addHere = bub - 1
            else
                bub = 2 ' early exit
            end if
            bub = bub - 1
        loop until bub < 2
    end if
    return addHere
end function

function PQ_TE_Del(ByVal thisOne as integer) as integer
    ' Deletes an event from the Timer Event Stack Sorted Array
    select case thisOne
        case is < TE_pntr
            for i as integer = thisOne to (TE_pntr-1)
                PQ_TE(i,0) = PQ_TE(i+1,0)
                PQ_TE(i,1) = PQ_TE(i+1,1)
            next i
            TE_pntr = TE_pntr - 1
        case is = TE_pntr
            TE_pntr = TE_pntr - 1
    end select
    return thisOne
end function


so, my questions are:
(1) Is this a good way to structure my program timings?
(2) What are the possible issues that this sort of structure might have? I assume it will easily keep track of Sprite Frame changes in addition to any other time-based event updates.
(3) Will the overhead required in 'unpacking' the event info end up becoming a mess? For instance, an Sprite Frame Change event would have to include some additional info like the Sprite # which would need to be stored with the TImer Event (PQ_TE(1000,2) in the above example, not used)

What other methods besides this one should I consider to accomplish my goals (keeping track of the timing for everything requiring it, and of course, overall program speed)
Last edited by leopardpm on Dec 09, 2018 23:35, edited 1 time in total.
badidea
Posts: 1286
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Game Main Loop Timing (desiring feedback)

Postby badidea » Dec 09, 2018 18:48

I noticed that you don't have a 'sleep' anywhere in the loop. This can give trouble. But adding a 'sleep' gives different trouble, especially on systems with a long sleep time.
leopardpm
Posts: 1791
Joined: Feb 28, 2009 20:58

Re: Game Main Loop Timing (desiring feedback)

Postby leopardpm » Dec 09, 2018 18:51

badidea wrote:I noticed that you don't have a 'sleep' anywhere in the loop. This can give trouble. But adding a 'sleep' gives different trouble, especially on systems with a long sleep time.
I am purposely trying to avoid using SLEEP. The only reason to use it is to give the OS some time AFTER using SCREENLOCK/SCREENUNLOCK which locks out the OS from updating. That is why I will use the PageFlip/Double-Bufferring technique for the display.

In my example, the OS is never locked out so there is no need to SLEEP

EDIT: Actually my understanding is a bit convoluted here. The SCREENLOCK/UNLOCK only prevents OS from screen refresh and you want this time to be as short as possible. SLEEP does give OS time, but I don't think it is needed as the OS isn't being locked out at any point (is this true?)
Last edited by leopardpm on Dec 09, 2018 19:02, edited 1 time in total.
badidea
Posts: 1286
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Game Main Loop Timing (desiring feedback)

Postby badidea » Dec 09, 2018 18:59

But your code keeps 1 CPU-core 100% busy here, and the laptop-fan blowing out hot air.

On the timing of events. It sounds like a good idea, but I did not study your code. For my game, I'll probably check a lot of timers each loop. I don't need to many (I hope).
Last edited by badidea on Dec 09, 2018 19:03, edited 1 time in total.
leopardpm
Posts: 1791
Joined: Feb 28, 2009 20:58

Re: Game Main Loop Timing (desiring feedback)

Postby leopardpm » Dec 09, 2018 19:03

badidea wrote:But your code keeps 1 CPU-core 100% busy here, and the laptop-fan blowing out hot air.
lol - sorry.... guess it does hog the cpu and will need a minimal SLEEP time... how does the core work with SLEEP 1 added?
badidea
Posts: 1286
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Game Main Loop Timing (desiring feedback)

Postby badidea » Dec 09, 2018 19:10

leopardpm wrote:
badidea wrote:But your code keeps 1 CPU-core 100% busy here, and the laptop-fan blowing out hot air.
lol - sorry.... guess it does hog the cpu and will need a minimal SLEEP time... how does the core work with SLEEP 1 added?

With sleep 1, the CPU will do nothing most of the time, unless there is has lot to process/calculate.
The problem is: The sleep 1 duration can be anything between 1 and 15.6 ms, depending on OS and other stuff.
More reading: viewtopic.php?f=15&t=26419
I use a different approach, in short: In one main loop:
* sleep 1
* graphics update
* multiple physics updates (calculations) (max 2 ms each)
Last edited by badidea on Dec 09, 2018 19:12, edited 1 time in total.
leopardpm
Posts: 1791
Joined: Feb 28, 2009 20:58

Re: Game Main Loop Timing (desiring feedback)

Postby leopardpm » Dec 09, 2018 19:11

On my system, when running the above code I get about 10% CPU utilization (where do I see the individual core utilization? I am looking at the Task Manager...)

When I add 'SLEEP 1' to the RefreshScreen routine, then the utilization drops to 1/2 or 1/3 of that

if I put the SLEEP 1 within the main loop, then I can't even keep up 60 FPS but utilization drops to non-existant

I don't like the sleep function because of its variability, but looks like it will need to be place in the RefreshScreen routine just so that people's laptops don't degenerate into melted piles of plastic...

The sleep 1 duration can be anything between 1 and 15.6 ms, depending on OS and other stuff.

Hate that! To run at 60FPS, the display needs to be updated every 16.6ms... if the sleep thing takes up 15.6ms then that only leaves 1ms to do everything else! That is not good....

there must be another(better) way...
badidea
Posts: 1286
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Game Main Loop Timing (desiring feedback)

Postby badidea » Dec 09, 2018 19:20

I run linux here, so I can't answer the first question. 10% sound fine to me.

Yes, sleep sucks. This wasn't needed in the old days with 80486 cpu's and the like. Those where always doing something or nothing full speed.

What does this code give you?

Code: Select all

dim as double t = timer
sleep 1
print (timer - t) * 1000; " ms"

Here about 1.1 ms

There is a way to reduces this sleep time on windows. There are posts on this somewhere on the forum.

Have a search for dodicat's FPS regulator, that may help in a simple way.
Last edited by badidea on Dec 09, 2018 19:28, edited 1 time in total.
leopardpm
Posts: 1791
Joined: Feb 28, 2009 20:58

Re: Game Main Loop Timing (desiring feedback)

Postby leopardpm » Dec 09, 2018 19:23

mine gives: 1.307731842771887 ms
badidea
Posts: 1286
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Game Main Loop Timing (desiring feedback)

Postby badidea » Dec 09, 2018 19:29

leopardpm wrote:mine gives: 1.307731842771887 ms

Then 60 FPS should not be a problem (on your system).
Edit: correction, It will not be exactly 60 FPS any more. I use the loop time in the movement of things.

Edit2: Dodicat's regulator: viewtopic.php?f=15&t=27052&p=252704&hilit=fps+regulator#p252705 Don't ask me how it works :-)
leopardpm
Posts: 1791
Joined: Feb 28, 2009 20:58

Re: Game Main Loop Timing (desiring feedback)

Postby leopardpm » Dec 09, 2018 19:47

it looks like dodicat's regulator uses the sleep function too, it just calculates the time needed to sleep based on the time passed since last frame update... so it should work on diff systems with diff SLEEP timings BUT, since it still uses the SLEEP function, on those systems where SLEEP produces the aforementioned 15.6ms delay - it is not a good solution....

hmmm, need to think a bit on this.... I want the program to run as fast as possible while dealing with any/all events that are due to be dealt with, but while waiting for the next event it can give the OS time..... actually, perhaps I can use dodi's function but only execute it if there is enough time.... argh... getting complicated...

I guess putting dodi routine in the RefreshScreen routine would cover all bases EXCEPT systems that have SLEEP 1 = 15.6 milliseconds (or any high value) will be unable to maintain the desired 60fps....
paul doe
Posts: 912
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Game Main Loop Timing (desiring feedback)

Postby paul doe » Dec 09, 2018 20:31

leopardpm wrote:Thinking about a good method for designing my Main Game Loop...

Check here. The metaballs demo I mentioned compares the two methods (fixed frame rate vs. fixed update time), so perhaps you'll hopefully be able to see why you don't want to use something like the regulate() function in real code.

Another example: Animation Class. There you can see one model to control individual times for each entity in the game.
leopardpm
Posts: 1791
Joined: Feb 28, 2009 20:58

Re: Game Main Loop Timing (desiring feedback)

Postby leopardpm » Dec 09, 2018 20:43

paul doe wrote:
leopardpm wrote:Thinking about a good method for designing my Main Game Loop...

Check here. The metaballs demo I mentioned compares the two methods (fixed frame rate vs. fixed update time), so perhaps you'll hopefully be able to see why you don't want to use something like the regulate() function in real code.

Hi Paul!
Yeah, I checked out your Meatball code earlier and it swamped my poor lil mind.... once someone starts talking OOP-speak (classes, etc) then I get lost. BUT, I do understand why I don't want to use something like regulate though and I LOVE your demo!

Here is my latest though:
(1) Stay with current code structure (I like the Event Timing Stack to keep track of things to do)
(2) Since I know the current time and the time that the next Event is due, I can check and see if there is enough time to SLEEP 1 - if there is not enough time then just go full speed processing events until there is time to give to OS

Here is the modified code, it shouldn't blow up badidea's laptop anymore, yet still be able to maintain a high speed to process Events....

Code: Select all

const TILEW = 5
const TILEH = 5

const SCRW = 1280
const SCRH = 600

    dim shared as integer map(100,100,5)
    dim shared as double starttime, endtime
    dim shared as long rfps

    ' PQ_TE = Sorted Array/Stack for Timer Event Stack
    dim shared as double PQ_TE(1000,1)
    ' TE_pntr = Timer Event stack pointer
    dim shared as integer TE_pntr

declare sub Refreshscreen
declare sub DrawGrid
declare function PQ_TE_Add(ByVal newtime as double, byval event as double) as integer
declare function PQ_TE_Del(ByVal thisOne as integer) as integer
declare Function Regulate(Byval MyFps As Long,Byref fps As Long) As Long

    screenres SCRW,SCRH,32,2 'set up 2 video pages (#0 visible, #1 working)
   
    dim shared as integer FPS, LPS, desiredFPS, Loops, Frames, SleepTImes
    dim shared as double TimeStart, OldTime, RefreshTime, EstRefreshdelay, Lastframe

' Initialize Main Loop
    locate 50,20 : input "Desired FPS :";desiredFPS
    RefreshTime = 1/desiredFPS
    SleepTImes = 0
    TE_pntr = 0 ' no events in stack
    Loops = 0 : Frames = 0
    ScreenSet 1, 0 ' working page #1, visible page #0
    DrawGrid
    PQ_TE_Add(timer+RefreshTime,100) ' add the next screen refresh to Timer Event Stack (100 = refresh screen event)

' Main Loop
do
    Loops = Loops + 1
   
    if timer > PQ_TE(TE_pntr,0) then 'check timer against the next event time
        select case PQ_TE(TE_pntr,1) ' figure out what Event needs to be dealt with
            case 100 ' this is the code for RefreshScreen Event
                Refreshscreen
            case 200 ' could be an action or world update or even animation frame change...
               
        end select
    end if
   
    ' if there is enough time for a minimal sleep (1.5ms) then sleep
    if PQ_TE(TE_pntr,0) > timer + .0015 then
        sleep 1
        SleepTImes += 1
    end if
   
loop until inkey = "q"

end


' some subroutines....

sub Refreshscreen
    dim as double t1

    t1 = timer
   
    'PQ_TE_Del(TE_pntr) ' remove the Event
    TE_pntr -= 1 ' Quick n Dirty remove this event
    PQ_TE_Add(t1+RefreshTime,100) ' add a new Scren Refresh Event to Timer Event Stack

    ' FPS stuff
    FPS = 1/(t1 - OldTime) ' time between frames
    OldTime = t1 'reset OldTime

    locate 3,70 : print "Main Loops per Frame =";Loops;"    "
    locate 5,70 : print "Display FPS =";FPS;"       "
    locate 7,70 : print "Timer =";t1;"      "
    locate 9,70 : print "Refresh Time = ";RefreshTime
    locate 11,70 : print "# of times Slept =";SleepTImes
    ScreenCopy
    Loops = 0 'reset Loop counter
end sub

sub DrawGrid
        dim as integer x1, y1
        dim as ulong c1

    cls
    ' draw grid
    for i as integer = 1 to 100
        x1 = i*TILEW
        for j as integer = 1 to 100
            y1 = j*TILEH
            c1 = rgb(200,200,200)
            select case map(i,j,0)
                case 1
                    c1 = rgb(0,255,0)
                case 2
                    c1 = rgb(255,0,0)
                case 3
                    c1 = rgb(0,0,255)
                case 4
                    c1 = rgb(255,255,0)
            end select
            line(x1,y1)- step(TILEW-2,TILEH-2),c1,BF
        next j
    next i
end sub

'
'   this is a Sorted Array which maintains an array in sorted order
'
'
function PQ_TE_Add(ByVal newtime as double, byval event as double) as integer
    ' Adds an event to the Timer Event Stack Sorted Array
    ' this function uses and alters the shared variables: PQ_TE() & TE_pntr

' ... add it to the end then bubble sort it down...
    dim as integer bub, addHere
    TE_pntr = TE_pntr + 1
    addHere = TE_pntr
    PQ_TE(TE_pntr,0) = newtime
    PQ_TE(TE_pntr,1) = event
    if TE_pntr > 1 then
        bub = TE_pntr
        do
            if PQ_TE(bub,0) > PQ_TE(bub-1,0) then
                swap PQ_TE(bub,0) , PQ_TE(bub-1,0)
                swap PQ_TE(bub,1) , PQ_TE(bub-1,1)
                addHere = bub - 1
            else
                bub = 2 ' early exit
            end if
            bub = bub - 1
        loop until bub < 2
    end if
    return addHere
end function

function PQ_TE_Del(ByVal thisOne as integer) as integer
    ' Deletes an event from the Timer Event Stack Sorted Array
    select case thisOne
        case is < TE_pntr
            for i as integer = thisOne to (TE_pntr-1)
                PQ_TE(i,0) = PQ_TE(i+1,0)
                PQ_TE(i,1) = PQ_TE(i+1,1)
            next i
            TE_pntr = TE_pntr - 1
        case is = TE_pntr
            TE_pntr = TE_pntr - 1
    end select
    return thisOne
end function


this is really the only change to the original code in the main loop:

Code: Select all

    ' if there is enough time for a minimal sleep (1.5ms) then sleep
    if PQ_TE(TE_pntr,0) > timer + .0015 then
        sleep 1
        SleepTImes += 1
    end if


with this modification, my system shows only 2% utilization of CPU instead of the 10% I got with the initial code
Last edited by leopardpm on Dec 09, 2018 20:54, edited 1 time in total.
leopardpm
Posts: 1791
Joined: Feb 28, 2009 20:58

Re: Game Main Loop Timing (desiring feedback)

Postby leopardpm » Dec 09, 2018 20:52

Paul,
Just looked at your Animation Class

First, I must say that I REALLY appreciate how well you comment your code and how clean and straightforward it is - this makes it so amateurs like me have a chance of understanding the inner workings of whats occurring - Thank you!

Though I don't understand the 'language' of classes, etc... I think I am already thinking along the same lines of what you are showing there:

Basically, each animation bitmap is only stored once:

And every 'agent' which uses that animation just maintains an index to which frame that particular agent is currently showing.

This way you could have 100 elves walking around, each having their individual frames advancing at different rates, yet still only uses one animation bitmap

is that what you are showing in your animation class demo?
badidea
Posts: 1286
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Game Main Loop Timing (desiring feedback)

Postby badidea » Dec 09, 2018 21:02

leopardpm wrote:... it shouldn't blow up badidea's laptop anymore ...

The first prize of the competition should be enough to buy me a new laptop :-)

I am going to draw horses of 33 x 33 pixels, that should be fun!

Return to “Game Dev”

Who is online

Users browsing this forum: No registered users and 2 guests