Message Boards Message Boards

Designing Townscaper town on computable base-grid

enter image description here

POSTED BY: Silvia Hao
11 Replies

Here is the algorithm abstract from the blog:

  1. Choose a cell at random, considering only the cells with the fewest possible values.
  2. Choose a random value to lock in for that cell, considering only the possible values for that cell.
  3. Propagate the effects of locking in the cell, removing the locked-in value from the possibilities of cells sharing the cell’s row, column, and 3x3 square.
  4. If during propagation, you removed the final possibility of a cell, give up and start again.

(Note: "frequency hints" is also important)

The one problem is that, unless the tile set is well chosen, the algorithm is probably too random to call "quantum", i.e. it probably won't lead to solutions of Schrödinger's equation. (The other problem is that step 4 is non-optimal. As mentioned in the post, a backtracking algorithm would be better).

POSTED BY: Brad Klee

Also, Silvia, nice work finding the WaveFunctionCollapse github, and the subsequent blog post. This is very well related to some of the other algorithms for growing Penrose tilings and to the Multicomputational Paradigm. Is anything like this available in Wolfram Function Repository?

One interesting property of the Penrose tilings (if I remember correctly) is: For any patch of a tiling also a toplogical disk, orientation and placement of all interior tiles is determined by the ring of tiles around the edge of the disk. The whole solution on the region is just a function of the matching rules, shape and chosen boundary condition.

In the case of non-tightly constrained tilesets, I would expect many different equivalent solutions with sufficiently large boundary. Sure the pictures turn out looking pretty, but it could also be an interesting combinatorial question how many patterns of square size $n \times n$ can be formed from some chosen initial data?

The other way to go is try to make the algorithm more complicated, whether by machine learning / genetic algorithms, or by comparing with data. Maybe quantum chaos?

POSTED BY: Brad Klee

Yes I'm quite interested in the WFC algorithm as well. It offers an interesting way to generate locally compatible structures. Should be fun to apply it to graphs and hyper-graphs. Also, the original WFC uses deterministic metric to collapse tiles, what will happen if stochastic process is used instead? I intend to explore WFC more when I get time.

POSTED BY: Silvia Hao

Thanks for the wonderful post and for making me discover Townscaper!

Hi Giulio, I'm glad you like them (the game and the post)! I discovered the game 1 years ago when it was still in beta. Since then it has been giving me a lot of enjoying time. :)

POSTED BY: Silvia Hao

Congratulations! Your post was highlighted on the Wolfram's official social media channel(s). Thank you for your contribution. We are looking forward to your future posts.

POSTED BY: Moderation Team

Hi Silvia,

Any chance some of this fascinating work could make its way into the Wolfram Function Repository?

POSTED BY: Daniel Lichtblau

Hi Daniel!

I guess most of the code is specific for that game, but morphology operations on graph could be of general interest. I'll wrap and submit them to WFR.

Thank you a lot for the suggestion!

POSTED BY: Silvia Hao

enter image description here -- you have earned Featured Contributor Badge enter image description here Your exceptional post has been selected for our editorial column Staff Picks http://wolfr.am/StaffPicks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you!

POSTED BY: Moderation Team

Wow, great Idea.

I wonder if it is possible to try a similar city planning based on (purely deterministic) cellular automata. Maybe it could be used not only for Townscaper, but also for real world's city planning. It would be great, if we have a 2D or 3D CA-rule which determines optimal city development (although it will be hard to determine the optimal CA-rule which is a common difficulty in NKS - most likely it will require an exhaustive search).

Happy New Year!

POSTED BY: Andreas Mämpel

Hey Andreas! Happy New Year!

When I was reading about the Wave Function Collapse algorithm behind the game, it actually reminded me your Summer School project. If you are interested, besides the original GitHub repo, I found this blog post very comprehensive.

POSTED BY: Silvia Hao
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract