Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Code optimization
Index -> Programming, Turing -> Turing Tutorials
View previous topic Printable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
mirhagk




PostPosted: Tue Dec 15, 2009 3:01 pm   Post subject: Code optimization

There are four things a programmer needs to do to make a good game.

1. Come up with a good idea and plan out the game.

2. Write the code for the game

3. Make the program idiot-proof (remember how dumb people are)

4. Make the amazing game as effecient as possible


Today I'm going to talk about the fourth item, because it seems to be the biggest problem for most programmers.

I have created a simple program to demonstrate many of the ways to optimize your code. The program is commented in case you don't understand it but you really should because it's very basic

Turing:

var x, y : int %the position of the character
x := maxx div 2
y := maxy div 2
var keys : array char of boolean %keyboard input
var t := Time.Elapsed %keep track of the time
var tlast := t %the time last frame
var fps : real %keep track of the Frames Per Second
colourback (black) %set the background to black
colour (white) %and the font colour to white
cls
loop
    Input.KeyDown (keys) %get keyboard state
    t := Time.Elapsed - tlast
    if t = 0 then %to prevent a division by 0 we say if less
        fps := 1000          %than 1 second has passed then it's 1000fps
    else
        fps := 1000 / (t) %fps equals 1 second divided by the time it took to run the last frame
    end if
    tlast := Time.Elapsed
    Text.Locate (1, 1)
    put fps
    if keys (KEY_UP_ARROW) then %very simple movement
        y += 1
    elsif keys (KEY_DOWN_ARROW) then
        y -= 1
    end if
    if keys (KEY_RIGHT_ARROW) then
        x += 1
    elsif keys (KEY_LEFT_ARROW) then
        x -= 1
    end if
    for X : 1 .. maxx by 10
        for Y : 1 .. maxy by 10
            drawfillstar (X, Y, X - 5, Y - 5, yellow) %draws stars for the background
        end for
    end for
    drawfilloval (x, y, 3, 3, brightred) %draw the character
    delay (10)
    cls %clears the screen
end loop


obviously not a very useful game lol but it's just as an example. So first of all, probably one of the most common problems is "the flickering".

Well the first problem with that is where the cls is. Right now it clears the screen then does a bunch of code, then draws the stuff. It flickers much less when it does the code, then clears the screen right before it draws it.

However that really doesn't make much difference because you can just use View.Update and offscreenonly [url=](to learn more about it go here)[/url] But keep in mind that offscreenonly creates a double buffer which slows it down.


Alright next up is my favourite improvement. Delay is a command you should almost never move. If you notice the FPS counter, it runs at about 25 fps on my computer (probably will run higher on yours but it doesn't run at 100 fps which it should be doing if it's a 10 millisecond delay)

What delay does is wait for the specified amount of milliseconds. This isn't very good however since you don't know how long the program will take to run on different machines or even on your own from minute to minute.

Time.DelaySinceLast(milliseconds:int) will wait for the specified amount of milliseconds since the last delay or Time.DelaySinceLast (so if the code takes 7 milliseconds to run and the Time.DelaySinceLast is 10 then it will wait for 3 milliseconds)

If you replace delay with Time.DelaySinceLast you will see immediate improvements to your programs speed (it will increase this program by 10 frames per second unless your computer runs the code exceptionally fast already)

But wait, why delay at all?? Why would you ever limit the speed of the computer?? The only reason we have for this code is that we want the speed of the character to be consistent.

Motion is relative my friends, so instead of increasing the position by a set amount, why don't we increase based on how much time has passed.
This is what I mean:
Turing:

    if keys (KEY_UP_ARROW) then %time relative movement
        y += 1 * (t) / 10
    elsif keys (KEY_DOWN_ARROW) then
        y -= 1 * (t) / 10
    end if
    if keys (KEY_RIGHT_ARROW) then
        x += 1 * (t) / 10
    elsif keys (KEY_LEFT_ARROW) then
        x -= 1 * (t) / 10
    end if

of course for this to work x and y must be real (change from int to real at top) and must be rounded when drawn like so:
Turing:

drawfilloval (round (x), round (y), 3, 3, brightred) %draw the character


In this example you won't notice the difference right away other than a smoother movement but if you take the drawfillstar command out you will notice he moves at the same speed as he did before.



And last but now least, closing your program. It's not a good thing if you have to keep clicking the 'X' at the top right corner to keep stopping your program. You should have an exit when statement in your main loop. For this one we'll use
[syntax=turing]
exit when keys (KEY_ESC)
[/syntax]

now this will stop the program if you press the escape key. However if you notice the window stays open. Well that's because you have no control over closing the default window. That's why instead of View.Set you should do the following at the top of your program
Turing:

var screen:=Window.Open("offscreenonly")

this works the same way View.Set (or setscreen) except you now have the window in a variable and can use the following
Turing:

Window.Close(scree)

if you put that at the end of your code(after end loop) then it will stop the program and close it when you press the Escape key.


There are of course many, MANY other ways to improve your code, these are just a few of the simplest ones that can be used in most programs.

If you post your code I can help you modify your code to make it run faster.

Btw the final code is:

Turing:

var screen := Window.Open ("offscreenonly") %opens a new window
var x, y : real %the position of the character
x := maxx div 2
y := maxy div 2
var keys : array char of boolean %keyboard input
var t := Time.Elapsed %keep track of the time
var tlast := t %the time last frame
var fps : real %keep track of the Frames Per Second
colourback (black) %set the background to black
colour (white) %and the font colour to white
cls
loop
    Input.KeyDown (keys) %get keyboard state
    t := Time.Elapsed - tlast
    if t = 0 then %to prevent a division by 0 we say if less
        fps := 1000          %than 1 second has passed then it's 1000fps
    else
        fps := 1000 / (t) %fps equals 1 second divided by the time it took to run the last frame
    end if
    tlast := Time.Elapsed
    Text.Locate (1, 1)
    put fps %puts the frames per second
    if keys (KEY_UP_ARROW) then %time relative movement
        y += 1 * (t) / 10
    elsif keys (KEY_DOWN_ARROW) then
        y -= 1 * (t) / 10
    end if
    if keys (KEY_RIGHT_ARROW) then
        x += 1 * (t) / 10
    elsif keys (KEY_LEFT_ARROW) then
        x -= 1 * (t) / 10
    end if
    for X : 1 .. maxx by 10
        for Y : 1 .. maxy - 10 by 10
            drawfillstar (X, Y, X - 5, Y - 5, yellow) %draws stars for the background
        end for
    end for
    drawfilloval (round (x), round (y), 3, 3, brightred) %draw the character
    View.Update %updates the screen
    cls %clears the screen
    exit when keys (KEY_ESC) %exits when you press escape
end loop
Window.Close (screen) %closes the window
Sponsor
Sponsor
Sponsor
sponsor
DemonWasp




PostPosted: Tue Dec 15, 2009 4:15 pm   Post subject: RE:Code optimization

First, your FPS-detection code is incorrect (if t<0 then FPS dips into the negatives) as you're testing t=0, not t<=0.

Second, there are legitimate reasons to lock to a given number of frames per second, including multiplayer network programming. I've also had to limit framerate in one of my programs (though that was in Java and used OpenGL) because my graphics card was making a weird whining noise.

Third, while your "finished" program may run more smoothly, what actual optimizations have you added here? Everything looks smoother, but nothing actually runs faster, as far as I can see.
Tony




PostPosted: Tue Dec 15, 2009 7:04 pm   Post subject: RE:Code optimization

As DemonWasp points out, a more appropriate title would be Frame Rate Control -- http://compsci.ca/v3/viewtopic.php?p=5626

Uhh.. that appears to be from 2003, I'm guessing back when DelaySinceLast was not introduced yet.
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
mirhagk




PostPosted: Wed Dec 16, 2009 8:00 am   Post subject: Re: RE:Code optimization

DemonWasp @ Tue Dec 15, 2009 4:15 pm wrote:
First, your FPS-detection code is incorrect (if t<0 then FPS dips into the negatives) as you're testing t=0, not t<=0.

Second, there are legitimate reasons to lock to a given number of frames per second, including multiplayer network programming. I've also had to limit framerate in one of my programs (though that was in Java and used OpenGL) because my graphics card was making a weird whining noise.

Third, while your "finished" program may run more smoothly, what actual optimizations have you added here? Everything looks smoother, but nothing actually runs faster, as far as I can see.


first off I didn't even realize that frame could take -seconds to run (thought it was kinda impossible...)

