Intro to Pathing and the Precise Map

For many games of the RTS style, pathing is a large concern. The calculations to find a clear path thru a map are not exactly speedy or neat. And the more units on the field of battle, the more difficult pathing becomes.

In a typical pathing system a program needs a start and stop point. It also needs a 2D array that indicates if a point is passable (can you move thru it).

In our COH2 example (Angermunde) we see what is called the IMPASS map in the worldbuilder. On this image I have also used the measuring tool to show a typical movement path. Noted by the BLUE(start) and RED(stop) circles. In COH2 our impass 2D array holds true or false data for each 1 meter x 1 meter grid point of the terrain/map we are playing on.



In most pathing algorithms such as the A* or A STAR (https://en.wikipedia.org/wiki/A*_search_algorithm), a program will start at the start point and try various paths to get to the stop point. The program will look on a cell by cell basis and try to calculate the shortest path. For our example image, we can see that the COH2 program also checks on a meter by meter basis and stores this path (YELLOW LINES).

WIKIPEDIA A-STAR ANIMATION


People who remember early vCOH may remember when a unit would get halfway thru its path and just stop dead because something blocked it? This indicated that the path was calculated once per move and when things blocked the path the program simply waited until it was not blocked anymore or just gave up. In COH2, this never happens. So pathing must be recalculated when blocked(FAST) or is constantly updated (VERY SLOW). Another observation is that moves are diagonal. This could be a form of optimization if orthoganol moves are available.

Now as you can see from the WIKI page graphic showing the filling of the 2D array as they search thru it, remember that this would be for single meter width units in the game. Units such as infantry only. This will not work for units such as light vehicles and tanks.

We now need a way to calculate a path for wider objects. Enter the PRECISE MAP view in the Worldbuilder. Most units in the game use are 1 meter wide, 3 meters wide, or 5 meters wide. To work with pathing for larger vehicles the IMPASS map is adjusted to say what not only is a point passable but also how close is the nearest impass object. If no objects are close by we can say this is an open point that all units can move thru and we will color it GREEN. If we see an impass object near we will color it YELLOW. If a point is close we will color ORANGE. If the points are too close by we cant pass thru this point at all and we color it RED.

Now these PRECISE MAPS need to be calculated for each of the crush types in the game: None, Light, Medium, and heavy.

For programming nerds like myself: It is probably stored at the bit level. So BIT0 = normal crush, BIT1 = Light crush, BIT2 = Medium crush, BIT3 = Heavy crush.

Here is an example of the PRECISE MAP for Angermunde when viewed with LIGHT VEHICLE IMPASS.


You can see from this image that light vehicle will have issues trying to pass between the center buildings.

Here is the IMPASS map for MEDIUM crush pathing. This shows that a medium crush vehicle will drive right thru the girder post object blocking pathing for light vehicles.


The PRECISE MAP for MEDIUM pathing shows that since we can drive thru the girder post and that we now have a GREEN lane between the buildings. This tells us mappers that a tank can get straight thru here easily. Of course that does not mean it wont start spinning and doing weird things when it enters or exits this area. So a little more space is always a good thing.


As stated above, you want pathing lanes to be at least one grid cell (texel) wider than the unit trying to get thru it. And adding a couple extra meters will help that unit not get stuck trying to find the best entry into this path.

As you can see, the precise map adds more calculations to the pathing code. We now have to calculate a path and give it some score as to how GOOD of a path it is. This is yet another thing that when the late game comes, and every player has multiple vehicles driving around, the code will begin to kill your FPS. Another thing that I try to point out when people say the game is not optimized. It is doing a million complex things and doing them very well.

So generically:
Make paths at least 1-3 meters wide for infantry and AT guns. Certain AT guns can path thru 1 meter. But a few require 3 meters. So 3 meters should be used in most instances.

Make paths at least 3 meters wide for light vehicles. A path that is 4-5 meters will let the vehicle move smoother.

Make paths at least 5 meters wide for medium and heavy. And add a few meters so the units dont spin in circles.

PLAYER NOTES:
Another thing for players to understand is that when they make sandbags or push up against a wall, those objects will not fall neatly on the impass grid they sit on. And that is why you get situations where some units are in green cover and some are not. Or you have to barbwire off two rows by green cover to block the enemy from using the green cover. You have to try and get as far away from the green cover object as you can that does not leave open space between them to be sure the wire separates the enemy from green cover.

Thank you, very informative!