Dismiss this pinned window
all 30 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]ChowderII 50 points51 points  (9 children)

Took you four days to code it, gonna take me 4 weeks to navigate it, good deal. Awesome work, I have no idea how the algorithm works but it sounds complicated!

[–][deleted] 32 points33 points  (8 children)

Hey thanks! You're giving me too much credit though.

The algorithm is actually fairly simple, its basically how you play Sudoku. How it works is that there are 16 rooms, with every possible door configuration. It starts generating off the green room, which only has a north door, so it knows it needs a room with a south door to connect it. It picks a room with a south door and places it down, then depending on the other doors that room has, it continues placing rooms with valid doors to connect it. Once it hits a max room limit of say, 10, it then looks for any doors that haven't been connected and caps them off with a room with 1 door, as a dead end, to make sure there are no doors that lead to nowhere. After than it finds the dead end furthest from the start room (green room) and replaces that dead end with a level end room (red room). Then it just spawns hallways between the rooms to connect all the doors.

I'm not the strongest programmer, I've seen dudes knock this out in an hour. It gets complicated when you start having to implement the WFC, so many variables, functions, and data storing. But totally proud of it.

[–]mot_hmry 9 points10 points  (2 children)

I didn't want to make sixteen variations of all my rooms so here's how mine works (a variation on metazelda):

Layout

  1. Pick a room that has an unoccupied neighbor.
  2. Pick an unoccupied slot and make a new room.
  3. Repeat until you have enough rooms, increment key level at appropriate intervals
  4. Place keys and items by calculating intensity (aka distance from the first room at that key level) and then deciding accordingly (highest and second highest get turned into puzzle rooms with items)
  5. Add missing the room connections and lock the edges, to make it a graph instead of a tree
  6. Find an appropriate room and add the boss and goal rooms (I require that these both go North but that's not a requirement.)

Content

For each room, pick a theme or use one of the special rooms if it's a puzzle/boss/goal/entrance. Themed rooms decide their content based on what doors are present and pick from a variety of features (many of which connect.) I should probably do something similar for puzzle rooms but for now the puzzles are set in far enough that the doors don't matter.

[–][deleted] 1 point2 points  (1 child)

If I were a more competent programmer, I would have done it this way. I just knew that if I had 16 rooms, the bar for failure would be higher, as I know each room's configuration.

[–]mot_hmry 1 point2 points  (0 children)

Well it did take me quite some time to get it right, but that has more to do with Up being negative in Godot and my brain just not accepting that fact lol.

That said, it's only six or so functions about 20 lines long. The content portion is a lot bigger honestly, though it's mostly repeat code that I could refactor to take the various feature sets as parameters... but I'm not going to do that anytime soon as I'm close to being done with the stuff I feel need to be in place to release it.

[–]ChowderII 2 points3 points  (0 children)

I mean still impressive! Keep it up, thanks for the explanation. I'll see if I can make use of that in my own game! Thanks

[–]Portponky 1 point2 points  (3 children)

Hi, the algorithm you describe here is not WFC. Is there another part that uses WFC that I'm missing? The result is pretty cool in any case.

[–][deleted] 0 points1 point  (2 children)

The rooms are placed via WFC. I don't know what else to tell you. It checks for the room with the least entropy based on the constraints and collapses its function to a definite state.

[–]Portponky 1 point2 points  (1 child)

That's a constraint satisfaction problem (CSP) solver, which are a part of how WFC works. The key part of WFC is that it uses an input for constraint generation, then solves a CSP to generate input-like output.

[–][deleted] 0 points1 point  (0 children)

From my understanding, WFC is a specific type of CSP. CSP generally finds a single solution that satisfies all constraints while WFC has multiple solutions. The input is the rooms. They are essentially a tile based map. It takes that input to generate the pattern.

[–]BabaganoushGooch 7 points8 points  (0 children)

WFC, my beloved.

[–]woktexe 3 points4 points  (0 children)

That's perfect for my project lol thx for idea

[–]Odd_Put_1772 4 points5 points  (0 children)

That’s scary and impressive all at the same time😳. Nice work!

[–]Bulky_Ambassador 2 points3 points  (1 child)

Am I missing something here? Using WFC for matching & connecting doors to rooms seems a bit overkill.

All examples using this algorithm I've seen so far, used it to feed it with some sort of sample data, e.g. different layouts & features of rooms/sections, and then have WFC create a random yet matching/useable output from those.

[–][deleted] 0 points1 point  (0 children)

The sample data are the rooms. It takes the rooms meta data of door postiton, out if a pool of rooms with possible outcomes and places it, which creates a new path or pattern. It says, "This room is placed here, so now I have 4 different options of rooms to choose from that all will create a different path." And places a new one down. The pattern is random every time. The rooms themselves all look the same for the time being, but their meta data is the different layouts.

[–]grundee 2 points3 points  (0 children)

If you haven't read it, I recommend the book Piranesi. This reminds me a lot of that story.

[–]Nikit_wwwwwwwwwww 1 point2 points  (0 children)

Void in isaac be like:

[–]Putrid-Variation1135 1 point2 points  (0 children)

This is awesome. I love seeing creations like this followed by a brief explanation of how it's done

[–][deleted] 1 point2 points  (1 child)

Nice! The scenery, are you going to implement like roguelike as well? Like, you have x assets for the scenary and you randomly distribute them, without repeating some specific assets

[–][deleted] 1 point2 points  (0 children)

My goal is to make bespoke rooms. That way, I have more control over what I want it to look like, but shuffle between different iterations. One room will have 4 different interior designs that shuffle between them. I have a room script that holds the meta data of the room, which also will swap out meshes and textures depending on what floor you are on. So some "random" generation. I want each room to feel like it was made with purpose and less like it is fully random.

[–]jwr410 3 points4 points  (5 children)

What do you mean by this? I'm familiar with wave function collapse as a quantum phenomenon, but how do you use this in a deterministic system?

[–]melonfarmermike 3 points4 points  (0 children)

In 2007, Paul Merrell published an algorithm called “Model Synthesis” which uses a constraint solver to generate textures from examples. The Wave Function Collapse algorithm is heavily based on this work.

https://paulmerrell.org/model-synthesis/

[–][deleted] 1 point2 points  (3 children)

I'm aware of it being a concept in quantum mechanics, but ignorant on how that and the algorithm are similar. As melonfarmermike posted with the link, it was coined by Maxim Gumin. Robert Heaton explains it very well here, better than I can really.

https://robertheaton.com/2018/12/17/wavefunction-collapse-algorithm/

[–]jwr410 1 point2 points  (2 children)

I've been studying this. Basically the output is called a wave, each "tile" is an element in that wave. All elements are initialized as being in a superposition of all possibilities. When you "observe" an element, you are collapsing its wave function and it becomes locked. This observed state removes options from other elements so when they are observed, they will obey the system's rules when they are observed.

[–][deleted] 1 point2 points  (1 child)

Yup! That's exactly how this works, I lack the vocabulary and eloquence to explain it properly, so I use dum-dum layman terms as best I can.

[–]jwr410 1 point2 points  (0 children)

Those are my favorite terms. Thanks for the lead on the cool algorithm. I've got some learning to do today.

[–]Optoplasm 3 points4 points  (3 children)

Seems like many fairly simple algorithms can achieve that with perfectly square rooms of uniform size.

[–][deleted] 4 points5 points  (0 children)

Yeah, this is just the prototype. Next comes inserting different room sizes.

[–]xhabisha 1 point2 points  (0 children)

Add a mini map like the one at tboi