"Bill Pragnell" <bil### [at] hotmailcom> wrote:
> "Samuel B." <stb### [at] hotmailcom> wrote:
> > Are you familiar with the so-called "wave function collapse" algorithm? It can
> > produce similar results to this, but must be run for many cycles.
>
> I was not! Having just looked it up, it does indeed seem applicable to this kind
> of thing. However, as you say, probably quite expensive for an SDL
> implementation. A very interesting approach to procedural generation that I'll
> be sure to come back to at some point, thanks for the pointer!

It is very interesting. And coincidentally, somebody posted an implementation of
the wave function collapse algorithm in Shadertoy today. I don't know what kind
of rig you're running over there, but perhaps you can view it (warning: it takes
a while to compile): https://www.shadertoy.com/view/st3GDM

> My somewhat naive algorithm currently traverses the grid only 5 times: once to
> zero it, once to populate it with 'floor' cells, once to remove 'loners', once
> to place stair cells between suitable near-neighbour floor cells (in a
> kind-of-random way), then finally once to build cell geometry based on the final
> state.

It sounds like a good algo.

I was doing some /slightly/ similar things a while back, but only in 2D. I was
using marching squares, basically. But to make it work, I had to use lookup
tables for 2x2 evaluation, which meant I needed to specify all 16 unique
cases... 16 different objects that I needed to script manually. :/ And it gets
worse for 3d, since I would need to make a table comprised of 256 entries. There
must be a better way. But all that work would be to get seamless geometry for
marching cubes, something that is not really needed for most things.

> > Are the pathways here completely traversable, or are there islands?
>
> Good question! There will most certainly be islands, the above algorithm in no
> way guarantees complete connectivity. However, given a high initial density of
> floor cells, and also that the stair cell pass might replace
> otherwise-unconnected floor cells with stair cells, it seems likely that
> completely connected structures might occur by chance!

Getting a single connected path can be accomplished by using a maze algorithm,
whereby you would choose a random cell and then test neighboring cells randomly
to see if they contain a filled cell, and then branch a pathway off from that,
making sure not to intersect older, filled cells (unless you wanted looping
paths, of course). But you would need to wait some time before all cells were
filled.

> A nice aspect of this approach is that setting floor and stair cells manually is
> an option. If I made the stair pass a bit more rigorous, in theory one could set
> floor cells alone and let the program fill in the stairs etc.

Well, whatever the case, the result is a very nice aesthetic!

Sam

Post a reply to this message