I’m brainstorming ideas on how to optimize the A* pathfinding algorithm. It looks fast but it will be more complex in the end and I will need it to run even every second for many bots at a time. I need some serious speedup ideas so if you have them please let me know.
Some ideas I’ve been considering:
– splitting the nodes into more general layers (this seems like the easiest approach but thinking about it I don’t see it as correct, how can it preserve information about the cost of the subroutes and shortest path information)
– precalculating the routes into memory (for all routes this will be 100s of MB’s unless there is a smarter way of calculating)
– using network theory (every network has hubs which are critical for the network, maybe utilize this?)
– use the GPU (?)
– calculate the routes iteratively as the game flows, instead of calculating it all at once (this is my best idea yet but it has a minus such that the bot will stand and think for a second before moving to a complicated position. But this is realistic behaviour cause it looks as if a human player is thinking and planning.)
Written by MM. Posted at 9:17 am on January 9th, 2010
21 comments.
Post a comment.
i think that the last option is the best. just like the player does: you want to get from point A to B in a general manner. like we talked earlier about the bot behaviour – sneak,rush,climb etc. Once u get the general idea you move towards that direction and u alter your way on the fly. if u precalcualte a path for 100 m and a bot stumbles upon an enemy on his way he has to fight, run away etc and half of the earlier calculations would be wasted. So making them find the way on the fly in small steps like 10 m or so would be fast enough even for a large amount of bots? you could also adapt one route for a squad with some differences in each bots behaviour like one is leading, second is guarding, etc and they cover each other once someone is climbing or waiting for all guys to climb. This way they would follow the same exact path and it would look as everyone has a different way of movement. With some math optimizations and simplifications it might be ok imo. Just the thing u said that the player is thinking about the way to go and standing in one place – it’s almost not true. ppl do this only in certain situations so u must avoid this.
another optimization would be precalculating a few general paths on the maps so the bots can use them and then alter their ways as they wish when necessary. (where’s the fucking edit button;p)
The last seems to be the simplest( to me although I’m a programming nubcake so I might be wrong) you could even play a “Move to position!” voice(you know as if you radioed in the orders to the soldier) although that spans more than 1 sec and it might look weird that way.
The only thing I don’t get is why the hell do you have to optimise your game when it isn’t even close to finished?
You can optimise much more effectively if everything is in place rather than floating in the air or in your head.
Moving in the general direction would be fastest but it won’t work. Consider this situation:
* | t
bot – wall – target
If he moves in the direction of the target he will stumble on the wall. I’ve thought about this many times and the only solution to avoid these situations is to compute the whole path.
Get a faster PC, finish the game, and optimize later.
What I used in a Age of Empires clone before is to create a higher level map by combining groups of nodes together then pathfind on the higher level and then use it as a mask for the lower level pathfinder.
For example: I had a 512×512 map (262144 nodes) then I did a pass in the beginning that identifies areas. In the end I had about 350 areas each knowing which tiles belongs to it. Then I pathfinded on the areas which gave me a rough path-like strip of area to do the lower level pathfind on.
so maybe set key points on the map, there’s a distance between A and B , u can very quickly chceck the nearest path on the key points, so u make a list of points which the bot has to reach then you calculate the proper way of movement point to point.
http://img706.imageshack.us/img706/3311/beztytuudah.png
makes sense imo
mman: thats like the thing VanBurgler said. It’s making an abstract layer on top of the proper map.
I need to optimize this particularly cause it will be unplayable if I add more bots right now.
You only have to calculate each route once and save it in a list that each bot have, a recalculation is only needed on special events when the bot needs to rethink his aim. Until then you just process the movement list of the bot and delete the processed item. This should not be a performance problem.
You could for each map have a set of predefined routes.
When the bot needs to get to A on a predefined route he goes to nearest route and follows the known path.
When the bot needs to get to A not on a known route it checks distance from bot to predefined routes, distance from A to known routes and distance from bot to A.
If bot to A is less than bot to route + A to route then pathfind bot to A, else pathfind A to route and pathfind route to B
mman, dont the bots have restricted movement in that idea ?
You coulduse the iterative method,but only search as far as the bots sight radius plus maybe 10%. It wouldn’t be hat memory intensive, an the bots could still find their way around.
tld:
with many well-placed key points on maps it’s a great solution imo. The bot moves as it wants from point to point and u can even search points that meet the bots moving pattern.
moreover if u’d tag them with some info about were they are, like “good view” “safe spot” “open terrain” etc it would make a great way of bots knowing their surroundings. And i don’t think that u’d see much difference.
Why the hell are none of my comments showing (tried like 4 times) but when I try the same exact thing twice, I get an error due to double post??
*Won’t work when I have links in the comment, wtf?
Some secret tag i need to use?
I’ve an idea.. What about landmarks and memory? There will be certain locations on the map, that the bot ill determine, and as they move around, they memorise locations, so a bot could pathfind between A and B using route 3 for example, and save this, later on another bot might recall that path, and will not have do do the same calculations again. If an enemy is encountered then depending on the bot personality, he will decide to either just kill the enemy (Brute) or check for an alternative path, if one does not exist, then make one, sort of like a long-term optimistion.
Matt on my Facebook posted a genius idea if anyone is interested.
I’m interested.
Same.
Its on my facebook wall. He drew this http://members.gamedev.net/matt_j/AStarTable.PNG
man that’s the same thing i said, just a bit simplier