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

User Interface in Roguelikes by Jim Babcock

These principles should guide the user interface design of any roguelike.

1. It should be easy for the player to familiarize himself with the

   controls.

2. The player should need to remember no more commands than necessary.

3. Finding the command for a particular action should be easy.

For (1), there are two corrollaries. First is that all keybindings should be mnemonic if at all possible. Second is that there should be a tutorial level. This is easier to do than you might imagine; just place messages around a level saying things like "Open this door with (O)", for each of the major concepts in the game.

(2) requires a little thought. First, auto-open-doors (ala Angband) is good; leave the open key, but make it unnecessary. For inventory management, I use an Angband-style system again; there is a pickup command, but it's rarely used because stepping on an item prompts you to pick it up. The < and > commands for stairs are completely unnecessary; I handle them by prompting "These stairs lead to dlvl 2. Climb them? [Y/N]" when stepping on stairs. The command is still there of course, and you can disable auto-follow-stairs as an option, but it's one less key for newbies to learn. It both eliminates a painful source of YASD and reduces the keycount if you just add a "Save? [Y/N]" prompt after the "Quit? [Y/N]" prompt.

I hardly need to explain the stupidity of Rogue/Hack/NetHack's separating "w"ear from "p"ut on, and "t"ake off from "r"emove. And certainly there's some redundancy among the 'z'ap, 'a'im, 'A'ctivate, 'q'uaff, 'a'pply, 'u'se, 'F'uel, 'E'at, 'r'ead, 'b'rowse, and 'G'ain, commands (vanilla Angband). NetHack's almost as bad, but at least it has the excuse of occasionally allowing crazy combinations like eating tools (polymorph into a metallivore) and reading armor (T-shirt).

Using too many obscure controls forces players to consult spoilers or newsgroups to find out that they need to wipe their face (ADOM) or #rub a lamp (NetHack).

(3) suggests a controls quick-reference. The problem is, the references in most roguelikes aren't very usable. It should go without saying that you should be able to scroll backwards, yet NetHack doesn't let you, and

 while Angband supports it, for some reason neither page up, backspace,

nor up arrow bound to this function. The keyboad reference should be easy to find; one keystroke is ideal. Angband's keyboard reference is three pages into the fifth chapter of the manual. How is anyone supposed

 to be able to find that?

The keyboard reference should not just be flat text; it should adjust itself to configuration options. And, depending on how the menu interface works, it should should also be a menu, where picking an action from the list does that action. This will make the player much more likely to go to the controls reference than if it were just reading a manual.

Furthermore, the keyboard should be uncluttered. It's hard to find the command you want in a keyboard reference that has keys for "display the name of your current deity" (should be on the character info page), "check literacy" (is already on the skills page), and "pick up items comfortably" keys (shouldn't be separate from regular pickup) (ADOM).

The problem with roguelike interfaces is not just that the games themselves require so many keys, it's that so little work has been put into them. You'd be surprised how much easier to use you can make a roguelike with a little bit of work.

(I grant permission to redistribute this text in any form, modified or unmodified, on the sole condition that proper credit is given.)

Mostly Turn-based Multiplayer Timing (MTbMT) -- Isaac Kuo

The sequence of play is handled in sequentially numbered "turns", which is further subdivided into "phases". In a turn, one player moves and then a number of monsters may move. A "phase" is where one creature performs one action. The first phase of a turn is always the player's move. The subsequent phases of a turn are monster actions.

The players do not move in a strict order, but instead are restricted by waiting for other nearby players to move. Whenever a player moves, a set of timers is started--one for each nearby player--according to distance:

1 space = 10 secs 2 spaces = 8 secs 3 spaces = 5 secs 4 spaces = 4 secs 5 spaces = 3 secs 6-8 spaces = 2 secs 9-15 spaces = 1 secs

The player must wait until all these timers run down to zero before moving. Whenever one of those nearby players moves, the associated timer drops to zero. Thus, a player can always move immediately after all other nearby players have moved (since his last move).

The purpose of these timers is to give all nearby players a chance to react to the player's move before the player may move again.

