Sign in to follow this  
HolyGrail

How to improve my game performance ? ( RTS)

Recommended Posts

Hi everybody, I'm finishing my game after a long hard work. It's an RTS game. Basically I have 2 kinds of unit ,player units and ennemies units. In the main loop during every time tick the player and ennemies units ( let's say every 100 milliseconds ) are updated : movement and fighting . I use A* algorithm for entity pathfinding. Concerning the attack of each unit , for example , if the player presses the mouse right button down, it gives the order to shoot at the enemy. I use STL containers to manage units. Basicially what I'm doing is a loop like this if the player gives the order to attack:
Quote:
std::list<PlayerUnit> listPlayers; std::list<EnemyUnit> listEnemies; ... std::list<PlayerUnit>::iterator iter; std::list<EnemyUnit>::iterator iter2; int PlayerPositionX; int PlayerPositionY; int EnemyPositionX; int EnemyPositionY; iter=listPlayers.begin(); while( iter !=listPlayers()) { PlayerPositionX=(*iter).GetPositionX; PlayerPositionY=(*iter).GetPositionY; iter2= listEnemies.begin(); while( iter !=listPlayers()) { EnemyPositionX=(*iter2).GetPositionX; EnemyPositionY=(*iter2).GetPositionY; // check if ennemy is in sight of player unit - 200 is random value if ( FindDistance( PlayerPositionX,PlayerPositionY,EnemyPositionX,EnemyPositionY) <200 ) { (*iter).Attack((*iter2); } iter2++; } iter++; }
This code is also used to make enemies units attack player units. My question is : instead of using a dumb and basic loop as mentioned aboved is there any way to improve the cross attack algorithm ? If you select a few amount of player units it's ok but hundred of units and the frame rates drops. Any "smart" algorithm to give ? Binary trees ? Thank you for the replies

Share this post


Link to post
Share on other sites
You will probably find unless you have implemented something else really badly, that optimising your A* function will have the most effect. This is because the loops in A* are running multiple, possibly hundreds of times per entity each tick.

Look around the web for optimisation techniques and try to apply them.

Share this post


Link to post
Share on other sites
The obvious choice is some form of spatial partitioning.
Quad trees and tiles work well for RTS style games. If you are already using a tile system for your path finding you could adapt it to provide functionallity to efficiently query all the entities in an area. Or just return the bounds of the area so you could iterate through only the relevant tiles checking for entities.
It would also double up as a broadphase collision check and could be used to speed up your rendering by only drawing the tiles (and the entities contained in that tile) that are visible.

There are also simpler optimisations you could do such as chaging FindDistance to be FindDistanceSquared, this avoids the costly square root, but the spatial partitioning will have a much bigger affect on the framerate.

Share this post


Link to post
Share on other sites
You should look at time-slicing if you've not already.

Does each individual tank really need to check it's heading 60 times a second? No

Many things can be shaved off to better spread their cpu load. In a batch of say 10 frames, update tanks 0,9,19,29 on frame 1, 1,10,20,30 on frame 2 etc. Nobody will notice and your A* already runs 10 times quicker by being called 10 times less often per frame.

Share this post


Link to post
Share on other sites
Hello everybody thank you replies :)

Quote:
Look around the web for optimisation techniques and try to apply them.

yes I was thinking of setting the pathfinding loop into a thread

Quote:
Original post by diablos_blade
The obvious choice is some form of spatial partitioning.
Quad trees and tiles work well for RTS style games. If you are already using a tile system for your path finding you could adapt it to provide functionallity to efficiently query all the entities in an area. .

ok this a good suggestion.
But how can I build quad trees for partitioning ?
Like a BSP tree in a FPS Game ( for example DOOM ) ?
You say by using a quad tree, what do I put on the root then on the leaves ?

Quote:
Original post by Rubicon
You should look at time-slicing if you've not already.

Many things can be shaved off to better spread their cpu load. In a batch of say 10 frames, update tanks 0,9,19,29 on frame 1, 1,10,20,30 on frame 2 etc. Nobody will notice and your A* already runs 10 times quicker by being called 10 times less often per frame.

It's a little bit complicated to me but I'm going to think about it.
Thank you again.

Share this post


Link to post
Share on other sites
A standard pathfinding optimization in RTS games is to make pathfinding asynchronous. That is, when a unit needs a path, it requests a path from the Pathfinding system. Then it just chills out until it gets one back.

The pathfinding system is set up so that it performs either X pathfinds per frame or operates for X milliseconds before stopping and waiting until next frame. Every time it generates a path it notifies the unit that requested one.

So you basically make your pathfinding cost constant per frame. This introduces several "problems":

1) latency. It may take ~200ms for the pathfinder to return a path. Usually this is not perceptible from the user and can actually add some realism: "i asked them to go somewhere and they didn't respond instantly like freak robots".

2) bad pointers: because it's asynchronous you need to deal with problems like the unit dying before the pathfind is complete. safe-pointers are a good solution here

3) you can run into problems where there are more pathfind requests than can be handled by your system. This generally means your A* is not optimized so attack it with a profiler: are you using a binary heap for storing the open node? do you actually implement a closed list that has to be searched (bad) or do you just have a bool per node bool isOnClosed (better). Cache coherency also a big deal. etc

4) duplicitous requests. If the user spam clicks a move order a couple times you need to clean out the request queue for stale entries. i.e. if i ordered you last frame to go to point A, but just ordered you to do to point B and if the pathfind for point A hasn't happened yet, remove that request.

Other techniques can involve grouping. i.e. if a group of units are given a move command it may work for your game to just generate a single path for that group and have everyone flock around the leader. but this is very game specific and may not work for you. I'd stick to the above first.

Hierarchical A* is also something you want to look at for an RTS. pathing across a whole map with traditional A* is obviously going to be hugely expensive.

-me

Share this post


Link to post
Share on other sites
Quote:
Original post by HolyGrail
ok this a good suggestion.
But how can I build quad trees for partitioning ?
Like a BSP tree in a FPS Game ( for example DOOM ) ?
You say by using a quad tree, what do I put on the root then on the leaves


Quadtrees are fairly different from BSP trees, most notably Quadtrees are just built up of deterministically sized axis-aligned bounding boxes, instead of frame dependant, awkwardly calculated split planes and polygon soups of data [smile].
But I'm sure this can explain it better than I can.

However, if you currently are using a tile system for your pathfinding, you probably would be better off just adapting that for now. The only reason I would switch from tiles to a Quadtreee in your situation would be if I was planning on implementing a Hierarchical A* system like Palidine suggested. Quadtrees would lend themselves better to that than a tile system, since they are already Heirarchical [smile].

Share this post


Link to post
Share on other sites
std::vector performs faster than std::list in iterating. if you don't add or remove a lot of elements at runtime, you might consider using std::vector.

Share this post


Link to post
Share on other sites
Your bottleneck is right at the loop inside the loop there, and you are going through all player and enemy units even though they are completely far away off from each other.

Quote:
Original post by HolyGrail
Quote:
Original post by diablos_blade
The obvious choice is some form of spatial partitioning.
Quad trees and tiles work well for RTS style games. If you are already using a tile system for your path finding you could adapt it to provide functionallity to efficiently query all the entities in an area. .

ok this a good suggestion.
But how can I build quad trees for partitioning ?
Like a BSP tree in a FPS Game ( for example DOOM ) ?
You say by using a quad tree, what do I put on the root then on the leaves ?

Quadtrees basically partition your space into smaller sub-rectangles. Imagine a rectangle divided into four evenly-sized smaller rectangles, then each of these smaller rectangles are divided even further.

Instead of having two giant lists of units, each smallest rectangle (leaf nodes) will maintain its own list of units that are present inside that rectangle. Units in this list are then checked against one another, but not against units that belong to another list of another rectangle. This will optimize your loop because a player unit that's located on the bottom-left corner of the map will not be checked against an enemy unit that's located on the top-right corner of the map.

Share this post


Link to post
Share on other sites
>>Your bottleneck is right at the loop inside the loop there, and you are going through all player and enemy units even though they are completely far away off from each other.<<

I wouldnt bet on it, my money would be on the A*

the OP needs to find the actual bottleneck

Share this post


Link to post
Share on other sites
Quote:
Original post by zedz
>>Your bottleneck is right at the loop inside the loop there, and you are going through all player and enemy units even though they are completely far away off from each other.<<

I wouldnt bet on it, my money would be on the A*

the OP needs to find the actual bottleneck


I must emphasize the truth in this. If you do not run a profiler to find the bottlenecks in your system, you will probably just waste your time.

Share this post


Link to post
Share on other sites
Quote:
[i]
Other techniques can involve grouping. i.e. if a group of units are given a move command it may work for your game to just generate a single path for that group and have everyone flock around the leader. but this is very game specific and may not work for you. I'd stick to the above first.

Hierarchical A* is also something you want to look at for an RTS. pathing across a whole map with traditional A* is obviously going to be hugely expensive.

-me


Wow I didn't think about grouping units and make a single path it's a good idea !
Thank you for the tip !

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this