Wilderness generation using Voronoi diagrams

Reposted from an old post on rec.games.roguelike.development.

I'm starting to think about re-doing wilderness generation for Unangband, a variant I've developed from Angband. I've spent considerable amounts of time developing a complex, dynamic terrain system, and whilst this is fun in the dungeon, I think for the player to fully appreciate it, I'm going to have to include a more complex wilderness than Unangband currently features.

Unangband currently has a fixed graph-based wilderness travel. Each wilderness location is the same size as a dungeon, which contains one or more terrain types generated by a drunken walk type algorithm, over a background terrain, and may feature dungeon rooms connected by trails, which are guaranteed to be traversable. To travel between wilderness areas, you press '<' on the surface level, and can travel to a number of 'adjacent' locations, which increases as you defeat the boss monster (Angband unique) featured at the bottom of the dungeons. At some points, the graph is one way - you can't travel back to the original location once you get there. Some wilderness locations act as towns, one-screen sized locations containing a variety of shops.

Dungeons under a wilderness location are distinguished by the types of locations, terrain types on the level generated by the same drunken walk algorithm as surface terrain, the background terrain through which corridors are tunnelled, and boss monster at the bottom of the dungeon, which is always fixed.

Unangband's current terrain system has received praise for being focused and simple. You don't spend forever wandering around a wilderness level - just until you find a set of stairs down. The wilderness levels are just dungeons with open space instead of walls around the terrain (they are still surrounded by permanent walls at the edges).

Unfortunately, the wilderness graph is not particularly easy to understand. Players complain that wilderness locations appear and disappear randomly as they move (a consequence of the implementation of the graph). In particular, its hard to make it clear that some graph locations are 'one-way'. Its also hard to make clear that some locations have no dungeon, just a surface boss monster, who, for play-balance reasons, only appears at night.

I've looked at a number of wilderness implementations, and have focused on Zangband's in particular (at least the new wilderness implementation). The terrain in Zangband's wilderness system, for want of a better word, is beautiful, and something I aspire to. However, the Zangband terrain generation system suffers from a number of serious problems, in particular, that the algorithms used are overly complicated, there is not enough incentive to travel between wilderness locations (I know the Zangband development team are improving this) and that the difficulty level is too high for starting out characters and exploitable for higher level characters.

Recently, I ran across an indirect reference to Voronoi diagrams in this newsgroup, and realised that this will provide the solution to my issues with the Zangband wilderness. I'll run through what I intend to do with them, and raise some questions that hopefully someone here can point me in the direction of.

The new Unangband wilderness will be divided up into regions, by randomly generating sufficient spoints on a large wilderness map (4096 x 4096) and using a Voronoi diagram to divide the space into the regions (each map grid will be associated with the region of the nearest point generated). Take the Delauney triangulation of the points and select a vertex (region point) and give it a difficulty 0. Give its neighbours a difficulty 1, and so on, 'flood-filling'
the graph until all vertexs are assigned difficulties. Then normalise these difficulties against the desired difficulty range of the whole wilderness.

The region data structure can then be expanded as per the following pseudo-structure:

region
point (x,y)
int difficulty_level
text region_name
dungeon_type dungeon
race_type monster
terrain_type terrain
etc.

To select a terrain type can be done using a variety of methods. I quite like the Zangband 'three-space' terrain parameters, law (which corresponds to difficulty_level above), population and altitude. Its possible to generate this fractally by picking one or more random low and high points on the Delauney triangulation, and interpolating between then (perhaps using a fractal
algorithm, and/or weighting the differences based on the distance between region points). You could pick points in a manner that guarantees that all possible terrain is available on each map, that Zangband cannot do currently. Its also more efficient than the Zangband method, because once you've generated this one, you can store the selected terrain type, and throw away the generation parameters.

Once you have the terrain type for the region, the actual terrain in each map grid can be determine a number of ways. I suspect I'll have the following:

1. Open regions, with randomly / fractally placed point terrain. These should be selected so that terrain types that are likely to be adjacent have some terrain types in common, so terrain transitions across between two terrains without creating a hard edge.
2. Building regions - as open regions above, but a rectangular feature is placed within the bounds of the region.
3. Field-type regions (as in farmers' fields), which are filled with passable terrain but have an impassable edge, with a gate/bridge placed at a random location on the edge. If two field regions are next to each other, the region with the lower difficulty level does not place the edge.
2. Hill-type regions, where the height is calculated as the distance from the point to the edge of the region, and the slope of the height change determines the terrain (flat, slope, or wall).
5. Mountain / lake-type regions, which are filled up with an impassable terrain up to an hard / fractal distance from the edge.
6. Completely impassable regions. I will use the Delauney triangulation graph to ensure every passable node is accessible.

It should be possible to 'merge' adjacent regions of the same type, so that any regions that share a common edge type / centre type do not generate edge terrain when next to each other.

Because I will be storing regions, it should be easier to replace region types, in the event, for instance, I want to have a huge building in on a magma island surrounded by lava that takes up multiple regions space.

Of course, I'm going to need some fairly good programming to get the above done, but I can see how to proceed.

Firstly, can someone point me in the direction of a fast integer based look-up algorithm to determine which region a map-grid is in? Ideally, I need a data-structure that supports searching the minimum number of points. Ideally in C.

I also need a fast algorithm to draw the terrain on a subset of the whole map. Obviously, I don't want to have every map-grid in memory. I'm thinking of adopting Zangband's in memory representation of 16x16 grid patches, that can be generated quickly when scrolling into the map area, and destroyed as a player moves away. Alternately, I'll have to have a large scrolling window looking down on the total map and generate larger areas as the player moves. So I need a fast drawing algorithm for each of the above terrain types, that doesn't create gaps. So some kind of rasterisation algorithm for a 2 dimensional Voronoi diagram please, and a good suggestion as what memory management technique to adopted (patches / scrolling window / etc.) Also, ideally in C.

Finally, any suggested strategies for generating and representing in memory the Delauney triangulation. This is only required for the initial region generation - however, I may also use it to determine difficulties for overland quests (by finding the highest difficulty of the regions required to cross to travel to the quest location).