First real game project - Performance Tips?

[andrew2110]

Hi Guys.

I've tried making a game for my friends website. They've gone ahead and integrated it with their system but I still worry that performance is not that great, frame rates are slow on older computers and route finding is incredibly slow especially when the user has made a maze and changes a route.

Thats a link to the free game on the site if anyone gets a chance to let me know their thoughts or ideas on how to make it all a bit faster?

http://www.dukesbox.com/publicAPI/doKo.php?cupid=103&round=1

The way I've tried to do the path finding is using A*, and every time I find a route from a tile I save that route information in a tile array. So next time a creep needs a route from that tile, the route doesn't need to be regenerated, it can just be copied over to the creeps local array. Also when a new route is generated, every tile in the path will be updated with the new route.

Example:

Tile A gets new route:
Tile A Route = {Tile B, Tile C, Tile D - Finish Tile)
New route gets copied to other tiles on the route
Tile B Route = {Tile C, Tile D - Finish Tile)
Tile C Route = {Tile D, Finish Tile)

But even with me trying to be clever like this route finding is very slow, the only extra idea I have is to make route finding find the quickest path to a known valid route, instead of always finding the route to the finish point. Hopefully there will be gains from this, but any other ideas would be great!

Thanks in advance guys!

[justkevin]

How often/under what circumstances do you recalculate routes?

[andrew2110]

When a new tower is placed all tiles will be checked as 'checkRoute=true'. Then next time a creep requests a route from that tile, it will check to see if the route is still valid. If it's not valid, only then will the A* algorithm be called to ask for another route. Also when a tower is sold, a new route is generated regardless of whether the existing route is valid or not (maybe theres a quicker route now a tower got sold?)

Couldnt think of a better way of doing that part of the route finding stuff.

[justkevin]

Could you spread out the route calculations over several frames? Let's say a new tower has been placed somewhere that blocks all best routes. Rather than recalculate everbody's route one the next frame, just recalculate the route for one unit. The next frame, recalcuate the route for the next unit. This would spread the load of route calculation over multiple frames.

[andrew2110]

When a new creep group gets released, they 'sleep' for a random amount of time (the range of the random value is determined on the type of creep, some come out in tightly packed groups so have a small random range). Anyway they wont look at the route for the tile they are started in until they are 'woken' from their sleep. This way the A* calculations are spread over many different frames.

I think that the biggest problem for me is that frame rates are slow on older computers when users have built a bit of a maze and each tower is targetting a creep and firing projectiles at them. I've tried to combat this in a lot of ways including: getting rid of gradients where possible, removing maths functions and replacing them with lookup tables (SIN/COSINE) and constants and a few other things. If anyone has any clever ideas about how else to optimise flash movies like this, I'd be very happy to hear it :)

[cooldude88]

ok so im not sure how to optimize your code without seeing it for one and another just a little quirk in the game, you should probobly put a marker of some sort as to where the enemies are gonna come out since when i started the game it was kinda like okay 4 doors 50-50 chance of getting it right.

[andrew2110]

I've been working all night on trying to cut down the amount of time the A* routine takes and have managed to get it from 600ms in the worst case scenario to 50ms in the worst case....

Is there much need for A* flash tutorials / code examples for tile based games? If there is I'll try publishing some of the code for people to use / improve as they wish.

I think most of the problems now are with the time it takes to render graphics, especially later on in the game. If anyone has any tips or tricks to speed up render time then that'd be great.

Just incase I'm doing something really dumb in my main loop... here it is:


function doCreeps()
{
if(gameStarted==true)
{
fps++;
aStarDoneThisFrame = false;
for(var i10=0;i10<_root.liveCreeps.length;i10++)
{
if(_root.liveCreeps[i10]._visible==true)
_root.liveCreeps[i10].doMovement(); else
{
_root.cleanCreep(i10);
}
}
for(var i10=0;i10<=_root.liveProjectiles.length;i10++)
{
_root.liveProjectiles[i10].doMovement();
if(_root.liveProjectiles[i10]._visible ==false)
{
_root.cleanProjectile(i10);
}
}
if(fps%2) // Towers need to be called half as much as creeps+projectiles
for(var i9=0;i9<=_root.towerList.length;i9++)
{
if(_root.towerList[i9].towerOnDisplay._visible ==false)
{ // Tower is sold, clean the tile.
unloadMovie(towerList[i9].towerOnDisplay);
towerList[i9].isTower=false;
towerList[i9].canBuild=true;
towerList[i9].towerType=0;
towerList[i9].upgradeLevel=0;
towerList[i9].rangeImage._visible = false;
towerList.splice(i9,1);
trace("unloading tower towerlist now "+towerList.length);
}
else
if(_root.towerList[i9].isTower==true)
_root.towerList[i9].takeAim();
}
}
}

var manageCreeps = setInterval(doCreeps, 1000/30);


Thanks guys

[lancerawks]

haha your game is fun and addictive but so crazy hard. i didnt find it slow on my computer and mines not that great. good job man

[andrew2110]

Thanks!

The guy I did the game for has now told me he needs Towers to be offset against each other which makes route finding far more difficult... I've got this far so far:

http://www.dukesbox.com/latestTDinDev.png

(sorry for the huge image)

This has meant A* is now not fast enough again so back to the drawing board! Back to the drawing board I guess :) Still open to any advice on speeding rendering info.

[Gathan]

If your really going back to the drawing board do the game in AS3, its fast enough to use A* directly. The AVM1 does have its limitations and speed wise palls in comparison to AVM2.
Also its not nearly as optimized as it could be.
For instance slower


for(var i10=0;i10<_root.liveCreeps.length;i10++) {
}
Faster


var length = _root.liveCreeps.length
for(var i10=0;i10<length;i10++) {
}

[andrew2110]

Wow thanks, I use those kind of For loops everywhere so hopefully that will help out a bit. Also I wasn't aware AS3 was much quicker than AS2, I'll try searching for some AS3 tutorials and try to find out what the key differences are. Hoping its syntactically quite similar though, this games ended up being ~5,000 lines long!

[mullwaden]

One hot tip for speeding up A* is using priority queues it can probably speed it up 3-4 times.

[Insane au]

@Gathan

I don't see how adding a superfluous variable will speed up your code, especially if there is only one loop.

[justkevin]

@Gathan

I don't see how adding a superfluous variable will speed up your code, especially if there is only one loop.

Array.length calls the array's getter method, which will be called once per loop. Presetting its value outside the loop will avoid this call. Someone has tested this and confirmed the benefit for AS3:

http://rozengain.com/?postid=35 (http://rozengain.com/?postid=35)

[andrew2110]

Sorry i hadnt checked back here in a few days, thanks for your messages.

I hadnt heard of priority queues before with A*, I'll try to find some examples on the web, unless anybody has some good articles bookmarked?

The rewrite in AS3 is almost complete now and can be viewed at:
http://www.dukesbox.net/games/game18.php

It seems a lot quicker on my computer, although computers with no graphics cards / graphics cards not compatible with flash really struggle with the rendering which is a bit of a worry.

[rrh]

It occurs to me that you say you re-check all the paths every time you place a tower. Would it be possible to only re-check the paths that pass through the location of the tower?

[andrew2110]

I tried to be clever about it in that respect,

When a user attempts to build a tower, the existing route from one of the startTiles to one of the endTiles is checked (routes for all tiles are contained in the routeCache) if they're not still valid, A* is ran to make sure that the new tower doesnt block the creeps from getting across the map. If it managed to find a route across the map, it will save the new route in all of the tiles that the route contains (in the routeCache).

When the tower is constructed, all Creeps have a flag named 'checkRoute'. If this is set to true then on the creeps next movement they will scan through their route to see if its valid still, if its not, it will check the tiles routeCache to see if a valid route exists for the creeps location. If it doesnt the creep will then generate a new route to a tile that does contain a valid route (or to the finish, which ever A* finds first).

I've been working for this for about a month now and have been adding new ideas to it whenever I've thought of them, any more ideas are welcomed!

[Gathan]

Sorry i hadnt checked back here in a few days, thanks for your messages.

I hadnt heard of priority queues before with A*, I'll try to find some examples on the web, unless anybody has some good articles bookmarked?

The rewrite in AS3 is almost complete now and can be viewed at:
http://www.dukesbox.net/games/game18.php

It seems a lot quicker on my computer, although computers with no graphics cards / graphics cards not compatible with flash really struggle with the rendering which is a bit of a worry.
One example of a priority queue would be a binary heap, heres a basic discussion about how to use it with pathfinding http://www.policyalmanac.org/games/binaryHeaps.htm
You only really gain any benefit with using that type of data structure with large number of nodes though, so depending on how many nodes your map has you may or may not gain any benefit from using it.
Also I don't know if your doing this or not but if the creeps are together on the same node than they would all be using the same path so you should only be using one path search for all of them instead of individually doing a path search for each one.
Looking at the that prototype I can see its running way to hot with 90% cpu usage and as soon as I put down another turrent the game completly stops for a second and two, heck I don't even have to do that all I got to do is move the mouse and it does the same thing.
Thats not good:|

