Skip to main content

Indie game storeFree gamesFun gamesHorror games
Game developmentAssetsComics
SalesBundles
Jobs
TagsGame Engines
A jam submission

GroundCollapseView project page

A flexible level generator using constraint solving based on Wave Function Collapse
Submitted by an npc dev — 7 hours, 24 minutes before the deadline
Add to collection

Play tool

GroundCollapse's itch.io page

Leave a comment

Log in with itch.io to leave a comment.

Comments

(+1)

Neat tool! I included it in my ProcJam compilation video series, if you’d like to take a look. :)

Developer

Thank you so much for being interested in the project and going so far as to include it in your video! I am extremely honored. It's so incredible that you highlight so many small creators and their work.

I am really sorry that you had trouble getting the demo working. If you have time and energy, I would very much appreciate hearing any specific details you can share about what happened when it failed to run: an immediate crash? A window that opened without any image displayed? Any information you could provide would be helpful for me.

Thank you, again!

Hey, it immediately crashed, along with my pc.  :/

Developer

Hey - just wanted to let you know that I really appreciate the reply, and I will do my best to try to find the cause of the crash!

Submitted (1 edit) (+1)

Pretty awesome infinite generator, I wish I can test (mac machine here) :) Just out of curiosity, Is it based on cellular automata infinite cave generator paper (https://core.ac.uk/download/pdf/132619480.pdf)?

Developer(+1)

Hey, thanks! You should be able to test it on Mac (as long as you are willing to install Python and some libraries) if you grab the code and follow the setup instructions in the README: https://gitlab.com/NPC-Dev/groundcollapse - unfortunately, I don't currently have a Mac to use to package a binary version. Feel free to contact me if you have any trouble.

It's not really related to Cellular Automata (although that paper looks super cool, and I should read it!). Instead, it's using Answer Set Programming, a form of constraint solving, to ensure that tiles always get placed in a valid arrangement. This means that, rather than writing rules for how each cell should change based on its neighbors, you simply write a list of tile types that can go next to each other and let the constraint solver build something valid.

You can then also add any extra constraints you want, including optimization constraints (such as "maximize the number of different tiles in the area," or "minimize using the same tile next to itself"). I believe this can extend easily to things like requiring pathability by marking certain tiles as having a path through them in certain directions, and adding constraints like "this path must connect all the way through the level chunk from at least one of these points to at least one of these other points," or many other possibilities! But I haven't yet had time to test that out.

Submitted(+1)

Oooh that is pretty amazing :) it reminds me with that paper a little bit (https://dl.acm.org/citation.cfm?id=3337722.3337752) which is using WFC with design constraints on the top.

Developer(+1)

Yes, it's absolutely related to that! Arunpreet is doing very cool stuff, though I didn't know about it when I first started trying out the concepts for this project. The difference is that GroundCollapse re-implements something similar to WFC in a standard constraint solver (clingo, with ASP), rather than trying to extend the original WFC algorithm. That paper notes a significant increase in conflicts due to the extra constraints, which standard WFC doesn't have very good ways to recover from (though I believe some folks are working on that problem). With a standard constraint solver, however, we get backtracking and conflict resolution, which can be slower, but guarantees a solution if one exists (and if you wait long enough).

More directly, GroundCollapse is very much inspired by two works, and I got the authors' permissions to adapt some snippets of constraint code from these. (I credit them in the code for the project):

Karth, Isaac, and Adam M. Smith. 2017. “WaveFunctionCollapse Is Constraint Solving in the Wild.” In Proceedings of the 12th International Conference on the Foundations of Digital Games, 68. ACM.

Nelson, Mark J., and Adam M. Smith. 2016. “ASP with Applications to Mazes and Levels.” In Procedural Content Generation in Games, 143–157. Springer.

Also, I'm very excited about this follow-up by Isaac and Adam from FDG this year. It has many cool insights about parallels between WFC and PCGML, and on how mixed initiative tools can communicate better with designers:

Karth, Isaac, and Adam M. Smith. 2019. “Addressing the Fundamental Tension of PCGML with Discriminative Learning.” In Proceedings of the 14th International Conference on the Foundations of Digital Games, 89. ACM.

Submitted (1 edit) (+1)

Yeah, I was running the PCG workshop this FDG :) it is pretty awesome work :)

Developer

Right, yes, of course you were! Thank you for all your work to make it such a great workshop.