After a player moves, he sees the word "wait 9" appear on their screen if he has had to wait for more than one second, until all of the timers run down to zero. (The wait counter counts down from 9 or whatever down to zero, based on the highest remaining timer.) When all the timers run down to zero, the wait message disappears, and the player may move at any time.

Monsters may move after a player moves. A monster will try to move if any of the following conditions apply:

1. The current player attacked the monster this turn. 2. The monster is chasing/fleeing/attacking the current player. 3. The current player is a closest player to the monster.

If the monster tries to move, it compares the turn number of its last move to the turn number of the current player's last move. If the monster's last turn number is less than or equal to the player's last turn number, the monster will move.

For example, suppose a pair of players Adol and Bahn are taking turns attacking a Rat. If the Rat starts off moving on Adol's turn, it can't move on Bahn's turn, and will wait until Adol's turn again before moving. The turn sequence looks like:

1. Adol, Rat 2. Bahn 3. Adol, Rat 4. Bahn 5. Adol, Rat

What happens if Adol waits too long and Bahn moves twice in a row? Then, the Rat will be able to move on Bahn's turn.

1. Adol, Rat 2. Bahn 3. Bahn, Rat 4. Adol 5. Bahn, Rat

In this case, it's possible for Adol to be attacked twice before reacting--but only because Bahn was nearby and Adol's move timed out. In the case of being attacked by an adjacent monster with Bahn also next to the monster, it would have taken at least 8 seconds for his turn to timeout before Bahn could make a move (thus allowing the monster another turn).

3D Representation for Roguelike Worlds -- Jimmy Babcock

All of the nice, simple LOS algorithms typically used in roguelikes break down when you introduce a vertical component. Fortunately, LOS in 3D is extremely important to 3D rendering and has been the subject of a lot of research. Unfortunately, generating BSP trees takes far too long to do when generating maps, and the storage requirements are, for a roguelike, absurd, so that's out.

Portal rendering, on the other hand, could fit nicely. The concept is simple: the world is represented as a set of sectors; each surface of each sector is either a portal (reference to another sector), or a texture (in this case, wall, floor, door, etc.). You should be able to find a good deal of information about this from Google, but there's one extension needed to adapt it to a roguelike.

A given face should have more than one portal/texture; it should be able to have multiple portals associated, and they should be able to overlap, and be stored in order of precedence. Thus, an arrangement like this:

1. 1. 2. ...#

..+...#

1. 1. 1. .@.#
      2. ...#

......#

would be represented as:

Sector 1: area: northwest-top (3,1,3), southwest-bottom (5,5,0)

     North face: (0-2,0-3) rock
     East face: (0-4,0-3) rock
     South face: (0-3,0-3) rock
     West face: (2-2,1-2) door -> sector 2
                (5-5,0-3) portal -> sector 3
                (1-5,0-3) rock

Sector 2: area: northwest-top (0,2,2), southwest-bottom (2,2,1)

     East face: (0-0) door -> sector 1
     etc.

The main room has a height of 4, the passages have heights of 1, and the upper passage is raised 1 above the ground.

I impose the restriction that all sectors must be completely rectangular, so that they can be represented by two coordinates; for textures/portals, I give ranges on the two non-fixed axes. (Note that I omitted the floor and ceiling faces; they are fairly simple to add.)

Once the data structure is done, line of sight is conceptually simple. Start by rendering (illuminating) all of the faces of the current sector, with the clipping region being all angles; when rendering a face that contains a portal, set the clipping region to the area that can be viewed through that portal and recurse. The actual implementation is considerably stickier, and involves a lot of math, so I won't talk about it here.

Map generation is also rather complicated. To place a corridor, we have to create a new sector, and then detect overlaps with existing ones. This is simple, except for a corridor which intersects two or more of a room's faces. If the faces are opposite, you must split the sector in two; if they are perpendicular, then you will end up with problematic overlapping sectors unless you carefully split up the end of the corridor into multiple, non-overlapping sectors.

Moving the player and moving creatures from one portal to another is, fortunately, simple, since a given tile is guaranteed to be entirely in one sector, so when walking outside the bounds of a sector, you need only identify the portal being moved into, and change the sector; no coordinate transformation is necessary.