Twitter  Facebook  YouTube  E-Mail  RSS
The One Man MMO Project
The story of a lone developer's quest to build an online world :: MMO programming, design, and industry commentary
Unit Movement in Miranda
By Robert Basler on 2014-03-15 17:37:04
Homepage: email:one at onemanmmo dot com

"I've seen [formations] done really well ... but the guy did spend something like 4 to 6 months on a 2d grid working on just that problem all by itself. And he had done it before." - TheMartian

The one thing you really need to nail with an RTS is unit movement. Unit movement has a surprising number of elements that all have to come together brilliantly to produce smart looking unit behaviour on the screen:

  • Long-distance pathfinding
  • Short-distance pathfinding
  • Collision avoidance
  • Collision resolution
  • Formations
  • Steering & Animation

The Imperial Realm :: Miranda - Formations

This screenshot shows Miranda's new unit movement systems in action. I still have some work to do on collision resolution, but it is already looking pretty sweet. First, you will notice that the tanks are moving in a square formation. There are some units that are out of position because they've just gone around those buildings (you can tell from the dust trails,) but they'll all eventually get back into a neat grid layout. In the bottom left corner is the formations flyout menu ready to select one of the available formations. Once one is selected, the menu shrinks to display just the selected formation.

Getting Here Is Not So Easy

Pathfinding and collision detection are pretty well solved problems in game development, assuming your map is reasonably small, there aren't too many moving entities, and not too many people are playing your game. Remove any of those three constraints, and things get really, really difficult.

I originally planned to use A* for all of my pathfinding and I started work on an A* implementation which would work on my huge terrain at the beginning of April 2011. The solution worked well enough for moving individual units around, but had some issues: it was buggy, it was horrifyingly CPU intensive, and it was slow when you moved a lot of units. At the end of July 2013 I spent some more time on it, fixed a bunch of bugs and got it working well enough to have a unit successfully trace out a 17km path across the terrain.

While I was working on finishing what has become my long-distance pathfinder, I started work on a solution for collision detection and resolution. It is interesting to look at different RTS games and see how they deal with collisions:
  • Starcraft doesn't.
  • Command and Conquer doesn't.
  • Supreme Commander does, but has some odd issues when space is cramped.
  • Company of Heroes nails it. Kudos to whoever wrote their unit movement system.

I don't like seeing RTS units drive through each other, so I needed a collision detection and resolution system. My original plan was a grid-based approach with prediction so unit collisions could be worked out ahead of time and identical solutions distributed to everyone who was interested in those units in advance of the collisions actually happening. This is more or less how individual unit movement works and I wanted to apply the same technique so that I could avoid the appearance of lag when units were colliding.

I struggled with that system and a half dozen other approaches with no real progress for 5 months while I worked on other systems. The big problem with the grid approach is accuracy. Miranda's buildings aren't lined up on grids, so vehicles wouldn't be able to go where (looking at them) you could see they should be able to. I struggled endlessly with algorithmic complexity, network bandwidth, memory use and accuracy.

I also spent a lot of time considering how to implement formations and coordinated movement between units. That article sums up pretty well the myriad problems that need to be solved for groups of units not to look dumb.

Then in December I saw this video of Supreme Commander 2 and it completely changed my perspective.

There was no way what I was working on could ever produce something that awesome. Expectations were raised. I needed a new approach.

I spent some time investigating how Supreme Commander did movement, pathfinding and multiplayer but to my great disappointment I learned that like most RTS games, they use lockstep multiplayer where everyone runs an identical simulation and only pass their inputs to each other. This model doesn't work for an MMO because it can't support players joining a game in progress (some lockstep games do support join-in-progress but it isn't anything that could be used in a seamless MMO.) The guy who did the pathfinding for Supreme Commander is now working on Planetary Annihilation and this video gave me some more useful info on how their pathfinding worked.

I let my mind grind away on the problem over the Christmas break, then on January 6 I solved all my movement, bandwidth, collision, formation and pathing problems in one fell swoop. I spent about a week trying to figure out how my solution could be wrong, but it wasn't. So in mid-January I got to work on the implementation. It was the biggest change I've made to the game in one go, about 7 weeks of development in one changelist, whole systems were removed or completely reworked. A couple weeks ago I had my first multiplayer session with all the new code in and I'm thrilled to report that it all works. I'm still bugfixing, tuning and adding little features, but soon I'll be tackling the combat revamp which is the final big ticket item before I start letting people play it.

Looking back, I should have selected a less technically challenging genre for my first MMO.

By Dondergod on 2014-03-16 14:32:37
Homepage: email:
Really looking forward to the game! keep it up Also a big fan of the blog
Don't suppose you already know a release date?
By Robert Basler on 2014-03-16 18:04:22
Homepage: email:one at onemanmmo dot com
Things are starting to come together now. Expect some firmer plans to be announced next month, but I'm thinking around December with early access maybe as early as June.

New Comment

Cookie Warning

We were unable to retrieve our cookie from your web browser. If pressing F5 once to reload this page does not get rid of this message, please read this to learn more.

You will not be able to post until you resolve this problem.

Comment (You can use HTML, but please double-check web link URLs and HTML tags!)
Your Name
Homepage (optional, don't include http://)
Email (optional, but automatically spam protected so please do)
Connery or Craig? (What's this?)

  Admin Log In

[The Imperial Realm :: Miranda] [Blog] [Gallery] [About]
Terms Of Use & Privacy Policy