Preventing Cascading Worldgen with Large, Randomized Structures

[TheXFactor117]

In one of my projects, I have a simple procedurally generating dungeon algorithm which generates the mod's dungeons. I've recently decided to rewrite to be more complex and accommodate more features than before. Before I do this though, I wanted to generate it in a way that it won't cause cascading world generation, which the current algorithm doesn't prevent. Right now it works kind of like this: I'll generate a structure on the surface somewhere, which will spawn staircases underneath it. From there, rooms can branch off of these staircases, and each room can generate new rooms off of it and so on until it reaches the maximum amount of "tries". This is done through recursion which is simple enough to do.

 

So I've been trying to come up with a way to prevent the cascading generation from happening because it's not as simple as just adding an offset. I won't know how many chunks the dungeon will take up until after I generate it. I'm wondering about what the easiest solution to this would be. Could I generate all of the parts of the structure that are in loaded chunks only and then generate the others once those chunks have been loaded? I think that's the fundamental solution but how would you go about knowing/storing where a structure should be, and then generating that structure when the chunk is loaded? Maybe this isn't entirely right and there is another way around it, I'm not sure. Anyways, any help on solving this issue would be much appreciated.

[Alexiy]

In theory, when an event is fired to which your generator is subscribed to, you should be able to get chunk's X an Y. Then while you generate the structure, you have to continuously check whether the next generated block will trigger generation of new chunk. If the blockpos is within current chunk, proceed generation; if not, then store this blockpos and maybe chunkpos in a map, perhaps. Then on next event you check whether the new chunkpos corresponds to any of the stored chunk positions and proceed generation if it does.

You can also find a way to track current chunkpos of player and based on it, pick chunks from the loaded ones and do your thing more safely - still, will have to start checking once the chunk positions are close to the border.

[Draco18s]

3 hours ago, Alexiy said:

In theory, when an event is fired to which your generator is subscribed to, you should be able to get chunk's X an Y. Then while you generate the structure, you have to continuously check whether the next generated block will trigger generation of new chunk.

Actually....

You want [inside the current chunk] + (8,8)

Due to the way Minecraft generates chunks, you want to always offset by 8 blocks in the positive X and positive Z directions. The next chunk in that direction are guaranteed to already exist. 

Edited August 21, 2017 by Draco18s

[TheXFactor117]

I don't think that's the best solution, at least in terms of what I'm trying to do.

 

I've been digging around in vanilla world generation (Stronghold/Village generation) to figure out how they generate structures without causing runaway chunk generation. It looks like vanilla generation (say a Stronghold) will generate the positions of the Stronghold and store them somehow (MapGenStronghold#generatePositions looks like it does this, but I don't see how this works fully). Somehow the Stronghold's StructureStart gets a list of components to be generated and builds them out. Anyways, I think my conclusion is vanilla world generation is a mess and is hard to trace and track down how everything works.

 

As for how to fix this, I'm thinking the easiest thing is to generate a "virtual" dungeon through the algorithm, but not to build anything during this time and storing each structure in a map. Then I would generate it when chunks are loaded and everything is ok for it to generate. The problem is, how would I go about generating it this way? Is it even possible?

[TheXFactor117]

Potential solution: When I go to generate the dungeon, instead of building each individual room during generation, I'm thinking I can just generate the positions of each individual structure and store the position and template into a map. If the bounding box of the structure intersects with the current chunk (which has an offset), generate the corresponding room. If it's outside of the currently generated chunks, it won't generate. As new chunks are generated through the WorldGenerator, I'm thinking about looping through all the pending structures, checking to see if the bounding box of the structure intersects with the current chunk and if it does, generate it and remove it from the map.

 

I'm not sure if this will work properly, so if anyone happens to find a flaw in it, I'd like to hear it before I try and implement it. If it sounds good, I'll work on implementing it.

[Alexiy]

Have you looked at mineshaft code? Might give some hints, too.

It's kind of difficult to abstractly imagine how your algorithm would work, so just do it and we'll see how it goes.

[TheXFactor117]

7 hours ago, Alexiy said:

Have you looked at mineshaft code? Might give some hints, too.

It's kind of difficult to abstractly imagine how your algorithm would work, so just do it and we'll see how it goes.

Well it is pretty easy actually. You do everything the algorithm normally would but you don't place any blocks and you store the position and individual structure into a map or whatever. Whenever new chunks are generated, you check to see if your positions of the structures are in it and you generate if so.

 

Seems to make since to me, so I'll try and implement this soon.

 

I think Minecraft does this by checking if a given structure is inside of the bounding box of the chunk, and if so, it generates. So that's the kinda check you would need.

Edited August 22, 2017 by TheXFactor117

[jeffryfisher]

If you don't mind having your world depend on the order of player exploration, then you could limit your code to generating only one complex at any given time (e.g. use a static field in one of your classes as a latch). Initialize it to "ready",  then check it before starting one of these structures. if "busy", then exit without starting a new complex. If "ready", then set it to "busy" and commence generation. Do the whole structure, loading as many chunks as it needs; any further would-be structures triggered would be suppressed by the field being set to "busy". When done, clear the field back to "ready".

 

Of course, if you're willing to do the work to map overlapping structures, then that's probably better (and repeatable).

 

[TheXFactor117]

I think it would be easier to do what what I mentioned above, considering these structures should be fairly common. I'm going to try and implement it and see what kind of results I get. I need to finish re-writing portions of it first, however.