User:Duerig/Archive8

Fill-area-with-rooms & Maze - algorithms - Judy Wray [j.k.wray@worldnet.att.net]

 Here is an algorithm I use (can't remember where I first saw the idea).
 It can generate a halfway decent castle-like environment with a few

tweaks, and can generate a maze as well. It's really simple. Just pick a starting point within the array, choose a direction, and draw a wall in that direction, stopping until you hit the edge of the maze or another wall. You can tweak your maze by various means.

1) Selection of starting points.

 I use a setting, called Granularity, to choose points. If Granularity=1,

any old point can be chose, and the maze ends up as a solid chunk of wall in most cases. If Granularity=2, then points are chosen on every other row/column, so that spaces are left in between. Granularity=2 mazes generate mazes with corridors one cell wide. The higher Granularity is, the wider the corridors are made. Beware of "wierdness" if you choose Granularity which is not a factor of maze size, or you can end up with skinny corridors on borders, or doubled up walls. (SX, SY) -- Wall starting point SX=Granularity * (rand()%(MAPWIDTH/Granularity)); SY=Granularity * (rand()%(MAPHEIGHT/Granularity));

2) Wall length

 I like to set a minimum and maximum wall length when drawing walls. Many

walls, of course, will be stopped before the chosen length, but on average your walls will fall within the range. Min=2 Max=4 would generate a maze with a lot of tiny little walls, while Min=16 Max=32 would generate a maze with generally long, straight corridors.

3) Number of walls

 You can modify maze density by changing the number of walls to draw. I

generally use N = number of walls to _attempt_ to draw, which will fail gracefully if a suitable staring point can not be located. Starting points are chosen only if the location is not already a wall, so it is possible to get in an endless hang looking for a location when all available locations are filled.

 A low number of walls results in lots of large, open rectangular areas,

while a high number progresses toward a full maze. For a perfect maze, pick an arbitarily high number of walls (50000 or something like that) to attempt to draw.

 The drawback to this as currently implemented is that the maps look only

generally castle-like. Enclosed, separate rooms are rare, as you'll see if you try it. I like to mix this algorithm with one of placement of randomly located "patterned" segments. In other words, I would place some special rooms (vaults, thronerooms, dungeon cellblocks, etc...) then fill in the remaining space with the former algorithm, using a Granularity of 4 or maybe even 8, for broad corridors, and decent size siderrooms which could be store rooms or the like. Levels tend to be rather boring if you don't mix algos.

 Anyway, hope this gives you some ideas of your own.

VertexNormal

Lake and Oasis Generator - Adam Szczepaniak [adamshc@wp.pl].txt

his article is covering an important skill you should posses when creating RL world; creating water areas. If you want to have a randomly-generated areas of water you should read this article thoroughly. Algorithm which I?ll describe below is of my own idea, and - to be honest it?s very simple but efficient and effective. All code in the article is in C++ - this is the language I?m most familiar with (of course it can easily be ported to Pascal, Java and even Basic). That said let?s begin!

1. Creating randomizer

I don?t know if you can create randomizer, which is generating number in specified range (for example: from 8 to 23). If you can then skip this step and proceed with the second one. If you can?t don?t worry, I?ll show you how to write a simple randomizer.

So, here?s a code: (remember about includeing stdlib.h!)

int rnd(int from, int to) { return (rand()%(to-from)+from); }

and, to have more "random" random numbers let?s implement function to change the seed:

void change_seed() { // here you must include windows.h srand((unsigned int)GetTickCount()); }

Of course, instead of Windows? GetTickCount() you can calculate seed using time functions declared in time.h, but I?m just too lazy to do this ;).

IMPORTANT: with this randomizer, you must ALWAYS add one to "to" value, without this you won?t get a number from range [from,to], but only [from,to-1]. I didn?t changed that because, as I said I?m too lazy and don?t want to change a huge amount of code in my RL :).

