1 October 2014

Editorial: Close Combat Pathfinder Updates

Jim Martin, Project Leader over the Close Combat remakes drops in with an article on the important pathfinder updates and the challenges they had to overcome.

Published on 13 JUN 2011 12:53pm by Scott Parrino

CLOSE COMBAT: LAST STAND ARNHEM - Project Preview – Addendum

Article author:  Jim Martin – Project Lead

Publisher:  Matrix Games

Developer:  Black Hand Studios


Pathfinder AI and general AI changes made to Close Combat: Last Stand Arnhem, Close Combat: The Longest Day, Close Combat: Wacht am Rhein, and Close Combat: Cross of Iron

One of the most significant changes users of Close Combat: Last Stand Arnhem will notice in the most recent updates are the improvements to the pathfinder AI that were made.  A complete overhaul of this section of the code was written by our Lead Developer Steve McClaire and is sure to satisfy veterans of Close Combat and new inductees alike.

The best introduction that can be given to explain what the pathfinder AI updates are about is to quote a response Steve gave in an interview for Wargamer.com:

For Steve, were there any big hurdles to clear in programming when doing the remakes of the older Close Combat titles?

The biggest programming challenge is the size and age of the Close Combat code base.  This is a game engine that is some 15 years old now, has been through roughly a dozen major releases, and has been worked on by a lot of different developers over the years.  There is a fair bit of baggage, as the engine was originally designed for Mac and Windows cross-platform development, and there are some design compromises, as it needed to perform well, in real-time, on the hardware available 15 years ago.  So fitting new features into the existing structure can be a challenge, and some of the existing components can be tricky to modify.  As a result it’s sometimes preferable to just re-write a whole component from scratch, and of course this takes extra time.

But one of these re-writes was probably the most satisfying programming I got to do for Last Stand Arnhem. The original Close Combat path finder was one of those components where the design had some compromises so it could run well in real-time. They couldn’t have the whole game stalling noticeably every time you gave a movement order, so it was designed to find a path, or fail to find one, quickly.  The result was that you’d sometimes have a unit fail to find a path when it seemed obvious to the player, or the unit would take an odd-looking path just because that was what the path finder could come up with in the time allowed.  We knew this was an occasional nuisance in the game, but the complex maps (lots of rivers with narrow bridges) in Last Stand Arnhem were aggravating it.  Matrix Games gave us the go-ahead to invest in fixing this the right way.  Then our volunteer testing team hammered on it for a couple of weeks.  The result is a lot less frustration when moving your units around.  It’s probably something players new to the series won’t even notice, but for me it felt great.

That should give you a general idea of the goal for the pathfinder AI rewrite and improvements.


What specifically should I as a user expect to see has changed in the pathfinder update?

The pathfinder AI, like any AI, is quite literally a generalized solving program that takes a given set of circumstances and makes a decision based on those circumstances.  For that reason it'd be impossible to illustrate each and every improvement as the number of circumstances it can encounter are for all intents and purposes nearly limitless and the improvements apply to many circumstances.  A few of the more notable improvements are outlined in this article by comparison to the Close Combat: Invasion Normandy (stock CC5) pathfinder in the hopes that helps folks to see just how big an improvement and impact this one change has on improving the game.

Quoting Steve:  The new path-finder does two things differently.  1) It evaluates the map with a lower level of abstraction than the old one.  So it just has more accurate information about the map and can thus find better paths.  2) it runs in slices, so that it does not have to try and find a path right at the exact instant the player drops a movement order.  Since the path-finder is not trying to do it all in one go, the game can continue running while the path finder churns away.   In most cases you won’t notice this at all, but for long paths on large, complex maps (like corner to corner of Nijmegen bridge) it can take a second of two for the path-finder to work and your unit to start moving, which is not too bad compared to a guaranteed ‘Can’t go there!’ in the old path finder.

A companion video to this article was created that illustrates these concepts.  Those examples are repeated here.

Example 1

Click for full image

This demonstrates how a short pathing solution has been improved.  In the old pathfinder AI even a short run could  sometimes result in unintended deviations from what would seem to be an simple and obvious path choice.  These deviations are caused by the fact that the pathfinder was using a higher level of abstraction.

With the improved pathfinder these deviations are eliminated and the vehicle proceeds to the destination without deviation or hesitation as shown by this example:

Click for full image

 

Example 2

For this demonstration a single destination point was dropped across Nijmegen Bridge map which is included in Close Combat: Last Stand Arnhem.  That route requires a very complex pathfinding solution that includes a long stretch of narrow egress (the bridges).  In the un-improved pathfinder the AI could not calculate the route most of the time.  With the improved pathfinder the AI is able to calculate the route with absolutely no delay on my machine and without fail.  See the picture below to see just how complex the chosen pathfinding solution was.  Note the number of obstacles and types of terrain it had to evaluate and navigate:

Click for full image


Example 3

The video demonstration of this improvement shows how soldier pathing has been improved and how individual soldiers pathing is improved for somewhat complex pathfinding solutions.  As with the complex vehicle pathfinding solution the un-improved pathfinder is unable to calculate the solution most of the time whereas the improved pathfinder calculates the path without hesitation.  See the picturebelow to the right for the path it chose.  The most direct simple route.

Click for full image

The picture below shows the straggling soldier (carrying the heaviest weapon therefore moving slow enough to lose contact) using his own pathfinding solution until rejoining to his team.

Click for full image


Other improvements of note

The byproduct of rewriting the entire pathfinding AI is that some long standing but extremely difficult and invasive issues to fix have been resolved.

Quoting Steve:  Soldier and vehicle driver decision-making was also improved to help the individual soldiers and vehicles deal with unexpected obstacles (like another vehicle moving into their way, or a wreck that was knocked out in their path after the path has already been determined), get out of dead-end locations, and to catch up to their team if they fall behind for some reason.

The “Bee Dance” of CC2 was related to this, in that the AI for the vehicle driver and the AI that tried to keep the team moving along the team’s path would get into a conflict about which way to go.  I believe this has long since been fixed (like Cross of Iron days).

An example of the unexpected obstacles improvement Steve mentions appears in Example 2 of the video the long complex pathfinding solution.  In the Close Combat: Last Stand Arnhem example the tank arrives amidst a mortar barrage that was placed to thwart any AT assets the AI might have at the destination point.  This was done to assure the pathfinding demonstration was not interrupted by the AI's efforts.  The barrage was still going on when the tank arrived and was churning up the road in front of the tank.  You'll notice some brief delays and can almost see the pathfinder “thinking” as new routes are calculated to navigate these new obstacles in the form of rubble in the road.

Likewise in that same video example the notorious “Bee Dance” is demonstrated as eliminated by the fact that the tank lurches into action immediately upon receiving orders to move to the point at the other side of the river.  In the unimproved version of the pathfinding AI the “Bee Dance” could continue for very long periods of time and at best last a few seconds before the pathfinder chose it's route.  The “Bee Dance” doesn't appear in the video example as the old pathfinder didn't get into that cycle of indecision due to the fact it couldn't even calculate such a complex path.


Some last points about the pathfinder made by continued comparison

Quoting Steve: Why did the old path-finder fail sometimes? Because it was designed to run in real-time, as quickly as possible. They couldn’t have the game stalling noticeably every time you gave a movement order. Some of the short-cuts taken to speed up the path-finding would cause it to take the first possible path it found, which was sometimes not the ‘obvious’ path from the player’s point of view. And if figuring out the best path took too long, it just said “can’t go there” and stopped.

It's important to keep development in context of the it's cycle as occasionally project focus changes slightly to adapt to new information that can only be discovered by doing.  Sometimes that information doesn't present itself during the development cycle at all and the original plan doesn't need to change.  Priorities and scope also follow that same axiom.  Given a limited amount of time and resources you make choices based on the highest priority items in the hopes of addressing all of the issues on your list.

Quoting Steve:  Why wasn’t it fixed before, and why fix for LSA?  While it was an occasional nuisance, fans of the series knew what to expect, and had learned to work around it / live with it. However the maps for LSA were much more complex, in terms of path finding, than previous releases.  Rivers that cut the whole map in half.  Long narrow bridges. Close city maps.  Etc.  We felt that improving the path-finder was necessary to make the game play well.


Other AI changes and improvements made to  Close Combat: Last Stand Arnhem, Close Combat: The Longest Day, and Close Combat: Wacht am Rhein

It's nearly impossible to talk about the function of the AI without talking about it in context of the rest of the data and function of the EXE.  For that reason discussion of the changes/improvements to the AI will focus on just that portion of the EXE that deals with utilizing that data and tertiary functions as a way of making this illustration of those improvements manageable.  For AI changes specific to Close Combat: Last Stand Arnhem I'd recommend looking at the following article at Wargamer.com for an in depth description of the list of improvements made to it's AI at the gold release: http://www.wargamer.com/article/2905/Close-Combat:-Last-Stand-Arnhem.

There you'll find detailed descriptions of features improvements, most of which focused on improving and/or altering the AI of the game advancing it from the previous build of Close Combat: The Longest Day.  Again, those features are specific to Close Combat: Last Stand Arnhem only.

Here's the summary of those features mentioned in that article that were improvements to the Close Combat: Last Stand Arnhem AI or resulted in a need for changes to the AI.  Please see the features list for Close Combat: Wacht am Rhein and Close Combat: The Longest Day for their respective features lists as they differ considerably from Close Combat: Last Stand Arnhem:

  • Troop Point Buying System
  • Destructible bridges
  • Ferry Assault River Crossings
  • Static Forces, Reserve Battle Groups, Locked Deployment Teams
  • Battle Group Stacking

 


Subsequent changes/improvements made to the AI in various patches not mentioned in the above article include the below list.  These improvements by their descriptions are in and of themselves self-explanatory needing no additional illustration:

  • AI choice of setup location for teams improved.
  • AI teams less likely to move forward, or to leave good cover, while defending.
  • AI teams are better at staying in small groups and supporting each other.
  • AI groups benefit from the new path finder, and thus are better at making their way to their objective.
  • Improved, more challenging AI opponent.
  • AI is less likely to pause for several minutes after capturing a victory location.
  • The AI is more likely to offer a cease fire when close to a Force Morale failure.
  • It's worth noting that the path finder improvements also helped make the AI better and more active, and the AI groups and teams are now able to find their way to their target as opposed to failing to find a path and sitting idle.
  • The AI is more likely to accept a cease fire offer if no Victory Locations have changed hands in some time.

The changes in this last bulleted list of this article were implemented/back-ported in Close Combat: The Longest Day and Close Combat: Wacht am Rhein. 


Conclusion

All of the improvements mentioned here, with the noted exceptions, have been included in updates of all four of the WWII Close Combat titles (Close Combat: Cross of Iron, Close Combat: Wacht am Rhein, Close Combat: The Longest Day, Close Combat: Last Stand Arnhem) and are available for download at www.matrixgames.com.  We're certain you'll find the pathfinding AI improvements a noticeable improvement on an already great game.  If you've not had a chance to give the new Close Combat releases a try and have always been a fan of the series we highly recommend doing so.  Thank you!