Article
havok

Terrain Area Generation from 2D Grids and Waypoint Graphs

Alex J. Champandard on December 6, 2008

In his terrain reasoning masterclass in October, William van der Sterren presented a simple yet effective algorithm for creating areas from an underlying graph of waypoints. The algorithm uses a variety of factors, and can be tuned to provide very useful areas depending on these factors. These areas provide a simplified yet sufficiently accurate representation of the terrain that can be used to speed up most algorithms that don’t require point perfect information.

An implementation of this algorithm was just released as part of the AiGameDev.com Sandbox. The result of processing a 32×32 grid looks like in the following video:

Creative solutions to problems often come from trying to reproduce algorithms that already work well (without necessarily knowing how they are done). So, here’s your chance to brainstorm how to solve this problem. The requirements are:

  • The algorithm should not require too much processing time, and provide sensible results very quickly.

  • If more time is available, the algorithm should be able to find good areas from the input graph.

  • The algorithm should be able to take into account various area criteria specified by the programmer.

Get those problem-solving juices flowing, and post your ideas below in the comments. (If you’re a member, please try to post different ideas than were described by William or implemented in the demo.)

Discussion 2 Comments

memoni on December 8th, 2008

If I were to solve the problem, I would start with watershed image segmentation on the highest density graph. The algorithm is really tricky to get working correctly as it is very prone to noise in the input data. But it produces really nice spatial partition of the input data. It has been used by few authors to generate automatic portals on 3D scenes [1]. This algorithm "automatically" creates partition which conforms most of the rules described in William's presentation. The only one which way tricky to implement with this partitioning method is the cluster size. Yet, I think that the type of partitioning I described captures most of the features which you usually care in shooter type of games. I attached an example image of the algorithm run on similar example data as in Williams presentation. Note that I used vector data as input, so some of the edges are more wobbly (that is, less precise data, better for testing :)). The decomposition captures most of the choke points and rooms and corridors really nicely. It should be pretty easy to run a classification pass on the segments to see what kind of type they are and apply different tactics or pathfinding weights based on that. If you have a multiplayer type of map with two sides, you could also use that partitioned map to find choke points and other important locations which you need to defend. As an added bonus, the decomposition is really nice structure to be used as a hierarchy for pathfinding. I think it is a novel idea, I have not seen it explained on any papers yet, so I guess it is time to pickup the pen and write one ;) The two examples were computed in about 30 ms (they were both in the same map). With some optimizations it should be possible to do the segmentation in half that time, maybe even less. There is a certain bound where the accessing the multiple input maps just becomes the bottleneck. The algorithm works pretty well for local updates too, which makes it nice candidate for dynamic updates at runtime. [1] Volumetric Cell-and-Portal Generation [url]http://artis.inrialpes.fr/Publications/2003/HDS03/[/url]

actionbasti on September 29th, 2011

Sad that the video is not available any longer... Not sure if it was intentional, but the algorithm seemed to slow down considerably towards the end of the video. I used a flood fill type approach, starting at a random \'walk-able\' tile. All tiles that can be considered for an area are given the same starting id. The algorithm starts filling space in a circular motion from the random starting point, assigning a new id per area while the size of the areas is below some threshold. A search method ensures that only tiles adjacent to the current area are used for clustering, if the search fails to find any neighbors, a new cluster id is returned. This algorithm is fast, and produces areas that are <= to the threshold.

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!