Looking for advice on procedural mapping an infinite dungeon.

[master.discord@gmail.com]

TL/DR - Trying to build random but repeatable cave gen without saving world data, need help understanding what is necessary.

I was thinking about good old games like Interplay FOTR, Ultima, Diablo, and an almost forgotten game from my childhood: Cavequest. I know the dungeons in the mentioned games were hardcoded, but I was thinking about a combo between Dwarf Fortress and Minecraft, and lots of other ideas swirling around, and feeling like I could make those ideas reality, but I would need to build up my abilities bit by bit. (pardon the pun)

TBH I hadn't though about Angband until I ran into this thread . Then I felt like I had the dumb, not thinking of it sooner.

I decided I'd be happy to start with a basic ASCII map in a console, and I hacked together a program that plunks down randomly sized rooms into a map then displays the map. So far so good. I also have a basic grasp of SDL so I can easily plunk together a tiler if I want to.

But what I really want to be the basis for the implementation, I can't figure out how to do. Here is the general idea:

I want to be able to generate and destroy rooms as needed, based on a seed. The only permanent storage of room data would be if the player has explored the room or changed something associated with it, and that could be freed after some interval. I think, for a possibly unlimited map area, world-coordinates might best be avoided, instead linking one room to another in a tree.

I think the essence of what I'm struggling with here is that even though rand() numbers (from a given seed) have a structure that can be determined and repeated, I can't figure out how to 'grab' numbers from an arbitrary place in the sequence without knowing where that place is. I could store the ID of a room but that brings us back to avoiding the storage of room data.

I want to be able to save the character's position in some form, and have the dungeon capable of regenerating itself from that data, moving outwards from the character's location on load time. Not like Minecraft, where once-explored lands are forever saved as explored (unless removed from the save file and thus regenerated from seed.) Actually, that's almost a perfect example: If MC were unable to store its data of previously explored terrain, any and all (original) blocks in the world can be regenerated from an arbitrary point where the player exists, based on the seed and the player's location. Of course, MC uses world coordinates, which causes the glitches near the Far Lands when variables start to overflow.

Of course I'm not going for the voxelly goodness that is Minecraft, but that's the general idea. I don't need to generate all the stuff between the character and the world origin in order to build the world within the player's immediate reach, it's a function of where the player is and the generator code - a technique I'm struggling to wrap my head around and reproduce.

