User:Duerig/Archive9
Jump to navigation
Jump to search
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:
- Allocate 2 dimensional array for 0,1 values of the nest size.
- In the centre add single object
- Create new sticky object on the ellipse which is around the nest, having centre in the centre of the nest
- Add random move vector to the object
- Move object a bit. If it crosses the border of our territory, then appears on the other side.
- 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.
- 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/