techPowerUp! Forums Optimizing Python game
 techPowerUp! Register FAQ Social Groups Search Today's Posts Mark Forums Read

 Jun 21, 2012, 09:35 PM #1 hellrazor     Join Date: Feb 2010 Posts: 1,361 (1.12/day) Thanks: 1,414 Thanked 276 Times in 194 Posts System Specs Optimizing Python game 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). __________________ "Doom means two things: demons and shotguns." -John Carmack
 Jun 21, 2012, 09:42 PM #2 FordGT90Concept "I go fast!1!11!1!"     Join Date: Oct 2008 Location: IA, USA Posts: 10,651 (6.23/day) Thanks: 1,787 Thanked 2,632 Times in 1,986 Posts System Specs Minimize your updates to only include data that requires updating. __________________ Golden Rule of Programming: Never assume. try { SteamDownload(); } catch (Steamception ex) { RageQuit(); }
 Jun 22, 2012, 04:19 PM #3 Jizzler     Join Date: Aug 2007 Location: Geneva, FL, USA Posts: 3,010 (1.41/day) Thanks: 567 Thanked 606 Times in 487 Posts System Specs 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.
 Jun 22, 2012, 04:59 PM #4 Aquinus     Join Date: Jan 2012 Location: Dover, New Hampshire, USA Posts: 4,508 (8.87/day) Thanks: 1,441 Thanked 1,424 Times in 1,064 Posts System Specs 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. __________________ MyHeat
Jun 22, 2012, 07:21 PM   #5
hellrazor

Join Date: Feb 2010
Posts: 1,361 (1.12/day)
Thanks: 1,414
Thanked 276 Times in 194 Posts

System Specs

Quote:
 Originally Posted by FordGT90Concept Minimize your updates to only include data that requires updating.
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.

Quote:
 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.

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

Quote:
 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:
Code:
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.
__________________
"Doom means two things: demons and shotguns." -John Carmack

Last edited by hellrazor; Jun 22, 2012 at 08:07 PM.

Jun 22, 2012, 08:29 PM   #6
Aquinus

Join Date: Jan 2012
Location: Dover, New Hampshire, USA
Posts: 4,508 (8.87/day)
Thanks: 1,441
Thanked 1,424 Times in 1,064 Posts

System Specs

Quote:
 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.)
__________________
MyHeat

Jun 22, 2012, 09:11 PM   #7
hellrazor

Join Date: Feb 2010
Posts: 1,361 (1.12/day)
Thanks: 1,414
Thanked 276 Times in 194 Posts

System Specs

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.

Quote:
 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.

Quote:
 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.

Quote:
 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.

Quote:
 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.
__________________
"Doom means two things: demons and shotguns." -John Carmack

