Really stuck generating a corridor creation algorithm for rl

[foxfire29]

Hi all,

I am developing a basic roguelike, I have a ok UI in place and for the first time I managed to make my dungeon rooms generated at random, this works well, I also place a single door at a random location in each rooms however I cannot for the life of me envisage how to connect these rooms up with paths, could someone explain to me how I can do this in a procedural way?

My current system works as follows:

I have a SCREEN array which has all the asci in it e.g '#' , '.' and '+'
I have an SFLAGS array which clones the screen array except that it has the following in the array :

#define FLOOR 0x1
#define WALL 0x2
#define ROOM 0x3
#define DOOR 0x6
#define UIHPBAR 0xA

I have a third array named PFIND which is made up of:

#define NCONN 0x4
#define CONN 0x5

(NCONN = not connected, CONN = connected)

for the PFIND array Im not sure if I have done things correct, basically everything gets marked as CONN except the room walls which are NCONN

I have another array called COORDS which is a 1d array only and is the format off

coords[x] =<room number>
Coords[x+1] = <rowCoord>
Coords[x+2] = <colCoord>

I could have saved on the arrays by using structures but I will tidy up later.

so in essence I have say 2 randommly generated rooms

####### ###+##
# # # #
# + ######
#######

I am unsure how to get the paths to connect the rooms from this setup and its the only aspect I need to understand and I know I can make a roguelike since I have done other aspects

note the formatting of my room is lost

also what constitutes a path in my rl is something the is 3 squares with , is bordered with 2 walls and has dots in the middle
Any help is greatly appreciated

[Grey]

I don't know myself, but I can direct you to some related pages on RogueBasin (a centre for roguelike development knowledge):

http://roguebasin.roguelikedevelopme...geon_Generator

http://roguebasin.roguelikedevelopme...tract_Dungeons

You could also try asking on rec.games.roguelike.development.

[foxfire29]

Thanks Grey!

Today prior to reading this I was coding.

Anyway out of 100&#37; my own newbish code I have pretty solid rectangular room random generation , and I can now join 1 random room to another random room that is down and to the left of roomA

I just need to altar my code so that every room in the array does this.

However going through this now I can see much differant ways I would do it in future such as storing room centers and that way I can class everything as a feature and join cool rooms and paths to other cool rooms and paths, however I want to stick basic until I have a complete project

Anyway I actually posted to say that the links you submitted at a quick glance seem to be what I am looking for, thanks! Just checking them now

Really appreciate that Grey, also no worrys about saying you are unsure yourself, to be honest Im just learning anyway

[Grey]

A hot tip I've heard other developers mention: use rooms of size 1x1 to help section up corridors and cause more loops around the dungeon. A good dungeon generator should loops instead of just branches so that you can successfully run away from enemies or find alternate paths. ADOM in particular is great for this.

I've developed a couple of roguelikes, but never gotten the knack of room-based dungeons. Instead I've done organic cave systems, which I've found a bit easier to do.

[Dorten]

The thing that worked for me was: make a room, make another room, try to shoot corridors in random directions, until one connects to first room or old corridor, etc. Add corridors to make loops.

Can see this here somewhere. Look in StGenerator.py

[Al-Khwarizmi]

You can check the dungeon generator on my unfinished RL project, it generates very ADOMy dungeons:

http://code.google.com/p/dairl/sourc...Generator.java

Example dungeons (not from the latest version, some glitches were removed in the source that I linked):

http://irreality.eu/rl/several80x25.txt
http://irreality.eu/rl/300x300.txt

What I use for the corridors is something like the following:

- Choose a random point (the representative point) in each room.
- Connect both points by a pathfinding algorithm. I use the A* algorithm so that I can enter things into the heuristic function like forbidding two corridors that run together, penalising corridors that have too many corners, etc. But for a first approach you can just use a greedy hill-climbing approach, i.e., start at one of the points, and at each point dig towards a direction that decreases the distance to the goal point (there may be two such directions, and you can use any criterion to choose among them - different criteria will produce different corridor shapes).

[nathrakh]

Hey, those are quite nice dungeons, but I don't like the double doors. :-P Nevertheless, good work!

[Al-Khwarizmi]

Removing the double doors was one of the improvements made after those "screenshots" were taken. If you get the code from the repository, it will generate dungeons without them.

[foxfire29]

Hey guys,

This may be perhaps seen as a sad indictment to some of the irc C development rooms I have tried thus far(Just 2 affiliated ones on the same server) but the advice and source provided by you guys has helped the most; easily the most!

