Thursday 5 July 2007

Wilderness generation using Voronoi diagrams

Reposted from an old post on

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:

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

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).


James McNeill said...

I like your idea of flood-filling difficulty level through the regions, but be aware that this may not do exactly what you want on the edges of your map, because distant nodes can end up as neighbors in the Delaunay triangulation. (Here's an illustration.) You might need to trim skinny triangles off the outer perimeter or something like that.

James McNeill said...

Come to think of it, you might get better luck just scaling difficulty with distance from the player start point, as long as the landscape is fairly open.

In general I'd think you would want to scale difficulty by travel distance/difficulty. If it takes special equipment to get up into mountains, for instance, the encounters up there might be more difficult even if it's close to an easy region, since the player can't get there until they've acquired crampons and ice axes.

I'm looking over some code I wrote to generate Delaunay triangulations years ago. Here's a sketch of one way to do it:

Create a simple initial triangulation that encloses all of the points. This could be a pair of triangles forming a rectangle, for instance. Ensure it is Delaunay (that is, the circle through by any three points does not contain any other points). For a rectangle this property always holds.

Insert the points into the triangulation one at a time, ensuring the empty-circumcircle property still holds after each one:

1. Find the existing triangle containing the new point and split it into three new ones such that the new point is now part of the triangulation.

2. Restore the empty circumcircle property by turning edges around the new point.

When you're done you can strip off the outer triangles connected to the original rectangle corner points, if you like, to get a triangulation of only the points of interest.

The Wikipedia article says pretty much the same stuff. For actual implementation you'll find a half-edge data structure pretty useful, I would think.

Another way is to come up with some triangulation, any triangulation, of the points. Then go through and turn edges wherever you find a point inside a circumcircle. If you attack them in an organized fashion, you can get the triangulation into Delaunay shape fairly quickly.

Andrew Doull said...

Thanks for the advice. I had in the back of my head similar ideas to your mountain suggestion, where difficult to traverse locations could seperate locations of extreme difficulty (e.g. mountains, seas, walls of fire or ice etc).

I also quite like the idea of being able to choose which path to take based on a difficulty slope e.g. the adjacent locations are either +1 or +2 difficulty. That way you can navigate a path of +2 difficulty increases if you find a powerful item that boosts your overall survival chances. It'd be important to distinguish the +2 difficulty slopes (dead bodies, piles of skulls, warning signs etc) of course.

This is equivalent to diving down multiple stairs quickly.