Archived from groups: rec.games.roguelike.development (More info?)
Hi,
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).
Regards,
Andrew
--
Unangband L:C E+ T- R- P+ D-- G+(+) F:Sangband RL-- RLA-- W:F Q++
AI+(++) GFX++ SFX++ RN+++(+) PO++ Hp+++ Re--(+) S++ C- O* KG--
Hi,
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).
Regards,
Andrew
--
Unangband L:C E+ T- R- P+ D-- G+(+) F:Sangband RL-- RLA-- W:F Q++
AI+(++) GFX++ SFX++ RN+++(+) PO++ Hp+++ Re--(+) S++ C- O* KG--
Facebook
Twitter
Instagram