# User:Duerig/Archive9

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

# 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)

```       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

• +

• +++
• +++
• +++

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

1. ............................###############.###..######
1. ,,,###.#########.#.######.##..###################.###.#######
1. ,,,......#######...######.....########.#####...#......##.####
1. ,,,###.#..#.##.##..##,,,#..#.######,,,.#####.#...###.....####
1. ..###......#...##..#,,,#....######,,,.#####.##.##......#####
1. .###......###.#,,,..##,,,.###,,,##.###.......###.....##
1. ..#,,,.........#.#.,,,..####.....##.####.#.######.##
1. .#,,,########.....,,,..####..####.....#...#########
1. ,,,###,,,...#######.####.#.#.##.#####.###.###..########
1. ,,,########.#######.####...#.#....###.####,,,##########
1. ,,,.,,,#.#.#.##..####.......................##,,,##########
1. ,,,...........#.....###.##.##.#.#####..##..###,,,#####.####
1. ,,,##.#,,,###...##...........##....#########..#..#.....####
1. ,,,#######,,,######.#..###.###.#####...###.#.##.##....#.#..###
1. ,,,,,,####,,,###.......##...##.####...........#....#.#########
1. ,,,,,,#######...#####.####..######...#.###.##......####....###
1. ..#.#,,,#######............##...#####.##...#..#..##...###.#.####
1. .#...##.###....##...##...##,,,.#..########.###..####..........###
1. ,,,.##...#...............#.......,,,.##.########...##..####.##....#####
1. ,,,....#...###.#..#.#..#.#,,,.#.#,,,############..###.....#.##.,,,#####
1. ,,,#,,,..###...####.######,,,##.###############..####.#....####,,,#####
1. ,,,.####...####..#####,,,##.###############..#######...####,,,#####
1. ,,,..##...#.....#######,,,#.##############...########..############
1. ..#.##.#..####..######,,,....############...########.#############
1. .#######.#############,,,..#.#######################.#############

80x40

1. .......................#....##......##############
1. ,,,#####,,,#....,,,.###...####.######...###.##..##############
1. ,,,.....,,,###.#,,,.###..#####.#..###.#####.##################
1. ,,,....#,,,#####,,,.####..####.....##..####.####.#############
1. ,,,.####,,,.####.##...#####.#.####.##.##.##...#############
1. ,,,.####,,,.#.##.#.##.###...#.###..#..##....##.....########
1. ,,,.####,,,......#..#..##..#..###.#..###.#####.,,,#########
1. .......#########.....#..##..#..##..#..###.#.....,,,#########
1. .###.#.########...##.#.###.##.##..........#....#,,,#########
1. .##....##,,,##,,,###.#.###....##..##........####..##########
1. ..####..##,,,##,,,##.....##.###.....##.##.#.###.#.....#######
1. ....####.##,,,.#,,,##...#.##.##..##,,,#..#.........#...#######
1. .......#.###...##..###.##....##...#,,,#.###.#.#.#####..#######
1. ......####.####.####,,,.#.#..#.#,,,#####.....#,,,##.#######
1. .###.#.##.####.###.,,,.#....#.......###.,,,..,,,##########
1. ......##.#.##..#..,,,..##.#####..#.###.,,,##,,,##########
1. ........####................#.########.##..###,,,###############
1. .#.#####.####....##.#.##.##.#...########..###,,,##################
1. ,,,............##,,,..##########.##..##.##########.,,,##################
2. ,,,...#####...###,,,.#####.#####....#.......#####..,,,##################
3. ,,,.#.###...#####,,,.####...#####.#...##.##.....#.,,,###################
1. .######..########.######...######....########...,,,#..################
1. ..#########.######.#..####...#.####.#####.,,,#..################
1. ..###,,,#....#...####.##.#######.##.,,,##############
1. .###,,,.##..............#.#####.#..,,,#..###########
1. .......###,,,....#.#..####.##...#.......#,,,...###########
1. .,,,....##.####.##....###...##......##..#.#.....###.,,,###
1. ,,,##,,,.#..........#...#.###.#.##.####..##.....,,,.....,,,###
1. ,,,..,,,#..#.#.####.#.#.#.###.#..#...##..##.#.#.,,,.#...,,,###
1. .,,,#.####.####.##...#####..##..#.##....###,,,.#.,,,###########
1. .............#...##....##....###..####.#.###,,,.#....###########
4. ,,,.#.######.#########..#####.###.##..##...###..####,,,..###############
5. ,,,...#...######.#.....#####..###.#...##.#####....######################

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

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

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

1. .#,,,..#....#.#...###.#,,,####...##..#####,,,######################
1. .#,,,##......##..####..#######..###.#####.,,,######################
1. .#,,,#..#.##......#############.###.####..,,,######################
1. ..#####..#.#####..##############.###........########################

80x50

1. .##..#.....#........##################################
1. .......#.,,,##.#.######################################
1. ..#.#.,,,##...######################################
1. ...,,,....######################,,,##############
1. ..#.#####...#####################,,,.#############
1. ....##.....#######.############,,,##...#########
1. ,,,####.#...#...######,,,.#############...#..##########
1. ,,,######......#,,,###,,,.############..#.#.##..#######
1. ,,,###,,,.#.....,,,###,,,..###########..#.#......######
1. ,,,####...#,,,###...#,,,...###.########,,,..##....##########
1. ,,,######..,,,#####.###...####..#######,,,.......#.#########
1. ,,,#.,,,#..##.......##..###.##.########,,,#.######.,,,#####.
1. ...,,,..#####,,,..##.##....#..###,,,#####........,,,####..
1. ..,,,..#####,,,........###...###,,,######.,,,##.,,,#####.
1. .......#####,,,...#.#,,,##.#,,,#,,,######.,,,###########.

..##

1. .####.....##.###.#..,,,##..,,,...######..,,,.##.#######.

.###

1. ,,,#####,,,,,,,,,#.##........,,,#..#,,,#..##...##..##....######..
1. ..,,,##.##,,,,,,,,,#...######.,,,###.,,,###.#.##.##.###.##,,,####.#
1. ...
1. ..,,,.....,,,,,,,,,....#####..,,,##..,,,.##...##..#.#.....,,,####..

...#

1. .#....#.#.....#.####,,,.#####..,,,###.,,,.#...####.#......#,,,#.....
1. .##
1. ......#.....###.#.###.,,,...###..#...##..##..#.#.,,,...##.#.......#.##
2. ..#
1. ..#########.##..#..#..,,,#..##......###..##.##.#.,,,..###...#######..#
1. .###..####........##.###..####.#.#..##..##.##.#.,,,.##.###..........#
3. ,,,
1. ,,,#........##..#...#.###...#.#####.###.....#..#.##.......#####,,,.#..

.,,,

1. ,,,####...#.###..#..#...........#...#....##.##...#..#.##.######,,,.###
1. ,,,
1. ,,,..#..#######.###.....#####..................#...############,,,#,,,
1. .
1. ...##############.#####.#.###.#.....##..##..#..#####.#....#####,,,

.##.

1. .########..#.....#####.#..##.#.##.####...#.####.........######,,,

....

1. ..######......####.........##.####....###.#.......#...##.###.#...#
1. .#.
1. .######.##..#####...#,,,.#...####.##....##.##.##...#..#.......#.#
2. ...
1. ..#####,,,...####...##,,,.##..###..###.#.#####.###....####.#.#####
3. ..#
1. .######,,,#..#####..##,,,###...##.###.....####..###.#.....##..####

,,,#

1. ,,,...#......###.###...########.##..####..#...########.####

,,,#

1. ......##.##.,,,##..........#####.###..###..##....######...##

,,,#

1. ..###.#,,,##,,,##.##.#....######..########.##.##.#######.###
1. .....#,,,##,,,...####.#...#####.##.######.##,,,...#########
1. .###.#,,,###..####.....#.#####......#####...,,,.#.#########
1. ,,,#..#..###..#..##..###..#.##########.,,,.#...#######
1. ,,,.....###..###.##.#######.##################..######
1. ,,,##..####..###.##.,,,####.......##.##..#############
1. .....####..#.....#.,,,####.##..#.......##############
1. ..#.#.#########.#.##,,,####...#..#.#.#..,,,###########
1. .#.#######.#..########.,,,###.####.,,,..#########
1. ,,,###.......###..##..#######.,,,###..####,,,...########
1. ,,,###..#,,,....#.#######,,,#.,,,###...####....#########
1. ,,,.....#,,,##.....######,,,....######.##...#..#########
1. .##,,,.#,,,....##....###,,,##....####........##########
1. ,,,.,,,#.#.####....####.....#..#...##..#..##########
1. ,,,.,,,....####..#.####.#.........##..#....#########
1. ,,,.....#......######..##.....####..############

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
```

``` 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/