About markers: movement / pathing markers

[Jip]

This article represents an in-depth discussion about markers used for pathing by the AI. We'll dive into what they are and we'll look at some good practices for when you mark up your map.

Parts of the markers series

• About markers: AI markers
• About markers: pathing markers (this article)

Requisites

Map editing tools, such as:

• FAForever Map Editor

The GPG editor is vastly outmatched feature-wise. The editor was built for the original game which did not include pathing markers. The symmetry option that Ozonex offers is extremely useful in the whole process of marking up your map. Therefore this article will not discuss how the same can be achieved in the old GPG editor.

Movement markers

Movement markers are used by the AI to find a reasonable path when the target is too far away. When a target is 50 units away then it will compute its path through the most markers that represent the most restricting movement. A unit is also referenced to as an ogrid and is the size of a wall.

Graph

When you place movement markers and connect them accordingly you are creating a graph. A graph is an abstract data structure that supports all kinds of interesting operations. A few examples are flow networks and the famous traveling salesman problem.

Supreme commander utilizes the graph for a search algorithm. The A* search algorithm is applied on the graph using both the distance between the markers and the threat value on a marker as their costs. The output is a path that is reasonably safe.

The AI intel grid

The AI uses a coarse grid structure that represents the level of detail that the AI can work in. The Ozonex editor has a feature to visualize this grid (Tools -> AI Intel Grid). This provides you with a good intuition up to what extent placing more markers will be more beneficial.

Density

The density of the graph is a trade off between effectiveness of the AI and the computational performance of the AI.

During runtime the AI performs threat analysis. It takes into account the weaponry of units and assigns the threat value to the corresponding movement graph. As an example, anti air weaponry will generate threat values on the air movement graph.

The AI utilizes this data in its pathfinding algorithm. As an example, imagine a fire base that has a heavy anti-land presence, but no anti air. Land-based platoons from the AI try to move around the firebase, where as air units simply fly over it because there is no threat.

With this in mind it may be tempting to make the graph quite dense. A dense graph allows for the generation of more unique paths, and therefore to evade more threats. The trade off is the performance: a dense graph can be (significantly) less performant then a sparse graph.

Operations that are computationally expensive:

• In order to know the origin and destination node the code needs to scan over all markers in the most restrictive layer of the platoon.
• In order to generate the path from the origin to the destination the code needs to traverse every marker between the two, including markers that will likely never be taken. This is fundamental to the algorithm and this waste should be reduced.

A visual example of a generated path

There are a few guidelines one can use to determine the density of the graph:

• A graph that is more dense than the AI Intel grid is wasting resources. The AI Intel grid is a visualization of the coarse approach of the AI to the simulation: it is not designed to take into account more fine-grained information.
• The range of units are another good indicator, especially T2 defenses. If you place a tech 2 point defense or flak turret on a position, would the AI be able to maneuver around it given the limitations of the terrain? If the answer to that is no then making a graph that is more dense at that location will only cost you performance.

An example of a situation where the graph can support two lanes: due to the height difference on the terrain a platoon may be able to completely negate a turret that is on either side of the path because the turret will not be able to hit the platoon

An example of a situation where the markers are unnecessarily dense. Whether or not a platoon takes the path on the right or the left, the results are roughly the same in practice

General guidelines

You should try and prevent having movement markers that are in close proximity or cross in close proximity other markers where buildings and / or units may stack up. You can think about (naval) rally points, (naval) expansion area's and the spawn location. Forcing a platoon to move through a building or a large bundle of units can cause some units of the platoon to get stuck, for which the platoon will wait indefinitely.

Movement markers should not be too close to unwalkable terrain. The computation of a path does not take into account the width of a platoon. Depending on the type of platoon (land, amphibious or navy) you want a half and up to three intel cells between the unwalkable terrain and the marker.

An example where the markers are centered to give the platoons as much space as possible

Land markers

As with any marker it is important to:

• Do not place them on top of other markers.
• Do not place them near expansions or other building sites, such as the spawn location.

Specifically to land markers it is important to:

• Try to have at least a half intel and preferably up to one intel cell between a land movement marker and unwalkable terrain.
• When the complexity of a path is low, place a marker every 1 - 3 intel cells away from one another.
• Have a marker at start, on top of and after each junction of a possible path.

An example where the land marker is too close to unwalkable terrain

An example of the density of a graph containing land movement nodes with the AI grid on

Units

Any unit that can only move on land. This includes the majority of the units from a land factory. Amphibious units, whether they hover or can submerge by moving on the ocean floor, do not utilize these markers. They use Amphibious markers instead.

Rally points

An example of a properly placed rally point which can never be crossed by a platoon

Rally points are a special type of movement marker. They are used by factories to gather units before they are moved in formation. It is vital to make sure that no movement marker, nor a path between two linked markers, crosses a rally point. The chaos that unfolds when a platoon tries to pass such a point may severely hamper the platoons capabilities and it may even get stuck.

Transport markers

Transport markers are used as an alternative to land movement markers. When the threat value of land movement markers surrounding the destination is too high then transport markers can be considered. Make sure they are not too close to expansions or other building sites, such as the spawn location. Also do not place transport markers on water - this will be bad for any non-amphibious unit that is being dropped .

Navy markers

As with any marker it is important to:

• Do not place them on top of other markers.
• Do not place them near expansions or other building sites, such as the spawn location.

Specifically to navy markers it is important to:

• Try to have at least one intel cell and preferably up to two intel cells between a navy movement marker and the coast, cliffs or other terrain that doesn't allow for navy units to move over it.
• When the complexity of a path is low, place a marker every 5 - 7 intel cells away from one another. Marking up a lake for example should result in quite a sparse graph since the formations and the range of navy units are significantly larger.

An example of naval movement markers

Units

Any unit that can lives on the water planes, such as boats and submarines. This includes the majority of the units from a naval factory. Amphibious units, whether they hover or can submerge by moving on the ocean floor, do not utilize these markers. They use Amphibious markers instead.

Naval Rally points

An example of a properly placed rally point which can never be crossed by a platoon

Rally points are a special type of movement marker. They are used by factories to gather units before they are moved in formation. It is vital to make sure that no movement marker, nor a path between two linked markers, crosses a rally point. The chaos that unfolds when a platoon tries to pass such a point may severely hamper the platoons capabilities and it may even get stuck.

Naval link

An example of naval link markers which describe positions that can be used for bombardment. These markers are intentionally closer to the shore and do not cross with any other movement markers

Naval links are used by the LOUD AI to describe locations that can easily bombard an expansion area or a spawn location.

Amphibious markers

As with any marker it is important to:

• Do not place them on top of other markers.
• Do not place them near expansions or other building sites, such as the spawn location.

Besides that the typical restrictions for land units apply. These are:

• Try to have at least a half intel and preferably up to one intel cell between a land movement marker and unwalkable terrain.
• When the complexity of a path is low, place a marker every 1 - 3 intel cells away from one another.
• Have a marker at start, on top of and after each junction of a possible path.

Units

All amphibious units, whether these hover or move over the ocean floor, use amphibious markers. This includes engineers, SACU's and the ACU.

Converting navy and land markers into amphibious markers

Typically there is little difference between amphibious movement markers and the combined set of naval and land movement markers. The only real difference is that there are connections to and from the water.

You can generate amphibious markers from the current set of land and navy markers. Navigate to Markers -> Layers and make sure that only the land markers, navy markers and connections are checked. Then navigate to Markers -> Markers and select all the markers on the map. We can export all the selected markers into a json-formatted file. The export button is underneath the list of markers.

Once exported you'll find a file with a .fafmarkers format. You can open up this file with any text editor, including notepad. We want to replace the following data:

• "MarkerType":14 -> "MarkerType":17
• "MarkerType":16 -> "MarkerType":17

Where a marker type of 14 are land markers and 16 are navy markers. We can perform these exchanges automatically using the 'Search and replace' functionality. You can access this functionality by pressing CTRL +H, which works even in Notepad .

Once completed you import the file back into the Ozonex editor. The import button is underneath the export button. Navigate to Markers -> Layers and uncheck the land and navy markers, then check the amphibious markers. Connect them accordingly and you're all good.

An example of imported amphibious markers that still need to be connected

Air markers

Air markers are special in a way that there is no terrain that can 'block' aerial units. Steep cliffs can hamper them, but it won't stop them. Therefore the general guidelines do not apply.

Air markers are best placed in a grid. Thankfully there are presets bundled with the editor for maps of size 5x5, 10x10 and 20x20. Larger maps can be marked up with the same bundles: move them into the correct quadrant after importing and then import them again.

You can find these presets inside the editor folder at fafmapeditor_alpha_v0606/FAForeverMapEditor_Data/Structure/MarkerPresets.

An example of the 20x20 preset on air markers

Units

All aerial units use air markers. Transport are specifically fond of using them to find a safe path to their drop off point.

Further reading

More information on the A* search algorithm:

• https://www.redblobgames.com/pathfinding/a-star/introduction.html
• https://www.youtube.com/watch?v=aKYlikFAV4k

More information about general algorithms that operate on graphs

• https://www.redblobgames.com/pathfinding/grids/graphs.html

About you

If you have interesting sources, approaches, opinions or ideas that aren't listed yet but may be valuable to the article: feel free to leave a message down below or contact me on Discord. The idea is to create a bunch of resources to share our knowledge surrounding various fields of development in Supreme Commander.

If you've used this resource for one of your maps feel free to make a post below: I'd love to know about it!