I have been spending the day reading up and completely redone my basic procedural rectangle//square room level generation. I have spent ages preparing the code into c structures, for example I have a Point structure for which a pointer to that structure is in the Lists structure, the Lists structure has a pointer to OpenList and ClosedList structures which I intend to use with the A* algorithm , the Lists structure has 2 global arrays

Lists Open_list[HEIGHT][WIDTH];
Lists Closed_List[HEIGHT][WIDTH];

I also have a structure which handles RoomData and holds a ton more info such as:

room number
struct Point p -> this points to respective h and w (height and width) --This is just pseudo code btw
Top left corner
top right corner
bottom left corner
bottom right corner //this may be overkill but this time I dont want paths joining at corners
roomcenterh
roomcenterw <------this is where I may have my A* node? or center - Topleft corner w (e.g col)
I have a host of other stuff as well such as all the rooms coords etc

One thing for the A* algorithm I flag the screen wall '#' boundry as unwalkable, however should all room walls be unwalkable? I assume yes , however when I do the algorithm I grab say the first and next found room in the screen array called

A & B

I then work out the path to B from a using the algorithm

I am about to start that but I am unsure as to when to cost everything, in essence you have

F = G+H

G = movement cost I think
H= heuristic ,
F= result

so say I do all horizontal and vertical squares as 10 and all diagonals as 14 , Im assuming this is movement cost, what I still dont know is how to put numbers in for heuristics, a tutorial Im about to share Is brilliant and I am still reading but I need to see the guys source which I am about to look at. I think I understand most parts in theory of A* but I am unsure of how to number each grid square properly, I was thinking of having in some struct

int Heuristic
int MovementCost_G
int F
Point p -> <somepoint struct with x and y>




>###<14 ----then on this square tut has 40
>#S#<10 30
>###<14 40 <<it is the second numbers I am unsure of how they get calculated, which base number arwe they using to get the total? 40 for this square, I assume something had a base of 30 at the start would that be the S square?

once I can reliably number all my squares I am at the last couple of stages! heres the tut:

btw This will hopefully help people who struggle getting room based dungeons to work:

http://www.policyalmanac.org/games/aStarTutorial.htm

anyway I am away on ADOM , I have made progress and my random room placement is reliable now, it never chooses a room location outside the boundries of the screen nor on top of my ui and I can specify the number of rooms to attempt per dungeon as well which is good for testing out this A* algorithm. I plan to just generate 3 random rooms and grab the first one and third one as a one of test, I will spam random room generation until the second room impedes the path between room 1 and 3 and hopefully I can learn A*

To be honest algorithms (although I have done some basic ones in the past) scare me somewhat, however after try a purely logic based solution to pathfinding, it is messy as hell! so I am going to try and learn this and once I get to grips with it way down the line so its second nature I will consider alterations but with the coding ive done I think A* is the way to go.

Although I have much cleaner code now I have been coding for hours so I think I should sleep on it and start trying to immplement A* with a clear head

Thanks again all

[Al-Khwarizmi]

roomcenterh
roomcenterw <------this is where I may have my A* node? or center - Topleft corner w (e.g col)

You could have it either way. In fact, in my version I choose a random point in each room (called the "representative") and I create paths between those representative points. That means that sometimes a path can start at a corner of a room, other times it will start at the center of a side, etc., giving a quite varied look.

One thing for the A* algorithm I flag the screen wall '#' boundry as unwalkable, however should all room walls be unwalkable?

Not necessarily. In my version they aren't unwalkable by the A* algorithm. A path found by the algorithm between two rooms will typically go from the representative point to a room wall, then it will cross the wall, and finally it reaches the other room, crosses its wall and goes to its representative.

What I do have though is a tweak by which vertical walls (both of rooms and corridors) are only diggable in a horizontal directions, and horizontal walls only in a vertical direction* (I got this idea from someone in r.g.r.d). This prevents things like corridors running right alongside rooms and "enlarging" the rooms, or double-width corridors. But if you add this it should probably be later, when you already have a working algorithm.

what I still dont know is how to put numbers in for heuristics

You have to use an estimate of the total cost from each node to the goal node. And it must be an estimate that never overestimates the total cost.

For example, if the cost of travelling one square in the up, down, left and right directions is at least 1, a good estimate is Manhattan distance: | x - xgoal | + | y - ygoal |. Check ManhattanAStarHeuristic in the code I linked to. What I do is, use that heuristic, and add cost penalties (to the cost, not to the heuristic!) to things that I don't want to happen (check the operatorCost method).

With these considerations you will get an extremely flexible dungeon generator that you can configure in a lot of ways by changing things such as the A* costs.

* Actually these walls are not really undiggable, it's just that I assign a huge cost (in A*) to digging them in those directions, so it will only happen if the algorithm is really desperate and has no other choice.