Hi there,

I'm starting this thread to describe the algorithm I use to generate outdoor maps for my RPG game (http://www-valoria.univ-ubs.fr/Nicolas.Bonnel/3D/world/loader.html) and discuss about it.

I won't talk about heightmaps : I use a well known algorithm to generates heightmaps : Diamond-square (http://en.wikipedia.org/wiki/Diamond-square_algorithm). The following strategy can be used both for 2D and 3D games.

The areas graph

Once the mesh is created, a random graph is generated : points are randomly generated in 2D space, with a dispersion constrain, so that all points have a minimal distance between them. I will now call these points nodes and connecting those nodes together will create the area graph. The rule to connect nodes is very simple: nodes are connected together when their distance is bellow a given treshold. By tuning the dispersion parameter and this threshold, the average number of connections between nodes can be tuned. For instance if this threshold is a little less than twice the dispersion parameter, nodes won't have more than 6 neighbors.

Nodes can then be visualy linked together, for instance with this algorithm : http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm . During this process, you will have to record the 'path' cells in a 2D array: this is usefull to avoid putting building on roads.

The areas

Areas are randomly assigned to nodes according to constrains. If one wants to add content to add more diversity, he has to creates new areas. Areas have :

- a shape (a disk or a rectangle)

- contrains (altitude, inclination, proximity to other type of areas, ...)

- static elements (vegetation, buildings, ...) that can have contrains on their placement (random, aligned, ...)

- creatures that can have like buildings contrains on their placement

For instance a pine forest can have a disk shape, a min altitude corresponding to a snowy ground, static elements wich are pines and spiders or trolls as creatures. When an area is assigned to a node, objects are put on the map according to constrains. Like said above, a 'path' layer allows to avoid putting objects on roads and give a better overall results. Of course, you will have to use collision detection to avoid overlapping objects.

Areas' level

In RPGs enemies have levels. Here the level of enemies (and loot) is given by the level of the area. To determine the level of the area, I use a breadth-first graph traversal algorithm. In the areas defined, there is a special one that is the starting points : this area is put first, and once on the map. It's level is 0. Then, while exploring the graph, the level of unexplored nodes is increased by 1 (or a random amount). This makes areas near the starting point easy and farther one difficult.

English is not my native language, sorry for the errors. I will be happy to answer any question about this strategy, and I am opened to any suggestion that would improve this :).