A* will work and is fairly easy to implement. It works well for single paths, but for a group of units all moving at the same time it can result in shuffling/instability, especially at the end when the units reach their destination. Allowing the solver to accept path solutions that are “close enough” i.e. within some distance of the desired location helps this, and also adds a more organic look to the final arrangement.
For A* to work, you will need to have a grid that overlays your terrain, and only allow one unit per cell. The unit can traverse all points within the cell, and this allows a smooth motion across the cell, as you hand off the unit from cell to cell. To avoid units overlapping, you should have the final position close to the center of the cell, but allow for some variance to make things look more natural.
Finally, not all units are equal. Units moving through each other when they are moving doesn’t look as bad as having two units parked on top of each other when stopped at the end. In Starcraft for example, the little miner droids can freely move through each other, but when stopped they do not park on top of each other.
Yes, that true, working drones in Starcraft indeed overlaps each other. But not other units…
other than units that are flying, ground units detect each other and try to rotate to right to avoid each other.
Which result in infinite left right avoidance…
I tried to think this as simple as possible.
Divide map into grid.
save each grid cell’s distance from the goal.
according to 2. Use A-star to find the path. using the closest cells!
if path is valid save the cell as used so other units can find their own path.
loop 2 - 4 for each units.
And this works quite well.
But now the trouble comes up with other units like …Tanks or Trucks…they got double, triple or even quadruple size of the original units…
Then, how can I assign the grid cell to these different size units?
The grid is going to contain information about the terrain. Each cell will contain something like…
terrain type (water, ground, mountain, etc.)
possibly terrain height if you want to make calculating cost more accurate, or useful for flying units avoiding certain elevations.
the unit occupying this cell
flags indicating which vehicle types this cell blocks
You will probably want to code your A* algorithm in such a way that it is stateless, and allows you to pass in state, i.e. a struct that contains the current solver state for a single path. This will allow you to specify a budget per unit for pathfinding and solve for a group of units simultaneously per frame, while amortizing the cost over many frames. This will allow you to begin moving along the path while still solving the path, and will also help prevent hitches in the frame rate since you can set a total budget of 1-2 milliseconds and continue the work next frame once you reach the per frame budget.
For a unit larger than a single cell, you will mark its footprint in the grid for however many cells it takes up, so 2x2 or 4x2 whatever it is. Those cells are marked impassable by ground unit types and all cells refer back to the unit. When testing for the next location of a unit, you need to check all cells in its footprint (ignoring cells currently occupied). Only when you know a unit can move to a new location do you unmark the cells and remark the cells in the new spot.
The higher resolution your grid is, i.e. the more cells a unit occupies, the better I think the units will cluster together, since you will waste less space if a unit is only slightly in some of the cells. You can take the bounding polygon of a unit and intersect it with cells to determine which cells the unit occupies.
I forgot to add and it’s largely superficial to the excellent in depth information appearing. You need to limit the space allowed for path finding, at least I did, but I was using a very fine grid and it was (“real time”) turn based, if you’ll excuse the paradox. For real time without turns, ah, that’s why they all are so blocky (the “grid”), I must have a nicely tuned algo somewhere if it is pixel based as I believe. Is even Warhammer blocky? That was the revolution for me in board games- taking them onto a free form battle plain.
Yes…I guess I have to limit the searching area, or it might get overhead.
I’m still looking for the simplest way to implement such algo for my game.
If you have one, plz share on git hub.
Thank you for your suggestions
For these type of RTS games the main thing required is a path finding algorithm A* too as everybody discussed but I am seeing that none of them shared the A* algorithm so here is the link:
