Optimizing Python game

[hellrazor]

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:

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:

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).

[FordGT90Concept]

Minimize your updates to only include data that requires updating.

[Jizzler]

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.

[Aquinus]

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.

[hellrazor]

Originally Posted by FordGT90Concept

Minimize your updates to only include data that requires updating.

That's what

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.

Originally Posted by Jizzler

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.

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.

Originally Posted by Aquinus

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.

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).

Originally Posted by Aquinus

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.

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:

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.

[Aquinus]

Originally Posted by hellrazor

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).

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.)

[hellrazor]

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.

Originally Posted by Aquinus

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.

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.

Originally Posted by Aquinus

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

Sure, shouldn't be too hard.

Originally Posted by Aquinus

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

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.

Originally Posted by Aquinus

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.)

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.

[Kreij]

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

[hellrazor]

But..... look how beautiful it is:



You gotta admit, that's pretty sexy.

[Chevalr1c]

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.

[hellrazor]

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).

[Vinska]

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.

[hellrazor]

Since it uses hexes, that would only get rid of 2 vertices for every 17 - not exactly a huge difference.

[Vinska]

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]

Originally Posted by hellrazor

Since it uses hexes, that would only get rid of 2 vertices for every 17 - not exactly a huge difference.

12% is actually reasonable imho.

[Vinska]

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!