Dev Journal: Pathfinding for Armies
[p]Ashes of the Singularity II is a game that supports thousands of individual soldiers and combat vehicles, each with their own local decision making. So, when I order some units to go somewhere how does that happen?[/p][p]First off, check out our Dev Journal on Armies for a bit of information on that system. Pathfinding starts with Armies, which are composed of Units. Each Unit isn’t necessarily a single vehicle or solider, it’s a small ‘squad’. The individuals within each Unit are called Elements. Elements represent the individuals that do the fighting, take the hits, etc. Units are organized within an Army according to create a desired formation, so you can issue an order to just the Army and it can pass it down to the Units and then the Units pass it down to the individual Elements.[/p][p]A navigation graph in games is a map of all possible movement paths for gameplay entities, in our case Armies, Units, and Elements. It breaks the world into connected points or cells, showing where movement is allowed and how different areas link together. In Ashes 2, even a Small map contains around 150,000 of these cells.[/p][p][/p][p]![]()
A Simple Visualization of Map Cell Density, Showing Some Passable and Impassable Cells[/p][p][/p][p]To move through this graph, the game uses the A* algorithm, which acts like a smart guide to find the quickest route. A* looks at how far an entity has already traveled and makes a good guess about how much farther they still need to go. By combining those two pieces of information, it compares different routes and chooses the one that seems most efficient. Step by step, this process continues until the destination is reached, ensuring they avoid dead ends and unnecessary detours while moving naturally through the world.[/p][p]When an Army receives a move order, it uses the A* algorithm to calculate the most efficient path on the navigation graph to its destination. This path is then cleaned up straightening out some wiggly parts and removing extraneous points. Once the path is determined, the Army establishes the new formation it will adopt upon arrival. The destination formation points are then passed down to the Units, which they use for their part of the pathfinding. The Army then starts moving along the path.[/p][p][/p][p]![]()
The Army Path, Visualized in Large Green Arrows. The Unit Goals, Visualized as Small Green Circles. Individual Element Goals, as the White and Red Lines.
[/p][p]Each of the Units of the Army then tries to see if it can go straight to their destination without hitting some bad terrain. If so, they are done. This is always the case for flying Units. If they can’t, they have A* compute a path to the destination. In either case, they start moving along their individual paths.[/p][p]While moving, they continuously update the squad formation around the current position of the Unit. These formation positions are used as local goals for each of the Elements of the Unit. Think of it like the carrot on the stick for the Element.[/p][p][/p][p]![]()
A Separated Unit and Its Elements Pathing Back to the Army to Rejoin the Formation[/p][p]
Elements constantly update their movement, making decisions multiple times each second. In choosing where to go next, they weigh a range of factors: the goal assigned by their Unit, nearby obstacles to avoid, other Elements they may want to steer clear of or engage with, and opportunities to reach firing positions that maximize their weapon effectiveness. When possible, they simply move directly to their target, which is often the case since the distances involved are usually very short. It should come as no surprise that if they can’t they will use A* to find a way there.[/p][p]A lot of optimization goes into a game like Ashes of the Singularity II, in order to keep the pathing costs manageable for literally hundreds of individual elements at a time. But in the end, it is this work that allows the game to feature robust and responsive movement of large-scale armies across vast maps, while keeping the performance something that older machines, and portable PCs, can run.[/p]
[/p][p]Each of the Units of the Army then tries to see if it can go straight to their destination without hitting some bad terrain. If so, they are done. This is always the case for flying Units. If they can’t, they have A* compute a path to the destination. In either case, they start moving along their individual paths.[/p][p]While moving, they continuously update the squad formation around the current position of the Unit. These formation positions are used as local goals for each of the Elements of the Unit. Think of it like the carrot on the stick for the Element.[/p][p][/p][p]
Elements constantly update their movement, making decisions multiple times each second. In choosing where to go next, they weigh a range of factors: the goal assigned by their Unit, nearby obstacles to avoid, other Elements they may want to steer clear of or engage with, and opportunities to reach firing positions that maximize their weapon effectiveness. When possible, they simply move directly to their target, which is often the case since the distances involved are usually very short. It should come as no surprise that if they can’t they will use A* to find a way there.[/p][p]A lot of optimization goes into a game like Ashes of the Singularity II, in order to keep the pathing costs manageable for literally hundreds of individual elements at a time. But in the end, it is this work that allows the game to feature robust and responsive movement of large-scale armies across vast maps, while keeping the performance something that older machines, and portable PCs, can run.[/p]