Procedurally generated maps

[erlend-sh]

In short, what we’d like to do is not to generate new maps entirely from scratch, but rather remix maps that players have already made with the in-game level editor.

We want to let users quickly put together a rough version of their initial idea, and then let them hit the “randomize” button to be presented with ~20 variations of the map they made. The generated maps won't even have to be 100% error-free, because they’re generated at the editing stage where broken maps can be manually fixed or rejected before putting them into play.

This is particularly useful for map makers on Console devices without mouse and keyboard: It’s not so important to place every tile pixel-perfect (which is hard to do on a gamepad) because that stuff can be smoothed out in the procgen versions anyhow.

[tversteeg]

Maybe Wave Function Collapse could be a nice technique for generating the maps? The user input can then be a small combination of input tiles.

[olefasting]

I think the best way to do this, would be to somehow resolve segments, based on platforms and rooms, and multiply randomly, maybe along a centered y-axis, that connects it all, or something like that

[erlend-sh]

Maybe Wave Function Collapse could be a nice technique for generating the maps?

Aha, looking at WFC again now with this use case in mind, its applications are much more clear to me.

What @olefasting suggests seems like a more simplistic and less math-y (I.e. better for an initial implementation) way to do roughly the same thing, right?

Anyhow, might indeed be worth exploring down the line. There are some some good Rust libraries for it as well. Maybe some of the maintainers could chime in here:

https://github.com/gridbugs/wfc @gridbugs
https://github.com/AustinHellerRepo/WaveFunctionCollapse @AustinHellerRepo
https://github.com/frederickjjoubert/bevy_ecs_tilemap_autotile_example @frederickjjoubert
https://github.com/madwareru/simple-tiled-wfc @madwareru
https://github.com/madwareru/ply-generator
https://github.com/Descrout/lemutate @Descrout

(bottom two are actual level generators).

[madwareru]

wow, you noticed my library :) be warned it isn't updated in crates.io for a quite a bit of time, so github version is a bit of reachier in features

[madwareru]

It's strange I noticed it now and not in 16 of february

[erlend-sh]

The move to a discussion must’ve triggered a new mention-notification; glad you didn’t mind!

We’re about to start exploring a real proof-of-concept for this with the help of a new contributor, so feel free to stick around if you’re interested in seeing where this goes 😊

[AustinHellerRepo]

Implementation:
My thought is to apply the same entropic propagation concept as presented in my "image" example from my repo for the solid structures and include another layer of nodes that would represent all possible locations for an element (excluding player spawns). If you review the image below, you will see only a small example of green squares floating above the blue area which visually represents a small collection of possible locations for the elements, dictated by the blue solid tiles as to which green elements are located at which possible location. As different tile structures are randomly generated, the green nodes which represent elements will fall into place similarly to how they exist in the sample map.

I'm going to construct another example in my repository soon to better illustrate exactly what I'm talking about in order to both reduce any confusion and to demonstrate the concept.

Architecture:
I'm thinking that we could have a struct whose soul purpose is to take in a map and output a randomized map. This would have its own unit tests for validating that the input and output map share similar densities of tiles and elements along with other features we would expect to exist. The randomize button would ultimately create an instance of this map randomizer and output maps as expected. Incorporating the map randomizer into the interface could be a separate ticket from creating the map randomizer.

[madwareru]

what you are describing looks like a fixed tiles section here https://www.boristhebrave.com/2020/02/08/wave-function-collapse-tips-and-tricks/

[zicklag]

I'm thinking that we could have a struct whose soul purpose is to take in a map and output a randomized map.

That sounds good to me. Currently maps are represented by a MapMeta that stores all of the map information and is also the representation of the map YAML format. If the map randomizer outputs a MapMeta, then it can be spawned into the world and displayed in the editor.

Format wise, a map is pretty much just a list of layers, each layer being either a tile layer or an element ( item ) layer. Each tile layer contains a list of tiles, with their tile index and position, and each element layer contains a list of elements and it's asset path and position on the map.

Also we're not hard set on our map format at all. We could change it if we have reason to, but for now it has worked fine.

[AustinHellerRepo]

what you are describing looks like a fixed tiles section here https://www.boristhebrave.com/2020/02/08/wave-function-collapse-tips-and-tricks/

Thanks for the link. It looks like what I'm describing is close to being fixed tiles, but it's not quite so demanding. You can imagine the elements placement to be in its own layer of possibility above the solid structures. The two layers enforce requirements upon each other such that the elements from the source map will all exist in the destination map, but they could be anywhere they would fit in the randomized solid layer such that they are nearby solid structures as they were in the source map. The solid layer would sometimes be forced to accommodate the element if there are no other places to put it and it's nearing the end of the collapse.

I'm currently working on an example to better demonstrate the concept. I wish there was an easier way to describe it. I think that viewing the solid layer as the randomizing part and the element layer as falling into place on top of it helps in visualizing it, but the "falling into place" can happen both ways.

Thanks again for the link. I'm always open to learning more and appreciate helpful articles/blogs.

[AustinHellerRepo]

I'm thinking that we could have a struct whose soul purpose is to take in a map and output a randomized map.

That sounds good to me. Currently maps are represented by a MapMeta that stores all of the map information and is also the representation of the map YAML format. If the map randomizer outputs a MapMeta, then it can be spawned into the world and displayed in the editor.

Format wise, a map is pretty much just a list of layers, each layer being either a tile layer or an element ( item ) layer. Each tile layer contains a list of tiles, with their tile index and position, and each element layer contains a list of elements and it's asset path and position on the map.

Also we're not hard set on our map format at all. We could change it if we have reason to, but for now it has worked fine.

Yeah, I see no reason to change it at the moment. I'm curious, though, when we would have more than one layer of each type of layer? Is it just for organizing? Like, "This is my bombs layer and this is my swords layer."?

[zicklag]

The layering should effect the Z indexing, for instance, items that players will pick up should usually be placed on a layer on top of decorations like seaweed, so that they can easily be seen, but sometimes you might want to place items like sproingers behind seaweed to cover it up slightly and make it less obvious or stylistic.

And user's might like it for organizing, but that's just preference at that point.

[AustinHellerRepo]

I'm working on an example in https://github.com/AustinHellerRepo/WaveFunctionCollapse called "level" that I will use to troubleshoot and figure out how to implement a method for generating 2D platformer levels based on existing level entities (tiles and elements). I have an example level created (image below) and applied the basic implementation of the entropic propagation algorithm on the tiles of the level (therefore excluding the elements) and found that it ends up generating terrible, sometimes unplayable, levels (other image below).
Source level:

Generated level:

My next idea is to create a method for isolating the different entity components of the level (tiles and elements together), treating them as movable groups of level entities, and then applying them to a wave function collapse algorithm based around placement locations and group overlap.

Process steps:

1. Collect tile groups based on their proximity to the outside first (finding any walls), then tile groups that protrude from any found walls, then tile groups that free-float in the level.
2. Append (into the tile groups) the elements that originally corresponded to each tile group (bombs, sproingers, etc.).
3. Identify all possible locations that each tile/element group could exist at in the absence of all other groups.
4. For each group, determine which other groups can exist at any other location when this group is placed at any given location.
5. Apply a wave function collapse algorithm (probably the AccommodatingCollapsableWaveFunction algorithm) to this information in order to place each group in appropriate places within the bounds of the level.

[zicklag]

Neat! Even if it's not working great yet, cool to see stuff being generated.

It sounds like the grouping technique might work well, if I understand right, especially because the levels often have similar grouped elements. For instance, a sproinger in the corner of a wall and the floor with some space above it, or, when we had fish school elements, I would often place fish around a seaweed element.

[AustinHellerRepo]

Neat! Even if it's not working great yet, cool to see stuff being generated.

It sounds like the grouping technique might work well, if I understand right, especially because the levels often have similar grouped elements. For instance, a sproinger in the corner of a wall and the floor with some space above it, or, when we had fish school elements, I would often place fish around a seaweed element.

Yeah, I think it will generate playable levels far more often then the current implementation, but we'll still need to run a search over the generated level to ensure that all locations can be reached from all other locations. That could always be part of a future update, though.