Making of Muridae Massacre: Waypoints and Weighting Paths

Central to the game’s design--particularly the layout of the levels—was the question of just where the rodents would plan their routes. The steering behaviors (see the first tutorial) are designed to answer the question of how a rodent travels to a particular waypoint, but not which waypoint to travel to.

The design goals of the waypoint system in MM were twofold: first, the waypoint system should be manageable from a level designer’s standpoint. It should provide branching and weighting structures to match the designer’s vision of the level’s flow. Secondly, the waypoint system should be dynamic so that events during the game may add, change, or remove waypoints or weights. For example, rodents may mark a route as “bad” when it is killed so that other rodents will be less likely to pick the path it died on, or a route may be removed if falling rocks block a path.

Virtools Dev has several features that are directly applicable to designing a path finding or waypoint system. At the inception of the MM project, the grids and the nodal paths system in Dev were investigated as potential backbones for the MM waypoint system. However, it was decided that a custom solution would be used for several reasons. An important factor was that the single programmer on the project was not knowledgeable enough to use the SDK in the timeframe available. This meant that any built-in systems were essentially black box in nature; if changes were required midway through the project, the team would be unable to utilize the SDK to make the necessary modifications. Therefore, a schematic-only system was more flexible considering the team’s makeup. If additional functionality was needed later in the project’s production, it would be added by the same programmer who designed the initial schematic-based waypoint system.

Also, nodal paths and grids tend to offer optimal solutions for solving a path. Nodal paths are fantastic for something like an RPG with non-player characters in a town (finding a path from the inn to the market, for instance). However, non-optimal solutions were desired for MM; many of the stages have meandering routes. If the rodents in the game walked down the obviously fastest routes, much of the fun would be lost. Nonsensical routes can be plotted with the custom waypoint system, as well: paths that cross, circular paths, etc.

The waypoint system in MM is based on arrays. 3D frames are used as waypoint markers, and arrays are created for each 3D frame with the same name as the waypoint whose connections they detail. The waypoint arrays have two columns: one designating a waypoint marker, and one designating the random weight of that waypoint. Rows are added for all connected waypoints. For instance, if waypoint A is connected to B and C as potential paths (from A), the array for waypoint A will have two rows; one for B, and one for C.

When a rodent arrives at a waypoint, it uses the strength information from the waypoint arrays in randomly deciding which connected waypoint to head to next. These strengths are used in the Random Switch BB. A waypoint with strength of 2 will be picked twice as often than a waypoint with strength of 1. The weighting is relative, such that 1 will be picked twice as often when chosen against 0.5, etc. The random weighting system proved to be the most tedious to implement. There is no way to dynamically alter the number of inputs on the Random Switch BB (or other dynamic building blocks). The practical solution was to branch streaming on the number of connected waypoints to schematic code specific to each amount. The example composition’s Behavior: Waypoint Walker script has schematic accommodations for up to 4 waypoint connections. For more information on this technique, see the comments in the script.

The rodents have attributes that track which waypoint they are going to, and which waypoint they are coming from. In selecting their next waypoint, they discount their source waypoint in the decision. This enables two opposing to share a middle waypoint and cross between them.

In MM, the weights for a waypoint are dynamically changed to reflect the danger level of a path. For instance, if a rodent is killed walking to waypoint X, it will reduce the weight of waypoint X on its source waypoint’s array. This effectively reduces the chances for more rodents branching in this direction. The visible effect to the player is rodents avoiding bloodied paths.

The included example composition uses a very simple model for strengthening waypoint strengths. When a character arrives at a waypoint, it increases its strength and therefore the likelihood that more characters will choose it. In turn, the increase in arriving characters increases the waypoint’s strength, and so. The end result is that one path quickly becomes dominant over the others. This is, in fact, a simple pheromone path system.

For more information on the techniques used, open the commented exampled composition "waypoints example.cmo".