# User:Duerig/Archive9

m (added code tags) |
m (make readable) |
||

(One intermediate revision by one user not shown) | |||

Line 475: | Line 475: | ||

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

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

− | and here is my idea: | + | |

− | Let's say, that we have some sticky dust. It goes through air | + | 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: |

− | 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: * | dust: * | ||

move vector: - | move vector: - | ||

− | *- | + | *- |

− | + | / * -* | |

− | + | * | |

− | * | + | | |

− | + | * | |

− | + | ||

− | + | ||

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

one: | one: | ||

− | + | ** | |

− | + | ||

− | + | ||

− | + | ||

− | + | ||

* | * | ||

+ | ***** | ||

+ | * * | ||

+ | * ** | ||

+ | * | ||

That's all. We have nice looking corridors with all the places | That's all. We have nice looking corridors with all the places | ||

reachabale. Algorithm is very simple and gives nice results: | 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 | |

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

− | appears on the other side. | + | # Goto 5 |

− | + | ||

− | size of the nest is enough, then stop, else go to 3. | + | |

− | + | ||

My two advices are to add guard for moving object, f.e. for 1000 steps, | My two advices are to add guard for moving object, f.e. for 1000 steps, | ||

Line 525: | Line 516: | ||

piece of nest: | piece of nest: | ||

− | * | + | * |

− | ***** | + | ***** |

− | ** | + | ** |

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

− | * | + | * |

− | ****+ | + | ****+ |

− | ** | + | ** |

add there 3x3 room | add there 3x3 room | ||

− | * +++ | + | * +++ |

− | ***+++ | + | ***+++ |

− | ** +++ | + | ** +++ |

source code: | source code: | ||

+ | <pre> | ||

#define NEST_SIZE_X 80 | #define NEST_SIZE_X 80 | ||

#define NEST_SIZE_Y 50 | #define NEST_SIZE_Y 50 | ||

Line 592: | Line 584: | ||

while (1) | while (1) | ||

{ | { | ||

− | // didn't catch anything after 1000 steps (just to avoid infinite | + | // didn't catch anything after 1000 steps (just to avoid infinite loops) |

− | loops) | + | |

if (counter++>1000) | if (counter++>1000) | ||

{ | { | ||

Line 651: | Line 642: | ||

for (y=1;y<NEST_SIZE_Y-1;y++) | 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 && | + | 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) |

− | y<NEST_SIZE_Y/2+5) || c[x][y]==0) | + | |

continue; | continue; | ||

Line 688: | Line 678: | ||

} | } | ||

+ | </pre> | ||

some samples | some samples | ||

Line 823: | Line 814: | ||

Here is an algorithm I have used to generate a passable cave: | 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. | |

− | 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 | + | 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. | |

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | + | ||

− | 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 | Josh Tippetts | ||

vertexnor...@email.com | vertexnor...@email.com | ||

OGRESlash- www.me.icobb.com/rpg/vertexnormal/ | OGRESlash- www.me.icobb.com/rpg/vertexnormal/ |

## Latest revision as of 15:19, 2 May 2008

# [edit] 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

# [edit] 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

# [edit] 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/