Looking at the source code for Command & Conquer Tiberian Dawn, pathfinding for units has an interesting algorithm. And that algorithm is, I would consider, fairly well balanced between how intelligent the units should find their paths versus how much compute and memory resources the game had at its disposal, when it was released in 1995. One of the constraints that there always were when we talk about AI isn’t the fact that we haven’t invented fantastic algorithms or machine learning or things like that – the limiting factor for “more and fancy AI” were rather the limited resources on the machine – and AI competing for compute and memory with other game elements, such as graphics, game logic, sound, loading assets. The rest of the game wouldn’t be able to operate and work anymore, if most we did was calculate potential next steps and routes, and an overall strategy for 200 different player steps that could perform next – just so the AI can react almost human-like. You still need to render the graphics, you still have to enforce the game rules, you still have to load and calculate assets that you need to display. In the great scheme of game design, if AI is competing with other game elements that, if impaired, severely impact your experience as a player, we could agree that AI will likely have to be deprioritized, if the answer is: let’s not load that sound effect or refresh the map only every so often.
In Command and Conquer, the whole map is structured in tiles. The tiles are used to place objects, give units waypoints and calculate ways, and also carry information as to whether the terrain is walkable, or if there’s an obstacle, or if there’s a tentative obstacle, such as another unit sitting there, if it’s occupied by a building.
When engaging in path finding, the system tries to find a direct line in between the starting point and the destination point. Since the whole map is a grid, that can be mapped to a direction – and the unit will follow that direct in a straight line. As the unif follows that line, we identify if, along the line, there’s terrain that can’t be crossed, such as trees, buildings or a river – there may also be height differences that we can’t cross easily.
When finding obstacles, we check if on the other side of the obstacle, still on the straight line between start point and destination, walkable terrain again? If there is, the unit must start finding a way around the obstacle, and look for ways around it. Is there a bridge? Can I move around the forest? The new, temporary destination for this “move around obstacle” exercise, is the next, walkable tile that’s on the other side of the obstacle, on the straight line to the destination.
The unit tries to find a way either counterclockwise or clockwise move around that obstacle. It is trying to calculate the most clever path around the obstacle by checking walkable tiles vs. not walkable tiles, and try one of the two directions, when both seem viable. The unit will follow the walkable tiles around the obstacle, until it reaches the point after the obstacle, from where a recalculation for the rest of the path is performed. Again, it starts on a straight line to the destination, and moves on.
The algorithm is tailored to break the long path down into smaller chunks, with recalculations along the way. If there is an obstacle, there’s a check for walkable terrain behind the obstacle, and then a calculation for a path around the obstacle to that point. The whole algorithm is performed in a constraint way, where the “look ahead” isn’t too far across the map – but only 9 cells ahead. The path is re-calculated every nine cells, with building the straight line between start and destination point, determining obstacles, and starting. Once we’ve moved to ~9 cells ahead, it re-calculates. This avoids keeping a long stack of waypoints or lengthy calculations for long paths in one go, but breaks down the way into chunks, sending the unit on early – recalculating along the way.
It’s interesting that the units don’t leverage an established algorithm such as A* or Dijkstra to find the shortest path somewhere, but that would mean that a complicated network of waypoints and nodes must be kept in memory, aligned with cost, and re-calculated every so often when other units move and buildings are built. Supposedly, that would mean more CPU and RAM usage, loading the initial level and then re-calculating the possible waypoints and maps. Since the map is a grid layout and we can map walkable/not walkable to the grid, and move from cell to cell with “visibility” of N amount of cells, that seems like a more resource-aligned algorithm and approach.
This seems to have saved a lot of resources, which is, I think, elegant for the time and serves in many scenarios the purpose of making units feel “human” too. What is more human than sending a unit somewhere and it needs to decide differently because it drove into a cul-de-sac or ends up stopping for a river, now re-calculating the path again, trying to find a bridge? As the units can only “see” 9 cells wide, going somewhere and getting stuck, making new plans is somewhat realistic, too. And there’s only so much you can see when driving a tank. It’s also realistic that units don’t have full visibility into the map and to perfectly from start to destination without ever needing to recalculate.
Pathfinding is an interesting and example of how AI was built back then. It’s not dynamic learning. It’s not Large Language Models, it’s not Machine Learning such that if a specific unit went a specific path N times, then the next unit benefits on their way for the N plus first time from other unit’s knowledge. AI back then was simply clever scripts, clever algorithms, logic in algorithms that observed the game world and deducted next possible steps for the computer opponent based on these observations of the worldview to act seemingly clever enough as if it were a human. It has a lot to do with logic, functions, if this, then that, finite state machines, and very simple behavior trees that an AI can draw actions from when specific inputs or specific events happen in the game world. So, far less sophisticated than we might think.
FRICKELSOFT 