Now, when we have a randomizer, we could start implementing a function with which we create lake.

2. Creating lake

Now we?ll take care about our lake generation. But before that, I have to say to you how I organized my map cells infomation. I created a structure called MapCell in which I store information about tile?s type and character representing it. Now, when everything?s clear (I hope so) I can present you my algorithm, can?t I?

A). An idea

Idea is simple: 1). You have the point (x,y):

. . . . . . . . . . . . . . . . . . . . . . . .

	. . . X . . .

. . . . . . . . . . . . . . . .

	. . . . . . . .

2). Next you roll a random value which determines part of square (width & height defined by radius). For example, if it?s 1 then you add one water cell somewhere in the south-east part of our square in random range from center (it varies from 0 to radius value):

. . . . . . . . . . . . . . . . . . . . . . . .

	. . . X . . . .

. . . . .=. . . . . . . . . . .

	. . . . . . . .

3). Repeat step 2 (but you have different directions and ranges from point you?ve got)

B). The code

1). First of all, we must decide about what input we?ll give to function. For me number of lakes and their radius is enough, but you may also want to decide a region in which lake will be placed. I decided to place my lake(s) randomly.

2). Now we?ll mark where is the left-top corner of square containing our lake. As I said, I let the randomizer do the work:

int sx,sy; sx = rnd(radius/2,MAP_WIDTH-radius/2+1); //I?ll tell about radius role sy = rnd(radius/2,MAP_HEIGHT-radius/2+1);

I know that I could change code a little bit to have better effects, but for me it?s fine as it is. So, now when the left-top corner of square is set, we can go on.

3). Now we?ll set point which is near center of our square:

int cx,cy; cx = sx+radius/2; cy = sy+radius/2;

Why I said about the point that?s near the center of square? Simply because if you divide 7 by 2 (assuming you?re using int data type) you?ll get 3.

4). Now we?ll create loop in which we?ll "take under consideration" map cells specified by radius: ? for(int x=0;x<radius*2;x++) { for(int y=0;y&gtradius*2;y++) { //see step 5 } }

5). At beginning of this function declare two variables: ax and ay. They?re responsible for showing where place water cell ([ax,ay] - position of our future water cell). Also, you should declare one variable of int type - it?ll keep randomized value. It might be confusing, but when you?ll look at code, everything will be clear:

s=rnd.rnd(1,5); if(s==1) { ax = cx + rnd.rnd(0,x/2+1); ay = cy + rnd.rnd(0,y/2+1); } if(s==2) { ax = cx - rnd.rnd(0,x/2+1); ay = cy - rnd.rnd(0,y/2+1); } if(s==3) { ax = cx + rnd.rnd(0,x/2+1); ay = cy - rnd.rnd(0,y/2+1); } if(s==4) { ax = cx - rnd.rnd(0,x/2+1); ay = cy + rnd.rnd(0,y/2+1); }

I hope you understand this simple code?

6). And this is the last step: give desired cell information that it contains water:

cells[ax][ay].tile = '='; cells[ax][ay].type = "water";

3. Creating oasis (on desert)

A). An idea

Creating oasis (or oases) is very similar to creating lakes, but of course, there are some diffrences:

1). Firstly you create a grass field (using the same algorithm) with radius larger than given (in my opinion grass_radius = water_radius+7).

2). Next thing is to create some palms (how would oasis look without palms?)

    Same radius as in grass.

IMPORTANT: if you?re randomly placing oases DO NOT use external function which is creating lakes - if you do, lakes won?t be in the center of the grass & palm area!

You must rewrite the code.

B). The code

I think you can write the code by yourself, so I don?t have to show it to you. But if you can?t do this, I?ll send you source.

4. Finishing

That?s all, I think it would help somebody. If you noticed a bug (or bugs) please inform me about that, I?ll be grateful. And if you want to have the source of described algorithm, mail me: adamshc@wp.pl