As promised, a first post on path finding solutions for games. The first structure I’m going to treat are so called waypoint graphs, and are still commonly used in games regardless of their downsides, mainly because of their simplicity.
A waypoint graph is actually a very simple concept; positions in the free space (so, the area that a character is supposed to be walking on) are sampled either by hand or by algorithm, and n‑nearest neighbor points are connected to the newly sampled point by an edge if no obstacles are detected between the two points. It is one of the most classical solutions used in games, and is still being used by games today. Short paths are found by applying A* on the graph. Start and goal configurations would be added to the graph as temporal waypoints and characters would move from waypoint to waypoint until the goal is reached.The problem with this is method of course is that it doesn’t give any idea on the boundaries of the free space, so the coverage cannot be optimal by definition and is dependent on how many waypoints are used. In other words, characters are stuck to using waypoint routes, and deviating from the path isn’t really possible unless you perform a collision test on the intermediate path to check if it doesn’t hit any obstacles. On of the games that recently came out still uses this technique; Alien Swarm by Valve. In Alien Swarm there are many waypoints, and they are all connected with a lot of neighboring points. Collision detection is used to check if a path is actually valid and disabled if not (see screenshots). The main reason this is done is because the environment can be dynamic. For the paths in a limited area where the environment is dynamic and changing, new paths are added if they are free from collisions with the changed environment.
Waypoint graphs can also be extended to include a radius. These kind of graphs are sometimes referred to as circle-based waypoint graphs. The idea is that characters may only traverse from waypoint to waypoint if their circles are intersecting. The improvement over a simple waypoint graph is that a circle-based waypoint graph approximates the free space. The problem is that when waypoints are placed in arbitrary locations, the approximation of the free space may still be fairly inaccurate, which means that characters still can’t reach locations that are visibly reachable. Also, the denser the environment is, the more waypoints you will need generally because the circles of the waypoints are smaller. By placing the waypoints along the medial axis of the environment (the axis on which the distance to two different obstacles is equal) you can insure connectivity.
Next time more on waypoint graphs 😉
By the way, Alien Swarm is freely available on Steam.