Castle Paradox

[Mr B]

I have lately been considering different algorithms for generating random maps. I realize that I have no real conceptual experience or reference from which to develop this, so it's a bit of a puzzle for me.

I have a few ideas as to how the job can be done, but they all seem rather...wrong, in a programmer-senses-tingling way, if you catch my meaning.

All of the methods are for developing maps with very basic walkable-impassible tiles (resulting in two tile types), and probably stairs.

1.) Column Generator Method. Sort-of the simplest way. Start in a corner of the map and generate rooms of random but constrained dimensions. Place a room so that its wall is "on top of" the wall of the most recent room and (probably) a previous one. So if I start from the top left corner and work in downward columns, the rooms in the second column would try to snuggle over to the ones in the first column as much as possible without overlapping other rooms. Doorways/openings would be places pretty logically.

2.) Crystal Growth Method. Place a random number of "room seeds" in random locations on the map. Expand their dimensions incrementally until they start bumping into each other. Rather difficult to figure out how to place doors.

3.) Scattered Hallways Method. This method is the first to actually use halls instead of just openings between rooms. The blank map is filled with several hallways of all different lengths and directions. The location of each intersection between hallways is noted, and "room seeds" are placed at those locations. Rooms are then grown as in the crystal growth method, though probably not to the same extent (leaving lots of hallway areas).

4.) Subclass Method. This uses the programming concept of subclasses (as I am thinking of it here, some things being more specific and tightly-defined derivations of others). The basic "class" is a hall. Halls have two subclasses; "junction" and "room." (think of a hall as a place where you can move, and a room as a big fat hall). Junctions generate other halls splitting off from a central point, and rooms generate...rooms. The basic room can (and will) have subclasses, probably doing stuff with different shapes and mazes and who-knows-what.

In this method, the blank map starts out with a single hall object possessing a random location, direction, and length. It "travels" to its final length, at which point it chooses between three options; generate a new instance of its own class (make a new hall), generate a new instance of its junction subclass (thus forming branching halls), or generate a new instance of its room subclass (thus forming a room).

If it chooses a new hall, it will look at the available space in the three remaining directions, choose one with a reasonable value, then proceed in that direction until it decays again.

If it chooses a junction, it will send out new halls in up to three of the remaining directions, depending on space.

If it chooses a room, it will determine the space available to make a room, then generate a room that does not exceed that space. Once the room is finished generating, it will (probably!) generate new halls from appropriate points in the room wall.

Basically, every time a new object is generated, it will randomly decide whether to become an instance of its own class, or that of a subclass. If it chooses a subclass it will decide whether to be an instance of that subclass, or an instance of its sub-subclass. And so on. This means that when a room is generated it might be a simple blank room, or it might be a pillared stadium or a cell block that contains other rooms. This means that the first hall may end up not being a hall at all, but the point is that the basic halls have the most potential to become anything because they're highest up.

5.) Wall Generator Method. Instead of constructing open areas in a default impassible area, this method generates walls in a default open area. It starts out with a simple wall that sends out tendrils that send out tendrils until the distances between walls are small enough that no new tendrils are made. It wouldn't generate hallways, but I don't need halls in order to survive.

Of course, this method means that the resulting rooms, while having interesting shapes, will not be easily navigable or -- more importantly -- contain anything interesting (after all, it's not making rooms, it's making walls).

Problems: #1, 2, 3, and 5 all share the problem of not being able to guarantee that rooms will be accessible to each other. It's entirely possible that the dungeon could end up dividing into two or more areas that do not connect. #4 (Subclass Method) circumvents that by growing areas that are by definition connected, but there is no way to guarantee that it won't generate itself into a corner, so to speak; it could loop back on itself and get trapped (though the fact that junctions send out multiple halls will probably prevent this -- none-the-less, the weakness is still very much present).

What do you think? Am I barking up the wrong tree? Does anyone know of any resources should I be looking at to understand this weird, promising world of random map generation?

[PlayerOne]

I've looked into this a bit, but didn't reach any really satisfactory conclusions. One possible resource is roguelikes. They tend to have random dungeons, and there are quite a few sites and sources available on the web. It seems likely to me that different methods would be needed for different styles of map. A corridor/room map like classic Rogue needs a different style of generator than a natural cave map.

One method I was once considering was combining a maze algorithm with pre-fabricated sections. The sections would be made so that the entrances and exits all lined up, and the maze algorithm would decide which sides of each section were connected. That was mainly because the tool I was considering at the time couldn't handle programmatically-generated maps.

[Mr B]

Yeah; what I have in mind is inspired by [url="http://www.thangorodrim.net"]Angband[/url], mapwise. I didn't really think of them having creation tutorials *headsmack*.

And in terms of what you said, I believe that Angband uses prefabricated rooms for all except the simplest rooms. You can see their templates if you open the right file.

After making my first post, I realized a couple of things. For starters, the strategy that #4 pursues would create a bit of a bottleneck -- there will be only one path from one point to any other point, because hallways will never connect with anything else. I suppose that I could fix this by simply allowing halls to connect to other things, but that seems a little cheap...I don't know if that would work. And of course, the halls would have to be able to detect that they've hit something so that they would just die when they decay.

The other thing I realized was a new strategy.

6.) Shotgun Method. This method generates rooms at different locations on the map. Each room is provided with one or more nodes. After all of the rooms are created, hallways are generated to connect the nodes.

This method is simple and conceptually pleasant. The only problem I percieve is creating an algorithm that allows hallways to connect to nodes without crossing other hallways or rooms. It would involve some sort of least effort algorithm... Something that recieves a set of points and connects them to form a net, where no two strands of the net cross over each other. Urg.

