Generating probabilistic roadmaps

A heuristics and rejection sampling based strategy.

A roadmap is an abstraction to represent traversable areas in a game world. Roadmaps, similar to graphs, consist of nodes and edges. Nodes indicate freely traversable locations and edges indicate whether a direct route is available between nodes.

Constructing a roadmap can be done randomly, this is called a probabilistic roadmap. Prior to implementing this into my game, I ran a few experiments to determine the usability. This first implementation is shown below. Rectangles indicate ‘buildings’ and the graph indicates traversable areas for player characters. Construction is quite simple: 1) add random nodes in free areas, 2) connect nodes if a line-of-sight exists. The result is as follows:

This roadmap isn’t very useful. It only reaches certain areas of the game world.

Heuristics (i.e., guidelines) can be used to determine which areas are interesting to add random nodes (inspiration). The the edge count of a node can be used as an indication that more nodes are required in a region. If a node has few edges, it is probably hard to reach; thus more nodes are required nearby. Extending the above implementation, I add more nodes if the edge count is low, the result is as follows:

It improves the roadmap somewhat; but two issues occur: 1) it may take some time before a valid node is found 2) some areas become too dense with nodes. Slow loading times aren’t terrible, but too many nodes in a region does become an issue when A* is ran. Filtering nodes with too many edges is possible, as seen here:

Note that I only remove edges when both nodes exceed the maximum edge count. This cleans up the roadmap nicely, but depending on randomness, it may disconnect regions. For my own game, this isn’t really an issue: the game world layout is far simpler than the random world in this article. One issue remains, the roadmaps seem biased to cover only large open areas. There isn’t nearly as much coverage near buildings. In my game, characters must run for cover - which is generally found close to buildings! To get a better spread of nodes, let’s experiment with different types of random numbers. The random numbers so far are uniformly distributed, however, if you observe the roadmap, the node spread doesn’t look very uniform at all! This is because the distribution will eventually converge to a uniform spread - but it may require thousands of samples before it appears uniform (see law of large numbers). I want something that is also uniform with a few samples drawn. A useful technique is rejection sampling, it works as follows: 1) pick random number, 2) determine if you like the number, 3) keep the number, or reject and go back to step 1. Practically speaking, I generate a random node, if the random node lies near an existing node, reject the node and generate a new one. See the demo below:

It’s a schematic representation, the existing node (blue square) lies in the middle, and new nodes (arrows) are generated based on either rejection sampling or uniform sampling. Notice this: if you increase the number of samples - they both become uniform, the rejection sampling just converges quicker, especially with less than 5 nodes. Putting this in practice gives the following result:

It looks kind-of nicer, but not overwhelmingly great. The spread visually appears better, but is far from uniformly spread. This could be explained by the initial random waypoints, those are not yet using rejection sampling. Another issue arose: when a node resides near a building, the rejection sampling repetitively tries to place a node inside the building (since that is a node-free area), it takes many tries before it eventually finds a suitable location outside a building.

Conclusion

This article followed my exploratory research towards generating probabilistic roadmaps and rejection sampling. Using a few heuristics, a randomly generated roadmap was improved. The resulting roadmap is usable, but appears far from perfect with respect to traversable area coverage. It is my expectation that nicer maps will be generated if the computer is granted more computational time - this demo was aimed at real-time generation. To be continued.