Lead Developer, Stardock Entertainment
Published on November 13, 2009 By CariElf In Elemental Dev Journals

We actually made a fairly major change to the code this week so I thought that I'd actually write a dev journal about it: CodeCritter and I gutted the movement code and re-implemented it.  For the developers out there, that meant creating a branch which generally makes me a bit nervous because I always worry that merging the branch back into the trunk is going to go poorly. But making a branch was essential in case it took us longer than a week to get the code to the point where we could subject others to it.

I'd actually implemented code over a month ago that prevented a new turn from happening until all of the units (including AI units) were finished moving, but it took forever even for the very first turn when there weren't a lot of units.  I did some investigating, and eventually found out that it was just that the movement code was really inefficient.  It was moving all units pixel by pixel, even the ones that were offscreen or under the fog of war.  Besides taking longer, this meant that it was hard to catch targeted units because they were moving at the same time as their pursuers.  It also didn't check to see if a tile was blocked before a unit moved into it, so if you decided not to attack another unit, you had to be moved out of the tile.

Now, the developer who coded this is not a bad coder; he's actually one of our best developers. But this code was written in the VERY early stages of engine development, probably before we started working on Twilight of the Arnor, and certainly before we even had the concept of game turns in the engine.  Sometimes you have to get code roughed in and move on to other stuff before you can come back to it, particularly when your betas are more like alphas.  Also, it wasn't really bad code.  It mostly just wasn't scalable.

At the time, I couldn't start work on fixing the movement code because I had probably 5 other critical things to work on and I knew that it would take at least a week to fix the movement code.  So I had to comment out my code that made the new turn code wait for all the units to start moving, and put in code that just checked for the local player to be done moving.

So while I was working on other stuff, I kept the movement code on the backburner of my mind.  It was probably actually a good thing that I had other stuff to work on because you have to do a lot of thinking before you can start coding something this critical.  I'd done the moving code for all of the GalCiv titles (1 and 2) so this wasn't new for me, but frankly the movement code for the GalCiv games sucked.  Those of you who played any of the GalCiv games probably remember the stuck turn button bug.  The main problem with the movement code in the GalCiv games, especially by the end of Twilight of the Arnor, was that it was too complicated.  So I needed to come up with a design that was fast and simple and scaleable.  I actually came up with the design while I was getting ready for work one morning, proving yet again that the best design is done away from a desk. 

In GalCiv2, ships that were off-screen or under Fog of War were teleported from tile to tile until they ran out of moves or became visible.  This was definitely one thing that I wanted to do in Elemental, but it had always bothered me that there were 3 different movement functions in GalCiv2: Move, QuickMove, and Teleport.  (QuickMove actualy called Teleport), and there were 6 different collision detection modes: pathfinding, move check (before moving into a tile), move, (on moving into a tile), quickmove (when calling QuickMove, was kind of a combination of move check and move) and teleport (used by Teleport and was just a check to see if you could teleport or if you need to fall back into moving pixel by pixel).  That was way too complicated, and every time we made a change to the moving code, we had to change it in 3 locations. 

My idea was simple but elegant: What if all the units used the same movement code and then if they were on-screen, have the graphics animate them moving, otherwise just teleport them?  I bounced the idea off of CodeCritter (who is our graphics engine guru), and he thought that it would work and agreed to take care of the graphics code side of the problem.

The first thing that I did when I started working on the new movement code was re-enable my code to force the turns to wait for all the units to stop moving.    That way, I'd be able to tell if my code was doing what it was supposed to do: going faster and not making the turn button get stuck. 

Next, I created a static variable in the base mobile object class, g_bQuickMoveAlways.  If true, it would just move the units from tile to tile (rather than pixel to pixel) whether or not they were visible.  This will be a good option for multiplayer, and it made it easy for me to test. 

Then I just had to look at the existing moving code.  I copied the existing function, renamed it, and started stripping out anything that had to do with graphics or animation.  I also broke the code that actually handled moving into a tile into its own function, to make it really clean.  All I had left to do was make sure that the unit actually did a collision detection before moving into the tile.

This was actually the most time-intensive part of the operation for me.  I had to go through all the different kinds of objects (units, goodie huts, improvements, etc) and make their hit detection functions handle two modes, MoveCheck and Move instead of just Move.  For most of the objects, this was fairly simple, but the units have to check to see if they're going to attack.

At this point, I realized that I was going to have to work on more than just the movement code.  We'd been planning on making it so that you have to be at war with the owner of another unit before attacking it, but that required interface code we didn't have, and player relations code that we didn't have, so units could attack at will.  I had two choices: hack something in so that it would work and change it later, or start laying the groundwork for the real code.  I decided that it wouldn't take me that much longer to write code that wasn't a hack, and it would save me the trouble of having to rip out the quick hack later.

There was rudimentary player relations code in that was based on GalCiv2's relations code, but it was missing some key concepts.  It didn't have checks to prevent your relations from improving from being at war to being merely hostile.  It didn't have checks to prevent your relations from just dropping into war, instead of requiring the player to declare it.  It didn't have a concept of being permanently at war, which we used for the pirates and Dread Lords in GalCiv2, and space monsters in GalCiv1.  I added all the necessary checks, made some wrapper functions for checking to see if you were at war with another player or if you were allied with them, and went to work on the existing DeclareWarOnPlayer function.

The DeclareWarOnPlayer function was just setting your relations to being at war, and it was only doing it on one side.  So you could declare war on the AI, but they wouldn't be at war with you.  It also wasn't moving all enemy units out of the territory.  So I made the war declaration mutual (easy) and started working on the problem of moving all enemy units out.  The same code in GalCiv2 was very simple, it just looked for the first tile out of enemy territory, which might be 1 tile away.  This was pretty cheesy and ineffective at preventing sneak attacks.  So in Elemental, I send the units to the nearest city.  However, what if you have no cities?  While I figured that this probably wouldn't happen very often, I had to account for it. 

Luckily, each player keeps a list of all objects that they know about, including forests and mountain ranges.  So all I had to do was go through the list and move them to one that wasn't on a tile owned by the enemy player (or someone you're not at war with). 

My next problem was that I had no interface for declaring war.  So I made it so that if you right click on a unit, it would pop up the prompt that asks you if you want to declare war on that unit's player. It's kinda lame, but it gets the job done and even after we get the interface in, it might save you some clicks.

So now that you had to be at war before attacking another player, that made it much easier to finish the unit movement code.  If a unit tried to move into a tile with another player's unit that was not its destination, it would be blocked and have to re-calculate its path.  If the tile was its destination, it would bring up the declare war prompt. 

If the unit passes its collision detection check for moving, then it moves into the tile and calls the collision detection with the mode set to Move and performs any necessary code like merging armies, collecting the goodie from the goodie hut, etc.

I was now ready to test.  I loaded up the game and started moving my sovereign, and building units. I had to tweak the code a bit as I caught bugs that made units get stuck, and the attack code needed to be tweaked a bit since attacks were now initiated before the attacker moved into the title.  Once it seemed to be working as it should be, I committed my changes to the branch and let CodeCritter start working on the graphics part of it.

While CodeCritter was changing the code to only move the unit model smoothly (as opposed to teleporting it) if it was visible, I worked on a few movement bugs that were now easier to fix after having rehauled the movement and collision detection code.  The first bug was that if you built a city and your sovereign had no moves left, he would neither move off the city tile nor be stationed within the city.  This was a quick fix, as he just wasn't being added back into the list of moveable units after being given another move to get him off the city. The second was that units leaving a city didn't do any collision detection on the tile that they landed on, so they wouldn't automatically form an army with another unit, or get the goodie from the goodie hut, etc.  Since I had my new handy MoveToTile function, I just made it use that instead of setting its position on the tile directly.

CodeCritter and I merged the branch back into the trunk Wednesday night, which mostly went smoothly.  We both nearly had heart attacks when CVS told us that we needed to update before commiting our changes, which meant that someone had checked in code after we'd started the merge.  I started shouting death threats and CodeCritter put his head in his hands, but we only had 3 minor merge errors to deal with so I didn't actually have to kill anyone. 

We're still tweaking the movement code so that the units move smoothly while on screen at all zoom levels, but we've made huge progress. Since the code is now much simpler than our movement code has ever been in any game, it should be less prone to cause bugs like the stuck turn button.

Anyway, I hope that I haven't bored all of you to tears.  I've been very excited about this new code, so I just had to share.  





Comments (Page 1)
on Nov 13, 2009



I really appreaciate the detail and explination of just how these huge projects get done.

+ who doen't feal like utting death threats from time to time when CVS rejects a merger.


on Nov 13, 2009

I'm wringing my hands in anticipation of being able to beta test a new patch already!

on Nov 13, 2009

The last thought of the 5th paragraph ends unfinished. Otherwise, an enlightening read. Can't wait for beta to reopen!

on Nov 13, 2009

Yay, Cari's doing a Journal entry again! Although I don't code myself very often I always enjoy these.

on Nov 13, 2009

  Loved the pseudo-codish logic explanation!

on Nov 13, 2009

Wow, I think the only extra detail that could have been added would have been the code itself

on Nov 13, 2009

That was great!

But you didn't finish this thought:

I actually came up with the design while I was getting ready for work one morning, proving yet again that  

on Nov 14, 2009

death threats!   


I am fairly amused.  You must feel great if you were motivated to type all of that.   I applause can be heard. 

on Nov 14, 2009

Carie leveled up ! Choose a perk : code +1, code +1 or code +1 ?

on Nov 14, 2009

Sounds good...waiting for the new patch!

on Nov 14, 2009

Thanks very much Cari, that was a great read.  Congratulations on the movement code stomach transplant

Source control is vital, but the "you must update" message can be harrowing.  I'm glad you didn't have to cause any casualties.

on Nov 14, 2009

I'm glad he didn't have the oppotunity, causing casualties might end him in the clink,  can't get as much coding done behind bars.

on Nov 14, 2009

One thing that bothers me is that SD seems to be proceeding as if the current border-relations system is the final system, i.e. speding a lot of extra time and effort making sure that it works well. As one of the main ajitators for a more reasonable border system, this has me concerned.

on Nov 14, 2009

Thanks for the very down-to-earth update. And a splendid tale of how real-life software development tends to evolve: Code tends to stick around longer than you expect. And, yup - have to take care with concurrent development even when using version control. The ground may move on under your feet, while your coding up against certain interfaces.

I must comment on your using CVS, though. I can recommend making the effort to shift to a more modern version control system at some point. There are several options such as Mercurial and Git, which provide for instance better tracking of history and typically better perfomance (in part due to their being distributed). Can recommend Mercurial (in unison with the  KDiff3-merger). Just made the transistion from CVS in a software development company with around 150 active developers. But, of course, it's an effort to change. Old CVS-skills take some time to to unlearn.

on Nov 14, 2009

Thank you Cari!  I know you've been wanting to re-visit the movement code for a long time, and I really appreciate you sharing this information.

Not boring at all!  Quite the opposite.  I quite enjoy reading posts like these, and I hope you and the other Devs continue to have the time and patience to write them in the future.