• Create Account

# Using A* in an RTS game

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

2 replies to this topic

### #1Calneon  Members   -  Reputation: 114

Like
0Likes
Like

Posted 02 February 2012 - 11:22 AM

I've implemented a working A* algorithm in an RTS game I'm making, but I have a few queries on improving it.

Firstly, to fix the jagged movement I'm going to iterate between tiles to create straight lines between tiles which can see each other. This would involve drawing a line between two tiles and using Bresenham's algorithm to determine which tiles are on the line and if any of them are impassable. Is this the best way to smooth out the A* path?

Secondly, I'm unsure how to actually implement the pathfinding into the gameplay. Currently, if a unit is given a move order, I will generate the path every frame and move towards the first cell in the path, though of course this is very costly if you're moving lots of units at once. However, if I was to only generate the path when the move order is given, any changes in the game world (such as adding new structures) would be ignored by the units and they would path through them. What is the best way to solve this?

Thirdly, if I have a bunch of units selected and I ask them to move towards a point, they will all collapse on top of each other. A way I could solve this is by using flocking AI, but I don't know how well it would integrate with A*. This video is an example of what I want to achieve.

I'm asking quite a lot, so thanks for any answers you can give!

### #2IADaveMark  Moderators   -  Reputation: 3433

Like
1Likes
Like

Posted 02 February 2012 - 02:04 PM

1) Yeah, if you game supports it, move as directly as you can to the farthest visible node on the path.
2) Another method is to only repath if you attempt to move to a blocked square. This can lead to some bad behavior, of course. Often, you just have to split the difference.
3) Don't use a billion zerglings as your guide. James Anhalt of Blizzard did a GDC AI Summit lecture on how he did this and it isn't necessarily for beginners. Options include station-keeping (i.e. formations) and local steering for collision avoidance (i.e. simplified flocking rules).
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

### #3Calneon  Members   -  Reputation: 114

Like
0Likes
Like

Posted 03 February 2012 - 02:33 PM