Every story ends somewhere...

[Super Vegeta]

Like SilverWarrior said, I'd create a classification of room types and only allow specific types to connect to each other. You must also take into account how the room exits must be aligned for everything to work properly. Then come the corner cases of no matching tiles - keep a dead end, or try to replace one of the neighbouring rooms? Also, if your maps are to serve some purpose (like a dungeon where you must find a certain chests) there must be a path from the start to the chest room.

I think it would be simplest to have a set of rooms - each room may have a different size, type, and a list of exits. You start generating the map with an exit/entrance tile, and then try to add neighbouring tiles to the existing map.

[SilverWarior]

I think it would be simplest to have a set of rooms - each room may have a different size, type, and a list of exits. You start generating the map with an exit/entrance tile, and then try to add neighbouring tiles to the existing map.

Yes using of predefined map chunks is also a good idea especially if you wan't to join multiple rooms into a whole map.
If you wan't to see this implemented in another game check out UFO Enemy Unknown, UFO Terror From The Deep, UFO Apocalipse or UFO Alien Invasion how they have implemented base map generation where each rom is prebuild and you are simply placing these rooms on your base layout.
There are probably other games which use similar approach but I can't remember any of them at the moment.

[Darkhog]

Well, I think it probably will be even simpler than you make it out to be as game is a text adventure (lookup Zork for example of one). So all rooms are largely "imaginary" and exits (north, south, east and west) are perfectly aligned - it's just case of whether or not two rooms have exits on the opposite sides (e.g. room that is connecting to one with exit at west MUST have exit on the east).

Also instead of "room types" (though those are still used e.g. so dragon won't spawn in middle of house or somewhere as much insane) I've devised system that I think is more flexible.

I've call it disposition system for some reason (dunno why anymore it is called that way, don't ask me at the time it made sense now it doesn't). The room can connect to other room when difference between disposition values of those is smaller than 3. The rooms that you spawn in at the beginning of the game always have disposition of 0 and aren't considered for spawning when going to another room (i.e. in whole playthrough you'll see only one room with disposition of 0, at the very beginning).

[SilverWarior]

Is this "disposition" something like room dificulty where room with disposition of 0 is the safest one?

[Darkhog]

No, more like factor deciding if room can connect to another.

Let's have an example. There are few rooms with different environments in that

1 - It's a simple grassy plain
2 - A forest
3 - Cave
4 - A meadow
5 - Hills
5 - Mountains
6 - Castle grounds
7 - Castle entrance
7 - Tower
9 - Castle hall
10 - Throne room

Since plains (disp. 1) can go well with a forest or a cave, it can even connect to a meadow without any jarring results, it gets disposition of 1. Meanwhile, it'd be bad if it'd connected to e.g. Throne room, but with difference between disposition of throne room and plains higher than 3 that won't ever happen.

Now more interesting case: Caves (disp. 3). It can go well with plains, forest, meadows, heck, it can even happen on hills, mountains or even near castle grounds. Hence it has disposition of 3. Works similarily for the rest.

Because of this system I don't have to invent algorithms that says what goes well with what or make quadrillion table fields, just plain simple math. Cleaner solution IMO. And if something is connecting where it shouldn't, I just need to adjust single numeric field.

As for disposition of 0... well that's kinda special case. Those rooms are designed as adventure's start. You certainly don't want to enter room with description of "You wake up on some grassy plain", hence they won't generate ever, except as first room (which will be closed after you exit it, dunno lore details for it yet, but it will happen).

[SilverWarior]

That is pretty nice idea.

Have you already made a mapmaking algorithm? I could think of a few choices which you can use:

Modified Perlin Noise Algorithm: http://freespace.virgin.net/hugo.eli...s/m_perlin.htm
With Perlin Noise Algorithm you could easily generate sort of heightmap image which you the use to determine the disposition for diferent parts of map (brighter the collor higher the desposition is).
Now the problem with original Perlin Noise Algorithm is that usig it it would probably generate you multiple areas with disposition for throne room. That is why I recomed you modify it in a way so that you generate its first octave yourself making sure only one point reaches the maximum disposition and only one point having minumum disposition (starting point). I can help you with this since I have a working Perlin Noise Algorithm somewhere that I reimplemented myself so I can make necessary changes t it.

In secoond idea for map generating approach I would use something like this (map is basically a cell grid):
First make some sort of list (open list) in which you will store map cels that still need to be processed.
Then make another list (closed list) to store already processed map cells.
Then use something like this:
//Placing starting position
1. randomly place your starting point somewhere on the map (asigning it X,Y position)
2. then add all four neighboring cels to an open list
//By using brach out system iterate through whole map assigning disposition values
3. now randomly chose one of the cels from open list and asign new dispositon value to it
4. add all neighboring map cells to the open list
5. move the cell from open list to closed list
6. repeat steps from 3 to 5 untill your open list has no more items (you have processed whole map)
//Making connections to neighboring cells
7. read first cell from open list
8. check the disposition value of each of neighboring cells to see if there can be valid path connection to them
9. repeat untill you have processed all map cells
If you don't want all gird cells to be part of map you can go and randomly remove some of them before your begin making room connections.
Main advantage of this algorithm is that you can actually have different map cells which are actually neighbors but don't have direct path between them (one cell is in the canyon and nother is on the canyon ridge for instance).

Now which ever algorithm you will use you probably don't wanna have multiple throne rooms so you have to make sure of that.
Also acording to your disposition list you may end up with lots of Castle grounds, Castle entrances, Towers and Castle Halls which can be on the other side of the map than the castle hall is. In order to avoid this I would use next rule:
- if cell with disposition of 9 can connect to Throne hall only by passing cells with disposition of 6 or higer then it is Castle hall else it is City hall
- if cell with disposition of 8 can connect to Throne hall it is Tower else it is City market district
- if cell with disposition of 7 can connect to Throne hall it is Castle entrance else it is City edge
- if cell with disposition of 6 can connect to Throne hall it is Castle grounds else it is vilage
Using this rule you make sure that all castle parts are connected to each other. It also gives you ability to have multiple towns and vilages on your map which would make your game even more interesting since you get more different room types.

If you have any further questions about implementing of each of theese aproaches (whichever you chose) feel free to ask. I will help you best as I can.

[Darkhog]

That is pretty nice idea.

Have you already made a mapmaking algorithm? I could think of a few choices which you can use:

Modified Perlin Noise Algorithm: http://freespace.virgin.net/hugo.eli...s/m_perlin.htm
With Perlin Noise Algorithm you could easily generate sort of heightmap image

First of all, thanks for an insightful post. Unfortunately perlin noise has no business here. This is text adventure game. It does have no graphics. It's not even an ascii art. It's something like this:

You are waking up on a cave floor. To your left there is a water pool. To the north there's a meadow. What do you do?
>_

So any kind of heightmap won't do a trick here, if anything it'll slow down generation. I'll use probably something like your second idea though heavily modified. And yes, in my idea there can be cells that don't have direct connection, but my algorithm makes sure there are always path. Also it generates cells only in direction room has exits (unless one is already generated like one player came from), so if room has only exit to the north, it'll only generate new room in that direction, of course making sure generated room has exit at the south, so player can go back if necessary.

And no, I haven't start coding yet (just done interface, game's is LCL-based as I don't like DOS prompt which may or may not work on new Windows version some time in future and has very small font by default on higher resolutions.

Getting back to the topic, I haven't started it because I first need to build big enough db of rooms so testing can be done properly. After I finish base code, it'll be just matter of adding new content to the db.