Creating Inventories - Erno Tuomainen [ernomat@evitech.fi].

----------------------------------------------------------------------------
           CREATING INVENTORIES - WHAT TOOLS ARE AVAILABLE
                       (C) 1997 Erno Tuomainen
                          ernomat@evitech.fi
                        16th of November 1997
----------------------------------------------------------------------------

I know that many of you wonder about this problem. Atleast I did so when starting my Roguelike project (Legend of Saladir). In this article I intend to give you some tools for making those inventories, it's not intended to be a complete tutorial for making player inventories, maybe later I can offer you some more routines/ideas related to this subject.

I assume that the reader of this article is not a total beginner (hey, you are starting to make your own game! :) and has a basic knowledge of C-language along with knowledge of pointers. And please, forgive me my bad english!

Without any more hassle, lets begin defining a basic item structure for all examples in this article. This is just an example, the item defined is not really useful in real development :)

  typedef struct ITEMTYPE
  {
     int itemtype;
     int weight;
     unsigned int attributes;
  } Titem;

So this is just a data structure which contains all the information needed for a particular item. Every item in the game has a similar (exactly!) structure.

There are basically two methods of creating the inventory list for player/monster.

1. Fixed size array

You allocate an array of for example 100 items. Obviously this has one big disadvantage, you can't carry more than 100 items if the programmer doesn't change the code and secondly this array always takes 100*sizeof(Titem) bytes of memory even if you were carrying just one item.

Player-information structure would look like this:

  typedef struct PLAYERTYPE
  {
     char name[100];   /* normal player information fields */
     int age;

     Titem inv[100];   /* inventory array containing 100 items (See Titem definition) */
  } Player;

So this is a structure which keeps all information about our player. You will have similar structures for your monsters/NPC's too, they might be a bit different but you can use the same methods for your monsters too.

So the size is constant. The good point is that additions and deletions to this list are easy, you can index it directly. However, you can't easily insert/delete items to/from the middle of the list. It requires rebuilding the array from the point where you are inserting. This is slow.

Another good point is that when you are going to save this structure, you just store this whole block into the file.

This kind of approach has it's own good uses, but I have a better method for the purpose we are talking about.

2. Dynamic memory allocation with linked lists

So what is this? Ok, you can guess from the name. Each time you need a new item added to the inventory you allocate space for it and link it to the inventory you already have for your player/monster.

This is a bit more complicated but it's not too hard when you go and think about it! When adding to the middle of the list, all you need to do is to go to the right place and move some pointers.

Now, keeping the above player structure mostly the same, but modifying only the inventory part we will get:

  typedef struct PLAYERTYPE
  {
     char name[100];   /* normal player information fields */
     int age;

     InvList *inv;  /* pointer to the start of inventory list */
  } Player;

What is the third field "InvList *" in the structure, I hear you ask.

"InvList" is also a structure, it defines ONE node for the inventory list. Node is one segment of the dynamic linked list. Look at this picture:

  +-------+      +-------+--+
  | start |----->| node 1| >---\    +-------+------+
  +-------+      +-------+--+   \-->| node 2| NULL |
                                    +-------+------+

This example resembles a linked list with TWO nodes, the first block named 'start' contains a pointer to the node 1, telling that the first node of the list is there. And again, you see that in 'node 1' there is a extra field which contains a pointer to the NEXT node or 0 (NULL) if the list ends there.

So the above "Player" structure contains just a POINTER to the players inventory list. It's a memory address holding the first node of the list if any (or NULL if inventory is empty!)

At this point, compare this method to the array method I showed you earlier. If items are stored in array they will be stored in sequential order in memory ( 1-2-3-4-5-6-..) as one big block next to each other. In the case of linked lists, the list consists of nodes, which can be all around in the memory, the order of the list is preserved with the pointers linking each node to another. This list is called as "one way linked-list" or "single linked list" meaning that you can traverse only to one direction along the list. There is also a list which contains a "previous" and "next" link. This is a "dual linked" or "two way linked" list. But I won't speak about it this time.

Now we have structures for the ITEM and the PLAYER. We must define the structure for InvList defining a one node of the list.

  typedef struct node
  {
     Titem item;
     struct node *next;
  } InvList;

  or like this:

  /* define a pointer to the list node */
  /* so we can use "Ipointer" instead of "struct node *" */
  typedef struct node *Ipointer;

  typedef struct node
  {
     Titem item;
     Ipointer next;
  } InvList;

I will use the first method.

The first field in the struct is the actual item stored in this node, and the "next" field contains an address to the NEXT node if there is such a node. (NULL telling that list is terminated here)

So basically this is a very simple idea, it requires a bit more work to maintain this kind of inventory, but it offers some advantage which are really good for Roguelike games. You can use this kind of list in many places. For example, I use it in these situations:

  List of monsters in the level
  List of items in the level
  List of items carried by the player
  List of items carried by monsters

So in my game, only limitation in the above situations is the amount of memory available. There can be for example 1000 items in a level.

This practise can be used in MANY other situations, in other programs too. It's all depends in your imagination and how you can make this thing useful in certain situations.

I must point however that this "linked list" method will make you some problems later on. Think about savegames. You must create a routine which saves each node from the list and when loading you must build the list again. Not a big deal, but it brings you again a bit more work to do :)

Now that we have the idea coverered, let's start writing some code for the list.

----------------------------------------------------------------------------
              WHAT FUNCTIONS DOES THIS KIND OF LIST NEED
----------------------------------------------------------------------------

First off, you need to initialize this list, you'll need node addition, node deletion and the routine for deleting the whole list. Let's create the actual code for these functions.

1) Initialization of the list

  void initialize_list(Player *player)
  {
     player->inv=NULL;
  }

This routine takes a pointer to the player structure and initializes the list pointer to NULL, telling that list does not exists yet. (so player has no items in inventory!)

Please note that you should not call this routine if you have items stored in the list. You will destroy the pointer to your list, thus you will have allocated memory which can't be freed because you lost the pointer.

2) Node addition

This routine adds a node to the list. I use the method where the last added node will be put to the BEGINNING of the list (thus to the field Player->inv) and this new node will point to the to the previous value of Player->inv. Like this:

  int add_node(Player *player, Titem newitem)
  {
     InvList *newnode;
     /* allocate memory for the new node */
     newnode=(InvList *)malloc(sizeof(InvList));

     /* if newnode == 0 then the memory is out or something is messed up */
     if(!newnode)
        return 0;

     /* now place the new data item to the item-field in space we allocated */
     /* remember, "newnode->item" is similar to "newitem", both are defined */
     /* by "Titem" */
     newnode->item=newitem;

     /* if player inventory does not yet exists */
     if(player->inv==NULL) {
        newnode->next=0;
        player->inv=newnode;
     }
     else {
        /* point the "next" field of "newnode" to the old player->inv */
        newnode->next=player->inv;
        /* point the player->inv field to the node we just created */
        player->inv=newnode;
     }
     return 1;
  }

The function returns 0 if the addition failed, otherwise 1.

3) Node deletion

This routine really depends on the fact how you want to delete the item from the list. I will create a routine which removes item with an index. For example, you might want to delete the fifth item from the list.

Here is an example, it's not the optimal routine, should be easy to understand

int delete_node(Player *player, int index) {

  InvList *node, *tmp;
  int count;

  /* again check first if the inventory exists */
  if(!player->inv)
     return 0;

  node=player->inv;

  /* if you are trying to delete the first node */
  if(index==0) {
     player->inv=node->next;
     free(node);

     /* we are done so return with success */
     return 1;
  }

  count=0;
  while(node) {
     /* remember the previous node */
     tmp=node;
     node=node->next;

     /* increase the item count in list */
     count++;
     if(count==index) break;
  }

  /* if trying to delete item over list boundaries */
  if(monesko>count) return 0;

  tmp->next=node->next;
  free(node);
  return 1;

}

4) Freeing the whole list at once

Here is a useful routine for freeing the whole list at once. Notice how I traverse on the list.

  void free_list(Player *player)
  {
     InvList *tmp, *freethis;

     /* put the start of inventory to temporary variable */
     tmp=player->inv;

     /* do until we reach NULL */
     while(tmp) {
        freethis=tmp;

        /* assign "tmp" with the next node, if there isn't a next node
           "tmp" will contain NULL */
        tmp=tmp->next;
        /* free the current node */
        free(freethis);
     }
     player->inv=NULL;
  }

The similar approach can be used for example when displaying the contents of the list.

----------------------------------------------------------------------------
                           SOMETHING EXTRA
----------------------------------------------------------------------------

Linked list is just one of the advanced data types (often called as Abstract Data Types, ADT), there are many other types of ADTs which can be useful in game programming. For example, Queue and Stack. Each of them have many uses, and again many ways to implement them. Some explanations.

Stack

Stack is a special case of a list. New items inserted to the stack will always go to the end of the list and when you take something out it will be taken from the end. So this type of list is called LAST IN FIRST OUT (LIFO). Stack has many uses.

  +-+----+
  |3|data| top/end of the stack (last added item)
  +-+----+
  |2|data|
  +-+----+
  |1|data|
  +-+----+
  |0|data| start of the stack
  +-+----+

So items will "pile up" in the stack. You'll get the most recent item when you get something from the stack.

One example from computer world. We want to check if a string is a palindrome: (string read forwards equals string read backwards)

  create 3 empty character stacks

  state1:
  for each_char_in_string do
     put_into_stack1(current char from string)
     put_into_stack2(current char from string)
     count=count+1
  end_do

  state2:
  while stack_2_has_something do
     put_into_stack3(take_from_stack2())
  end_do

  state3:
  while stack_1_has_something do
     if take_from_stack1() equals take_from_stack3()
        palindrome=true,
     else
        palindrome=false
  end do

for example for word "automatic" it would go like this:

  after state1
  stack 1 contains: automatic
  stack 2 contains: automatic
  after state2
  stack 1 contains: automatic
  stack 3 contains: citamotua
  in state3 we take from both stacks and compare them:
  ? a==c ?
  ? u==i ?
  and so on...

Queue

Again, queue is a special case of a list. Items placed into the queue will go to the end and items taken from the queue will be taken from the start.

      first                              last
     +------+------+------+------+------+------+         +------+
  <--| data | data | data | data | data | data | <-- add | new  |
     +------+------+------+------+------+------+         +------+

Good example taken from the Real Life(tm) could be a BANK QUEUE. You come to the bank and the desk you go has a long long and long queue (it's friday and the bank is going to close soon :), you will have to go to the end of the queue. When the bank clerk can, he/she takes a next customer from the first position of the queue.

The end?

This ends this part of the lesson. I've tried to provide you a method for creating dynamic inventories along with some knowledge of other advanced data types. It's up to you to decide how you make use of them.

I thank you for reading this, and apologise for any errors in C-examples I provided, there might be some since this text was written on a fly without any aid of C-compiler :)

If you have any questions, ideas for my game, or want to report a bug in my examples, please feel free to contact me via email.

  ernomat@evitech.fi

Also go see the homepage of my Roguelike project:

  The Legend of Saladir
  http://www.evitech.fi/~ernomat/saladir/main.html

This text is written specially for Darren Hebden's Roguelike News developers section. Visit Darren's great pages at

       "http://www2.krisalis.co.uk/wwwdheb/index.html"

----------------------------------------------------------------------------
(C) 1997 by Erno Tuomainen                      Sunday 16th of November 1997
----------------------------------------------------------------------------
            Do not modify or publish without my approval.

Equipment Wear and Tear - Michael Heinich [mheinich@yahoo.com].

 Every piece of equipment should have a durability. One example of this

system is demonstrated in a popular series of commercial hack and slash games with some Rogue-Like tendencies. Another example can be found in ADOM. Both of these implementations could be improved upon.

 In the commercial games, durability played a very important if limited role.

If an item's durability reached 0, it was broke beyond repair. This was normally kept as a ratio of current:maximum durability. The game allowed a character class a repair skill to partially repair an item. The drawback was that the maximum durability was reduced. Or a member of the town was able to provide this service. Found items had a lower then maximum durability and equipment that was used, lost durability during the course of weilding or wearing them. Durability also effected the value of the item in question. An item in great shape was worth more then the same item in bad repair. While the measurement system was easy to understand and to manage, it could still be improved upon.

 One area is in the item's use. The equipement was either broke or not. A

better method would be to reduce the effectivness of the item in question. Using a sword for example, as it becomes worn out, the sword may cause less damage because it has become dull with use. Or the sword may have an ever increasing change where it may break during an attack as it's durability decreases. An armor example would be that the protection a chain mail shirt provides may be reduced as it's durability worsens.

 ADOM does take some of these factors into consideration, but it can be

confusing to figure out the multitude of stats offered (some would say that this is one of it's strengths)and it lacks adequate skills or town services for the repairing of items. Usually it is usually better to replace an item then to repair it.

Here are some more ideas thrown out more or less at random that build on this concept. The use of durability can also open other possibilities for object descriptives and use. For example, a sword that is undamaged and is like brand new may have a desciption before identification of Shiny and Sharp, as the sword becomes used, the description may change to dull and nicked. Durability provides an interesting twist to potions or items made of glass. Potions may be in delicate containers. In Angband, potions sometimes break when they are subject to heat or cold attacks. But what if a potion is dropped or thrown. They should spill, spreading their contents over the floor, wall or monster. This could cause interesting effects if the Potion was healing or Acid. A Crystal Ball may not last too long under a heavy attack by giants or earth hounds. Just how sturdy is a Lantern full of Oil anyway? Why hasn't one of these broke after an attack, spilling flaming oil all over the user. Or throwing the lantern, to have it's flaming contents spill over the monster. This is much preffered to the Flask of Oil attack in Angband. Since it assumes that you have lit the Flask first somehow.

The code to add statistics for wear and tear should not be to hard to add to your Roguelike. Specially if you are using an Object Oriented programming language. You can just add an extra two lines to the Class for starters.

int CurrentWear, NoWear; // Measure how much wear and tear int Durability; // How durable is this item

In your object definition for a sword you would add the value for NoWear an the value for Durability. During the Object creation you would assign the value of NoWear to CurrentWear.

CurrentWear = NoWear; // set CurrentWear value to NoWear

Then when ever the item is used or after a certin number of uses, you would subtract from the value.

if (NumOfUses == 10) { CurrentWear--; if (possiblebreak(Sword.CurrentWear)) Sword.Status = BROKE; NumOfUses=0; }

I hope these meanderings showed you a new diminsion for your Game. The code examples were way oversimplified but will hopefully point you in the right direction.

Happy Coding!

Fractal Landscapes - Mike Anderson [mike@mikera.net].

30th October 1999

There's something special about fractals. Maybe it's the way that infinitely complex shapes appear out of the simplest mathematical formulae.....

Certainly beautiful, but why would you want to use them in your game? The answer, quite simply, is that they are perfect for generating realistic-looking landscapes. For example, real coastlines frequently exhibit fractal-like properties and fractal heightfields are often a good first approximation to the contours of mountainous terrain.

Here I'm going to present a basic fractal algorithm that was originally designed for generating random islands, seas and coastlines. With a few minor alterations, it could easily be adapted to producing all kinds of natural landscape patterns. My algorithm is vaguely based on the familiar "plasma" type of fractal heightfield, but modified to work with tiled maps.

I've included the source for a simple Java coastline generator applet at the end of this article. If you are impatient and want to see the thing working right away, just go to:

 http://www.mikera.net/code/coastline.html

The Fractal Algorithm

=========

One of the distinctive properties of fractal images is self-similarity. That is, a zoomed in version will look similar to the whole image. This algorithm achieves this effect by starting with a coarse map, and then enhancing it by applying increasing levels of random detail.

Let's say that you are considering a square area of your map with the corners labelled a, b, c and d :

a * b

* *

c * d

Each map square can have a different colour. I used green for land and blue for sea in the example applet.

The algorithm will then determine the map colours for the intermediate points marked "*". It does this by randomly choosing a colour from one of the adjacent corner squares. The "*" in the centre could take the colour of either a, b, c or d.

Thus a possible final result might be:

a a b

c b d

c c d

We have now defined smaller squares on the map. The algorithm can then be applied iteratively on a smaller scale. This process continues until the desired level of detail is achieved.

a*a*b

c*b*d

c*c*d

Note that for convenience, it is helpful to have a map size that is a power of two so that it can be repeatedly subdivided.

Example

=

Below shows the iterations for a 16*16 grid.

For viewing convenience, the larger tiles have been completely filled with the colour from the top-left corner, though this is not needed for the algorithm to work.

In addition, the map is considered to be toroidal, i.e. the points on the left edge are considered to be adjacent to those on the right edge, and similarly for top and bottom.

Step 1: a-------b#######

########

c#######d-------

1. 1. 1. 1. --------
        
        --------
        
        --------
        
        --------
        
        --------
        
        --------
        
        --------

(a, b, c and d mark the points that are coloured at the start. This can be done randomly, or they can be pre-set to create land masses)

Step 2:

########

1. 1. 1. 1. ----####
        
        ----####
        
        ----####
        
        ----####

####--------

1. 1. 1. 1. ----
        
        ----
        
        ----
        
        ----

Step 3:

########--

--##----######## --##----########

1. 1. 1. 1. ----####
        
        ----####
        
        --------##
        
        --------##

####--------

##----------

1. 1. 1. 1. ------
        
        ------
2. --########----
3. --########----

Step 4:

########---

########--

-##-----######## --##----#--#####

1. 1. 1. 1. ----####
        
        -----###
        
        --------##
-####--------#-

####--------

---####--------- ---###---------- -#--#--#--------

1. 1. 1. 1. -----#
        
        -#-----
2. -#########----
----######-----

Et voila - one random continent ready to be populated with thriving cities, dangerous mountain ranges and deep forests.

The Code

==

Here's a quick Java implementation of the fractal coastline algorithm. It generates a new landscape each time the applet is repainted.

The makeFractal(step) method does all the actual work. This method calls itself to handle finer detail levels.

=== CoastApp.java ====

package kult.quest;

import java.awt.*; import java.applet.*; import java.awt.event.*;

public class CoastApp extends Applet {

 // map size: must be a power of 2
 public static final int size=128;

 // allocate map storage
 public int[] map= new int[size*size];

 public void paint(Graphics g) {
   super.paint(g);

   // initial pattern (0=sea, 1=land)
   setCell(0,0,0);
   setCell(size/2,0,0);
   setCell(0,size/2,0);
   setCell(size/2,size/2,1);

   makeFractal(size/4);

   // draw the map
   for (int y=0; y<size; y++) for (int x=0; x<size; x++) {
     g.setColor( (getCell(x,y)==0) ? Color.blue : Color.green );
     g.fillRect(x*2,y*2,2,2);
   }
 }

 public void setCell(int x, int y, int c) {
   map[x+size*y]=c;
 }

 public int getCell(int x, int y) {
   return map[x+size*y];
 }

 // this routine builds the landscape....
 //   step = detail square width
 public void makeFractal(int step) {
 for (int y=0; y<size; y+=step) {
   for (int x=0; x<size; x+=step) {
     // The inner loop calculates (cx,cy)
     // this is the point from which to copy map colour

     // add random offsets
     int cx=x+ ((Math.random()<0.5) ? 0 : step);
     int cy=y+ ((Math.random()<0.5) ? 0 : step);

     // truncate to nearest multiple of step*2
     // since step*2 is the previous detail level calculated
     cx=(cx/(step*2))*step*2;
     cy=(cy/(step*2))*step*2;

     // wrap around to reference world as torus
     // also guarantees getCell() and setCell() are within bounds
     cx=cx%size;
     cy=cy%size;

     // copy from (cx,cy) to (x,y)
     setCell(x,y,getCell(cx,cy));
   }
 }

   // recursively calculate finer detail levels
   if (step>1) makeFractal(step/2);
 }

 // applet initialisation
 public void init() {
   super.init();

   // repaint on mouse clicks
   addMouseListener(new MouseAdapter()
     public void mouseClicked( MouseEvent e ) {
       repaint();
     }
   });
 }

 // main function allows applet to run as an application
 public static void main(String[] args) {

   // create a frame
   Frame f = new Frame("Fractal Coastlines");
   f.addWindowListener(new WindowAdapter() {
     public void windowClosing(WindowEvent e) {
       System.exit(0);
     }
   });

   // set up frame and add applet
   f.setSize(300,300);
   f.setLayout(new BorderLayout());
   CoastApp q=new CoastApp();
   q.init();
   f.add(q);

   // go live....
   f.show();
 }

}

Conclusion

==

Well, I hope I've given you a quick way to get some good-looking fractal landscapes. It is easy to extend this by adding different land types (forests, deserts etc). You could also enhance the method to include a height map by taking averages of adjacent points and adding random offsets.

In fact, I've implemented a fractal algorithm to generate the World Maps for Tyrant, my very own roguelike. You can see it in action at:

 http://www.mikera.net/tyrant/

This uses essentially the same method as the one described above, except that it uses a little bit of coding magic to make the landscapes look more realistic and textured. While it's still far from perfect, it does at least show there's scope for a lot of imaginative use of this technique.

Happy Coding.

Mike.

Any questions or comments:

 mike@mikera.net

Terrain Generator - Mixi Lauronen [mplauron@paju.oulu.fi].txt

I have experimented with the following algorithm:

1) Decide the range of land height values (I think 0-255 is conveninent)

2) Initialize the land area with a value of 0. (Arbitrarily, you can initialize it with the average of the height minimum and maximum)

3) Randomly set a rectangle of random size with a random value of (0-255) on the map, adding the value to every coordinate inside the rectangle's area. Arbitrarily the value can be anything between (-x to x). If the result is less than the minimum height or more than maximum height, readjust the value.

4) Repeat as many times as needed.

5) Apply a smoothing routine to every coordinate, thus simulating the effect of erosion. I use a simple method of setting the value of a land block to the average of (block+southern block+northern block+eastern block+western block).

6) Set the water level. Anything under that will be water.

Haven't implemented a river algorithm yet. Otherwise it seems to work fine, although it is a little bit slow (especially the smoothing routine). Of course the building blocks could be circles, ovals or single pixels, too.

Metaballs Dungeon.txt

The Metaballs Dungeon

The idea of the metaballs dungeon is to generate two dimensional meatballs to construct a cave-like dungeon that looks natural and rough but still constructed by... goblin hands! If anyone here has ever worked with a 3d raytracer you may know what i am talking about. Basically the idea is that in many 3-D raytracing applications you can place these metaballs in your scene. Each meta ball has x,y,z coordinate variables and a t--threshhold. If you have one metaball then the edge of the ball is mearly a distance away from the center equal to the threshhold. In case you havent already guessed this, we are thinking about doing this in 2d (x,y,t). So lets look at how that would look.

                       ####
                      #....#
                     #......#
                     #......#
                     #......#
                      #....#
                       ####
        (a better looking circle then above)

Now this is because we only have one ball. If we place another right next too the first, then in our 2-D scenerio we will say that for every square we look to see if there is a ball or are balls nearby. Nearby is defigned like this

If the square in question's distance to a ball's center is less then the ball's threshhold then that ball is "nearby".

Now if we have a vector of balls (x,y,t) that have contructed (I will explain later) then we want to find out what our betaballs dungeon looks like. We would do the following.

(slow version, could be optimized!! a lot!) For every square on our grid, we compile a list of the "nearby" balls. We then add the threshhold of every nearby ball to a temporary integer and then subtract the distance to every ball from this integer. If this number is positive then we have a floor tile. if not we have a wall tile. Its that simple. This algorthim could be optimized and the math is probably a little off. There are algorithms you can find through a google search that will probably be better/faster and offer you much more control. My simple example does work and has been tested on QBasic. I will probably implement this for some levels in my upcomming game CHAZM!

A sample might look like this. A nice smooth melted merge between balls. You could also experiment with using ellipes and rounded rectangles. There are algorithms for those out their too.

                     ################
                     #########....###
                     ##....##......##
                     #.............##
                     #.............##
                     #......##.....##
                     ##....####...###
                     ################
          (This was handdrawn as a representation only...)

If you cant visualize what this would look like with many rooms/balls then take a look here:

http://foresightsagas.com/software/chazm/metaballs_cave_example.htm

Laying out the Rooms

You could lay out the rooms in any way you want but personally i would advocate for a recursive flow.

call branch 2-4 times on randome angles at the center...

void branch(x,y,a){

 do{
   a += randombetweenr(-.2 radians, +.2radiant);
   step x and y forward 8-12 squares forward in the direction of angle

a

   then add room at location
   if (randombetween(0,6) == 2) branch(x,y,a);
   if (randombetween(0,6) == 3) return;
 }

}

thus you get a branching and twisting maze of caverns that go out quite far. You could also add other end conditions like hitting the edge of the screen or getting a cirtain distance from the original center.... If you have any questions you can ask me about this recursion.

I think this would work out great as a caves level. Any thoughts or questions: email me at comments (AT) foresightsagas .com

Thanks. And have fun making your RL.

By Thomas Gilray foresightsagas.com

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

/-*/

User:Duerig/Archive3

Contents

Creating Inventories - Erno Tuomainen [ernomat@evitech.fi].

Equipment Wear and Tear - Michael Heinich [mheinich@yahoo.com].

Fractal Landscapes - Mike Anderson [mike@mikera.net].

=========

=

==

=== CoastApp.java ====

==

Terrain Generator - Mixi Lauronen [mplauron@paju.oulu.fi].txt

Metaballs Dungeon.txt

More Continuous Content - Joseph Swing [JSwing@wport.com].

Creating A Dungeon - Brian Bucklew [bbucklew@inteletek.com].

The Building of Towns - Michael Blackney [michaelblackney@hotmail.com].

Navigation menu

Search