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 2)
on Nov 15, 2009

Great post... it's neat to know the behind the scene stuff.

Scoutdog
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.

Yes, I do share a similar concern.  Scoutdog, good eye!  While I guess border/relation system maybe too early to discuss (and in the OP don't spend too much time trying to make it final either), I want a better system than GalCiv.

   I'll like to play with/against illusionary unit, building, terrain; all of these should be relevant to the movement code.  Can the movement code include the 'possibility' of illusion object? Or put illusion in many design consideration in EWOM?

For example, an illusionary goodie hut will disappear when you move a unit into that tile, but NOT when you are standing next to it.  Or pathfinding will always avoid the illusionary mountain unless you explicitly move a unit into that tile.   I can write-up what I really want from illusionary spells, but probably there is already someone asked/wrote about that in the forum.

on Nov 15, 2009

Do a search and if not go for it, illusionary spells are somthing that I didn't thought about....

 

Warder

on Nov 15, 2009

Climber
Great post... it's neat to know the behind the scene stuff.


Quoting Scoutdog, reply 13One 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.
Yes, I do share a similar concern.  Scoutdog, good eye!  While I guess border/relation system maybe too early to discuss (and in the OP CariElf don't spend too much time trying to make it final either), I want a better system than GalCiv.

CariElf, I always want illusion based spells.   I'll like to play with/against illusionary unit, building, terrain; all of these should be relevant to the movement code.  Can the movement code include the 'possibility' of illusion object? Or put illusion in many design consideration in EWOM?

For example, an illusionary goodie hut will disappear when you move a unit into that tile, but NOT when you are standing next to it.  Or pathfinding will always avoid the illusionary mountain unless you explicitly move a unit into that tile.   I can write-up what I really want from illusionary spells, but probably there is already someone asked/wrote about that in the forum.

She said that there's a check before movement AND a check after. So with illusionary spells you move "like if" there's a hut, but when you reach the tile "poof nothing happens, or bad things"

on Nov 15, 2009

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).

What if you know zero tile that are not owned by an opponent?

Yes, unlikely. But still, it can happen, most probably in a scenario.

on Nov 15, 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.

Actually, the code that I did doesn't require the existing border system.  All I did was make it so that you have to be at war with the other player before attacking them, and than if you declare war, all of your units get moved out of that player's territory (and all of theirs get moved out of yours).  Even if we decide that you can move freely through other people's territory, we'd probably still make it so that you have to declare war and teleport the units out.  We really can't make a final decision one way or another until we get more of the diplomacy code in place.

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

We've been using CVS for years, but we have been discussing switching to SVN or Perforce.  It's never a good time for that big of a switch, but I suppose we're eventually going to have to pick a date and just do it. 

CariElf, I always want illusion based spells.   I'll like to play with/against illusionary unit, building, terrain; all of these should be relevant to the movement code.  Can the movement code include the 'possibility' of illusion object? Or put illusion in many design consideration in EWOM?

For example, an illusionary goodie hut will disappear when you move a unit into that tile, but NOT when you are standing next to it.  Or pathfinding will always avoid the illusionary mountain unless you explicitly move a unit into that tile.   I can write-up what I really want from illusionary spells, but probably there is already someone asked/wrote about that in the forum.

Umm...technically it would be possible.  But I would probably rate it as a low priority for feature requests just because we have a lot of core stuff that's not in yet.

What if you know zero tile that are not owned by an opponent?

Yes, unlikely. But still, it can happen, most probably in a scenario.

At some point we're going to put in alliances and teams, and those will be also tiles that you can move to.  If there's absolutely nowhere you can go, I was thinking of doing something like setting all the units moves to 0, cancelling their destinations, and maybe incurring some kind of penalty on them for a specified period of time.  At the moment, it just won't move them. 

 

on Nov 15, 2009

Actually, the code that I did doesn't require the existing border system. All I did was make it so that you have to be at war with the other player before attacking them, and than if you declare war, all of your units get moved out of that player's territory (and all of theirs get moved out of yours). Even if we decide that you can move freely through other people's territory, we'd probably still make it so that you have to declare war and teleport the units out. We really can't make a final decision one way or another until we get more of the diplomacy code in place.
That's refreshing. Of course, the auto-teleport-out system is a bit unralistic even for a fantasy game, but we'll pick this up at a later date. Nice to see that something more inventive is in the works!

on Nov 15, 2009

Scoutdog

Actually, the code that I did doesn't require the existing border system. All I did was make it so that you have to be at war with the other player before attacking them, and than if you declare war, all of your units get moved out of that player's territory (and all of theirs get moved out of yours). Even if we decide that you can move freely through other people's territory, we'd probably still make it so that you have to declare war and teleport the units out. We really can't make a final decision one way or another until we get more of the diplomacy code in place.That's refreshing. Of course, the auto-teleport-out system is a bit unralistic even for a fantasy game, but we'll pick this up at a later date. Nice to see that something more inventive is in the works!

I'm with Scoutdog, I really do not like the "declare war get teleported out of their territory and they get teleported out of yours" option. I would much prefer something along the lines of taling a severe diplomacy hit from all factions as they note that you are a no-good sneaky bastard who attacks someone who they had right of passage. I realize they put that kind of teleport code in for a reason, but I really think there would be better ways to discourage sneak attacks on allies.

on Nov 16, 2009

CariElf

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.
Actually, the code that I did doesn't require the existing border system.  All I did was make it so that you have to be at war with the other player before attacking them, and than if you declare war, all of your units get moved out of that player's territory (and all of theirs get moved out of yours).  Even if we decide that you can move freely through other people's territory, we'd probably still make it so that you have to declare war and teleport the units out.  We really can't make a final decision one way or another until we get more of the diplomacy code in place. 


I've suggested a way to avoid the unpleasant "declare war get teleported out of their territory" issue by using the Shades of diplomacy .  A quick summary here:

War
- All units can trespass its border
- Allow fighting, including capture of rival settlement
- Needs to be in “Conflict” for a random 5-10 turns before turning to “War”

Conflict
- All units can trespass its border
- Allow fighting, but rival city cannot be captured

There probably are some better ways, but above can be one of the ways.

CariElf

... illusion based spells...

Umm...technically it would be possible.  But I would probably rate it as a low priority for feature requests just because we have a lot of core stuff that's not in yet.

I agree this is non-core, but it will be nice to keep it at the back of your mind when designing the movement code (or other aspect of the game).  Illusion can be a feature that distingush EWOM from your competition.

on Nov 16, 2009

The idea of a 'pre war CONFLICT' mode is excellent and I would like to strongly support it.

War is a serious business and commits both nations to a major investment of resources.  It would be very nice to have a lower level conflict, similar to a border war, where the two sides skirmish but where the nations do not feel like they must commit to a major conflict.  The was may follow, or it may not, but the conflict mode would be another diplomatic tool of interest.

on Nov 16, 2009

I prefer a diplomacy option to "expel" intruders from your territory or force them to declare war at a negative penalty to their diplomacy.

 

But teleportation is a lot better than what happens in most other 4x games. It worked okay in my opinion for Galciv 2. I just don't think it is optimal.

on Nov 16, 2009

on movement ... if an unknown entity/object causes my soldiers path to change, I would like for said unit to pause, with remaining movement points, in the location just before the change in path. This way the all annoying "misclick" which people sometimes blame for failed war campaigns can be best avoided.

on Nov 17, 2009



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 peaceful opponent units can block movement, that means they will be able to control you without declaring war. This can be pretty exploitable against the AI if you string a bunch of weak armies across a peninsula to stop them from exploration/expansion. Ive seen this problem in a few games, where people use this to avoid the consequences of an open declaration, when it should be obvious to all that preventing movement is a blatant act of war.

In Civ4 they solved it by only making an actual enemy block movement, while units of different nations at peace can co exist. That's probably the best way to handle that.

on Nov 17, 2009

CariElf

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.
Actually, the code that I did doesn't require the existing border system.  All I did was make it so that you have to be at war with the other player before attacking them, and than if you declare war, all of your units get moved out of that player's territory (and all of theirs get moved out of yours).  Even if we decide that you can move freely through other people's territory, we'd probably still make it so that you have to declare war and teleport the units out.  We really can't make a final decision one way or another until we get more of the diplomacy code in place.


 

 

Cari - FWIW, it'd be very nice to have a diplomatic option to allow factions to move through each others' territories.  For bonus points, it'd be cool if we could specify how much (quantity of troops, perhaps).

"Okay, in exchange for the Tome of Unlikely Power, you can move 1,000 soldiers through my land."

or

"I think you should pay me 1,000 talents of gold, and let me station as many of my troops as I want on your land.  For your own protection, of course.  You have dangerous neighbors."

on Nov 17, 2009

On source control, I know people bang on about it a lot, but distributed source control systems like Git and Mercurial are absolutely worth it for one good reason: local commits. This means less sitting around waiting for a central server to pull its finger out, which really adds up.

SVN is probably the simplest move though, it means less time learning the new system the tools to port your existing repository over should be pretty solid by now.

on Nov 17, 2009

Nights Edge
On source control, I know people bang on about it a lot, but distributed source control systems like Git and Mercurial are absolutely worth it for one good reason: local commits. This means less sitting around waiting for a central server to pull its finger out, which really adds up.

SVN is probably the simplest move though, it means less time learning the new system the tools to port your existing repository over should be pretty solid by now.

Agreeed - on both accounts.

I would add that apart from speed of local commits, speedy local log-operations are really nice on larger codebases with years of revisions. That alone was actually one of the key reasons that made us go for a distributed revision control system.