User:Duerig/Archive9

Random Dungeon Algo in QBasic - Andrew Collins [andrewcollins@hotmail.com].txt

DEFINT A-Z' speeds things up
DECLARE SUB initdungeon () 'blanks out dungeon array
DECLARE SUB displaydungeon () 'draws dungeon to the screen
DECLARE SUB generate (recurdepth) 'main generation function

'checks bounds for halls and rooms
DECLARE FUNCTION CheckBounds (x1, x2, y1, y2, direction)
DECLARE FUNCTION CheckBoundsHall (x1, x2, y1, y2, direction)

'makes the halls and rooms
DECLARE SUB makehall (x1, x2, y1, y2, direction)
DECLARE SUB makeroom (x1, x2, y1, y2, direction, recurdepth)

'random number between lowest and highest
DECLARE FUNCTION Rand (Lowest, Highest)



'map array
DIM SHARED DungeonLayer(150, 150) AS INTEGER

'what this does is makes a list of rooms that were created.
'then if the generator hits a dead end it goes back to a random room
'in the list and takes up generation from there.
DIM SHARED RoomHolder(200, 4) AS INTEGER

'max numbers of maps
DIM SHARED maxx 'MaxX coord of Dungeon
DIM SHARED maxy 'MaxY of Dungeon
DIM recurdepth AS INTEGER

'map and engine constants
DIM SHARED wall AS INTEGER
DIM SHARED floor AS INTEGER
DIM SHARED door AS INTEGER
DIM SHARED true AS INTEGER
DIM SHARED false AS INTEGER
DIM SHARED Permwall AS INTEGER
DIM SHARED numofrooms AS INTEGER
DIM SHARED maxnumofrooms AS INTEGER

'these are the ascii numbers (like angband for the door and walls)
door = 43
Permwall = 178
wall = 176
floor = 46

true = 1
false = -1

recurdepth = 0
numofrooms = 0

DIM x1 AS INTEGER' top right coordinates
DIM y1 AS INTEGER' top left coordinates
DIM x2 AS INTEGER' bottom right coordinates
DIM y2 AS INTEGER' bottom left coordinates
DIM direction AS INTEGER






'these tie into the DungeonLayer array so the size will have to be
'increased there to increase these numbers
maxx = 150
maxy = 150

' maxnumofrooms is tied into RoomHolder
' at 200 it bogs down and fails a lot try setting to 200 you'll see

maxnumofrooms = 150

RANDOMIZE TIMER

DO
'this times the generation
T! = TIMER
initdungeon
generate (recurdepth)
T2! = TIMER
T3! = T2! - T!

displaydungeon' I'm not adding this into the timer
'seeing as it only displays the dungeon
LOCATE 1, 21: COLOR 4: PRINT "Door color"
LOCATE 2, 21: COLOR 8: PRINT "Wall color "
LOCATE 3, 21: COLOR 15: PRINT "PermaWall color"
LOCATE 6, 21: COLOR 15: PRINT "# of Rooms"; numofrooms
LOCATE 9, 21: PRINT "One pixel ="
LOCATE 10, 23: PRINT "one ascii tile"
LOCATE 21, 1: PRINT "Time to make "; T3!; " Seconds."
LOCATE 22, 1: PRINT "Press esc to quit"
LOCATE 23, 1: PRINT "Any other key to generate again"
SLEEP
LOOP UNTIL INKEY$ = CHR$(27)
END


FUNCTION CheckBounds (x1, x2, y1, y2, direction)
CheckBounds = 0
'Makes sure room isn't out of bounds of Dungeon
'Our dungeon is 1 to MaxX and 1 to MaxY

        IF (x1 - 1) < 1 THEN CheckBounds = false: EXIT FUNCTION
        IF (y1 - 1) < 1 THEN CheckBounds = false: EXIT FUNCTION
        IF (x2 + 1) > maxx THEN CheckBounds = false: EXIT FUNCTION
        IF (y2 + 1) > maxy THEN CheckBounds = false: EXIT FUNCTION

FOR x = (x1 - 1) TO (x2 + 1)
 FOR y = (y1 - 1) TO (y2 + 1)
  IF DungeonLayer(x, y) = floor THEN CheckBounds = false: EXIT FUNCTION
 NEXT y
NEXT x
CheckBounds = true
END FUNCTION

FUNCTION CheckBoundsHall (x1, x2, y1, y2, direction)
CheckBoundsHall = 0
'Makes sure hall isn't out of bounds of Dungeon
'Our dungeon is 1 to MaxX and 1 to MaxY
       
        IF (x1 - 1) < 1 THEN CheckBoundsHall = false: EXIT FUNCTION
        IF (y1 - 1) < 1 THEN CheckBoundsHall = false: EXIT FUNCTION
        IF (x2 + 1) > maxx THEN CheckBoundsHall = false: EXIT FUNCTION
        IF (y2 + 1) > maxy THEN CheckBoundsHall = false: EXIT FUNCTION

IF direction = 0 OR direction = 2 THEN
FOR x = x1 TO x2
 FOR y = (y1 - 1) TO (y2 + 1)
  IF DungeonLayer(x, y) = floor THEN CheckBoundsHall = false: EXIT FUNCTION
 NEXT y
NEXT x
END IF


IF direction = 1 OR direction = 3 THEN
FOR x = (x1 - 1) TO (x2 + 1)
 FOR y = y1 TO y2
  IF DungeonLayer(x, y) = floor THEN CheckBoundsHall = false: EXIT FUNCTION
 NEXT y
NEXT x
END IF

CheckBoundsHall = true
END FUNCTION

SUB displaydungeon
'this just draws the dungeon    
        CLS
SCREEN 13
        FOR x = 1 TO maxx
         FOR y = 1 TO maxy
IF DungeonLayer(x, y) = wall THEN PSET (x, y), 8
IF DungeonLayer(x, y) = Permwall THEN PSET (x, y), 15
IF DungeonLayer(x, y) = door THEN PSET (x, y), 4
IF DungeonLayer(x, y) = floor THEN PSET (x, y), 0
         NEXT y
        NEXT x
END SUB

SUB generate (recurdepth)

'start with a random room
        x1 = Rand(2, (maxx - 1))
        y1 = Rand(2, (maxy - 1))
        x2 = x1 + Rand(2, 4)
        y2 = y1 + Rand(3, 7)



        direction = Rand(0, 3)
        IF CheckBounds(x1, x2, y1, y2, direction) = true THEN
         CALL makeroom(x1, x2, y1, y2, direction, recurdepth)
        END IF


room = true

DO
'these are all to make sure we dont get into an infinite loop
hallcount = 0
hallcountmultp = 0
roomcount = 0
roomcountmultp = 0
'ite mean iterations


DO
ite = ite + 1
direction = Rand(0, 3)'the direction we want to draw towards
'0 north(up) : 1 east(right) : 2 south(down) : 3 west(left)

hall = false
hallcount = hallcount + 1

halllength = Rand(2, 7)'min and max length of halls
        
'for all hall generation they are basically the same
IF direction = 0 THEN
'halls are only 1 square wide    
        dy1 = Rand(y1, y2)
        dy2 = dy1
'and as long as our halllength variable      
        dx2 = x1 - 2
        dx1 = dx2 - halllength
' we check to see if it's in bounds       
        IF CheckBoundsHall(dx1, dx2, dy1, dy2, direction) = true THEN
' if it is we actually put it there       
         CALL makehall(dx1, dx2, dy1, dy2, direction)
' draw a door if it hits a room (this can be change to randomly place any type      
' of feature)
          IF room = true THEN
           DungeonLayer(dx2 + 1, dy1) = door
          ELSE
'make it a floor tile if it doesn't hit a room         
           DungeonLayer(dx2 + 1, dy1) = floor
          END IF
'these are saved to pass to the room creation section below              
                x1 = dx1
                x2 = dx2
                y1 = dy1
                y2 = dy2
'sets hall to true so we can move on      
        hall = true
        END IF

END IF
IF direction = 1 THEN
        dy1 = y2 + 2
        dy2 = dy1 + halllength
        dx1 = Rand(x1, x2)
        dx2 = dx1
        IF CheckBoundsHall(dx1, dx2, dy1, dy2, direction) = true THEN
        CALL makehall(dx1, dx2, dy1, dy2, direction)
        IF room = true THEN
        DungeonLayer(dx1, dy1 - 1) = door
        ELSE
        DungeonLayer(dx1, dy1 - 1) = floor
        END IF
                x1 = dx1
                x2 = dx2
                y1 = dy1
                y2 = dy2
        hall = true
        END IF

END IF

IF direction = 2 THEN
        dy1 = Rand(y1, y2)
        dy2 = dy1
        dx1 = x2 + 2
        dx2 = dx1 + halllength
        IF CheckBoundsHall(dx1, dx2, dy1, dy2, direction) = true THEN
        CALL makehall(dx1, dx2, dy1, dy2, direction)
        IF room = true THEN
        DungeonLayer(dx1 - 1, dy1) = door
        ELSE
        DungeonLayer(dx1 - 1, dy1) = floor
        END IF
                x1 = dx1
                x2 = dx2
                y1 = dy1
                y2 = dy2
        hall = true
        END IF
END IF

IF direction = 3 THEN
        dy1 = (y1 - halllength) - 2
        dy2 = dy1 + halllength
        dx1 = Rand(x1, x2)
        dx2 = dx1
        IF CheckBoundsHall(dx1, dx2, dy1, dy2, direction) = true THEN
         CALL makehall(dx1, dx2, dy1, dy2, direction)
          IF room = true THEN
           DungeonLayer(dx2, dy2 + 1) = door
          ELSE
           DungeonLayer(dx2, dy2 + 1) = floor
          END IF
                x1 = dx1
                x2 = dx2
                y1 = dy1
                y2 = dy2
               hall = true
        END IF
END IF
       
       
        'if we cant make a hall after 10 tries then we....
        IF hallcount > 10 AND hall = false THEN
        'pick a random room from our list
        RDepth = Rand(1, recurdepth)
        'make old room the dimensions of our current room
        x1 = RoomHolder(RDepth, 0)
        x2 = RoomHolder(RDepth, 1)
        y1 = RoomHolder(RDepth, 2)
        y2 = RoomHolder(RDepth, 3)
        'reset hall count
        hallcount = 0
        'increment our hallmult counter and go again
        hallcountmultp = hallcountmultp + 1
END IF

'if we tried to make a hall more than 1000 times (hallcount * hallcountmultp)
'and no hall was made then we failed
IF hallcountmultp > 100 THEN
        PRINT "FAILED at "; recurdepth; " Rooms": SLEEP
        numofrooms = recurdepth: EXIT SUB
END IF

LOOP UNTIL hall = true



'************ room creation below


room = false


IF direction = 0 THEN
'holder is a dummy variable      
        holder = Rand(3, 7)
        dx2 = x1 - 2
        dx1 = dx2 - Rand(2, 4)
        dy1 = Rand((y1 - holder), y2)
        dy2 = dy1 + holder
'check to see if our room is in bounds      
        IF CheckBounds(dx1, dx2, dy1, dy2, direction) = true THEN
'if it is, set it in stone(so to speak)       
         CALL makeroom(dx1, dx2, dy1, dy2, direction, recurdepth)
'put a door here cause this is where our hall will begin
       DungeonLayer(x1 - 1, y1) = door
'put our end room coordiantes into these variables so we can send them
'to our hall creation section above
                x1 = dx1
                x2 = dx2
                y1 = dy1
                y2 = dy2
'set to true so we can end             
               room = true
               END IF

END IF

IF direction = 1 THEN
        holder = Rand(2, 4)
        dx1 = Rand((x1 - holder), x2)
        dx2 = dx1 + holder
        dy1 = y2 + 2
        dy2 = dy1 + Rand(3, 7)
        IF CheckBounds(dx1, dx2, dy1, dy2, direction) = true THEN
         CALL makeroom(dx1, dx2, dy1, dy2, direction, recurdepth)
        DungeonLayer(x2, y2 + 1) = door
                x1 = dx1
                x2 = dx2
                y1 = dy1
                y2 = dy2
        room = true
        END IF
END IF

IF direction = 2 THEN
        holder = Rand(3, 7)
        dx1 = x2 + 2
        dx2 = dx1 + Rand(2, 4)
        dy1 = Rand(y1 - holder, y2)
        dy2 = dy1 + holder
        IF CheckBounds(dx1, dx2, dy1, dy2, direction) = true THEN
         CALL makeroom(dx1, dx2, dy1, dy2, direction, recurdepth)
        DungeonLayer(x2 + 1, y2) = door
                x1 = dx1
                x2 = dx2
                y1 = dy1
                y2 = dy2
       room = true
       END IF
END IF

IF direction = 3 THEN
        holder = Rand(2, 4)
        dx1 = Rand((x1 - holder), x2)
        dx2 = dx1 + holder
        dy2 = y1 - 2
        dy1 = dy2 - Rand(3, 7)
        IF CheckBounds(dx1, dx2, dy1, dy2, direction) = true THEN
         CALL makeroom(dx1, dx2, dy1, dy2, direction, recurdepth)
        DungeonLayer(x2, y1 - 1) = door
                x1 = dx1
                x2 = dx2
                y1 = dy1
                y2 = dy2
       room = true
       END IF
END IF

'do 4000 total loops,if it is more than 4000 then fail
        IF ite > 4000 THEN
                PRINT "FAILED at"; recurdepth; "Rooms": SLEEP
                numofrooms = recurdepth: EXIT SUB
        END IF
LOOP UNTIL recurdepth = maxnumofrooms
numofrooms = recurdepth
END SUB

SUB initdungeon
                'fill our dungeon with rock
FOR x = 1 TO maxx
 FOR y = 1 TO maxy
  DungeonLayer(x, y) = wall
 NEXT y
NEXT x
                ' make the edges permawall         
FOR y = 1 TO maxy
 DungeonLayer(maxx, y) = Permwall
 DungeonLayer(1, y) = Permwall
NEXT y
FOR x = 1 TO maxx
 DungeonLayer(x, maxy) = Permwall
 DungeonLayer(x, 1) = Permwall
NEXT x
END SUB

SUB makehall (x1, x2, y1, y2, direction)
'draw our dungeon always from upper left to lower right   
        FOR x = x1 TO x2
         FOR y = y1 TO y2
          DungeonLayer(x, y) = floor
         NEXT y
        NEXT x
END SUB

SUB makeroom (x1, x2, y1, y2, direction, recurdepth)
'draw our dungeon always from upper left to lower right          
        FOR x = x1 TO x2
         FOR y = y1 TO y2
          DungeonLayer(x, y) = floor
         NEXT y
        NEXT x
recurdepth = recurdepth + 1
' this holds our rooms so we can choose one at random if we get stuck
' we never save halls or it would be a horrendous mess
RoomHolder(recurdepth, 0) = x1
RoomHolder(recurdepth, 1) = x2
RoomHolder(recurdepth, 2) = y1
RoomHolder(recurdepth, 3) = y2
END SUB

FUNCTION Rand (Lowest, Highest)
DIM a AS INTEGER
DIM b AS INTEGER
DIM c AS INTEGER

a = Lowest
b = Highest
IF a > b THEN
        c = a - b
        ELSEIF b > a THEN
                c = b - a
        ELSE
Rand = a: EXIT FUNCTION
END IF
Rand = INT(RND(1) * (c + 1)) + a

END FUNCTION

Nest of Ants - Jakub Debski [jakub@mks.com.pl].txt

I was wondering how to create a nice looking nest for the ants, and here is my idea:

Let's say, that we have some sticky dust. It goes through air and catch all the static objects. So, let's see, if we have one static object at the beginning, and a lot of randomly moving objects of the same type:

dust: * move vector: -

*- 
 /  *   -*
*
  |
  *

then these objects will catch the first one and group into larger one:

  **
  *
*****
 * *
 * **
   *

That's all. We have nice looking corridors with all the places reachabale. Algorithm is very simple and gives nice results:

1. Allocate 2 dimensional array for 0,1 values of the nest size.
2. In the centre add single object
3. Create new sticky object on the ellipse which is around the nest, having centre in the centre of the nest
4. Add random move vector to the object
5. Move object a bit. If it crosses the border of our territory, then appears on the other side.
6. Look around the object and if there is something to catch then stop. If size of the nest is enough, then stop, else go to 3.
7. Goto 5

My two advices are to add guard for moving object, f.e. for 1000 steps, because depending on vector it's possible, that object won't catch any other. The second advice it to add some "rooms" at the end of corridors (on cell, which has only one neighbour:

piece of nest:

 * 
 *****
 **

+ - the cell with one neighbour, means end of corridor

 *
 ****+
 **

add there 3x3 room

 *  +++
 ***+++
 ** +++

source code:

#define NEST_SIZE_X 80
#define NEST_SIZE_Y 50

int main(void)
{
  init_graph(); // not neccecary, for draw_char(x,y,char)
  srand(get_ticks_count()); // for (rand())

  bool c[NEST_SIZE_X][NEST_SIZE_Y];
  int x,y;
  for (x=0;x<NEST_SIZE_X;x++)
    for (y=0;y<NEST_SIZE_Y;y++)
    {
      c[x][y]=0;
      draw_char(x,y,'#');
    }

  // in the centre we put one object
  c[NEST_SIZE_X/2][NEST_SIZE_Y/2]=1; // in the array
  draw_char(NEST_SIZE_X/2,NEST_SIZE_Y/2,'.'); // and on the screen for test
  myrefresh();

  float x1,y1; // position of object
  float k; // angle
  float dx, dy; // move vector
  int px, py;

  for (int object=0;object<NEST_SIZE_X*NEST_SIZE_Y/3;object++)
  {
    // degree
    k = (rand()%360)*3.1419532/180;
    // position on ellipse by degree
    x1 = NEST_SIZE_X/2+(NEST_SIZE_X/2)*sin(k);
    y1 = NEST_SIZE_Y/2+(NEST_SIZE_Y/2)*cos(k);
//    draw_char(x1,y1,'*');

    // object will move not too horizontal and not too vertival
    do {
      dx=rand()%100;
      dy=rand()%100;
    } while ((abs(dx)<10 && abs(dy)<10));
    dx-=50;
    dy-=50;
    dx/=100; // by little steps
    dy/=100; // by little steps

    int counter=0;
    while (1)
    {
      // didn't catch anything after 1000 steps (just to avoid infinite loops)
      if (counter++>1000)
      {
        object--;
        break;
      }
      // move object by small step
      x1+=dx;
      y1+=dy;

      // change float to int

      px=x1;
      py=y1;

      // go through the border to the other side

      if (px<0)
      {
        px=NEST_SIZE_X-1;
        x1=px;
      }
      if (px>NEST_SIZE_X-1)
      {
        px=0;
        x1=px;
      }
      if (py<0)
      {
        py=NEST_SIZE_Y-1;
        y1=py;
      }
      if (py>NEST_SIZE_Y-1)
      {
        py=0;
        y1=py;
      }

      // if object has something to catch, then catch it

      if ((px>0 && c[px-1][py]==1) ||
        (py>0 && c[px][py-1]==1) ||
        (px<NEST_SIZE_X-1 && c[px+1][py]==1) ||
        (py<NEST_SIZE_Y-1 && c[px][py+1]==1))
      {
        c[px][py]=1;
        draw_char(px,py,'.');
        myrefresh();
        break; // go to creation of new object
      }
    } // end of while(1)
  } // end of for

  // add halls at the end of corridors
  int neighbours;
  for (x=1;x<NEST_SIZE_X-1;x++)
    for (y=1;y<NEST_SIZE_Y-1;y++)
    {
      if ((x>NEST_SIZE_X/2-10 && x<NEST_SIZE_X/2+10 && y>NEST_SIZE_Y/2-5 && y<NEST_SIZE_Y/2+5) || c[x][y]==0)
        continue;

      neighbours=0;
      if (c[x-1][y-1]!=0)
        neighbours++;
      if (c[x][y-1]!=0)
        neighbours++;
      if (c[x+1][y-1]!=0)
        neighbours++;
      if (c[x-1][y]!=0)
        neighbours++;
      if (c[x+1][y]!=0)
        neighbours++;
      if (c[x-1][y+1]!=0)
        neighbours++;
      if (c[x][y+1]!=0)
        neighbours++;
      if (c[x-1][y+1]!=0)
        neighbours++;

      if (neighbours==1)
      {
        for (px=-1;px<=1;px++)
          for (py=-1;py<=1;py++)
          {
            c[x+px][y+py]=1;
            draw_char(x+px,y+py,',');
            myrefresh();
          }
      }
    }

  return 0;

}

some samples

80x25
#####################............................###############.###..##########
###############,,,###.#########.#.######.##..###################.###.###########
###############,,,......#######...######.....########.#####...#......##.########
###############,,,###.#..#.##.##..##,,,#..#.######,,,.#####.#...###.....########
################..###......#...##..#,,,#....######,,,.#####.##.##......#########
#####################.###......###.#,,,..##,,,.###,,,##.###.......###.....######
########################..#,,,.........#.#.,,,..####.....##.####.#.######.######
#########################.#,,,########.....,,,..####..####.....#...#############
#####################,,,###,,,...#######.####.#.#.##.#####.###.###..############
#####################,,,########.#######.####...#.#....###.####,,,##############
#################,,,.,,,#.#.#.##..####.......................##,,,##############
#################,,,...........#.....###.##.##.#.#####..##..###,,,#####.########
#################,,,##.#,,,###...##...........##....#########..#..#.....########
##############,,,#######,,,######.#..###.###.#####...###.#.##.##....#.#..#######
##############,,,,,,####,,,###.......##...##.####...........#....#.#############
##############,,,,,,#######...#####.####..######...#.###.##......####....#######
############..#.#,,,#######............##...#####.##...#..#..##...###.#.########
###########.#...##.###....##...##...##,,,.#..########.###..####..........#######
#####,,,.##...#...............#.......,,,.##.########...##..####.##....#########
#####,,,....#...###.#..#.#..#.#,,,.#.#,,,############..###.....#.##.,,,#########
#####,,,#,,,..###...####.######,,,##.###############..####.#....####,,,#########
#########,,,.####...####..#####,,,##.###############..#######...####,,,#########
#########,,,..##...#.....#######,,,#.##############...########..################
##########..#.##.#..####..######,,,....############...########.#################
##########.#######.#############,,,..#.#######################.#################

80x40

##########################.......................#....##......##################
##############,,,#####,,,#....,,,.###...####.######...###.##..##################
##############,,,.....,,,###.#,,,.###..#####.#..###.#####.######################
##############,,,....#,,,#####,,,.####..####.....##..####.####.#################
#################,,,.####,,,.####.##...#####.#.####.##.##.##...#################
#################,,,.####,,,.#.##.#.##.###...#.###..#..##....##.....############
#################,,,.####,,,......#..#..##..#..###.#..###.#####.,,,#############
################.......#########.....#..##..#..##..#..###.#.....,,,#############
################.###.#.########...##.#.###.##.##..........#....#,,,#############
################.##....##,,,##,,,###.#.###....##..##........####..##############
###############..####..##,,,##,,,##.....##.###.....##.##.#.###.#.....###########
##############....####.##,,,.#,,,##...#.##.##..##,,,#..#.........#...###########
##############.......#.###...##..###.##....##...#,,,#.###.#.#.#####..###########
#################......####.####.####,,,.#.#..#.#,,,#####.....#,,,##.###########
##################.###.#.##.####.###.,,,.#....#.......###.,,,..,,,##############
###################......##.#.##..#..,,,..##.#####..#.###.,,,##,,,##############
############........####................#.########.##..###,,,###################
##########.#.#####.####....##.#.##.##.#...########..###,,,######################
####,,,............##,,,..##########.##..##.##########.,,,######################
####,,,...#####...###,,,.#####.#####....#.......#####..,,,######################
####,,,.#.###...#####,,,.####...#####.#...##.##.....#.,,,#######################
######.######..########.######...######....########...,,,#..####################
############..#########.######.#..####...#.####.#####.,,,#..####################
#######################..###,,,#....#...####.##.#######.##.,,,##################
########################.###,,,.##..............#.#####.#..,,,#..###############
##################.......###,,,....#.#..####.##...#.......#,,,...###############
##################.,,,....##.####.##....###...##......##..#.#.....###.,,,#######
##############,,,##,,,.#..........#...#.###.#.##.####..##.....,,,.....,,,#######
##############,,,..,,,#..#.#.####.#.#.#.###.#..#...##..##.#.#.,,,.#...,,,#######
#############.,,,#.####.####.##...#####..##..#.##....###,,,.#.,,,###############
############.............#...##....##....###..####.#.###,,,.#....###############
####,,,.#.######.#########..#####.###.##..##...###..####,,,..###################
####,,,...#...######.#.....#####..###.#...##.#####....##########################
,,,.,,,#....#.####.....##...###...##...##.##...###.##..#########################
,,,.#...............##.###..###.,,,#.####.##....##...#..########################
,,,....##.##..#.#.#....##..###..,,,######.##.##.####..##########################
#########.#,,,..#....#.#...###.#,,,####...##..#####,,,##########################
#########.#,,,##......##..####..#######..###.#####.,,,##########################
#########.#,,,#..#.##......#############.###.####..,,,##########################
########..#####..#.#####..##############.###........############################

80x50

######################.##..#.....#........######################################
#####################.......#.,,,##.#.##########################################
########################..#.#.,,,##...##########################################
###########################...,,,....######################,,,##################
##########################..#.#####...#####################,,,.#################
############################....##.....#######.############,,,##...#############
#####################,,,####.#...#...######,,,.#############...#..##############
#####################,,,######......#,,,###,,,.############..#.#.##..###########
#####################,,,###,,,.#.....,,,###,,,..###########..#.#......##########
################,,,####...#,,,###...#,,,...###.########,,,..##....##############
################,,,######..,,,#####.###...####..#######,,,.......#.#############
################,,,#.,,,#..##.......##..###.##.########,,,#.######.,,,#####.####
##################...,,,..#####,,,..##.##....#..###,,,#####........,,,####..####
###################..,,,..#####,,,........###...###,,,######.,,,##.,,,#####.####
###################.......#####,,,...#.#,,,##.#,,,#,,,######.,,,###########...##
####################.####.....##.###.#..,,,##..,,,...######..,,,.##.#######..###
###########,,,#####,,,,,,,,,#.##........,,,#..#,,,#..##...##..##....######..####
#########..,,,##.##,,,,,,,,,#...######.,,,###.,,,###.#.##.##.###.##,,,####.##...
#########..,,,.....,,,,,,,,,....#####..,,,##..,,,.##...##..#.#.....,,,####.....#
########.#....#.#.....#.####,,,.#####..,,,###.,,,.#...####.#......#,,,#.....#.##
######......#.....###.#.###.,,,...###..#...##..##..#.#.,,,...##.#.......#.###..#
######..#########.##..#..#..,,,#..##......###..##.##.#.,,,..###...#######..#####
#######.###..####........##.###..####.#.#..##..##.##.#.,,,.##.###..........##,,,
######,,,#........##..#...#.###...#.#####.###.....#..#.##.......#####,,,.#...,,,
######,,,####...#.###..#..#...........#...#....##.##...#..#.##.######,,,.####,,,
######,,,..#..#######.###.....#####..................#...############,,,#,,,###.
##########...##############.#####.#.###.#.....##..##..#..#####.#....#####,,,.##.
###########.########..#.....#####.#..##.#.##.####...#.####.........######,,,....
##########..######......####.........##.####....###.#.......#...##.###.#...##.#.
###########.######.##..#####...#,,,.#...####.##....##.##.##...#..#.......#.##...
##########..#####,,,...####...##,,,.##..###..###.#.#####.###....####.#.######..#
##########.######,,,#..#####..##,,,###...##.###.....####..###.#.....##..####,,,#
#################,,,...#......###.###...########.##..####..#...########.####,,,#
################......##.##.,,,##..........#####.###..###..##....######...##,,,#
################..###.#,,,##,,,##.##.#....######..########.##.##.#######.#######
#################.....#,,,##,,,...####.#...#####.##.######.##,,,...#############
#################.###.#,,,###..####.....#.#####......#####...,,,.#.#############
######################,,,#..#..###..#..##..###..#.##########.,,,.#...###########
######################,,,.....###..###.##.#######.##################..##########
######################,,,##..####..###.##.,,,####.......##.##..#################
#######################.....####..#.....#.,,,####.##..#.......##################
######################..#.#.#########.#.##,,,####...#..#.#.#..,,,###############
###########################.#.#######.#..########.,,,###.####.,,,..#############
####################,,,###.......###..##..#######.,,,###..####,,,...############
####################,,,###..#,,,....#.#######,,,#.,,,###...####....#############
####################,,,.....#,,,##.....######,,,....######.##...#..#############
#####################.##,,,.#,,,....##....###,,,##....####........##############
########################,,,.,,,#.#.####....####.....#..#...##..#..##############
########################,,,.,,,....####..#.####.#.........##..#....#############
############################,,,.....#......######..##.....####..################

regards Jakub

Passable Cave Building Algorithm - Josh Tippets [vertexnormal@email.com].txt

Here is an algorithm I have used to generate a passable cave:

First of all, I need a couple of support functions, which I call Blobbers. Basically, these functions use various methods to create "blobs" within the grid of the level array.

The first Blobber I call ProbBlob, which has the prototype:

 void ProbBlob(int X, int Y, int Reps, int Value, float Up, float Down, float Left, float Right);

• (X,Y)=Location within map grid at which to start.
• Reps=Number of times to iterate. Determines the size of the blob.
• Value=Grid-type value to fill in the blob with. FLOOR_TYPE,WALL_TYPE, etc.
• Up,Down,Left,Right=Values in the range [0,1], which all must add up to 1.0

These values are used to setup a probability table that determines which direction the blobber will move next.

By giving ProbBlob the values of 0.25, 0.25, 0.25, 0.25, I generate a blob with an equal probability of moving in any given direction. By playing with these numbers, I can cause the blob to trend in a general direction.

ProbBlob basically iterates through a loop Reps number of times, each time writing Value to the current location. After writing Value, I use the probability table generated from Up,Down,Left and Right to determine a direction to move. I move one cell in the chosen direction, write Value, and choose again until the loop terminates.

Reps roughly determines the size of the blob. I say roughly, because a lot of the repetitions may actually re-visit a cell already blobbed, in effect being wasted, but you get the idea.

The second helper function I need is called BlobToward:

 void BlobToward(int X1, int Y1, int X2, int Y2, float *Up, float *Down, float *Left, float *Right);

This function doesn't actually draw a blob. Rather, it uses the given start and end coordinates to generate the directional values Up, Down, Left, and Right, which are later fed to the ProbBlob function.

This function finds the difference between X1 and X2, and the difference between Y1 and Y2, and uses the results to compute probabilities which will cause the blob to progress generally from (X1,Y1) toward (X2,Y2). This is good for drawing random cave tunnels; you can specify a start and an end, generate the probabilities, then feed the numbers to the blobber.

Another possible blobber function is one which functions almost exactly like ProbBlob, but which doesn't exit until some location is reached. If done this way, it is sometimes best to continually re-calculate Up, Down, Left, and Right, in the event that the blob runs past the destination position without actually hitting it. If the probabilities are not recomputed, the blob will tend to keep going past the destination, and might never actually hit it. Re-computing the probs routinely will ensure that the blob is always directed toward the destination.

Given these functions and a grid filled with WALL_TYPE, I am given a number of options. One I commonly use is to call ProbBlob with (0.25,0.25,0.25,0.25) and generate a large blob in the very center of the map. Then I loop an arbitrary number of times, each time randomly selecting (X1,Y1) and (X2,Y2) coordinates, which I feed to BlobToward. Taking the results of BlobToward, I call ProbBlob again with the generated probabilities, using randomly determined Reps. By passing FLOOR_TYPE to ProbBlob, the generated blob is written as a floor type of cell.

The result of this algorithm tends to be a large central cave complex with many arms radiating outward and terminating in dead ends.

Alternately, you could partition the level grid into maybe nine blocks, 3x3, and use ProbBlob to generate a regular blob within each block. BlobToward could then be used to connect the various regular blobs into something resembling an interconnected series of rooms.

I'm sure there are hundreds of ways these methods could be used, in conjunction with other ideas. This might give you a place to start. Good luck, and keep us all posted on how it goes.

Josh Tippetts vertexnor...@email.com OGRESlash- www.me.icobb.com/rpg/vertexnormal/