Can't figure out how to use the stinking url tag. Sorry.

[PlayerOne]

Here's a url I seem to have saved while I was researching the subject:

http://www.roguelikedevelopment.org/

I can't remember how useful it was.

[Mr B]

It's a decent link. I'm going to catalogue it.

*catalogues it*

I guess the main thing for me to do is to not obsess over it at this stage. Making something too technical too soon results in making something too technical never.

After all, the OHR has a bit of memory limitation regarding map saves. Pace yourself, pace yourself.

[msw188]

I'm not sure I quite understand this topic.

Are you trying to make dungeons generated randomly in the middle of a game? If that is the case, I'm not sure that the OHR is well suited for this kind of map-scripting, so to speak. Especially if you need the map to stay stable through random-battles, doors, etc. NPCs could be a pain as well (how to randomly place them? how to make sure they don't get caught somewhere where there is only a one space passage?).

Are you trying to have a separate program generate a dungeon for you, and then 'copy and paste' it into the OHR? If this is the case, then your problem in #6 can be easily circumvented using multiple floors for halls to 'cross over' each other.

The problem with disconnectedness still exists, however. A 'least effort' algorithm could solve this, but it will itself overrule your 'nodes', I believe, and then this and the 'Crystal Growth' method basically become one 'random room seed' method. Seems to hold the most promise.

Okay, I've thought about this for a little while, but I'm not getting anything effective. I had some graph theory in college, but only one introductory programming course. I'm starting to lean more toward number 4 now. What about disabling any kind of 'available space' check with the hallways, and begin by only generating these halls and rooms as 'walkable' tiles. In this way, if you create rooms and halls that overlap, you just get a new, stranger-shaped room, or adjoining halls. Walls are only added at the end, placed on any unused tile that is next to a 'walkable' tile. Keep track of a 'distance from starting point', and if this is not increased in, say, three room generations, point the next hallway away from the starting point...?

[Mr B]

Yeah, I'll probably end up doing something similar to that. It's very much up in the air, as this is at least one or two large projects away from now (so who knows if it will ever see the light of day?).

Thanks for the input, guys. I should get something together.

[planethunter]

I think you should start with something simple, such as just two tiles a water and land tile, randomise it in such a way that a player can safely move around a continent (i.e. enough land tiles to move around) but also enough water tiles for lakes and perhaps rivers.

Mess about with something simple like that before you go on to creating rooms and such. I think Moogle1 made an example "random world generator" script for that purpose.

When you are making rooms, the co-ords of those newly created rooms should all be stored (somewhere, with locals or globals, preferably globals) and make sure that no new rooms are created "on top of them" by using the existing stored co-ordinates as a database, and anything in, say... the co-ords minus the length of the room created is a minus figure... then create it beside it, i.e. zero tiles away from the room in question that's there.

To help fix the problem of the dungeon being too spread out or cornered... let the first room or hall be random... but within a certain range of the centre of your map. Then apply your crystal growth method. Try to think of it as if you were making this map in the OHR yourself, if you were making a dungeon, and you weren't sure where you were going to go with it... wouldn't it be best to start in the middle? That way you don't limit your design, as your making it.

As for map saves, leaving the map and such... can't you save the tile co-ordinates in global variables? They get saved along with the game. The limit ages ago was a hundred though... I hope that's been upped. There are scripts available to get more out of your variables, as far as I know you could use them if you really needed to.

I understand that my explanation isn't very clear, I'm not very good at explaining longwinded things such as this... but I'll take the time to write some code as soon as I can, that way it'll be much clearer. Apologies for the long post, I tried to make it as concise as possible.

[Moogle1]

The random world generator was intended to make landmasses, but IIRC it never went to the trouble of connecting any of them. It was also way, way too slow to be of any use.

It does give me an idea, though -- if there were a plotscripting command to reseed the RNG, one could reproduce the same randomly generated dungeon based on just one number. Does anyone know if the OHR uses the QB built-in RND function or if James programmed his own?
_________________

Slime Salad :: Independent Game Design

[Mr B]

I'm pretty certain that the RNG can be reseeded...I remember seeing a reference to it some time ago. I'll have to puzzle through the plotscript declarations file again -- I think that's where I saw it.

Either way, I'll let you know.

[Mr B]

Pardon the double post...the two posts cover very different things.

I believe that the OHR permits 999 global variables. If I save one tile per variable, it would give me a 30x30 map...almost larger than the screen.

No -- I think that I should probably be able to save multiple tiles per variable. Especially if I use merely two types of tiles (wall and floor), or four types of tiles (wall, floor, undiggable, monkey), I could store 16/2 = 8 or 16/4 = 4 tiles per variable. That gives me a map of size sqrt(999*4) = 63 tiles by 63 tiles.

I am not certain how I would store these values, though it could probably be done...I don't think that the OHR AND function would give me the capability...I could always just divide and then muliply to clear out lower-value numbers.

In any case, I won't be storing these values in the save slot itself...I would probably have several save slots chained together for data storage.

Either that or I could regenerate the dungeon like Moogle1 said. The only problem that would give me is that the map couldn't be dynamically modified after being generated, but how necessary is that? It would probably depend on which method would load faster.

*rumenate* I probably wouldn't be able to get 16 bytes of data from each variable, as the last byte (first byte...) is concerned chiefly with charge...er, negativity. Sommat.

[Moogle1]

The number of variables is a little over 1000 -- 1025 if I remember correctly (0-1024). No, I can't think of a good reason why, either.
_________________

Slime Salad :: Independent Game Design

[Mr B]

*coughahem* I looked in plotscr.hsd and found this function reference: