Type of Research: Commercial computer game development.

Summary:
Pottinger, the technical director for Ensemble Studios the creators of Age of Empires (AOE) and Age of Empires 2 (AOE2) describes the methods used in the game to analyze and store homogenous terrain types within the game.

AOE, AOE2 and most other Real Time Strategy (RTS) games must support randomly generated maps. Consequentially, after the random map is generated, but before the game actually starts, an analysis must quickly be made of the map and stored for future use.

Figure 3: Influence map around gold mines.	Figure 5: Terrain from Figure 4 mapped into subareas.

The technique employed by Pottinger involves mapping ‘influence’ (or what we used to call ‘spheres of influence’ around key areas. Furthermore, Pottinger divides the areas into subareas (see Figure 5) above. These areas are determined by a flood fill algorithm (old but effective) with some modifications to keep from overrunning the stack.

The 3D maps are created using the proprietary BANG! 3D engine which allows for multiple layers of influence mapping and storage.

It is interesting to note that Pottinger writes, “Pathfinding is one of the slowest things most RTS games do (e.g. Age of Empires 2 spends roughly 60 to 70% of simulation time doing pathfinding).” Having played AOE and AOE2, and being aware of the fairly small size of the maps (usually less than 100 x 100 tiles) I would have thought it would have been possible to pre-calculate paths and store them leaving the CPU time for other things.

Pottinger concludes with this advice:

Useful Tidbits

Terrain analysis doesn’t need to be exact. If you try to make it perfect, you’ll either end up spending a lot of time tweaking heuristics or you’ll have a lot of extra areas that really don’t buy you anything.

Abstract the area representation (tile vs. polygonal) away from the users (e.g. the CP AI) as much as possible. This will allow you to change it to fix bugs or upgrade as needed.

Build it to support dynamic terrain. Even if you don’t have dynamic terrain in your shipping game, this helps debugging and testing.

Write all of the processing so that it is time-sliced. Even if you don’t use it right away,someone will inevitably code (or ask you to code) a feature that blows out your carefully constructed time budgets. If you have time slicing built into the system from the start, that’s not a problem. This also lets you run the terrain analysis during the game much more easily and effectively.

Build area specification tools into the scenario editor. Use these to simplify the processing. There’s no reason why a scenario author can’t put hints for the terrain analysis into the scenario. This also lets the scenario author tweak how the CP AI thinks about the map.

Since the random map generator already has to manage areas and connectivity to generate a decent map, it should just pass that data to the terrain analysis. If the random map also has a general shape (e.g. AOE2’s Mediterranean map), that information can also simplify the terrain analysis’ task.

Don’t use tiles as a measure of distance. Be trendy and use meters as the unit of measure so that you can change the tile size without having to rebalance your game data and your AI heuristics.

Pattern recognition is a hit or miss proposition. If scenario authors do a little work and know the basic properties of the game’s random maps are known, real pattern recognition may not be needed to do effective terrain analysis.

If real pattern recognition is needed, though, a couple of easy options present themselves. Since the tile subareas have too much data and convex areas have unknown holes inside the areas, the tile subareas could be hulled used instead. The data reduction would make recognition easier and the smaller areas would tend to have fewer holes. Running pattern matching on the mip-mapped version of the map is also another option.



---