Higher-level representation of spatial location and procedural generation of maps.

[adarshp]

We will need a higher-level representation of spatial position of the human players, i.e. semantically meaningful regions (which house, which room, etc.) for modeling, planning, and NLP purposes.

We have already been discussing moving towards procedurally generated worlds, so it makes sense to couple the two, i.e. create a data structure with semantic region information (coordinates, bounding boxes, etc) at the time of the world generation.

To find out which region the player is in, we can either:

1. Loop over the regions to see which one the player is in by analyzing the coordinates of the player and the bounding box corresponding to the region, or
2. Construct a bounding volume hierarchy (e.g. an R-tree or octree) data structure that can be used for queries.

If we have relatively few regions in the map, then method 1 could work - it's easier to implement. If we have a large number of regions, then method 2 might be the way to go (assuming that we want to provide region information at the same frequency as we were providing the X, Y, and Z coordinates).

@Adi-UA is currently looking into procedural generation, I am just adding this issue to keep track of people's task queues.

To discuss:

Generating things from scratch (more flexibility, easier version control - no need to download additional file assets from scratch) vs using .nbt files corresponding to pre-built structures (@Adi-UA : I am assuming that this is faster? If so, by how much?)

[adarshp]

@Adi-UA I took a quick look at the addBlocksToWorld function in net.minecraft.world.gen.structure.template.Template, and I think that the internal logic of loading structures from a .nbt file is not really more complex than just looping over each block of the structure saved in the .nbt file and placing the structure centered at a given position. But please double check this.

If that is indeed the case, then I think it would be good to go ahead with trying to generate the structures themselves programmatically.

If the procedural generation of the world does start to take overly long due to the complexity of the generation algorithm, it would make sense to 'cache' the output of the procedural generation as a world file (similar to the zombie and tutorial mission worlds we currently have), and have the game load that up (I think it would be simple enough to encode this with Make, i.e. rebuilding the world if any of the source code that it depends upon changes). But let's see how far we can get without having to cache worlds.

But before writing any code, we should probably:

1. Do some research into what other people have already done in this space, so that we can build upon it, and
2. Think at a high level about the desired features of the map output by the procedural generation algorithm, and then design the algorithm appropriately.

Regarding point 1, a quick Google search shows that there are a few interesting research threads in this area:

• Organic building generation in Minecraft
• The AI Settlement Generation Challenge in Minecraft
• Generative Design in Minecraft

If we look beyond Minecraft specifically, we will surely find tons of additional material. But you may want to take a look at these first.

[adarshp]

@Adi-UA Nice work on the recent PR. For the next one, there are a couple of minor changes we should incorporate:

• [x] Replacing the use of Boost.Random with the random number generation routines in the C++11 standard. Boost is pretty useful, but it's also a heavy dependency, so if there is a standard library equivalent of some Boost functionality (that doesn't differ too much in terms of ergonomics), we will almost certainly want to use that instead. Since we are requiring a C++17 - compatible compiler, we automatically support C++11 as well.
• [x] Moving docstrings from source (.cpp) files to header (.h) files - generally, documentation for functions, methods, and macros should go in the header where they are declared. Historically, header files have served as a 'quick reference' for a library's functionality. This is somewhat less important these days due to the ubiquity of IDEs and autogenerated HTML documentation (e.g. with Doxygen), but still a good convention to follow.

[Adi-UA]

Thanks!

Yes, I'll include these changes in the next PR.