Type of Research: Academic; student research.

Summary:
This article is a very broad overview of pathfinding techniques currently being used in commercial Real Time Strategy (RTS) games. The author points out that “Most games today use some variation of the A* algorithm… This algorithm is based on a heuristic function that ranks nodes in a possible path by… an estimate of the best path through that node.” This algorithm and numerous variations of it are covered in greater detail in Smart Moves: Intelligent Pathfinding. Stout (1996)

The author also made observations about the implementation of pathfinding algorithms in two classic RTSs: Warcraft and Age of Empires 2 and their ability to “look ahead.” Fisher writes, “…[G]ains are readily apparent when comparing Warcraft (the oldest game in the pack) with Age of Empires 2 (the newest). The Age of Empires units are better able to determine a "good" route to a goal. In Warcraft, the units would not reevaluate their positions when moving around objects. They would treat each new obstacle as a separate entity and move around it until reaching the original vector of their path. This wastes time and is an obvious flaw in the pathfinding. Also, the Warcraft units are slower to react (even on the same test machine as the Age units), slower to calculate an alternative when faced with an obstacle, and less likely to take a "good" route when there is unit congestion (a clustering of units, or traffic jam). Furthermore, there is more unit congestion overall as the units are less able to detangle themselves from other units.”

---