Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Infinite procedurally-generated city with the Wave Function Collapse algorithm

marian42.itch.io

Post reply on HN
Print view View original

121–130 of 145 posts

Re: Infinite procedurally-generated city with the Wave Function Collapse algorithm

#121

Post by lloeki »

anonytrary wrote: post #114
deathanatos wrote: post #108

Earlier quoted context omitted.

There's something special about it when applied to code though. Spaghetti code that's been copy/pasted is, in particular, quite worthy of being called "copypasta".

I have never seen the term being used in programming (for code) this way to refer to spaghetti code. Unless your definition caught on, using it that way would just confuse people, because copypasta already means something else.

I concur that this is an interpretation I encountered, that is bad copy/paste of possibly good code (often from stackoverflow) that results in spaghetti/pasta code, due to pasted code not being reformatted/refactored to fit surrounding code.

Re: Infinite procedurally-generated city with the Wave Function Collapse algorithm

#124

Post by mcphage »

roywiggins wrote: post #88
mcphage wrote: post #41

Earlier quoted context omitted.

There's a book called "Possible Palladian Villas" which gets into procedurally generated houses (in the style of Palladio), and that kind of thing came up—they'd run their algorithm to generate some houses, and then notice details in what was generated that were just... off. Not impossible, just... not quite right, either. Things you wouldn't think about unless you saw plans for a house that didn't consider it. So th…

I assume McMansion builders use the same design process.

Honestly I think that's giving them too much credit ;-)

Re: Infinite procedurally-generated city with the Wave Function Collapse algorithm

#125

Post by falsedan »

nrb wrote: post #98
tikhonj wrote: post #70

Earlier quoted context omitted.

I haven't designed levels, but playing maps across a few games, I'm constantly amazed at how well small details are thought out. A seemingly random crate actually blocks off a line of fire that would give one team a major positional advantage; a tree breaks up the line of sight between two objectives; a decorative fire provides visual cover in an otherwise overly open lane; a curved passage has exactly the right prop…

Compared to Fortnite, where every match is a unique experience with the addition of player-crafted buildings, and the static game map is under constant transformation each season.

"Guided by human actions" isn't exactly random; chaotic and unpredictable, sure!

Re: Infinite procedurally-generated city with the Wave Function Collapse algorithm

#126

Post by falsedan »

marian42 wrote: post #50
ajuc wrote: post #34

So, does this algorithm need to remember all already decided tiles forever to be consistent? Or to recalculate everything from the start each time you teleport? I've been working on similar (but much simpler and 2d) algorithm, and the gist of it was: - divide infinite world into 2d chunks of constant size that easily fit in memory - when player is nearby - deterministicaly generate edges of the visible chunks basing…

My implementation keeps the entire world in memory, forever. This is obviously not desirable, but I didn't figure out a way around it. You can't generate a place again that you have been to because the result would be different. If you do chunks and generate the edges first, you could run into a situation where it's impossible to fill the chunk based on it's edges. For generating terrain, using noise functions makes…

You'd use something like Perlin noise to seed whatever makes the decision about which tile to pick. Perlin noise is deterministic, so it's perfect to generate from the (x,y,z) of the tile & you can be certain that the location will resolve to the same tile if you recalculated the area from scratch. Divide up your world into areas, and force the centre of the area you're in and adjacent areas before filling out the area the player is in.

Re: Infinite procedurally-generated city with the Wave Function Collapse algorithm

#127

Post by falsedan »

J253 wrote: post #67

Anyone have any experience applying this to the generation of time series data? It's easy enough to generate random time series data but this looks like a promising way to generate interesting signals with prescribed shapes or features while still being "random".

Time series data is one-dimensional?

Re: Infinite procedurally-generated city with the Wave Function Collapse algorithm

#128

Post by marian42 »

falsedan wrote: post #126
marian42 wrote: post #50

Earlier quoted context omitted.

My implementation keeps the entire world in memory, forever. This is obviously not desirable, but I didn't figure out a way around it. You can't generate a place again that you have been to because the result would be different. If you do chunks and generate the edges first, you could run into a situation where it's impossible to fill the chunk based on it's edges. For generating terrain, using noise functions makes…

You'd use something like Perlin noise to seed whatever makes the decision about which tile to pick. Perlin noise is deterministic, so it's perfect to generate from the (x,y,z) of the tile & you can be certain that the location will resolve to the same tile if you recalculated the area from scratch. Divide up your world into areas, and force the centre of the area you're in and adjacent areas before filling out the ar…

If you have two adjacent chunks, collapsing one will impose constraints on the other one. Even if the RNG part is deterministic, as you suggested, the result will be different depending on which chunk you collapse first.

Re: Infinite procedurally-generated city with the Wave Function Collapse algorithm

#129

Post by swiftcoder »

How does the infinite part work?

The key problems with Wave Function Collapse tend to be that it gets exponentially slower as the area you need to collapse increases, and that it easily gets "stuck" (i.e. finds an combination of tiles that cannot be resolved, and has to backtrack arbitrarily far).

I assume the speed is solved by operating only on new chunks at the edge of the explored space, but backtracking across chunks seems... painful.

Re: Infinite procedurally-generated city with the Wave Function Collapse algorithm

#130

Post by optimuspaul »

meko wrote: post #104
naikrovek wrote: post #99

Earlier quoted context omitted.

That's not what "copypasta" means, you're thinking of "copy and paste." "Copypasta" is when you copy sections of code from one or more program's source code and paste it into another, trying to pluck specific functionality from them, and create a mess in the destination program doing it.

While a clever interpretation, that's not what copypasta means. It's literally a permutation of the phrase 'copy and paste'; popularized on 4chan, as a term for posts that would be repeatedly copy/pasted.

Actually the previous assertion predates 4chan. Anecdotally I recall using "copypasta" in the late 90's when working with code that had obviously been copied from another source and turned into a a spaghetti code mess. I don't doubt that it has taken on many other meanings, but I know for a fact that it means what naikrovek is not alone with that definition.
Post reply on HN