Basic Unit Movement
“Making a RTS is hard.” – Something I’ve heard and said a lot. In the past when I said it, I thought about fairly generic problems such as balance or networking and how they apply to a RTS. In this post, I’m going to talk about a problem which is pretty unique to the RTS genre: Unit movement.
A player orders one or more units to move from point A to B, how does everything work under the hood?
The easiest place to start is the movement of a single unit from point A to B. This can be broken down into 2 high level steps:
- Calculate a path from point A to B.
- Move the unit along the path.
Calculating a Path
Here were the first few things that we considered:
- The map.
- How is the map structured? Is it a grid with a defined cell size? This will determine how the position of an entity is defined.
- What kind of obstacles will there be? Does the terrain change in height? Will there be walls or other static fixtures?
- The unit.
- How big is the unit? What’s the thinnest space it can fit into? Is it solid or can its shape change?
Maps in Deepfield don’t have any height and most of space is empty; the only static fixtures are resources (for now anyways). I’m not sure what the drivers behind these choices were, Stefan made them long ago, but they have made unit pathing much, much simpler.
In Deepfield Space the map was grid-less, the position of entities was defined by a pair of floats (x, y) which have as much precision as you would ever need. (0, 0) is the centre of the map with positive x and y bringing you to the bottom right hand corner.
Pathing algorithm, does anyone use anything other than A*?
For A* to work, you need a graph (a set of nodes/points connected by edges/lines). Since Deepfield Space, we have attempted 2 methods of graph generation: Dynamic Voronoi diagrams and pre-generated grid shaped navmeshes.
Here is a video of Stefan explaining the dynamic Voronoi diagram method in Deepfield Space.
When we stopped working on Deepfield Space and started to adapt Fractal for Hatches, we switched to using a pre-generated grid shaped navmesh. We done this because maps in Hatches were procedurally generated mazes with lots of static fixtures like walls; the easiest way to do this was to use a square shaped grid so it made sense to use that same grid as a pathfinding graph.
Maps in Deepfield and Deepfield Space are the same so the square shaped grid was dropped in favour of dynamic Voronoi diagrams once again.
The size of units in Deepfield can be more than an order of magnitude in difference and their shapes can vary from circular to polygon made up of as many points as you want. In contrast to the map design decisions, these ones make pathing much more complicated.
We haven’t tackled any of these issues yet. For now, all units are assumed to be of constant size and shape. This does lead to some bugs such as large units attempting to path through spaces which are too small for them.
We decided not to address these issues till after we’ve done some alpha testing. We need to see what specific issues come up during play testing and more importantly, we don’t have the luxury of time to get this right before we start alpha testing.
It should be “okay” for now, these issues are mitigated by the map mostly being empty space and physics engine which the units use.
Moving a Unit Along a Path
Now we have the ability to get a path between two points on the map; we have to find a way to move a unit along that path.
Fractal uses Box2D for its physics engine. I mentioned before that this mitigates pathing issues with larger units; it does this by allowing larger units to push smaller units out of the way (most obstacles on the map are other units).
Physics makes it a little harder to move a unit along a path. If you watched the dynamic pathfinding video above you may have noticed units in Deepfield Space having to counter thrust to change direction or stop moving. Luckily, this is not a problem in Deepfield, the units are travelling through fluid which provides sufficient friction.
So other than the process of actually moving a unit along the path, there are a couple of other things which must be addressed:
- Unit hits an object.
- Obstacle appears on the path.
Unit Hits an Object
We haven’t implemented anything for this yet, we’re letting the physics engine handle this interaction for now. In the future, it would be good to handle some cases; e.g. If the unit is stationary and gets hit by a smaller allied unit, move out of the way slightly to let the smaller unit pass through.
Obstacle Appears on Path
In Deepfield, a unit moving along a path constantly checks if there is an obstacle between itself and the next waypoint, if something is blocking its way, it will re-path. This is fine when moving a single unit but becomes a problem when moving a group of units. If a group of tightly packed units are all moving to the same destination, the units at the back of the group will think the units in front are blocking the way and attempt to path around them causing the formation of the group to break up. To alleviate this issue we check what is blocking the path of the unit and if it’s moving in the same direction we ignore it.
Unit movement needs to be close to 100% reliable. It’s one of those things that when done right, players don’t even notice, but when it’s even a little wrong it’s obvious and has the potential to cause a player to lose the game.
At the moment, if you issue a move command to a unit, it might not get to where you asked it to go. If the pathfinder fails to calculate a path to a destination it will return a failure state and the unit will stop moving.
There are some bugs which make this problem worse: Big units travel too close to smaller units; and groups of smaller units can fail to generate a valid Voronoi diagram in the first place.
As pathing improves and more edge cases and bugs are handled, reliability will get better.
At the moment we’ve implemented a Band-Aid to alleviate this issue. We’ve put a wrapper around the component that deals with pathing and movement, all it does is checks if the unit has stopped without being at the desired destination and to retry moving if so. This completely breaks, for example, when the desired destination is invalid; but it’ll do for now.
This topic is huge as there are so many things to consider. If you ever want to scare anyone off from making an RTS, talk about this in depth.
Dave Pottinger, who worked on the Age of Empires series, wrote a 2 part article about this back in 1999. In part 2 he details some of the situations which groups of units can come up against and what to do in those situations.
Here are just some of the situations to be considered:
- Groups with different size units.
- Groups with units of varying speed.
- Groups with units spread out arbitrarily and how they should travel to a single point.
- Group movement through a space which would cause the shape of the group to deform.
- Rotating a formation as it turns.
- Combinations of the above.
We will probably have to deal with all of that in the future, especially if the maps in Deepfield get more complex.
For now, we’ve implemented simple group formations and movement, here is some of it in action:
Hopefully through this post I’ve given you an idea of how deep the unit movement rabbit hole goes. You can expect more unit movement posts in the future when we discover more issues and start making improvements.
Making a RTS is really fricking hard.