and yeah I guess the title was kinda a misnomer, cuz it just makes the programs run smoother. The big thing I wanted to point out is the use of Time.DelaySinceLast instead of delay (makes it more likely to run at a constant speed, so what you would probably use for mulitplayer stuff).

And also I do believe if you are making a mulitplayer game then as long as your getting the positions and not velocities then you shouldn't have a problem making it run as fast as you can. (XNA by default goes as fast as it can, the only thing ever limited is the drawing).

If your having a problem with the drawing or mulitplayer aspects then you can limit those things by doing the following:
Turing:

var t:int
var told:=Time.Elapsed
var fps:int
var refresh:=0


loop
t:=Time.Elapsed-told
if t<=0 then
fps:=1000
else
fps:=1000 div t
refresh+=t
end if
told:=Time.Elapsed

%%update code

if refresh>=20 then
refresh:= refresh mod 20
%%drawing code
end if
end loop


That will limit the drawing to 50fps while the game while the update code will still run as fast as it can. This is pretty much the exact way that XNA does it, so that they don't get games with slow refresh rates or worse a game that ran slow on someone's computer but when switched to the xbox ran alot faster than anticipated which would screw up the game. All programmer's should learn how to move their objects at a constant speed, no matter what system it's on. (for instance what happens if you make the multiplayer game but one player's computer is slow, will it slow everyone's speed down as they wait for that person or will that person kinda move a little glitchy but still work and everyone with a good computer can still play normally, correct me if I'm wrong but I believe that second option is better because you can still at least play if only player is glitching out, rather than having to quit because everyone is)

edit: also if a mod would like to change the topic title to something more appropriate feel free to do so
DemonWasp




PostPosted: Wed Dec 16, 2009 10:48 am   Post subject: RE:Code optimization

The only reason that the subtraction can yield a negative number is because Time.Elapsed has a relatively large inaccuracy on it, something like 50ms on some systems. That doesn't sound like much, but at 60fps, each frame is only about 17ms.

I concur that movement rate should be independent of framerate.

In general, multiplayer games have a "tick rate" that governs how frequently they send messages to the server. Common values are 33, 66 and 100 times per second. These are independent of draw rate. In the case that a client cannot keep up with the rate the server expects, either the client will experience some horrendous lag, or else the server will kick them.

Your latest code is much more useful, though it's worth remembering the inaccuracy in Time.Elapsed (I don't know as there's any better option in Turing, but many other languages let you get the current time in nanoseconds).
mirhagk




PostPosted: Wed Dec 16, 2009 11:50 am   Post subject: RE:Code optimization

a 50 ms lag?? are you sure about that?? Wow that's actually like intensely off. That could make the difference between life and death, (a 50ms lag on a multi player game certainly would).

As for the multi player game thing, wouldn't it be better if the client's last data was used and the host just skipped sending it data (if it missed more than one in a row then it would be kicked)

That way if the client's computer was lagging then they would have a frame skip mode (everything moves at half that amount of frames, same speed still though) but everyone else would be lag free (with the exception of that person skipping a frame)

It'd look kinda bad but it wouldn't affect game play too much.

I'm thinking about making a multiplayer game.... If only Turing could do games over the internet (as far as I know the net commands only do across a LAN)
DemonWasp




PostPosted: Wed Dec 16, 2009 1:48 pm   Post subject: RE:Code optimization

Turing specification: "On IBM PC compatibles, this is the total time since the Turing system was started up. The hardware resolution of duration is in units of 55 milliseconds. For example, Time.Elapsed may be off by as much as 55 milliseconds."

It's not a lag though, just an error margin. The value given could be up to 55ms ahead or 55ms behind of the actual value.

There are a lot of strategies for dealing with network problems in multiplayer games. Given the objectives of smooth, real-time play in a network that loses some portion of your packets (50% or more, even), there are a few main strategies.

1. Never wait on data from other end (client if you are server, server if you are client). If updates arrive on time then great, update.
2. Extrapolate movement based on prior data. This usually means continuing to move players based on your physics model (usually a velocity, plus the physics of collisions and gravity and so forth).
3. Keep track of how long it has been since the other end last sent data; if it's been too long, disconnect them.
4. Keep track of how frequently the other end sends data. If they're sending too infrequently, disconnect them.

There's also some work you would have to do if you want to consider the important possibility that a client isn't necessarily playing fair. A client could conceivably send lies and trickery as their update-data to confuse the server into making them invincible, super-fast or super-accurate. A wily client could even "travel in time" by sending update packets postmarked a few ms ago to make the server think that legitimate packets were just arriving late, allowing said client to lie about what it had actually done during that time.

It's also important to distinguish between physics and graphics update rates. Often, the physics update rate is relatively low (20-30 updates per second) while the graphics and network update rates are high (variable, 30-90 and fixed, 33, 66 or 100, respectively). This is because physics is expensive computationally and because nobody really notices if the physics only updates every third frame.
mirhagk




PostPosted: Wed Dec 16, 2009 3:11 pm   Post subject: RE:Code optimization

some things need to be updated every frame though, like collision detection (although if your using purely linear collision detection then you don't have to worry)

other things don't need to be updated very often at all, like score, noone really notices if score takes even 500 ms to update.

I'm going to do two things now. First I'm going to research what's the slowest a frame rate can be in order for someone to notice, then I'm going to research and see if a game runs faster by only updating pieces of code when they need to be updated.

Also if someone knows how to make a game actually work across the internet, please let me know okay?
Sponsor
Sponsor
Sponsor
sponsor
DemonWasp




PostPosted: Wed Dec 16, 2009 3:33 pm   Post subject: RE:Code optimization

You probably just need to specify an actual internet address, rather than a LAN address. The simplest way to tell is that LAN addresses are almost always 192.168.1.* or 192.168.0.*, where * is from 1 to 255. The more complicated way is to traceroute to that IP address and see if the packets ever leave the local network.
mirhagk




PostPosted: Wed Dec 16, 2009 3:48 pm   Post subject: RE:Code optimization

well here's my test for screen refresh rate. I'd say you could get away with about 20, but you don't notice at 30. Let me know though okay.
Turing:

var win := Window.Open ("offscreenonly")
put "This is a test to see how slow a visual update can be before you notice:"
var fps : int
var t : int
var told := Time.Elapsed
var maxframe := true

var xv, yv : real := 1
var x, y : real := 0
var col := brightblue
var collided := false
var c : string (1)
colour (white)
colourback (black)

loop
    if maxframe then
        t := Time.Elapsed - told
        if t < 1 then
            fps := 1000
        else
            fps := 1000 div t
        end if
        if hasch then
            getch (c)
            fps := 200
            maxframe := false
        end if
    else
        delay ((1000 div fps) - t)
        if hasch then
            getch (c)
            if fps > 20 then
                fps -= 10
            elsif fps > 1 then
                fps -= 1
            else
                exit
            end if
        end if
    end if
    told := Time.Elapsed
    %drawfilloval (round (x), round (y), 15, 15, white)
    cls
    x += xv * (1000 / fps) / 2
    y += yv * (1000 / fps) / 2
    Text.Locate (1, 1)
    put fps
    if maxframe then
        put "Currenty running as fast as it can"
        put "Press any key to switch to 200 fps" ..
    else
        put "Currently running at the above rate"
        put "If you can notice a lag please let me know"
        put "Press any key to decrease the refresh rate"
    end if
    drawfilloval (round (x), round (y), 15, 15, col)
    View.Update
    if x > maxx then
        xv := -1
        collided := true
    elsif x < 0 then
        xv := 1
        collided := true
    end if
    if y > maxy then
        yv := -1
        collided := true
    elsif y < 0 then
        yv := 1
        collided := true
    end if
    if collided then
        col := Rand.Int (0, 5)
        case col of
            label 0 :
                col := brightred
            label 1 :
                col := brightblue
            label 2 :
                col := brightpurple
            label 3 :
                col := 42
            label 4 :
                col := yellow
            label 5 :
                col := brightgreen
        end case
        collided := false
    end if
end loop
put "Thank you for using Nathan's frame rate test. Please go to www.compsci" ..
put ".ca and find the code optimization thread under turing>turing tutorials"
put "Please let me post and let me know what speed you noticed it lagging at"
put "(if you haven't yet please try this a couple of times so you can get " ..
put "an accurate answer"
View.Update
Input.Pause
Window.Close (win)


okay and is there a way to get the ip address with turing? I guess it only returns the local ip address
Display posts from previous:   
   Index -> Programming, Turing -> Turing Tutorials
View previous topic Tell A FriendPrintable versionDownload TopicRate TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 10 Posts ]
Jump to:   


Style:  
Search: