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:

1. define NEST_SIZE_X 80
2. 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/