User:Duerig/Archive7
More Continuous Content - Joseph Swing [JSwing@wport.com].
One feature of RL games is the random placement of monsters and objects. While this is good in general, it leads to setups that are highly improbable at best, and ludicrous at worst. You know what I'm talking about. A barrack of soldiers with one exit leading to a room containing half a dozen giant spiders. Orcs frolicing in one room while a lone elf wanders next door. Wargs who ignore the juicy smell of the nearby ratling. And so forth.
A good AI helps, but if the initial placement of the monsters makes it unlikely the would encounter each other by their default behavior, the problem isn't fixed. The community has done a fantastic job developing dungeons that are physically continuous, but whose content is not.
First of all, we need some additional data for our generic monsters. Something which indicates which monsters tend to be next to which monsters. Call it a Theme. For a Goblin Lair theme it might look like:
1 Goblin King and 3 advisors (1-3 hobgoblins) (unique, mandatory) 2 Goblin guards (1-6) 2 Hobgoblin guards (1-2) 3 Goblin Wolfriders (1-3) 3 Goblin Shopkeeper (unique) 3 1-3 Goblins and 1-2 Goblin thieves 4 1-2 Goblins and a Crate 4 1-2 Goblin Guards 4 Goblin pig farm - 1 goblin and 3 pigs 4 Empty Room 5 Empty Room 6 Empty Room - random monster possible 7 Empty Room -random monster or stairs allowed
First, as you;re building your level, check if there's a theme. Not all levels should have one. If your level has a theme then start at the top of the list.
In this case, the first room that you plunk down should have a Goblin King (#1) in it. When you draw your doors/hallways, draw them leaving from this room, and carry with it the number on the left. Moving to the next room, move down the list (75% chance) or back up the list (25%). For the example above, there are two possibilities, either some Goblin or Hobgoblin guards. Add these to the next room. Draw your doors/halls from there and continue.
You may even choose to add some entries to the hallways themselves, if they're large enough. The Goblin King might have a few guards in the outside hall, but it would be difficult to have a pig farm in a hallway. If you wanted to use this option, the simple solution is staggering your entries so that odd ones were in rooms and even ones were the hallways between.
The nice thing is that you end up with a small goblin community, with a few empty rooms between them and any wandering monsters. The Goblin King sits at the middle, furthest from the stairs where the hero will enter, which is nice.
How to implement? If you're carving your dungeon this is easy. Starting with an empty dungeon level, you maintain a separate list of doorways: 1) Start with a dummy doorway with a content value of 1 2) From the doorway, try and add a room filling with content value from the doorway; if successful, add both the room and doorway to the map. 3) Add doorways from the room, migrating the content (1->2, etc) 4) Step through your list of doorways and go back to step 2; You're done when you;re out of doorways
If you're using the grid to plunk down your rooms you either need to wait until you draw the hallways (and draw them carefully), or use a flood fill algorithm.
If you don't always use fixed rooms (like Crawl) I suppose you could also flood fill with each entry having a certain radius before it transitions to the next one. It's trickier.
Other thoughts: Not all levels should have a theme. Some themes should be smaller than others, maybe only a few connected rooms, with the rest of the level being more random. To set up the themes you could make them more abstract. Make the sample above generic to humanoids (xxx lair) and fill in with the details fro the appropriate level at run time (Orc Lair, Goblin liar, etc). Or you could make a large Monster Map connecting the likely monsters/groups. One whole edge of the map should be 'random monster'. I recommend that no more than about 1/3 to 1/2 of your dungeon be filled with this kind of theme, to keep the replay value. If you include stairs with doors as transition points, it's possible to spread the theme in 3d, and no longer required to keep the stairs so far from the center (just treat it like you would a door). Along with the monsters, make the objects more continuous too. The Goblin Guards might have an extra sword lying around, but the peasants aren't going to have 50gold for very long. The empty rooms near the Lair might thave signs of the local occupants - grafitti in the goblin tongue, for example.
Creating A Dungeon - Brian Bucklew [bbucklew@inteletek.com].
Section 1 : Creating A Map
When creating a rogue-like game (RL from this point on), there
are several points you have to address. One of the first problems you are likely to encounter is the problem of generating a suitable dungeon level. Actually, not only do you need a level, you need a pretty much infinite supply of random levels all filled to the brim with monsters, treasure, traps and other various unsundries.
Our first goal will be to actually create the maze, empty. Later
we can integrate code that stocks our dungeon, but for now our main goal will be to just get a pretty fair complex of passages and rooms.
As with an programming problem there are many solutions, each
that generates a perfectly acceptable dungeon. The first method we will discuss is a recursive one.
Creating A Map : A Recursive Method
This algorithm will be based around taking a solid chunk of rock,
let's say 256x256 and carving a dungeon out of it using rooms and passages. We'll try to stay as simplistic as possible at the beginning, though this algorithm can be expanded to generate many different dungeon types from caves to castles, with fairly minor changes to the basic code.
So we begin with a 256x256 array of blocks, each filled with stone.
For our basic dungeon generation we will also need two functions:
MakeRoom(), which generates a random room and then calls: MakeHall(), which generates a hall of random length.
We will call MakeRoom() which will generate a randomly sized room, which will then call MakeHall() a randomly determined number of times out into the dungeon from the walls of the room. MakeHall() will generate a hall of a random length. At the hall's end, the hall will either 1:End 2:Call MakeHall() a random number of times in random directions or 3:Call MakeRoom(). Later we can improve the algorithm my making a hall stop if it hits another hall or room, or coding rooms so that they won't overlap, but for now this will suffice.
lets say, using pseudocode we have:
... StartX and StartY will be integers defining the seed location ... of each room and hall
... Direction will be an integer defining the direction the ... room or hall is facing
... RecurseDepth will be used to terminate the recursion at a specific ... depth
First we will define MakeRoom.
void MakeRoom( StartX, StartY, Direction, RecurseDepth ) {
integer X1,Y1,X2,Y2; // These variables will be used to define
// the extents of the room
// limit the recursion to some depth
if( RecurseDepth > MAXRECURSEDEPTH ) return;
DetermineExtents();
/* We need to take direction into account when determining the extents
... For Example:
( '#' = Rock '.' = open space, in standard RL convention )
##########
##########
##########
#####X.... <--- Hall calls MakeRoom at X going west.
##########
##########
##########
This is the situation we want to create when determining
the extents:
a = x1,y1
b = x2,y2
##########
##########
#a****####
#****X....
#****b####
##########
##########
This is good...
If we did not take direction into account, we would most
likely end up with this:
a = x1,y1
b = x2,y2
##########
##########
###a****##
###**X....
###****b##
##########
##########
This is bad...
- /
CreateTheRoom();
for( x = x1 to x2 )
for( y = y1 to y2 )
Dungeon[x,y] = OpenSpace;
integer R = Random(0,4); // Actually this is probably some non-linear
// random choice, but this will suffice.
for( x = 0 to R )
{
int hx,hy,hd;
DetermineLocationOfHall();
// Choose a spot along one of the walls,
// Then determine the appropriate direction
// (North,South,East or West) depending
// on the chosen wall.
MakeHall( hx,hy,hd, RecurseDepth+1 );
}
}
Now, MakeHall which is comparatively simple:
void MakeHall( StartX, StartY, Direction, RecurseDepth ) {
// Limit the recursion...
if( RecurseDepth > MAXRECURSEDEPTH ) return;
integer x1,y1;
x1 = StartX;
y1 = StartY;
for( x = 1 to RandomLength )
{
if( x1 or y1 is out of bounds ) return;
Dungeon[x1,y1] = OpenSpace;
// Note:
// For ease of stepping in a direction we will define
// two arrays containing the X & Y deltas of each direction
x1 += DirectionXDelta[Direction];
y1 += DirectionYDelta[Direction];
}
RandomChoice = Random(1,3);
if( RandomChoice == 1 ) return;
if( RandomChoice == 2 )
for( x = 1 to Random(0,3) )
MakeHall( x1,y1, RandomDirection, RecurseDepth+1 );
if( RandomChoice == 3 )
MakeRoom( x1,y1, Direction, RecurseDepth+1 );
}
That's it... A simple recursive algorithm for carving out a dungeon. This is by no means an ideal algorthm and requires quite a bit of tweaking and a few algorithmic improvements to generate a really good dungeon, but this example serves to illustrate the method.
The Author: Brian Bucklew, 18 bbucklew@inteletek.com Current RL Project : Dungeon or "This game needs a new name"... :) Projected Beta Release : Early 98
The Building of Towns - Michael Blackney [michaelblackney@hotmail.com].
Introduction
Most roguelikes of reasonable popularity contain towns, though not always in the design we are used to seeing them in real life. I for one am utterly confused by the first town in ADOM. How is it that this small group of farmers and rations salesmen were not wiped out long ago by horrible dorn beasts? How do they defend themselves? And with the multitude of eager young adventurers at their doorstep, why has no one opened a sucker-market? In this article I intend on addressing these points, and other problems I have encountered with town-creation. This method should, with few adjustments, work equally well with all sizes of towns and can be used both as a random-town generator (like in Angband) and to help with preset-town design (like in ADOM). For code excerpts I have used C++, as I favor it. I could have used Pseudocode for those of you who don't understand C++, but then nobody would be happy.
Features
Most of this article will refer to 'Feature's. This is a class
created for the town design stage. A Feature represents an arbitrary
feature in your town, be it a house, a forest or a grave. You may
even decide for consitency to make the Town a Feature as well. A Feature
upon creation often creates other Features which are part of it, such
as a Castle Feature which creates a Moat, a Guardhouse and a Keep.
A simple C++ interface for the class Feature could be as follows:
/-*/
class Feature {
public:
// Construction / Destruction
Feature( Level*l, char x1, char y1, char x2, char y2 )
: onlevel( l ), name( "" ), bounds( x1, y1, x2, y2 ) { create(); }
virtual ~Feature( void );
// public methods
virtual void create( void ) = 0; // Specialized classes must override
// this method.
protected:
// inheritable data
String name;
Rectangle bounds;
Level *onlevel;
};
/*-/
This class would interact with the Level class, which describes a 2d
array of LevelElements where each LevelElement represents one game
square. The create() method would then alter the Level accordingly,
adding walls, floor space, trees or whatever.
Natural Terrain All towns (which I intend on covering here) are situated in the 'real' world that you have created, and as such all have surrounding terrain. In fact many of the decisions to be made regarding the features found in your town will be affected by the terrain in and around the town. We all know that when people decide to establish a town, the terrain is already there. For this reason, we should create the surrounding terrain first. One way of implementing this is to make a series of specialized Features each dealing with a different type of terrain. Classes such as Clearing, Swamp, Coast and Hills are all examples of this. These classes can then create the streams, forests and so forth.
TEST RUN:: The following is an example of terrain creation. We begin with a blank 15x5 level like so:
xxxxxxxxxxxxxxx xxxxxxxxxxxxxxx x unallocated LevelElement xxxxxxxxxxxxxxx xxxxxxxxxxxxxxx xxxxxxxxxxxxxxx
We then decide (using our special number generator) to create a grass field. The GrassField class calls its version of create() which at first will do nothing more than filling the level with grass squares, like so:
............... ............... . grass ............... ............... ...............
create() then has some decisions to make, such as how sparse vegetation is and how frequently streams occur. Our GrassField decides to have a SmallStream and a few scattered trees. Soon out GrassField looks like this:
............... .T....T..=...T. . grass .........===... T tree ..T....==...... = water (now part of SmallStream) .....==.....T..
The actual generation of your terrain is up to you. You can make this as simple or complicated as you wish. Now that we have a Level filled with adequate terrain, it is time to establish a settlement.
Your Town In order to make a sensible Town, it must be created and inhabited by your residents, with all of the benefits and drawbacks this brings. eg. If you wish to have thieves in your world, it makes sense to either have a thieving skill (such as ADOM's Pickpocketing) or to have houses where our friend the Aimless Merchant keeps all of his most valued posessions. Otherwise our poor friend the thief would be out of a job. In order to know what types of features to create, we really should know the types of people who will be interacting with them. To get the ball rolling, I have created a small list of likely residents in a fantasy world. In doing this, it becomes more clear what sorts of features I will expect to find in towns.
Professions (in no particular order) - Warriors - Mages - Scholars - Smiths - Guides - Alchemists - Rogues - Bards - Merchants - Assassins - Paladins - Monks - Priests - Runesmiths - Thieves - Druids - Rangers - Farmers - Men-at-Arms - Knights - Guards (and police) - Traders - Pirates - Masons - Healers - and so on...
Try to make the list smallish to begin with to speed things up a little, you can always return to this point if you think of more later.
Profession-Related Features For each possible profession in your rich and complex world, you will require a place for them to 'hang out'. Examine your profession list and see what you can come up with. For this I have separated my profession list into three categories: Class, Guild and Religion- based, though this is not really necessary.
Class-based features - Taverns (for Bards and drunkards [warriors, rogues]), - Houses (for people to live in and thieves to steal from), - Library (for Scholars and Mages), - Hospital (for Healers), - xxxxsmiths (for Smiths), - Shops (for Merchants), - Ports (for Traders, Pirates, Rogues, &c.), - Farms (for Farmers), - Alpharmacy? (for Alchemists).
Guilds - Barracks (for Men-at-Arms), - Thieves Guild, - Assassins Guild, - Runemasters Guild, - Gatehouse (for Guards), - School of Magic (for Mages), - Palaces, Castles, &c. (for Guards, Knights).
Religions - Assorted Temples and Churches. These should have variance to shew the alignments of your gods, eg. - Monastery, - Nunnery, - Cathedral, - Stone Circle (for Druids).
Other - Inn, - Stables, - Asylum?, - Town Square.
Now that we have a nice beginner's list of features for every fantasy denizen, we can flesh it out by adding some nice small details. Many other types of features are required for efficient town life. These quite frequently have to do with keeping the residents alive, or disposing with the dead. Small additions such as wells and fountains can add much richness to a settlement; as can graveyards, statues, gibbets (and all other forms of public humiliation and execution), and so forth.
Town Themes Before taking the above information directly to coding, one key issue must be addressed: that of town themes. In life, towns are frequently created for specific needs, be it a need for metals thereby necessitating a minetown or merely a need for clean water and safe refuge. If you wish to have more than one town in your game, it will be quite integral to their design to give them themes. The best example of why town themes are important is to think briefly of what your towns would look like without them. Imagine ten towns, all of roughly the same size, all with mines, all with markets, all with churches, all with guilds. These towns look artificial and can be much worse to play in than towns built completely randomly merely because of the cookie-cutter look they will have. I will assume here that if you do wish to have more than one town, you have a way of modelling the landscapes surrounding them, like the realm maps of ADOM, Omega, &c. This is not required, though as themed towns can add a lot of flavour even to games like Vanillangband with only one town. It may be handy to make note of the types of terrain your denomination of humanoids may inhabit, and why they would be there. eg. Human - Mainly near water, forests. Have Castles on hills, Ports
near running water, only small towns in mountains. Dwarf - Mainly on hills. Have Mines in mountains. &c.
Doing so will help the software in setting the theme for a town. Upon the decision to settle a specific area, the designer should examine the surrounding areas to see what a town here could add to life elsewhere. Is it a port for merchant ships? an oasis for passing travellers? a mine- town to supply precious metals to neighbors? You will acquire a rough idea of how large a town will grow to be, given the amount the town is needed at its location and the theme of town created. eg. If a town theme TouristTown is decided upon for an area with only a small surrounding population and no hot tourist spots (no dungeons, &c.) then the town will be quite small. Whereas if a MineTown is decided upon and the mine is a necessary backbone for the arms and armour of a whole race, I would bet that it would be defended quite well, no matter how close they were to the enemy borders. Town themes also generally restrict the types of Features occuring in them. It would be nothing short of disastrous to have your WitheredHouse near the StoneCircle filled with Cultists, only to have the evil random number generator put HappyJoesFriendlyInn between them. After the decision of what Theme to use has been made by the software for the town, it should then access a list of what features will be available for this theme. You can do this any way you wish. For article continuity I will use a similar sort of list as Joseph Swing [JSwing@wport.com] used in his article on Continuous Content in dungeons, though I have adapted it to make use of my system of Features creating sub-Features. A sample list of a Human MineTown:
Human MineTown
.1 MineShaft ( exactly 1 )
.2 Port ( if running water is available, maximum of 1 )
.1 Market
.3 Keep ( exactly 1 )
.3 Tower
.3 Castle ( if town is large, maximum of 1 )
.1 City Walls ( exactly 1 )
.2 Keep ( exactly 1 )
.3 Gatehouse
.3 Barracks
.4 Tower
.5 Tower
.6 Tower
.4 Temple ( or other religious site )
.5 Tavern
.5 Inn
.1 Tavern
.5 Shop
.6 Shop
.6 xxxsmith
.6 Town Square
.7 Farm
.7 Farm
.7 House
.8 House
.9 House
The actual order of adding Features to your town is up to you. I suggest that you first create the important parts, such as mines, ports, and any other parts which depend on a certain type of terrain for positioning. This is to ensure that you don't place another Feature where it will obscure access to the required terrain. You may wish to add (for added complexity) a system which records certain values for each town: foodAccess, shelter, defence, trade, and so on. This will allow you to avoid adding redundant features, such as excessive shelter per resident, and more food than your residents can eat, trade or store.
Townspeople (t) Now that you have a reasonable idea of how you can design the towns, you now have the option of adding towns-people. I say option, because it would be nice to have a version which doesn't create 'regular' inhabitants so you could adapt it to create ghost-towns, overrun towns, and more. This could easily be done by creating the class Town, then the derived classes PopulatedTown, GhostTown, &c. Then all that these specialized versions need do is add the residents (possibly also knocking a few walls down for that 'derelict' look). This is also a nice way to create over- run towns, such as the Human town taken over by Goblin Berserkers (or vice-versa). I will not go into the depths of creature behaviour here, though I will say that if you are going to this much trouble to make realistic towns, you really should think about adding at least a little depth and complexity to your creatures. You may also wish to consider racial tensions (if any) when creating your towns. It is a fairly common fantasy convention that Dwarves don't really like anyone. This could be taken into account when creating your towns, lowering the probability of other races living in a mainly Dwarvern town. In the system I have developed, I take a creature's religious alignment to be much more important than their actual alignment. This allows creatures of all nationalities to befriend each other should they follow the same god: but creatures of opposed gods will certainly not tolerate living in the same town as each other.
Creation TEST RUN::
Below is a demonstration of the previous methods in action, of the steps
an implementation of this might undergo. - Map. We begin with a map, created by some other means, showing our lovely countryside, as below. Take note that this is a 'Realm Map', such as in ADOM.
..^^....==... # Dungeon (or tower, ghost town, etc.) ^~^~.^~..=... . Clearing ^#~......==~~ T Forest .....TT...=== = River ......TT..~^^ ~ Hills .T.........~. ^ Mountains
- Choose an area. How you do this is up to you: you can use the RNG, or (my personal preference) you can have a Race(Human) class make the decision on where they would likely settle. If you use this method you must choose at this point what race will be living here. We will create a Human city for this example. Here, the X marks the spot where we have decided to build.
..^^....==... ^~^~.^~..=... ^#~......==~~ X Proposed town site .....TT...=== ......TT..X^^ .T.........~.
- Pick a Theme. Examining the terrain around the designated area, we see that on four sides there are plains, on two sides there are rivers, and on one side each there are mountains and hills. Given also that this site has high access (from the river) and is on hilly terrain, the designer decides to create a large city, which will contain mines, a castle for defense from the denizens of the dungeon '#' (and because, as was written above, Humans usually build their Castles on hills), and a port for trade. We also decide now whether to create a populated town or not: for this example we will not make a population - this is really another topic, and dependant on how your creature system works.
- Now we create the town, terrain first. I will use (to save space here) a quarter-screen sized map, 40x12. You may not wish to use elevation in your RL, but I have added here hills, marked with ':'. These have a few special rules: combat bonuses for creatures on elevated areas when in combat with those on normal ground; improved LOS and missile range. Our terrain generator has created a HillyArea, which has then created a River, some Hills and a few scattered trees.
...............====............=======.. ................======================== . ground ..T................=============...:.=== : hill ......................:::T::......:::... T trees ...T...::.....:.......:::::......::::..: = water ....:::::....::......:T..:T:........:::: .....::....::::...........:.........:::: ...::::...:::.::::.............::....:.: ..........::...::.......:::............: ......::.T......:.......:::.....TT....:: ...........T.............::..........::: .................................:::::::
- The Town. We have the list of Features above, and by now you have likely added to the list some of your own favourites. Now choose the first Feature from the list ( MineShaft ) and add it somewhere sensible (near hills). We can then continue in the fashion described by Mr Swing ( 75% chance of choosing the next item, 25% chance of choosing the previous ), creating a Port and so on.
...............====............=======.. ................======================== a Mine ..T................=#===#=======...:.=== b Port ....................#b::#T::......:::... ...T...::.....:.....#+###::......::::..: ....:::::....::......:T..:T:........:::: .....::....::::...........:.........:::: ...::::...:::.::::.............::....:.: ..........::...::.......:::......##+###: ......::.T......:.......:::.....T#a..>#: ...........T.............::......######: .................................:::::::
After a few more recursions, the town will hav begun to take shape. The map below shows what the town might look like after having created a castle. Note that the castle walls do not fully include the Mine. This was due to the mine being close to the border of the map. Obviously there will be situations such as this, so your code might need a little tweaking. Given the small scale of the map used, I will end the demonstration here, though on a larger map there would be sufficient room for adding the rest of the features on the list. The up staircases on the map below connect with to the second floor (where any guards would be) and the down staircases in the Mine and Keep can connect with Mines and Dungeons respectively. There are enough articles on how to make these last two items: you shouldn't need my help.
Ground Floor
...............====............=======.. ................======================== ..T........#+####..=#===#=======...:.=== a Gatehouses ......####.#a.#.#####.::####......:::... b Towers ...T..#<b####+#....c#+###:<#.....::::..: c City walls ....::#::+...::.........#:b#........:::: d Keep .....:##+#####:.........#+###..######::: ...::::#.#<..+::::g.......+a+..+<+.a#:.: .......#.#>.f#.::.......#+#########+###: e space (on a larger map ......:#.#####.:........#:b#....T#...>#: you would add .......#.......##########:<#.....######: shops, houses, .......#########........####.....::::::: an inn, and such.)
Upstairs
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx x Either unallocated xxxxxxxxxxx######xxx#####xxxxxxxxxxxxxxx tiles or 'air' tiles. xxxxxx######....#####...####xxxxxxxxxxxx xxxxxx#>................/.>#xxxxxxxxxxxx xxxxxx#..################..#xxxxxxxxxxxx xxxxxx########xxxxxxxxxx#..##########xxx xxxxxx#>..#xxxxxxxxxxxxx#.......>...#xxx xxxxxx#...#xxxxxxxxxxxxx#..#######..###x xxxxxx#####xxxxxxxxxxxxx#..#xxxxx#....#x xxxxxxxxxxxxxxxxxxxxxxxx#.>#xxxxx######x xxxxxxxxxxxxxxxxxxxxxxxx####xxxxxxxxxxxx
That's it. After creating your town, you have only the task of giving it some inhabitants of reasonable wit. I hope that I have inspired a little something in some of you. Please feel free to send me comments to me [michaelblackney@hotmail.com].
/-*/
Recursive Level Generation - Radomir 'The Sheep' Dopieralski [sheep@venus.wmid.amu.edu.pl]
Introduction.
This article contains some of my thoughts about level generation in roguelike games. It's inspired with an algorithm used in Alphaman to generate buildings, some articles red on Roguelike News and, that's a little odd, Bison and Yacc input files format. The ideas may seem a little complicated and hard to implement, but I hope the article proves useful in some way.
Overview.
The idea is to describe the level in form similar to BNF (Backus-Naur Form), used usually for describing context-free grammars.
It's natural for humans to describe large and complicated objects in terms of
more simple ones. So we can describe a level.
For example:
a level is either: a maze, a dungeon, a cave, a castle, etc...
a maze is a set of connected corridors and crossroads.
a corridor is a vertical or horizontal line of floor tiles, surrounded
by walls on each side, opened at at least one end.
a crossroad is a single floor tile with walls around, opened in at least two directions.
a dungeon is a set of rooms, crossroads and corridors.
a room is either: a vault, a minor vault, an ordinary room.
etc...
There are some rules not covered here. For example, we'd like to ensure each
place of the level is reachable. It's not very easy to do, so we won't try to
describe any level type, like in the example above. We'll try to only describe
(and then generate) some special level type, constructed by dividing rooms.
Alphaman's buildings.
We will use an algorithm similar to this used in Alphaman. I'll first describe the original algorithm. It is quite simple:
1. Start with a large, empty room.
XXXXXXXXXXXXXXXXX
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
XXXXXXXXXXXXXXXXX
2. Pick an acxis (horizontal or vertical) and a point within the room (far from walls).
Let's suppose we have picked horizontal axis and point marked with '1'.
XXXXXXXXXXXXXXXXX
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X...............X
X......1........X
X...............X
X...............X
X...............X
X...............X
X...............X
XXXXXXXXXXXXXXXXX
3. Make a wall in selected axis, crossing the chosen point, ending at the room's walls and with door in point '1'. XXXXXXXXXXXXXXXXX X...............X X...............X X...............X X...............X X...............X X...............X X...............X X######+########X X...............X X...............X X...............X X...............X X...............X XXXXXXXXXXXXXXXXX
4. You get two new rooms. Repeat the procedure with those of them, that arte large enough. XXXXXXXXXXXXXXXXX X...............X X...............X X###########+###X X...............X X...............X X...............X X...............X X######+########X X.........#.....X X.........+.....X X.........#.....X X.........#.....X X.........#.....X XXXXXXXXXXXXXXXXX
5. You end up with set of interconnected rooms, with exactly one way between every two rooms. Something like a tree.
The procedure is simple, but the result is not very nice. It's always a labirynth of rooms and you usually have to walk a lot to explore it. We'll try to make the result better.
Adding corridors.
We can try to add some corridors, so our level will look more naturally and there will be more connections between rooms. So, instead of adding a wall, we'll add two parallel walls, making a corridor. We also add doorways at the ends of the corridors, so there will be more connections. The algorithm goes like this:
1. Start with a large, empty room. XXXXXXXXXXXXXXXXX X...............X X...............X X...............X X...............X X...............X X...............X X...............X X...............X X...............X X...............X X...............X X...............X X...............X XXXXXXXXXXXXXXXXX
2. Pick an acxis (horizontal or vertical) and a point within the room (far from walls). Let's suppose we have picked horizontal axis and point marked with '1'. XXXXXXXXXXXXXXXXX X...............X X...............X X...............X X...............X X...............X X...............X X...............X X......1........X X...............X X...............X X...............X X...............X X...............X XXXXXXXXXXXXXXXXX
3. Make a corridor in selected axis, crossing the chosen point, ending at the room's walls. If the walls at it's ends are not permanent, make some doorways there. XXXXXXXXXXXXXXXXX X...............X X...............X X...............X X...............X X...............X X...............X X###############X X......1........X X###############X X...............X X...............X X...............X X...............X XXXXXXXXXXXXXXXXX
4. Make some doors along the corridor's walls. There should be at leas one door in each wall, so you make sure all the rooms are connected. XXXXXXXXXXXXXXXXX X...............X X...............X X...............X X...............X X...............X X...............X X####+######+###X X......1........X X###+###########X X...............X X...............X X...............X X...............X XXXXXXXXXXXXXXXXX
5. You get two new rooms. Repeat the procedure with those of them, that are large enough. XXXXXXXXXXXXXXXXX X...............X X###+###########X X...........2...X X#####+#####+###X X...............X X...............X X####+######+###X X......1........X X###+#####.#####X X........#3#....X X........#.+....X X........+.#....X X........#.#....X XXXXXXXXXXXXXXXXX
The result doesn't look so bad, especially if the rooms left at the end are big enough (in the example there isn't much place). But there is another problem -- how to fill the rooms with appropriate contents (that is items and monsters)? How to make sure the rooms are connected with some logic?
Level definitions.
Here's what we can do. We don't just split in two similar rooms. We will have to name these rooms and provide some rules how to split them. For example, for a scientific level in sf roguelike:
a level may: (put some probabilities here) be a scientific level;
a scientific level must: be at least SIZE large, but not larger than SIZE;
a scientific level may: consist of two scientific sections, divided (horizontally or vertically) with a scientific hall;
a scientific hall may: be a very wide corridor, with large doors at each end and at least one door at each side; there may be some plants or statues; there may be some scientific guards; there may be some scientific monsters; tehre may even be some scientific scientifists;
a scientific section may: consist of two scientific sections divided (horizontally or vertically) with a scientific corridor;
a scientific corridor may: be a wide corridor with open doorways at each end and at least one door at each side;
a scientific section must: be at least SIZE large, but not larger than SIZE;
a scientific section may: consist of two scientific labs divided (horizontally or vertically) with a scientific corridor;
a scientific lab must: be at least SIZE large, but not larger than SIZE;
a scientific lab may: consist of two scientific labs divided with a scientific wall;
a scientific wall may: be a wall with door in the middle;
a scientific lab may: be a room with tiled floor; there may be some scientific artifacts; there may be some scientific monsters; there may even be some scientific scientifists;
Building a level.
Now, let's see how to produce a random level from such an information. First, we want to build a level. So we look at the definitions and see that our level may be a scientific level with such-and-such probability. But there may be also other level definitions, so we have to choose (randomly) which level definition to choose. Let's suppose we have chosen the scientific level. We see that it has to be such-and-such big, so we provide an empty starting room of given size. Now we look into the definion and see that we have to split our level in two with a scientific hall and put a scientific section on each side. So we pick a point, pick an axis, put aour corridor in the middle and a scientific section at each side. It would be good to pay attention on the minimal size of each of the sections while picking a point to split the level. Then, we have to make our scientific sections. As we look into definitions, we see that we have two choices. So we pick randomly one of them. We can either split these sections into smaller ones, or into scientific labs. At some points, we'll have to do the second thing, because there will be no place to put a scientific section (which is supposedly larger than a lab). We continue down the tree of level fetures, until we arrive at the 'atom' ones, that is the features that doesn't consist of other features, and taht we can generate using other algorithms. Sometimes there may be need for the algorithm to 'back up' wrong decissions, because there is no way it can get to the atoms. This is because of the size limitations. It's a drawback and I don't know how to make sure it ever completes the level. But I believe it can be solved somehow.
Level representation.
With this algorithm you can use different level representations. The most common, simple two-dimensional array will do. But you can also have a linked list of features, or even a binary tree. If there were no doors at the ends of the corridors, you could even generete only these parts of the level you need at the moment, making all the fetures from the root of the tree to the node you want to know.
-- The Sheep
Finding Explorable Regions - Ross Morgan-Linial [rmorgan@jetcity.com].
This program takes a map and divides it into regions that are fully connected - that is, not split in half by walls, so the player can get anywhere in the region starting from a random point. I wrote it to determine if all of a dungeon level can be reached from the stairs, but you might find other uses for it; for example, you could use the results to find out where corridors need to be added to result in a fully connected level. Without further ado, here it is.
- include <stdio.h>
/*
* This program divides a set of 'grids', which can be either wall or * floor, into connected regions. Every grid in a region is connected * to every other square in that region by vertical or horizontal (not * diagonal) connections, and not connected to grids in any other * region. * * We maintain a map that shows which region each grid is in. To avoid * iterating over the entire map every time we discover two candidate * regions are joined, we use a table that maps the numbers used on * the grid to actual region numbers. At the end of the computation, * we renumber the grid using this table. */
/* Change this to 1 to see how it works */
- define debug 0
- define MAP_WIDTH 12
- define MAP_HEIGHT 12
/*
* Our map - 0 is wall, 1 is floor. * * We have to have a border of walls, or we may get strange errors. */
char grid[MAP_HEIGHT][MAP_WIDTH] = { {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0}, {0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0}, {0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0}, {0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0}, {0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0}, {0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0}, {0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
- define MAX_REGIONS 16
- define NO_REGION 0 /* 0 is also a valid region */
int region_grid[MAP_HEIGHT][MAP_WIDTH]; int region_map[MAX_REGIONS]; int num_regions;
/*
* To reduce processing time, when two regions are found to connect * (they're really the same region), we just mark them as the same * without actually renumbering grids. At the end of the computation, * or if we run out of region numbers, we use this function to update * all grids to true region numbers. It also compacts the region * numbers, so that afterwards all region numbers 0..num_regions-1 * are still used. */
void remap_regions(void) {
int region_index[MAX_REGIONS]; int region_index2[MAX_REGIONS]; int new_regions; int x, y; int i;
new_regions = 0;
/*
* Iterate through the regions, and assign a new number to each
* non-remapped region so that they'll end up compacted.
*/
for (i = 0; i < num_regions; i++)
{
/* Has this region not been mapped to another region? */
if (region_map[i] == i)
{
/* No, it hasn't. Assign it a new region number. */
if (debug)
{
printf("Mapping region: #%i -> #%i\n", i,
new_regions);
}
region_index[i] = new_regions++;
}
else
{
/* It's been renumbered. Check for processing errors. */
if (region_map[region_map[i]] != region_map[i])
{
/*
* We've encountered a bug: this region has been
* mapped to a region that has also been mapped. Give
* an error and abort.
*/
fprintf(stderr, "Map %i->%i->%i\n", i, region_map[i],
region_map[region_map[i]]);
abort();
}
/* Assign an in-bounds but otherwise meaningless value. */
region_index[i] = NO_REGION;
}
}
/*
* Construct a table of the double-indirection through remapping
* and compaction.
*/
for (i = 0; i < num_regions; i++)
region_index2[i] = region_index[region_map[i]];
/* Renumber the grids, using the table we just computed. */
for (y = 0; y < MAP_HEIGHT; y++)
for (x = 0; x < MAP_WIDTH; x++)
region_grid[y][x] = region_index2[region_grid[y][x]];
/* Create a new do-nothing region mapping table. */
for (i = 0; i < new_regions; i++)
region_map[i] = i;
/* Save the new number of regions. */ num_regions = new_regions;
}
/*
* Join two candidate regions together. This just involves updating * the region remapping table. */
void join_regions(int r1, int r2) {
int i; int r1_map, r2_map;
/* We have to operate on primary (unremapped) regions here */ r1_map = region_map[r1]; r2_map = region_map[r2];
if (debug)
{
printf("Joining regions #%i (%i) and #%i (%i)\n", r1, r1_map,
r2, r2_map);
}
/* Modify the region mapping table. */
for (i = 0; i < num_regions; i++)
if (region_map[i] == r2_map)
{
if (debug)
{
printf("Mapping region #%i (%i) -> #%i\n", i,
region_map[i], r1_map);
}
region_map[i] = r1_map;
}
}
/*
* Create a new region. */
int new_region(void) {
int i;
/* If we're out of regions, compact them. */
if (num_regions >= MAX_REGIONS)
{
if (debug)
printf("Remapping regions\n");
remap_regions();
}
/* If we're still out of regions, we have a problem. */
if (num_regions >= MAX_REGIONS)
{
fprintf(stderr, "Too many regions\n");
abort();
}
/* Allocate a new region. */ i = num_regions++; region_map[i] = i;
if (debug)
printf("New region: #%i\n", i);
return i;
}
void find_regions(void) {
int x, y; int i;
if (debug)
printf("Clearing region grid\n");
/* Clear the region grid to a valid (but meaningless) value. */
for (y = 0; y < MAP_HEIGHT; y++)
for (x = 0; x < MAP_WIDTH; x++)
region_grid[y][x] = NO_REGION;
/* Initialize the remapping table to a null map. */
for (i = 0; i < MAX_REGIONS; i++)
region_map[i] = i;
/* Start with no regions. */ num_regions = 0;
/* Consider each grid, except the borders (leave them as walls) */
for (y = 1; y < MAP_HEIGHT - 1; y++)
{
for (x = 1; x < MAP_WIDTH - 1; x++)
{
/* Skip wall grids. */
if (!grid[y][x])
continue;
if (debug)
printf("(%i, %i) ", x, y);
/*
* Consider the possible combinations of left, above
* grids.
*/
if (!grid[y - 1][x])
{
if (!grid[y][x - 1])
{
/* No floor left or above */
region_grid[y][x] = new_region();
}
else
{
/* Floor left, but not above */
if (debug)
{
printf("Copying over #%i\n",
region_grid[y][x - 1]);
}
region_grid[y][x] = region_grid[y][x - 1];
}
}
else
{
if (!grid[y][x - 1])
{
/* Floor above, but not left */
if (debug)
{
printf("Copying down #%i\n",
region_grid[y - 1][x]);
}
region_grid[y][x] = region_grid[y - 1][x];
}
else
{
/*
* Floor both left and above - are they the same
* region?
*/
if (region_map[region_grid[y - 1][x]] !=
region_map[region_grid[y][x - 1]])
{
/* No, join them. */
join_regions(region_grid[y - 1][x],
region_grid[y][x - 1]);
}
/* They're now the same region, so copy one. */
if (debug)
{
printf("Copying down #%i\n",
region_grid[y - 1][x]);
}
region_grid[y][x] = region_grid[y - 1][x];
}
}
}
}
/* Do a final remapping, to make the region_grid[][] accurate. */ remap_regions();
}
/*
* Print our results. */
void print_map(void) {
int x, y;
for (y = 1; y < MAP_HEIGHT - 1; y++)
{
for (x = 1; x < MAP_WIDTH - 1; x++)
{
if (grid[y][x])
{
printf("%c", 'A' + region_grid[y][x]);
}
else
printf(" ");
}
printf("\n");
}
}
int main(void) {
find_regions();
print_map();
return 0;
}
Representing the Dungeon - Brian Bucklew [bbucklew@inteletek.com].
[Note: C++ Class Definitions Will Be Used Throughout]
Section 1 : The Question
One of the most important things in writing a computer game of
any sort is the way in which you represent the universe the game takes place in. In a rogue-like, you will need to represent several things:
- 1. The Dungeon
- 2. The Slimy Things in The Dungeon
- 3. The Pointy Things with which a player kills Slimy Things
- 4. The Player that holds the Pointy Things
This Article will cover #1: The Dungeon.
Section 2 : The Dungeon
Alright, we need to find some way to represent the corridors and
rooms of The Dungeon itself. One of the easiest and most flexible methods of doing this is to create a two-dimensional array of cells. Each cell will be a wall, a floor, a door, a hideous spiked pit of death, or any number of other things we might want to represent as one tile:
class Tile {
public:
int Type; // 0-Wall 1-Floor 2-Water 3-Open Door 4-Closed Door...
unsigned int Flags; // see below...
}
Section 2b : Bit-Flags
One of the more important and space-saving methods of information tracking
is the use of bit-flags. As you know, a number in a computer is represented in binary, which is a series of ones and zeros... For instance the number 14 might be represented as: 00001110
Now, say we need to keep track of a number of things about a tile... Is it lit? Is it explored? Is is permenatly dark? Is it hairy?
We can use each individual bit in an integer to keep track of a true/false answer for questions like these.
So, how do you single out an individual bit? Well, bitwise operators come to save the day.
We can single out individual bits of a number by using the & (bitwise AND) operator. Each bit represents a power of two... So the first bit is 1, the second is 2 the third is 4 the fourth is 8 and so on... The & Operator takes two integers and returns an integer that only has 1 bits where the two origional integers BOTH had 1 bits... So to single out a bit, we take the variable containing the flags (Flags, in this case), and & it with the number represented by the bit we wish to read. If the returned number isn't zero, the flag is set, if it is zero the flag is not set...
This is a bit confusing, I'm sure, so here's some examples:
Example 1: (We'll use 16-bit integers to save space)
Flags : 0101000010010100
We want This Bit-^ It's the fifth bit, so 2^4 = 16. 16 is 0000000000010000... so
Flags & 16 = ?
Flags:0101000010010100
&&&&&&&&&&&&&&&&
16:0000000000010000
================
0000000000010000;
Which is greater than 0, so the flag is set...
Example 2:
Flags : 0101000010010100
We want This Bit--^ It's the fourth bit, so 2^3 = 8. 8 is 0000000000001000... so
Flags & 8 = ?
Flags:0000000010010100
&&&&&&&&&&&&&&&&
8:0000000000001000
================
0000000000000000;
Which is 0, so the flag is not set...
Section 2c : Returning to The Dungeon...
So we have our basic Tile class defined. All we need to do now is create
an array of these tiles:
Tile Map[256][256];
Now, apply your favorite dungeon-generation method to this array of tiles and viola! You have a dungeon.
Section 3 : Positional Representation
Anything in your Dungeon is going to have a position within the
Dungeon. This position is simply defined as an x and y coordinate within the 2D array of Tiles. If a player is at 16,19 we could look up the tile he is in using the line : Map[16][19], If the player is at 31,53 we could use Map[31][53]... So we can generalize and say that if the player had a position holding X and Y we could use the line : Map[Player.X][Player.Y];
We might also want to extend a position definition by giving it a facing...
8 1 2
\ | / \|/
7--*--3
/|\ / | \
6 5 4
So...
class Position {
public:
int X,Y; // Our (X,Y) Coordinates
int Facing; // The direction this object is facing.
}
Everything in your dungeon should have a position. Each Monster,
each item that is lying on the ground, and the player. This will allow you to keep track of each thing and their relations to one-another.
The Author: Brian Bucklew, 18 bbucklew@inteletek.com Current RL Project : Dungeon or "This game needs a new name"... :) Projected Beta Release : Early 98
Fun with dungeongeneration in QBasic - R.Alan Monroe.txt
I wondered what it would be like to do a random dungeon by repeatedly placing random sized "L" shaped hallways, each with a random 90 degree orientation, all over the map. Here's the results.
This method doesn't guarantee that all areas are reachable. You get a lot of cul-de-sacs, which could be good or bad depending on your game...
[fixed width font]
- ####### ######### ####### ########## # ##########
- ### ### ######## ####### ### ###### # ##########
- ######### ### ## ### ### ##### ### ###### # ### ######
- ## ## # ## ## # # ######
- ## # ### # ## ## ### ## # #
- ## # # # # #####
- #### # # # # ### ## ## # # #####
- # # # ## # # ## # # #####
- ## # ## # # # # #### # # # #####
- # ### # # ### ## # ## ##### #######
- ###### # # # # ## # ## ### ######
- ## #### # ##### ###### # #####
- # ############ ##### # ## # # ########### ########### #####
- ############## ########### # ########################## ######
- ########################## ############################ ######
- ########################## ############################ ######
- #################### ################################ #######
- ################ ### ### ############### ########### #######
- ############# ## ### ### ## #### # ##### #### ###### #######
- ######## ### ## ### ### ## ### ### # #### ## ### #######
- ####### # # ###
- # ### # ## ## # # # ## #####
- # # ## # # ## ####
- # #### # # ## # # ## ## # # ####
- # #### # ## # ## ## # # # # ########
- # # ## # ### # # # ########
- #### ## # ## #####
- #### # ##### ### ###
- #### ## # ## #####
- # # ## # ### # # # ########
- ## ##### ### ## #### # #####
- ## ## ###### # ### ## ####### # ### #### # # #####
- ##### # ###### # #### ## ####### # ###### ##### #########
- ####### ################## ####### # ############ #########
- #########################
- #########################
- ##### ####################################
- ##### ############# #####################
- ############### ##### ######### ### # ###################
- ### ###### ## # # # ## ## ### # ### ###############
- # # # ### # # ## ## ######
- # # ## ## ### # ####### ######
- # ### ## ### # ###### ####
- ### ## #### # # ## ## ### #####
- # # ## # ## ## ## # # ## # #####
- ## ## # # ##
- # ### ### ## ## ####
- # ##### ### #### # ###
- ##### ##### #### ### ### # ### ###### ### ###### # ######
- ##### ##### #### ### ### ## #### ###### ########## # ######
- ########### ############ ############## ########### ## #######
- ############ ############## ########### ## #######
- ############ ############## ########### ## #######
RANDOMIZE TIMER
DIM a(70, 20)
begin:
CLEAR CLS
FOR l = 1 TO 150
x = INT(RND * 59) + 6
y = INT(RND * 9) + 6
d = INT(RND * 4)
a(x, y) = 1
SELECT CASE d
CASE 0
FOR i = 1 TO INT(RND * 5)
a(x + i, y) = 1
a(x, y - i) = 1
NEXT i
CASE 1
FOR i = 1 TO INT(RND * 5)
a(x + i, y) = 1
a(x, y + i) = 1
NEXT i
CASE 2
FOR i = 1 TO INT(RND * 5)
a(x - i, y) = 1
a(x, y - i) = 1
NEXT i
CASE 3
FOR i = 1 TO INT(RND * 5)
a(x - i, y) = 1
a(x, y + i) = 1
NEXT i
END SELECT
NEXT l
FOR row = 1 TO 19
FOR col = 1 TO 69
IF a(col, row) = 0 THEN
PRINT "#";
ELSE
PRINT " ";
END IF
NEXT col
PRINT
NEXT row
WHILE INKEY$ = "" WEND
GOTO begin
Populating The Dungeon Of Items & NPC's - Stuart George [entropy@ihug.com.au].
By Stuart George :: [entropy@ihug.com.au] :: 3may99
I have to say up front, I have not looked in depth
(if at all) at how other rogue likes approach this task.
So my methods are probably not as fast or good as ones
tried and tested in code like nethack + angband for the
past N years they have been using it ;)
Quite often one of the first tasks in a rogue like
is creating the mazes... Once you have created
a working maze generation routine you have to fill
it, both with items, traps, monsters, stairs, etc.
Kitting out your dungeon can be as hard or as easy as you like, but a lot of it has to do with how you generated your maze.
I'll discuss here how I've gone about doing it.
First I'll discuss how NOT to do it, I saw this example
only once (in a quite basic "in development" game)...
The dungeon was hewn from a static 128x128 grid
and for placement of objects, a random position of
x=rnd(128), y=rnd(128) was taken for every object
wanting to be placed on the map, this x.y was then
tested against the grid to see if it was a floor tile,
if so was placed, and if not was repeatedly calling for
random numbers for x.y and testing them all over the grid.
Needless to say, with lots of objects and a small dungeon, this could make the computer test locations for days until it got a match...
That is how NOT to do it, basically its a poor mans algorithm. (But as someone pointed out, its easy to do things this way and it does indeed work if you maze fills most of the confines of your 'grid')
When I generate the maze, i store in a list all the
rooms created. Hallways are just "skinny" rooms in my
view, so they all get put on the list.
This list is quite basic, its a linked list and contains the x1.y1-x2.y2 and a flag of every object and nothing else. the flag is just set when its wider or longer than 1 (ie flag is set when its not a "hall"), if you have to refer to the list often its easier to test a flag than to test x2-x1 + y2-y1 for every object..
When I want to add say, stairs up, i just randomly pick an object from my list, then once you have your "room" randomly pick an x.y within that room y=rnd(y2)+y1, x=rnd(x2)+x1 and place the object. repeat as necessary.
You can check for overlapping if you wish or simply stack items in a list.
Since hallways outnumber rooms by a great number, its nice to not always have everything generated in a hallway, thats why the flag is for, so when objects from the list are selected, you can give a greater chance to gen something in a room than in a hallway...
You could also store two lists, one for "rooms" and one for "halls".
My dungeons are created entirely by the RNG, so when i save/load
a level I only need take note of the RNG seed before creation
starts, since the same seed produces the same level, the object
list gets rebuilt and thus you don't have to store that list.
You _do_ have to save the x.y positions of static things, ala traps (moving bear pits?) and stairs. monsters move (for the most part) so if they are not in the same spot, you could say they wandered about ;), and items, well they got picked up and moved and dropped ;). But these are weak excuses for cutting code really... ^_^
When going from 1 level to another you can dump the object list
for the same reasons as the load/save given above.
This is of course, very simple and does not take into account someone with a digging wand adding a new corridor to your dungeon (since its user created, it wont be created with the RNG seed). Of course it would be easy to add the newly created portions to a list, stored with the RNG dungeon seed, etc.
I find this method quite good, its quick and easy to "spawn"
monsters with this method..
The one thing I thought I should mention is the fact that my
"rooms" and "hallways" are not connected. doors are placed
in between as "connections" but they not connected on creation
by "touching" each other, and thus doorways don't show up on my
object list. (good or bad I don't know, but I'm very happy
with my dun-gen routine, it also just means nothing will
be placed over the top of a doorway)
A Method For Growing Rivers In A Randomly Generated World - Dana Larose [dana@pixelenvy.ca].txt
In response to a question on rec.games.roguelike.development, I coded up a demo on how one might make randomized rivers that originate in a part of the world that hasn't been generated yet.
The Problem
You are building a world region by region (as the player explores them), so you do not the the layout of the entire planet in advance. How to create long rivers that can span into regions that haven't be created yet? I'll present here an explanation of how this can be done and provide a demo written in Python.
Summary of Algorithm (Although it's simple enough to almost not qualify as an
algorithm!)
Suppose you generate a 20X20 area of the world that looks like this:
. . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ = water
. . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ . = plains
. . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ # = trees
. . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ^ = hills/mountains
. . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~
^ . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~
^ ^ . . . . . . . . . . . . ~ ~ ~ ~ ~ ~
^ ^ ^ . . . . . . . . . . . . ~ ~ ~ ~ ~
^ ^ ^ ^ . . . . . . . . . . . . ~ ~ ~ ~
^ ^ ^ ^ ^ . . . # # # . . . . . . ~ ~ ~
^ ^ ^ ^ ^ . . # # . . . . . . . . . ~ ~
^ ^ ^ ^ ^ ^ # # # # . . . . . . . . . ~
^ ^ ^ ^ ^ ^ ^ ^ # # # . . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ # # . . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . .
Your world generation algorithm determines this lake/ocean will have a river
flowing into it. Start drawing a river backwards from the ocean. For my
simple demo, I used the following stopping condition for the river: If river
was about to cross from an area of higher elevation to an area of lower
elevation, terminate the loop. Additionally, I started with a 5% chance of
terminating the river and each time the drawing loop iterates, I increase that
by 5%.
One particular run of my demo made the following map:
. . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
. . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
. . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
. . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~
. . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~
^ . . . . . . . . . . ~ . ~ ~ ~ ~ ~ ~ ~
^ ^ . . . . . . . . ~ . . . ~ ~ ~ ~ ~ ~
^ ^ ^ . . . . . . ~ . . . . . ~ ~ ~ ~ ~
^ ^ ^ ^ . . . . ~ . . . . . . . ~ ~ ~ ~
^ ^ ^ ^ ^ . ~ ~ # # # . . . . . . ~ ~ ~
^ ^ ^ ^ ~ ~ . # # . . . . . . . . . ~ ~
^ ~ ~ ~ ^ ^ # # # # . . . . . . . . . ~
~ ^ ^ ^ ^ ^ ^ ^ # # # . . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ # # . . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . .
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . .
If your river reaches the border of a region, again terminate it. (Note that it should also terminate before crossing into region that has already been generated, my demo doesn't do this). At this point, you need to store the fact that a river has terminated at a border of the region. Python is OOP-enabled, so it was quite easy for me to add this information to the region class. I stored the instance of the terrain, it's coordinates and the last move the drawing algorithm was about to make (so I can continue drawing it in the same general direction when it is time to build the next region).
When the player cross into an previously unexplored region, you will have to pass the details of already generated neighbouring regions, providing access to their lists of border features. If a neighbour is null, it hasn't been made yet and can be ignored. In the demo, when a new region is made, we see that it has a neighbour to the east, and that a river terminated at the border (row 12, column 0). After the new region is created, we need to draw a river starting at (row 12, column 19). Using the same algorithm, we draw until we hit a termination condition. In this case, the river started in the hills, so it will continue until it hits a border, or is about to cross from the hills (high elevation) to the plains (lower elevation).
A sample run of my demo produce: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
- # # # # # # # . . . . . . . . . . . .
- . . . . . . . . . . . . . . . . . . .
- # # # # # # ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
- # # . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
- # # # # # # . . . . . ^ ^ ^ ^ ^ ^ ^ ^
- # # # # # . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^
- # # # # # # # ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
- # . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^
- # # # # # # . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
- # # # # # # . . . . . . . ^ ^ ^ ^ ^ ~
- # . . . . . . ^ ^ ^ ^ ^ * ^ ^ ^ ^ * ^
- # # # . . . . . . ^ ^ ^ ^ * ^ ^ * ^ ^
- # # # # # # # . . ^ ^ ^ ^ ^ * * ^ ^ ^
- # . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^
- . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
. . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
(The river created is marked with *'s so they stand out a little better).
Putting them side by side: . . . . . . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
- # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~
- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~
- # # # # # # ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . . ~ . ~ ~ ~ ~ ~ ~ ~
- # # . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . ~ . . . ~ ~ ~ ~ ~ ~
- # # # # # # . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . ~ . . . . . ~ ~ ~ ~ ~
- # # # # # . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . ~ . . . . . . . ~ ~ ~ ~
- # # # # # # # ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . ~ ~ # # # . . . . . . ~ ~ ~
- # . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ~ ~ . # # . . . . . . . . . ~ ~
- # # # # # # . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ~ ~ ~ ^ ^ # # # # . . . . . . . . . ~
- # # # # # # . . . . . . . ^ ^ ^ ^ ^ ~ ~ ^ ^ ^ ^ ^ ^ ^ # # # . . . . . . . . .
- # . . . . . . ^ ^ ^ ^ ^ * ^ ^ ^ ^ * ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ # # . . . . . . . . .
- # # # . . . . . . ^ ^ ^ ^ * ^ ^ * ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . .
- # # # # # # # . . ^ ^ ^ ^ ^ * * ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . .
- # . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . .
- . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . .
. . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . .
A nice, slightly winding river is created in one region, then continued in the bordering region when it comes time to generate the neighbour.
Notes About The Demo
- The demo was slapped together in about an hour, so please don't judge my
coding skills on it! It probably has bugs, invalid assumptions, poor coding
standards/styles, inefficiencies and/or redundant code!
- There are probably plenty of ways to generate nicer looking rivers, I just used a couple of ideas that popped into my head while coding. Mine often generates straight lines, which look silly (it took me a couple tries to get a nice looking river for this page). But again, that wasn't the point of the demo!
- The termination condititions could be improved. For instance, if you are stopping because you are about to cross into another region, you could back the drawing up one square so it doesn't look like the river originates at the border of two elevations.
- It would be neat to look for good likely termination points. Suppose a lake was generated at the same (or higher) elevation as the river, it would make a good candidate for a termination point. (Hmm - confusing terminology - when I speak of termination point, I mean where the algorithm stops drawing, which is the origin point for the river in the geographic sense)
- The demo doesn't generate terrain, I don't know if my roguelike is going to have random or fixed wildernesses, I just wanted to offer a solution to the question on the newsgroup.
- The demo is cooked to draw a river that starts at the lake and ends at the border of the first region (the cooked functions are labeled as such). See previous point.
- My method only draws rivers from the mouth of the river backwards to the spring, but it woulddn't take a great leap to make a version that draws from a spring to a terminatition point. Indeed, since you would be drawing into a region that has not been determined, you could force the generator to create a nice termination point for your river.
- Written and tested in Python 2.2.1, probably works with Python 2.x.x, might even work with Python 1.5.x
There are three main classes used in the demo:
Terrain - Represents an individual square of terrain. Uses fields ch (the character to display), type (the type of terrain and elevation - integer saying how high the terrain is. I used ocean/lake = 0, plains/trees = 1 and hills = 2. An interesting idea would be to store a floating point number and use that to determine where the river should flow from the geography of the land?
Region - stores information about the section of the world this represents. In the demo, this is essentially a collection of Terrain squares and a little additional info used in the demo (such as the border features of this region). In a full game, this would need to store a fair amount of additional information.
RegionGenerator - builds a region of land. Note that in the demo, the regions are cooked and the river in the first region is partially cooked.
The code is offered without warranty or guarantee as an idea for folks writing map generators. If you want to use a substantial part of the code in your game, please ask permission. Here is grow_river.py.txt (named so because browsers sometimes complain about .py extentions, save it your harddrive and rename it grow_river.py before running).
You can reach me at dana@pixelenvy.ca with questions, suggestions, etc.
How to finish your roguelike - Peter Farabaugh [pete@tbe.net]
I've been doing software professionally for 15 years now. Business programming is easy, rogue-likes are HARD! The amount of complexity is staggering, the event model is convoluted, and the interactions between objects are incredibly complex. When you add a GUI to it (as mine does) you add the fun of marrying two incompatable event models. But, business programming is boring, rogue-like programming is FUN! I found that several rules have kept me moving forward:
1. Don't obsess on performance. You can speed the system up better later on when you really understand where the bottlenecks are. Also, if you spend three weeks wresting every millisecond of performance out of LOS code, you will burn out interest in the project.
2. Think big and bold. If you aren't writing a better roguelike than what's out there, then why are you bothering to write it? Also, take advantage of technology that is around today- don't limit yourself to what was available when rogue-likes were invented. My game is Java, with XML data, Swing graphics and I'm thinking about using imbedded ECMAscript for scripting.
3. Separate mechanincs from flavor. Don't think about individual items and monsters much at the beginning. Think about basic mechanics needed to support items and monster. A wand of fire is just a specific example of a charged item with a usable power (a targeted effect with an area of effect of a bolt that produces fire damage). The breath of a fire hound is another instance of the same power, and the extra damage of a fire-bran is the same effect, targeted differently.
4. Don't get hung up on graphics or data. I made a conscious decision not to spend my time on graphics. I am a so-so artist and my best efforts will be mediocre. I limit myself to 10 minutes when building a new icon or set of icons. Mostly I steal them (for now) from David or Adam's tiles. I found I can often change exisiting icons a lot better than I can create new ones. (I will try to put my set of Giant icons unto the web-site, I took David's icon and duped them several times. I modified them for guards, shaman, juveniles and chiefs). As far as the data goes, I detail items and monsters and traps, etc that exercise a mechanic I am implementing; a complete set of objects can wait till the end and wil be easier to implement once all the mechanics are in place. The few items I have, I have had to update six or seven times as I develop mechanics.
5. Don't get stuck. Many parts of the game are hard. If you find your self getting frustrated, step back. Implement something else, do something really easy just to remember that you are still moving forward. I was just stuck for a long time on targeted actions (and how to implement them in an event driven system), so I stopped and implemented rings. When I went back to the targetting I was refreshed and more importantly, my subconscious "tortoise-mind" (see a book entitled "Hare-Brain and Tortoise-Mind", I don't remember the author) had worked out most of my problems.
6. Don't be afraid to rewrite. You will rip out huge sections of code. You will rework entire mechanics. Embrace it. It's progress; a bad mechanic or implementation is not going to fix itself. The longer you try to work around it the harder it will be to fix later. But use safe coding, kids. Always use a source code control system.
7. Remember it's should be fun, if it isn't walk away for a while- go fishing, take a hike, play Diablo, get laid. Then come back.