(AFAIK I think there are SOME things such as water and lava source blocks that may not be tied to seed? Can't recall exactly.)

So please help a noob out and offer any insight into this problem that you might have. I don't really need code examples, but I can't quite pin down a metaphor to understand how to do this.

[Patashu]

One way to do it might be to have a function that pseudorandomly, yet deterministically (and since the rest of the map is deterministic it could use data around it) determines if tile (X,Y) is a room starting tile. If it is, then it pseudorandomly, yet deterministically builds a room, again it can use the deterministic landscape around it to help guide the room to be placed well.

[Derakon]

Okay, so, correct me if I'm wrong, but basically what you want to do is have an infinite playing area where you explore as far as you like in any direction, and then backtrack and have the area you came from be consistent, without actually having to store that area?

Unfortunately, to keep the world consistent, you have to store something about it. That can be the entire world, or it can be a seed of some kind, but it has to be stored.

Let's say you do store absolute world coordinates. For example, say you generate your world in 100x100 chunks. Each chunk has a position in X and Y; we combine those X and Y positions into a single 32-bit number (X * 2^16 + Y), and pass that as the random seed to your dungeon generator. Of course this isn't a truly infinite playing field, but in my example it's 6.5 million blocks on a side (2^16 * 100), which seems entirely adequate. If you needed more, then you could increase the chunk size (e.g. make the map in 1000x1000 chunks instead, now you have 65 million blocks on a side). Or you could use more than 32 bits to indicate position: 2^32 * 100 is about 430 billion. How much time do you plan to spend on exploring?

You mentioned a "tree" approach. Presumably in this method, each sector would lead to the next sector. You'd be saved from having to store world coordinates, but you'd have to remember the "breadcrumbs" that lead from one node to another. For example, you start at node A, then you go to node B, then to node C. You want to backtrack to B, well, B has to remember that it attaches to A. For every node the player visits, you must remember not just the seed to generate that node, but also the connectivities to the other nodes. Now, this isn't much of a memory requirement, but it means you can't make a truly infinite world.

It also has another, less pleasant consequence: the world has no loops in it. Each node is generated without knowledge of the structure or placement of other nodes, so they cannot connect (or, if they do connect, the connections are probably not Euclidean). When A was generated, it probably had several outbound connections, but we don't know what nodes those connections go to. When the player traveled down one connection, we said "Okay, this connection goes to B". Then we repeat that with B to get the player to C. Now, C might overlap A -- or it might be nowhere near A. We have no way of knowing, and thus no idea if it's sensible for C to connect to A.

[master.discord@gmail.com]

Hmm, perhaps using a noise generator to decide where room candidates might be, then check if they're appropriate, and so on. I *think* if I keep track of the offset from the spawn point, (say the noise grid is 100 tiles square, I just count to 99, rinse and repeat) I could use the character's position as the origin. Or something. :s

Beginning to think that C++ is a bad idea this time. It's a great tool but I'm just not schooled enough in all the nuances, and other tools would likely be easier and as effective. (I'm particularly bad at managing memory and pointers, though I can use them when I need to they drive me nuts.) Since I do eventually want to play around with Minecraft mods, maybe Java would be a better option. I dunno.

[EDIT] Derakon posted while I was typing. Unfortunately I don't have a deep or broad background in computer science, I've just been playing with it since I was a child messing with LogoWR and making Nibbles in QBasic crap itself. Anyway, I see what you mean about the world, and my example of Minecraft does exhibit the same limitation of EVENTUALLY reaching the limits of the generator. Certainly I didn't mean to imply I wouldn't save the seed, but if the world can be regenerated from the seed in some fashion, I'd rather not store the tile data at all. I did also consider the issue you mentioned with the tree format, and that's part of the reason I thought it might be less than ideal.[/edit]

I'm definitely going to keep pounding on this problem, but I've come to the conclusion that I'll need a little more help/experience before I'm really ready to tackle it, so I'm going to start working on the other parts necessary for a playable game, putting in a cheap, file-based mapper while I try to figure it out.

I have a general plot and setting figured out - though it's just a version of the cliche "you've been chosen by X, Champion! Go into the dungeon and find baws lewt!" I think it is a little different than what I've seen before. I've also got what I consider to be an interesting mechanic in mind for deaths, experience and equipment. I think I'll start off with turn-based combat, I've always preferred it to button mashing. I also have a mechanic in mind for doors/locks that may be fun and interesting, idk. I've always hated games in which you're blocked by some random wooden door/object, you have a fireball, or a Big Effin Axe but can't remove the obstacle (in one game I was blocked from my desired destination by a simple rope and my BFA was useless). Definitely gonna have door bashing.

[Nick]

I am doing this for http://nickmcconnell.github.com/Beleriand/ - most of the relevant C code for it is in this file.

Essentially, I am using Derakon's world coordinates approach, with seed determined by coordinates (plus some per-game randomness). I keep a big list of all chunks that have been generated.

The tricky part comes with how to do the looping thing - if you have to generate a chunk which will be adjacent to one previously generated, how do you make sure they fit together seamlessly? The two approaches I considered were

1. Regenerate any previously done chunks or
2. Store details of the borders every time you generate a chunk.

In the end I went with 2; the problem I saw with 1 is you could get a lot of recursion.

[fizzix]

I think you have to do this in chunks. Exploring far enough in one direction generates a new chunk. If you make chunks variable in size, then you can avoid some of the artificial blocking feelings that arise. If you feel a little freely about coordinates you can just have chunks connect to other chunks regardless of whether they actually "fit" on a large map. If you care about coordinates you can fit them in with long connecting corridors.

If you want to have a fully scrolling map this all gets a bit tricky, especially around corners where 3-4 chunks may coexist. Of course depending on your approach. If you are ok with moving between chunks with a full screen refresh, you can get away with a lot of geometrical impossibilities.

When you create a chunk you need to determine the number of connections between the chunks and what direction they lie relative to others.

I would recommend starting with uniform chunks in a grid with a set number of connections between them. Then once you get that working let one of the dimensions (width) be variable but the other constant (or constant for an entire row). Once you get all that working, you can decide whether alternate sizings are necessary or whether this approach is close enough to the illusion you want to create.

If you go room by room creation then dungeon structures that aren't trees are difficult to create. You can do it though. When a character goes down an unknown dungeon path it can choose to link up with a previously created but unexplored path. Random intersections and rooms can be placed along the way. You do need to keep track of quite a bit though and I'm not sure how much you actually gain over just creating a somewhat large section to begin with.

[master.discord@gmail.com]

More good ideas, and they're most certainly helping to solidify things in my mind.

What if I were to generate a large block of noise, using something fast and low-overhead, based on a world seed. That block could be thousands or millions of units per dimension. The value of cel[x][y] would be the seed for chunk[x][y], and would begin to repeat, should the player reach the edge of the noise block. I'd probably have chunks link up like Wang tiles or Herringbone tiles, where each chunk is capable of connecting to other chunks only at certain points (center NSEW edge is what I'm thinking), and is otherwise self-contained.

Not quite sure how I'd go about using variable sized chunks, unless they could fit together into larger, uniform chunks.

Kinda thinking of a "deep roads" layout now, where there's a single wide highway that proceeds indefinitely in the horizontal axis with a small meander for interest, and other systems branch off of that. Some might be nobly furnished, others might just be caves or mines or even creature burrows.

Hopefully discussing it and getting ideas from others will help cement things into something that I can actually build. If at all possible, I want to make this code compact, tight and reliable. It doesn't have to have all the bells and whistles, but it needs not be the War and Peace of map generators.

[Derakon]

What if I were to generate a large block of noise, using something fast and low-overhead, based on a world seed. That block could be thousands or millions of units per dimension. The value of cel[x][y] would be the seed for chunk[x][y], and would begin to repeat, should the player reach the edge of the noise block. I'd probably have chunks link up like Wang tiles or Herringbone tiles, where each chunk is capable of connecting to other chunks only at certain points (center NSEW edge is what I'm thinking), and is otherwise self-contained.

There's no need to generate the large block of noise if you're just going to use it as a further seed. In fact, I believe that feeding the random number generator into itself actually reduces the noise you get (I've read that this is the case, but not read why it happens). Just use (x, y) as the seed for the chunk, as I suggested earlier.

[master.discord@gmail.com]

Sorry, I suppose I missed it the first time. Now that you mention it again, that makes perfect sense. No need to multiply randoms together or anything like that, it doesn't help.

[Patashu]

There's no need to generate the large block of noise if you're just going to use it as a further seed. In fact, I believe that feeding the random number generator into itself actually reduces the noise you get (I've read that this is the case, but not read why it happens). Just use (x, y) as the seed for the chunk, as I suggested earlier.

It's because skipping values makes the period of the RNG quicker.

A good case study of what happens when the RNG is called a variable number of times, based on earlier output of the RNG, is the board setting up RNG in Minesweeper: http://www.minesweeper.info/wiki/Board_Cycles

[master.discord@gmail.com]

Neat article. It follows more or less with what I gleaned in my understanding about PRNGs.

[Patashu]

Neat article. It follows more or less with what I gleaned in my understanding about PRNGs.

It won't be a problem on any modern PRNG though, since the periods are so massive and you can grab 64 bit random numbers instead of 8 bit random numbers.

[LostTemplar]

Also it may be nice to write dungeon generation without any chunks, just make a function, which generates rectangle of tiles with the given offset. IMHO tile-base approach is better, then chunk-based. You need several pseudo random but deterministic functions to generate various features on the map, e.g. rooms, so most of the tiles will have no rooms, and maybe one out of 1000 will have a room centered on it, then some algorythm to actually place this rooms and connect them, then go to the second layer and place traps, etc.

[fizzix]

Also it may be nice to write dungeon generation without any chunks, just make a function, which generates rectangle of tiles with the given offset. IMHO tile-base approach is better, then chunk-based. You need several pseudo random but deterministic functions to generate various features on the map, e.g. rooms, so most of the tiles will have no rooms, and maybe one out of 1000 will have a room centered on it, then some algorythm to actually place this rooms and connect them, then go to the second layer and place traps, etc.

The trick is connecting rooms to already explored areas. If you do this, you need to prognosticate the existence of the room in a past area. If you don't you are left with a tree structure which is fairly boring.

[Tobias]

A straightforward way to generate a block in a pseudorandom stream would be to take a counter ( or the coordinates of a chunk in your case ) and encrypt it.

The cyphertext will be your pseudorandom block. The chunk coordinates are the plaintext. And the passphrase is your dungeon seed.