#Wave Function Collapse and other procedural generation methods

1 messages · Page 1 of 1 (latest)

meager path
#

let's go here

bronze tide
#

@quiet kiln This is the thread. Use it.

quiet kiln
#

cool

#

anyway

meager path
#

this has been written in less than an hour, theres 100% a lot of things that can be fixed, made better, including the overall class structure, but it does the job and is quite simple

📎 WaveCollapseFunction.zip
quiet kiln
#

@warped plover there shouldn't be a problem with the constraint if the code were correct

meager path
#

it was literally meant as just a test, not an actual usable library

warped plover
quiet kiln
warped plover
#

You said you knew the basics. I just shown you that there is a lot more than what you knew.

#

If you want to learn on procedural generation and be good at it, CSP is inevitable.

quiet kiln
warped plover
#

Also, there is a lot of things that you need to consider

quiet kiln
#

btw there are probably 100 other concepts i'm working on rn

warped plover
#

Like what variable you take.

#

WaveCollapseFunction is the backtracking algorithm with prefined configuration.

#

Just read the articles and you gonna be good. Read the book and you gonna be a god.

junior sand
#

I could really use a formal introduction to CSP

quiet kiln
#

to your question : What happens if you find in a position where your randomly generated map cannot fit the constraint you made ?

answer is, if red can't be next to green then blue should be generated around red to fill the gap

junior sand
#

this is certainly one solution

#

it's what I did in my first crack at implementing "wave-function collapse"

meager path
#

@quiet kiln that can only happen if you set up invalid constraints

quiet kiln
warped plover
meager path
junior sand
warped plover
#

Meaning that you need to backtrack

junior sand
#

Now, you can reduce the chances of that happening by collapsing the lowest-entropy tile first

meager path
junior sand
#

if you have two tiles that form two halves of a building, and you generate one half of the building, the adjacent tile obviously has to be the other half of the building

#

so you collapse that next

warped plover
junior sand
#

suppose the building halves may not touch water

quiet kiln
meager path
#

it can only result in an invalid state, if the constraint setup allows that, maybe that's a better way to say it..

junior sand
junior sand
#

the blank space must be the right half of the building, but it also must not be a building

warped plover
junior sand
#

oh hey, this is like graph coloring!

#

i somehow never drew that connection

warped plover
#

Oh hey ! This is one of the first CSP problem you ever encounter

quiet kiln
#

this is getting confusing

junior sand
quiet kiln
warped plover
quiet kiln
meager path
#

if you propagate outwards from a starting point, you can avoid problems like that though..
lets say a "building right" has to have a "building left" tile on the left of it, and visa versa on the left..
paths can be next to buildings and land.. land can only be next to other land or paths...
tile 10,10 is getting collapsed into the right side of the building.. tile 9,10 therefore loses all incompatible types, leaving it with only the left building type..
now if you collapse 8,10, you might collapse it into land.. but land cant be next to buldings, so 9,10 will lose its last option -> being a left building..
but if you collapse all those neighbors first, and THEN recursively their neighbors and so on, you can avoid at least half of those "invalid" issues

quiet kiln
meager path
#

because you spread out from known information, and dont create two or more seperate "starting points"

#

but i would not place buildings with wave collapse like that, but thats another story, for this example it's fine 😄 (i would spread it inito multiple layers of collapsing, first just terrain is collapsed, of which a tile might be a building-platform, on which a second generator could place random buildings etc etc

quiet kiln
#

i never use nodes, i always use grids for reference

meager path
#

nodes, 2d or 3d grid positions, they are all just vectors

#

how you define neighbors is the jumpin point :p

quiet kiln
meager path
#

if it sounded like that, im sorry

quiet kiln
meager path
#

4 nodes with 3 possibilities rather, right?

#

or rather n nodes

quiet kiln
#

3 nodes 3 possiblities

warped plover
#

@quiet kiln I'm done. Procedural generation is a complex subject. There is different way to approach the issue, CSP is definitely one of the basic way of doing. Understanding how things play out in a CSP would help you understand and create algorithm.

You have the right to stay in the double ignorance. However, this is definitely not how you going to improve.

junior sand
#

agreed.

quiet kiln
meager path
#

i thought we are spit balling ideas and concepts, and not fighting over who is right, but i guess this is just how it always goes on this discord 😐

quiet kiln
#

i just got a bit baffled

meager path
#

people are very offensive in their delivery, but even more, OFFENDED all the time for virtually everything -.-'

quiet kiln
#

i'll just re read for now, i probably would get some ideas

meager path
#

good luck

#

im stll here for actually fruitful discussions 😉

#

not penis measurements

quiet kiln
meager path
quiet kiln
#

so, the image reference he provided with 4 nodes, what was the problem exactly?

meager path
#

but they often deteriorate ..

quiet kiln
meager path
#

well the thing is.. let's say you want to specify colors of N nodes.. there are 3 colors... and green can only be next to yellow, yellow only next to blue, blue only next to green (or any of them next to their own color).. what matters is the relation and the constraints of those relations between the nodes.. if those nodes are a position on a 3d grid, or 2d grid, or virtually any amount of dimensions, it only matters "who are my neighbors".. so the only difference between having a grid, or just some random placed entities with any sort of connection inbetween them, is what is seen as a neighbor node of what node, which defines the path of the propagation when collapsing

#

if you have 20 nodes, or 3 nodes, 10x10 grid or 2x2x2x2 grid of entities, what matters in the collapsing is who is who's "neighbor"

#

thats at least what i meant, but since you said there is a difference between nodes and grids, id like to hear what you meant exactly

quiet kiln
#

there is a connecting line between nodes which can be removed, but in a grid the connection is only next to each block

#

and can't be removed

meager path
#

okay, then it is indeed the same.. the difference is the resolving of neighbors..
if you take a grid position 5,5 -> the neighbor resolver will give you 4,4 | 4,5 | 4,6 | 5,4 | 5,6 | 6,4 | 6,5 | 6,6 -> those are all the neighbors that you need for propagation when you collapse a tile..
if you take a any node of your node system -> the neighbor resilver will give you all other nodes that are connected to it via the connections

#

the rest is the same concept

#

the code i sent before actually splits this properly, so you can write a new neighbor resolver implementing the interface which takes nodes and resolves the neighbors via the made connections, and that's basically it

quiet kiln
#

so what do you mean by the neighbor resolver?

#

i know this will be taking so long, i'll explain things more simply

if nodes has fixed connection which can't be removed, this will make them same as grids but if connection can be removed then they will not be same as grid

meager path
#

when you collapse a tile, you have to change the neighbors available possibilities..
let's say you have colors yellow, green, and blue.. and like above, they can connect to themselves and only 1 other color, not the other (like written above)..
first of all you go through all nodes and add all colors to their possibilities..

you grab a random node, and you take a random entry of that nodes color possibilities.. and thats the new color, lets say you picked yellow..
first of all you mark this entry as collapsed (or implicite by setting the color), and then you have to change all possibilities of the neighbors.. yellow cannot be next to green, so you remove green from the "possible colors" list of all the connected nodes..
then you start collapsing all those neighbors, and add their neighbors to a "todo" lists.. after you propagated all the changes sto those neighbors, you can propagate that neighbors change to its neighbors (that are not yet collapsed, from the todo list)

meager path
#

so if the connection is there or has been removed between node A and node B, defines if node A and node B are "neighbors" or not

#

so if theres no connection, you dont propagate to that node.. if there is a connection, you propagate (and then continue with collapsing the connected node(s))

#

just looked at my code and it's actually really shit 😄 dont use that lol

pale fox
#

Theres a pretty simple implementation of it on youtube thats great for a small tileset cuz it requires manually assigning the top, left, right, and bottom neighbors of each tile

quiet kiln
#

it's fine, i'm just not yet ready for this layer of complexitiy, i got the idea so don't worry

pale fox
#

Problem with me is im using a lot of tiles so i could do that and take forever assigning but im more fascinated in how to read a given sample and pull the patterns from it to@use for wfc

quiet kiln
meager path
#

there is nodes, connection between nodes, and states of nodes.. and the states is what the wave function collapse will generate in this example

quiet kiln
meager path
#

what exactly are you trying to do? maybe we can rather use your actual use-case as the basis of examples :p

#

instead of arbitrary terms that might confuse

quiet kiln
#

is Procedural generation a general term for different concepts?

meager path
#

definitely yes

#

it means basically it was generated at run time.. thats it

quiet kiln
#

oh

meager path
#

so not before the game was build, but when the game starts, it is generated.. which can be in any way you want 😛

#

let's say you just randomly assign a color to any node.. that could be a way of procedural generating a set of colors 😛

#

not a good one, but it is one hehe

quiet kiln
#

well, i'll learn from you

#

but for now

#

i need to go to bed, it's late

meager path
#

good luck i hope it was some sort of help, i had fun talkin about it at least haha

quiet kiln
#

last thing

#

wait lol

#

wait

pale fox
#

Tbh im still thrown off by the talk of nodes and the connections, i def need to research more

shy veldt
# pale fox Problem with me is im using a lot of tiles so i could do that and take forever a...

Oskar Stalberg has a talk on the topic. He goes into basics as well. https://youtu.be/0bcZb-SsnrA

YouTube
BUas Games
EPC2018 - Oskar Stalberg - Wave Function Collapse in Bad North

Presentation from Oskar Stalberg (Bad North) at the Breda University of Applied Sciences Everything Procedural Conference 2018.

Bad North is a procedurally generated strategy game about fighting Vikings. Oskar Stalberg will talk about how the Wave Function Collapse algorithm is employed to magically assemble idyllic island dioramas from handcra...

▶ Play video
pale fox
#

Thought i understood the concept of tiles and possible neighbors and how it changes when collapsed but im prob wrong

quiet kiln
#

if you have a grid 1, 2, 3, 4, and node 1---2
]
3---4

you can go from 2 to 4 on grid, but on the node you can't because of the connection not being there, right?

meager path
#

in a 2x2 grid:

0x0 -> neighbors are 0x1 and 1x0
0x1 -> neighbors are 0x0 and 1x1
1x1 -> neighbors are 0x1 and 1x0
1x0 -> neighbors are 0x0 and 1x1

in your text drawing:
node 1: neighbors are node 2 and node 3
node 2: neighbors are node 1
node 3: neighbors are node 3 and node 4
node 4: neighbors are node 3

#

i might have brainfarted on those grid positions 😄 but you get the gist haha

meager path
#

when a connection is there, you do propagate the changes

quiet kiln
#

so nodes are not the same as grids! just admit that you failed the argument lol

meager path
#

if you put now a cable between node 4 and node 1, then node 1 gets a 3rd neighbor: node 4.. and node 4 gets a 2nd neighbor: node 1

quiet kiln
#

yes i get it but i have no time rn

#

i will talk about whatever topic but not today

meager path
#

^^ sure

pale fox
quiet kiln
meager path
#

we've been talkin about this for an hour now... so.. yea..

pale fox
#

So i might honestly just take rhe time to assign each neighbor of each tile then. Lot of tedious work but seems to be simplest way

shy veldt
#

If you have predictable structure like a grid, you already know your neighbours

meager path
#

Wave Function Collapse and other procedural generation methods

pale fox
#

Well im trying to make a large scale open world top down game. Like elden ring or skyrim but 16x16 top down and bigger map so was looking into WFC to generate the main terrain and foliage as it would be near impossible to hand make that

#

I have large tilesets

#

Different biomes

#

This is like the best implementation of it ive seen so far that handles this

meager path
#

i think having a set of constraints per biome (and possibly other "type" combinations) will save you indeed immense time, and depending on how simple the constraint requirements are (for example: any tile only defines what their exact neighbor tile can be) it is also fairly simple.. it gets a bit harder if you have constraints like trees can only be X tiles next to water... or sand needs to be surrounded by sand to have a minimum size of 3x3, etc

#

but you can also make several layers of this, with different gridsizes even

#

also biome selection could be its own wave collapse on a "biome-size" scale

pale fox
#

I feel like i understand how WFC itself works but in that video i just linked, they somehow make a tool that lets you create a sample tilemap with multiple layers and then it reads that sample and breaks it down into patterns to use for WFC

meager path
#

so first youd collapse all the biomes, then you start colapsing tiles in each biome.. biome transitions can be done after you generated everything, it doesnt need to be perfect, but it needs to be a viable time saving basis

#

also you can feed it with manual input.. as in placing a river somewhere, or a lake or anything, so "collapse these by hand" if you will, and have the rest be generated

#

so instead of setting all kinds of constraints you could just build the "more complex" stuff yourself and get the rest filled in

pale fox
#

Yeah i plan on doing most of the landmarks and major stuff by hand, only trying to to the main base level terrain with WFC

#

Maybe trees and simple foliage

meager path
#

minecraft uses sort of layered heightmaps with several different wave functions in different gridsizes to create its world

#

yea you could either generate or mark per hand areas at first.. so the first wave collapse is splitting the terrain up into sections, like pathways, forests, grass fields, etc etc.. and afterwards do a new collapse to fill in these areas, which is the actual tile placing, having constraints related to what area they are on etc etc

#

you can go as shallow or as deep into it as you want haha 😛 all quite fun tbh

pale fox
#

Yeah its a very interesting concept to me

#

Still in early stages of researching it but im sure if i put enough effort in i could get something pretty good working

#

I was even able to get my hands on some of the scripts used in that Stitched WFC video from the creator. Just not the biome and Multilayer scripts but got the main training and master script i could look over and learn from

meager path
#

using heightmaps or some sort of tileable noise like perlin noise can also help a lot with transitions between certain "areas", let them be biomes or whatever..
you could for example have a temperature map, an elevation map, and use them together to define those areas

meager path
pale fox
#

Looked into perlin noise too, never considered heightmaps or temperature maps though

#

Thats an interesting idea

meager path
#

minecraft does something similar, just way more complex

pale fox
#

Alright well i gotta head to classes. Thank you for the help though, ill try to mess around a bit more with it tonight

meager path
#

the cool thing about using several "input" maps to define biomes and areas like that is that you have a lot more traditional transitions (if you want ofc) but you have also a lot of freedom, w ithout it feeling off, really fun to play around with that stuff.. and more important, you constraint yourself from doing wrong transitions by basing them on multiple factors, which each on their own are much easier to handle/define

meager path
#

https://www.youtube.com/watch?v=ob3VwY4JyzE
have a look at this

YouTube
Jfokus
Reinventing Minecraft world generation by Henrik Kniberg

The past year and a half I've worked almost full time with Minecraft world generation. We've radically changed how the world is generated, to enable dramatic new caves, massive mountains ranges and overall more natural-looking terrain.

In this talk we'll geek out on the gory details of this. How does Minecraft procedural world generation actual...

▶ Play video
pale fox
pale fox
#

The biome section of the video is even more interesting to me on how the biomes are created and blended

#

its helping me to brainstorm some ideas of how to implement it with WFC

meager path
#

Yeah great video/pr3sentation

pale fox
#

ok, now im curious if you guys think WFC could be used to generate structures too like mountains, buildings, etc. Theoretically i think it could, it would just take a lot of extra constraint logic to make sure like it doesnt make a mansion with the building tiles and makes a proper mountain rather than a jumbled mess of walls that dont fit right

#

Idk im sure im biting off way more than i can chew, but my dream game is a large open world (and i mean large, where it takes a few real hours to travel from one side to the other) skyrim/dark souls game. I would have to procedurally generate the terrain and some structures/enemies spread out so theres stuff to do. only hand creating the major locations and stuff

#

all 2d top-down though

meager path
#

at least thats one way

#

and it really depends, ive made a world generator for a 3d survival game, using several heightmaps and noise functions to define the height of the terrain on each given point, and using the height (and additional heightmap/noise data) to determine textures per height range..