1. Welcome to TechPowerUp Forums, Guest! Please check out our forum guidelines for info related to our community.

Optimizing Python game

Discussion in 'Programming & Webmastering' started by hellrazor, Jun 21, 2012.

  1. hellrazor

    hellrazor

    Joined:
    Feb 18, 2010
    Messages:
    1,572 (0.96/day)
    Thanks Received:
    315
    I'm currently pretending to make a game, it uses a hex-based tile system and uses Python 3.2 and PyGame. Most everything is fine, but I decided I want to use really big maps - and therein lies the problem.

    I am currently using a map that is ~22000 tiles big, and guess what? Things are really slow, and I've spent about 3 hours optimizing every thing that's related to it.

    So here is my unoptimized code:
    Code:
    def drawhex(tile, layer=0, pos=(int(VIEW[x]+(MODE[x]/2)), int(VIEW[y]+(MODE[y]/2))), mul=STEP*VIEW[z]):
        #This needs to be seriously sped up:
        tile.polys = ((tile.verts[0][x]*mul+pos[x], tile.verts[0][y]*VIEW[z]+pos[y]),
                      (tile.verts[1][x]*mul+pos[x], tile.verts[1][y]*VIEW[z]+pos[y]),
                      (tile.verts[2][x]*mul+pos[x], tile.verts[2][y]*VIEW[z]+pos[y]),
                      (tile.verts[3][x]*mul+pos[x], tile.verts[3][y]*VIEW[z]+pos[y]),
                      (tile.verts[4][x]*mul+pos[x], tile.verts[4][y]*VIEW[z]+pos[y]),
                      (tile.verts[5][x]*mul+pos[x], tile.verts[5][y]*VIEW[z]+pos[y]))
        #This is fine:
        pygame.draw.polygon(LAYERSURFACES[layer], COLORS[tile.terrain], tile.polys)
        if GRIDSPACING: pygame.draw.lines(OVERLAYSURFACES[0], (0, 0, 0, 255), True, tile.polys, GRIDSPACING)
    Which takes ~1.5 seconds (also, it gets called for every tile).

    And here is my optimized code:
    Code:
    def drawhex(tileset, layer=0):
        #Sorry, I had to optimize the shit out of this
        #This needs to be seriously sped up (still a significant slowdown while zoomed out):
        #for tile in tileset.values():
        #timmay = time.time()
        pos = (int(VIEW[x]+(MODE[x]/2)), int(VIEW[y]+(MODE[y]/2)))
        mul = STEP*VIEW[z]
        posx = pos[x]
        posy = pos[y]
        zoom = VIEW[z]
        #These seem help when zoomed out
        drawlayer = LAYERSURFACES[layer]
        overlay = OVERLAYSURFACES[0]
        space = GRIDSPACING
        color = COLORS
        #Seems to help a little bit:
        xA = 0.00
        xB = 0.00
        xC = 0.00
        yA = 0.00
        yB = 0.00
        yC = 0.00
        yD = 0.00
        for tile in tileset:
            verts = tile.verts
            xB = verts[1][0]*mul+posx
            if xB > 0:#Maybe check Y values first?
                xC = verts[4][0]*mul+posx
                if xC < MODE[0]:#Width
                    yA = verts[0][1]*zoom+posy
                    if yA > 0:
                        yD = verts[3][1]*zoom+posy
                        if yD < MODE[1]:#Height
                            polys = tile.polys
                            xA = verts[0][0]*mul+posx
                            yB = verts[1][1]*zoom+posy
                            yC = verts[2][1]*zoom+posy
                            polys = ((xA, yA),
                                     (xB, yB),
                                     (xB, yC),
                                     (xA, yD),
                                     (xC, yC),
                                     (xC, yB))
                            pygame.draw.polygon(drawlayer, color[tile.terrain], polys)
                            if GRIDSPACING: pygame.draw.lines(overlay, (0, 0, 0, 255), True, polys, space)
                            #print(time.time()-timmay)
    Which takes ~.08 seconds at default zoom and ~.72 seconds zoomed out as far as I can go. It only gets called the one time and does everything from there and tileset is currently a frozenset (I was thinking about sorting it into a tuple and culling from there).

    Unfortunately I'm still not happy with that and the only way I can think to make it faster is to rewrite it in C - which I really do not want to do (at least not at the moment).

    So do you have any tips (aside from the sorting, which I'll get on later today)? Anything small little thing should help (seriously, it loops 21,931 times, anything will do).
  2. FordGT90Concept

    FordGT90Concept "I go fast!1!11!1!"

    Joined:
    Oct 13, 2008
    Messages:
    13,415 (6.27/day)
    Thanks Received:
    3,395
    Location:
    IA, USA
    Minimize your updates to only include data that requires updating.
    Crunching for Team TPU
  3. Jizzler

    Jizzler

    Joined:
    Aug 10, 2007
    Messages:
    3,404 (1.33/day)
    Thanks Received:
    635
    Location:
    Geneva, FL, USA
    How much time is spent doing the calculations and how much time is spent drawing? Comment out the draw calls and re-run. It may turn out that there's no amount of noticeable optimization left on your end and you'll have to take a different approach to your tile system.

    Looking through the PyGame docs I see there's a new (still experimental) alternative to draw, gfxdraw. Try it out?

    I was going to say thread it out because of how parallel the work is, but that won't help you on your Athlon64.

    Anything else you can tell us about the game? Might be an easier to accomplish what you're after.
  4. Aquinus

    Aquinus Resident Wat-man

    Joined:
    Jan 28, 2012
    Messages:
    6,165 (6.58/day)
    Thanks Received:
    2,022
    Location:
    Concord, NH
    You know, as long as the viewport position and zoom doesn't change, you can use the already calculated polys on each tile. Then only when the position or zoom changes you can recalculate. You will need to watch the posx, posy, and zoom for changes, if none don't calculate, otherwise calculate. xB and xC can also be stored and only recalculated if posx changes instead of calculating it every time. yA and yD can also be stored and only recalculated if zoom and posy change (since changes to posx doesn't impact these calculations.)

    What I would do is keep track of the "state" of posx, posy, and zoom so you don't have to calculate more than you have to because you should only recalculate if you're:
    A: running out of memory and can't store everything.
    B: if any of the variable for the calculation that get used have changed.

    So you need some variables like last_posx, last_posy, and last_zoom, and base your calculations on the difference between the last_ variable and the current one. That would speed up calculations when the viewport doesn't change. You can try and make this multithreaded as well, because this kind of workload is extremely parallel. I would recommend a couple of worker threads that work through the calculations and to store them and a single thread to actually render the polys of the tiles.

    I don't know what else I can say*without actually trying to implement it. I hope that was of some use to you.
  5. hellrazor

    hellrazor

    Joined:
    Feb 18, 2010
    Messages:
    1,572 (0.96/day)
    Thanks Received:
    315
    That's what

    Code:
    for tile in tileset:
            verts = tile.verts
            xB = verts[1][0]*mul+posx
            if xB > 0:#Maybe check Y values first?
                xC = verts[4][0]*mul+posx
                if xC < MODE[0]:#Width
                    yA = verts[0][1]*zoom+posy
                    if yA > 0:
                        yD = verts[3][1]*zoom+posy
                        if yD < MODE[1]:#Height
    is mostly for.

    I'm not sure whether you mean what kind of game it is or the technical stuff, so I'll go for all of it. At the moment it's just an engine (as in, there's no campaign), it's meant to be used for turn-based RPG games, and it uses hexes as tiles. There are a few screenshots of it: a small map without gridspaces and a big map with gridspaces, I'm currently benching it with the big one (although I changed the terrain so that all the outside ones are water instead of dirt because dirt looked ugly). I'm currently using a big dictionary to store the info about the tiles, which (at the moment) include attributes for where the vertices are and what terrain the tile is. I'm also trying to keep the graphics system and the game engine itself as separate as possible so that should I ever actually get good at this I can build better (maybe even 3D, the game engine supports it) graphics systems and just shove them in there (or give people an option between the two).

    Most of the actual "game" (rules, monsters, stats, skills, etc) will be defined by the campaign, and the one I'm thinking about building around it will be based on Pathfinder. I'm currently think about a free-roaming game (pronounced "I don't have a plot yet"). I'm also thinking about making it more mature (this'll go awesome with the '93 era graphics system) so you or villains or whoever can have sex, rob people, raze cities, kill kids, kidnap kids (and maybe ransom them), rape, torture, slavery, racism, the whole bit (I'm not gonna make you do any of it, but there's a really good chance you'll come across it). I'm also trying to make it quite big, with lots of societies each with their own laws, flaws, religions, government, people etc., etc.

    I already did something like that (it was tied to the zoom in/out and move left/right/up/down controls), but it just recalculated everything (I just had an UPDATE variable). I never came up with the idea that Xs and Ys could stay the same (to be fair, I was using zooming as a benchmark anyways, so it probably wouldn't have helped too much).

    I was thinking about that last night, but as Jizzler pointed out, my current CPU is single core (and knowing Python, making it multithreaded would likely hurt my performance). But I'm sure I could come up with something like:
    Code:
    if MULTITHREADED:
        sets = []
        for i in range(len(SUBPROCESSES)):
            sets.append(split up tileset)
        for i in SUBPROCESSES:
            SUBPROCESSES[i].run(drawhex, something something)
    else:
        drawhex(tileset)
    And maybe change it up some so that the threads do the calculations of where the vertices are and the main thread actually does the drawing.


    EDIT:
    It turns out that drawing the tiles is about half the work.
    Last edited: Jun 22, 2012
  6. Aquinus

    Aquinus Resident Wat-man

    Joined:
    Jan 28, 2012
    Messages:
    6,165 (6.58/day)
    Thanks Received:
    2,022
    Location:
    Concord, NH
    The issue with having an update variable is that you have to do the checks and calculations anyways. You want to be able to compare the raw data and use that to determine if an update is required. That way you don't need to do this extra work.

    Could you get the previous posx posy, and zoom variables from the last frame sent to the next frame to compare? If you can you can find out what needs to be updated:

    If posx or mul changes update:
    xA, xB, and xC

    If posy or zoom changes update:
    yA, yB, yC, and yD

    if nothing changes use the already stored polys. The only downfall of this is that you need to store all of those variables.

    Is it possible to provide a little more of the project you're working on? It might help us to get a wider perspective and to know what you have available to you before drawhex gets called because you might have data that could help you do less floating point math (which is reasonably slower than integer math and comparisons.)
  7. hellrazor

    hellrazor

    Joined:
    Feb 18, 2010
    Messages:
    1,572 (0.96/day)
    Thanks Received:
    315
    I tried gfxdraw and I'm not sure if it's faster (it uses a different argument order, so I had to put an if statement to a global variable - globals are slow), but it looks significantly nicer so I think I'll use it anyway.

    No, no, no. I made the zoom/move controls turn the UPDATE variable on, and during the loop it checks if UPDATE is True -i f it is, it calculates/draws everything.

    Sure, shouldn't be too hard.

    It doesn't calculate or draw anything unless UPDATE is True. I just update the display (without changing it's contents) so Windows doesn't say it isn't responding.

    Here's the current source. It's in rough shape (there are a few things I should get busy deleting).


    EDIT:
    I think I'm going to just use pygame.gfxdraw instead of pygame.draw, so the current source will be a little out dated.
    Last edited: Jun 22, 2012
  8. Kreij

    Kreij Senior Monkey Moderator Staff Member

    Joined:
    Feb 6, 2007
    Messages:
    13,881 (5.04/day)
    Thanks Received:
    5,615
    Location:
    Cheeseland (Wisconsin, USA)
    Great job, HR, but after looking at the pygame docs your going to hit the wall real soon.
    Stop now and switch to a language that supports poly and model instancing, has full matrice API support (translation, tranformation, etc.) and fully utilizes HLSL.

    Yes, it has a steep learning curve and will make your brain hurt. Yes, it will be worth it.

    I'm in no way bashing your code or anything, but in a short time you are going to reach a point of no-can-do (or crazy hard to do) with pygame and delaying the move to something else will not make things any easier or give you more insight into writing a solid engine.

    Just my humble opinion. :)

    Code on :rockout:
  9. hellrazor

    hellrazor

    Joined:
    Feb 18, 2010
    Messages:
    1,572 (0.96/day)
    Thanks Received:
    315
    But..... look how beautiful it is:

    [​IMG]

    You gotta admit, that's pretty sexy.
    Jizzler says thanks.
  10. Chevalr1c

    Chevalr1c

    Joined:
    Sep 3, 2010
    Messages:
    3,178 (2.19/day)
    Thanks Received:
    1,356
    Take a look at the source code of the F/OSS game "The Battle for Wesnoth" which is similar to what you seem to want to do: www.wesnoth.org. It is written in a C variety though, AFAIK.
    Crunching for Team TPU
  11. hellrazor

    hellrazor

    Joined:
    Feb 18, 2010
    Messages:
    1,572 (0.96/day)
    Thanks Received:
    315
    If it's C I'm not exactly looking forward to it, but I'll take a stab anyways.

    Anyways I had dinner and it dawned on me that any given vertex can have up to 3 tiles connected to it, and I'm calculating each vertex every time it appears in a tile. So I'll see what I can do about that (I'll probably be gone most of tomorrow though).
  12. Vinska

    Vinska

    Joined:
    Jul 23, 2011
    Messages:
    1,406 (1.25/day)
    Thanks Received:
    1,244
    Location:
    Kaunas, Lithuania
    How 'bout a little "cheating"? ;)
    I mean, LOD. For example, when zoomed out enough, draw 1 "bigger" tile 'stead of 4. Of course, You would lose accuracy of what's visible. Although, If at one point, You would use a map, that when zoomed out completely, would have more than 1 tile/screen_pixel, it wouldn't make that much of visual difference anyway. :laugh:
    Crunching for Team TPU
  13. hellrazor

    hellrazor

    Joined:
    Feb 18, 2010
    Messages:
    1,572 (0.96/day)
    Thanks Received:
    315
    Since it uses hexes, that would only get rid of 2 vertices for every 17 - not exactly a huge difference.
  14. Vinska

    Vinska

    Joined:
    Jul 23, 2011
    Messages:
    1,406 (1.25/day)
    Thanks Received:
    1,244
    Location:
    Kaunas, Lithuania
    1 in place of 4 was an example. You can do various levels of LOD. That's why its 'levels of detail' ;]
    If You can pull this off correctly, even as little as reducing by 2 vertices for every 17 can make a large difference when You have a sh*tload of tiles. Also, If I understand it correctly, it would drastically reduce gfxdraw calls. I think You really do want to reduce gfxdraw by as much as possible. That was the idea in the first place, not the vertices.
    And also the most important thing: right now You only have tiles. When those tiles start holding something more than 'only themselves' (i.e.: objects 'n stuff). Then - not drawing and not even assessing those tiles in the first place, is probably going to be a huge speed-up at that point of development.

    [humble tone]I suppose You do realize that the more You optimize, the less You are able to shave off with each optimization.[/humble tone]
    Aquinus says thanks.
    Crunching for Team TPU
  15. Aquinus

    Aquinus Resident Wat-man

    Joined:
    Jan 28, 2012
    Messages:
    6,165 (6.58/day)
    Thanks Received:
    2,022
    Location:
    Concord, NH
    12% is actually reasonable imho.
  16. Vinska

    Vinska

    Joined:
    Jul 23, 2011
    Messages:
    1,406 (1.25/day)
    Thanks Received:
    1,244
    Location:
    Kaunas, Lithuania
    How's Your progress?
    You just went silent here. Yet, it would really be nice to hear how You are doing there with that engine!
    Crunching for Team TPU

Currently Active Users Viewing This Thread: 1 (0 members and 1 guest)

Share This Page