Last edited by hellrazor; Jun 22, 2012 at 09:20 PM.

 Jun 22, 2012, 10:35 PM #8 Kreij Hardcore Monkey Moderator     Join Date: Feb 2007 Location: Cheeseland (Wisconsin, USA) Posts: 12,254 (5.27/day) Thanks: 591 Thanked 5,510 Times in 2,948 Posts System Specs 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 __________________ Cloud (noun, singular): A dynamic arrangement of multiple potential single points of failure, with a user at one end and their data at the other. Get more tech news on a wide variety of topics at NextPowerUp
 Jun 23, 2012, 02:21 AM #9 hellrazor     Join Date: Feb 2010 Posts: 1,361 (1.12/day) Thanks: 1,414 Thanked 276 Times in 194 Posts System Specs But..... look how beautiful it is: You gotta admit, that's pretty sexy. __________________ "Doom means two things: demons and shotguns." -John Carmack
 The Following User Says Thank You to hellrazor For This Useful Post:
 Jun 23, 2012, 03:03 AM #10 Chevalr1c     Join Date: Sep 2010 Location: Tilburg, Netherlands Posts: 2,101 (2.06/day) Thanks: 5,202 Thanked 815 Times in 550 Posts System Specs 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. __________________ My FS/FT thread (EU only) | DynMap of the TPU Minecraft server | Quick monitor calibration guide | Boot Failure Troubleshooting Chart | Solar Team Eindhoven Family Car Project Using BOINC I crunch numbers for World Community Grid, Climateprediction, Free Rainbow Tables (currently on hold) and POEM@home; hence assisting research.
 Jun 23, 2012, 03:41 AM #11 hellrazor     Join Date: Feb 2010 Posts: 1,361 (1.12/day) Thanks: 1,414 Thanked 276 Times in 194 Posts System Specs 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). __________________ "Doom means two things: demons and shotguns." -John Carmack
 Jun 23, 2012, 05:47 AM #12 Vinska     Join Date: Jul 2011 Location: Kaunas, Lithuania Posts: 578 (0.83/day) Thanks: 444 Thanked 274 Times in 159 Posts System Specs 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. __________________ Why do you wear glasses if you're deaf? Code: while (1) { alone(); }
 Jun 23, 2012, 05:09 PM #13 hellrazor     Join Date: Feb 2010 Posts: 1,361 (1.12/day) Thanks: 1,414 Thanked 276 Times in 194 Posts System Specs Since it uses hexes, that would only get rid of 2 vertices for every 17 - not exactly a huge difference. __________________ "Doom means two things: demons and shotguns." -John Carmack
 Jun 23, 2012, 06:02 PM #14 Vinska     Join Date: Jul 2011 Location: Kaunas, Lithuania Posts: 578 (0.83/day) Thanks: 444 Thanked 274 Times in 159 Posts System Specs 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] __________________ Why do you wear glasses if you're deaf? Code: while (1) { alone(); }
 The Following User Says Thank You to Vinska For This Useful Post:
Jun 25, 2012, 12:04 PM   #15
Aquinus

Join Date: Jan 2012
Location: Dover, New Hampshire, USA
Posts: 4,508 (8.87/day)
Thanks: 1,441
Thanked 1,424 Times in 1,064 Posts

System Specs

Quote:
 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.
__________________
MyHeat

 Aug 4, 2012, 06:56 AM #16 Vinska     Join Date: Jul 2011 Location: Kaunas, Lithuania Posts: 578 (0.83/day) Thanks: 444 Thanked 274 Times in 159 Posts System Specs 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! __________________ Why do you wear glasses if you're deaf? Code: while (1) { alone(); }

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

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Hardware     General Hardware     Graphics Cards         NVIDIA         AMD / ATI     Overclocking & Cooling     Motherboards & Memory     System Builder's Advice     Cases, Modding & Electronics     Storage     Networking & Security     Project Logs     Audio, Video & Home Theater     Official Vendor Support & Information Forums         be quiet!         NZXT         Thermaltake Software     Games     Linux / BSD / Mac OS X     General Software     Programming & Webmastering Other     General Nonsense     Science & Technology     Folding@Home     World Community Grid (WCG)     Buy/Sell/Trade/Giveaway Forum     Hot Deals     techPowerUp! Club Forum www.techpowerup.com     Comments & Feedback     Reviews     Articles     News         TPU Frontpage Polls     Case Mod Gallery     Contests Our Software     GPU-Z         GPU-Z Test Builds         GPU-Z Translations     ATITool         ATITool Beta Area         ATITool Bug Reports     RBE     RealTemp

 Similar Threads Thread Thread Starter Forum Replies Last Post MikeJeng Storage 10 Feb 3, 2011 08:22 PM D007 Games 14 Feb 17, 2010 10:18 PM audiotranceable Games 13 Sep 8, 2009 03:46 AM ho0dzy General Hardware 48 Jan 27, 2008 06:16 AM naseltzer Graphics Cards 1 Jan 8, 2006 02:48 AM

All times are GMT. The time now is 06:05 PM.

 -- Default Style -- Lightweight Contact Us - techPowerUp! - Archive - Top