[andrew2110]

well thats more than just a little bit terrifying that it run's at 90% cpu for you. I put some monitoring code in to see where the time was bein taken up. The results were that on average about 60ms in a 1000ms time period processing the main game loop. So given the main game loop runs 30 times a second, 2ms to calculate everything doesn't seem too bad (when a star is used average time taken in a 1000ms period goes up to 150ms). There are more optimisations i can make to the code but in my opinion those times seem ok. My worry is that i've caused problems 4the renderer some how, although i'm not sure how, the movies frame rate is set to 25fps...

O also creatures will always check to see if a premade route is available from their current node and use a* as a last resort. Thanks for the link as well, i'll check it now :)

[andrew2110]

I've been advised that combining everything to a few visible bitmaps would help speed up performance as having a lot of seperate movie clips on stage is a bad idea.

The current way I do things is:

var towerLayer:MovieClip = this.addChild(new layer()) as MovieClip;
var creepLayer:MovieClip = this.addChild(new layer()) as MovieClip;
var projectileLayer:MovieClip = this.addChild(new layer()) as MovieClip;
var ainterfaceLayer:MovieClip = this.addChild(new interfaceLayer()) as MovieClip;

And then if I want to say add a tower for example i do:

this.towerLayer.addChild(new towerBase());

So I guess now instead of attaching the movieClip to the layer.stage , I'll somehow draw the bitmap thats representative of the towers current state to that stage.

I've had a look around and haven't been able to find any tutorials that suggest a method for doing this in AS3, so any advice would be great :) thanks for your patience with me guys, its very much appreciated.

[Giferd]

Really easy way-

Half your vars and speed rates then double the frame rate.

Make the game run far far smoother.

[andrew2110]

The problem i foresee with that is that it will effectively double the amount of processing power required (correct me if I'm wrong on that). I think I need to work out how to do the bitmap thing, although reading up about it, I dont understand at all what I'm being told to do with it.

[rrh]

Not directly related, but noteworthy:

for(var i9=0;i9<=_root.towerList.length;i9++)
Note that if the length of an array is, for example, 3, then the indices are 0,1 and 2. Your loop will execute for values of 0,1,2 and 3. Something everyone deals with when first using arrays and loops.

Next, how are you storing the A star data?

[andrew2110]

Wow what a rookie mistake that was.... I was fairly new to flash before this, but a professional C++ developer still so should have known a lot better! I'll put that down to being tired!

Once A* has finished, I store the found route in an array. and store this array in a routeCache. For example routeCache[5,5] = foundRoute; would give the tile with co-ordinates 5,5 the route 'foundRoute'

The route array is fairly simple, each element on the array contains only the x and y co-ordinates of that part of the route, this corresponds to a tile on the map.

The actual A* part itself has the obvious open lists and closed lists (will be changing the open list to a binary heap now). But also contains data structures so that I can speed up the 'existsOnClosed()' function. The tile map is not huge, about 1000 tiles in total. I sped up the existOnClosed() function by adding a new datatype - flaggedOnClosed[][]. Each element on this array corresponds to a tile, and initially all values in this datatype are set to false. Whenever an element is added to the closed list the corresponding 'flaggedOnClosed[][] element is set to true. For example if tile 12,8 is added to the closed list, flaggedOnClosed[12][8] = true. Then when it comes to check whether an item (x,y) is on the closed list or not I can simply return flaggedOnClosed[x][y] rather than scanning through the whole closed list checking whats there. Most of my approaches now seem to be based around taking up a lot of memory in return for speed improvements :S

[Gathan]

The problem i foresee with that is that it will effectively double the amount of processing power required (correct me if I'm wrong on that). I think I need to work out how to do the bitmap thing, although reading up about it, I dont understand at all what I'm being told to do with it.
You mean bitmap rendering, yes it does have its uses and is faster as far as rendering goes.
It does have its draw backs such as if you want to scale a object, the pixels don't make it look pretty at all which is where vector graphics shines.
Anyways why not try something simple for starters like http://www.8bitrocket.com/newsdisplay.aspx?newspage=6765

[andrew2110]

Thanks for the link, it looks a really valuable resource. Not being able to scale sprites is fine as I can just pre-make my sprites in different sizes if I need, but the thing I see being the problem is rotating sprites around 360 degrees. I tried this with AS2 and bitmaps and it looked just awful. Should I premake all my sprites facing in a large number of directions or will I not have a problem rotating these sprites in AS3?

Off to read that 8bitrocket site now, thanks very much for that