Terrain Analysis for Realtime Strategy Games

Pottinger

games terrain situation context analysis ai pathfinding

@article{pottinger:gamasutra-2000,
  title={Terrain Analysis for Realtime Strategy Games},
  author={Dave C. Pottinger},
  journal={Gamasutra},
  year={2000},
  howpublished=
   {\url{http://www.gamasutra.com/features/gdcarchive/2000/pottinger.doc}}
}

Good terrain analysis creates location-based knowledge base

• Greatly simplifies AI players, actions
• Can speed up pathfinding greatly by creating high level plans before coarse pathfinding
  • Pathfinding is typically largest consumer of AI cycles in RTS games
• Can help random map generation, still generally poorly done
• Can extend flexibility, capability of triggers

Pathfinding is a major task in RTS games and biggest tool in analysis

• Consumes 60--70% of AI cycles in some games
• Large maps, many obstructions make it difficult
• But very visible to user when performance is inadequate
• Important to have high level AI make decisions based on same technique used for low level movement, otherwise the two can mismatch oddly
  • "canPath()" checks

Influence maps/volumes help direct planning

• Goal/hazard based reward/cost gradients
  • Example uses: positive resources, to place near them; positive high ground, to move idle troops there; negative weights along previous attack vectors, to bias for new angles of attack
• Has trouble with some cases, e.g. if a tile has both rewards and hazards which cancel each other out

Area decomposition is primary human terrain analysis tool

• Can speed up analysis by abstracting map
• Greatly improves decision making, e.g. defense placement
• Requires careful coding for dynamic terrain, e.g. when obstructions are added/removed
• Probably have to have restrictions in size, e.g. to avoid all-land maps from being one area
• Useful to track statistics within areas, e.g. attacks, sightings, etc
  • Much less clear if areas overlap
• Simple flood fill approach creates decent areas
  • Must be iterative rather than recursive, as areas are large
  • Best if FIFO rather than stack based---latter tends to produce long areas, the former tends to cluster around the starting point

Coding everything to be time sliced is useful

• Some feature will overrun time budgets and have to be spread out

Putting area hints into the terrain editor can help a lot

Using actual units (e.g., meters) as game units greatly simplifies changing tile sizes