Vote 2020 graphic
Everything you need to know about and expect during
the most important election of our lifetimes

To Create Smart AI Command & Conquer Devs Made Units Stop Acting Stupid

Gif: Ars Technica (YouTube)

Developing the popular RTS Command & Conquer: Tiberian Sun involved solving a whole host of problems. But the biggest and most interesting problem was figuring out to allow hundreds of troops and vehicles to move around maps without slowing and destroying PCs at the time.

Advertisement

The latest video in Ars Technica’s wonderful War Stories series is all about how developers Westwood Stuidos solved pathfinding and unit management in Tiberian Sun.

In games, characters and units figure out where to go using pathfinding. This creates a series of possible routes the AI can take to reach their objective. With even one unit, this can mean dozens or more different paths.

Advertisement

In a game like C&C: Tiberian Sun this pathfinding becomes more complicated as players can spawn hundreds of units, all of them moving and stopping in different areas of a large map, which can contain other players doing the same thing. This many units all trying to pathfind could cause even powerful PCs back in the day to collapse under the computational weight.

One of my favorite quotes from the video is easily this: “Players don’t realize how hard you have to work to make a game not do something stupid.”

An example of one unit and all their possible paths.
An example of one unit and all their possible paths.
Illustration: Ars Technica (YouTube )

This is in reference to when pathfinding stops working or makes a mistake. These issues create the feeling that the AI unit you are ordering around is an idiot. So the team spent a lot of time making their AI not do dumb things. As Westwood Studios co-founder Louis Castle explained: “If you spend time making something not do something stupid it will actually look pretty smart.”

Advertisement

The solution to their pathfinding problems was to create a series of rules and directions, that helped lessen how much processing power would be needed.

For example, if a unit is near friendly AI units that are moving, the game tells these units to ignore each other. When AI units encounter a friendly AI unit who is moving and is in their way, the game simply tells the unit to bump that stationary friend out of their way. Using these techniques allowed Westwood Studios to have hundreds of units in their game without destroying players’ computers.

Advertisement

The whole video is interesting as Louis Castle explains how they solved other problems, including issues with the CD-ROM and video compression.

Kotaku Weekend Editor | Zack Zwiezen is a writer living in Kansas. He has written for GameCritics, USgamer, Kill Screen & Entertainment Fuse.

Share This Story

Get our newsletter

DISCUSSION

He didn’t mention some of the other specific tech we used for fast pathfinding. That would probably be too much detail for the video, and he wasn’t the guy who implemented it...

- Group Pathfinding

You ignore the friendly units when moving, but for some of those examples of hundreds of units moving across a bridge it would be prohibitive to pathfind for each one. So what you do is you take all units of the same type in a group and you make the lead guy your pathfinder. He does the heavy computational lifting and the rest just follow his general path and do very local pathfinding to stay on his path.

If the bridge gets destroyed while some guys have made it across and others haven’t, well now you’ve got two groups.

You do it by unit type because obviously a flier’s path may look very different from a grunt’s, which may look different from a unit which can tunnel...

- LoD (Level of Detail) pathfinding

Again, it would be prohibitive to plot a path for a guy all the way across the map pixel by pixel. What you do is keep node graphs of different scales saying ‘If you want to get from this large part of the map to that large part of the map you can go through here’. Then when moving across that large part of the map you have a smaller mesh, and at the lowest level maybe a grid that tells you ‘this square is occupied’ or ‘this square has a gate you could destroy’.

You only need to recalculate those when something changes, and these can all be done in the background with spare CPU cycles. When a link disappears (bridge destroyed) it can take a bit to recompute, but that’s okay because you expect any unit trapped on the wrong side to take a second to re-evaluate the situation.

- Group Maneuvers

Tiberian Sun didn’t do it (it used the jostling), but some RTSes would use smarter group logic which would try to move units while keeping them looking nice and being smart about moving through small gaps. For instance if you’re moving three tanks abreast, when they turn you can have them all pivot around the middle tank to keep them in a straight line. When they go through a small gap they can go one at a time and reassemble on the other side instead of all jostling to get through. You can optimize movement through the gap. But this wasn’t very popular because it’s a hell of a lot of work for something most players won’t be looking for.

And there’s always quantum computing:

http://www.smbc-comics.com/comic/cosmology-2