References on procedural generation and texture synthesis

[dlight]

Here I'll leave some references with material relevant to this project; mostly papers and blog posts.

[dlight]

I'll begin with the following three-post blog series (written in Rust!)

• Procedural level generation with Rust

• Drawing tile maps with Rust and Cairo

• Procedural generation using binary space partitioning (perhaps this one was inspired by this article How to Use BSP Trees to Generate Game Maps, but in any case using BSP trees for map generation is a well known technique)

[dlight]

Roguelike articles from RogueBasin

• Cellular Automata Method for Generating Random Cave-Like Levels
• Diffusion-limited aggregation
• Creating Measurably "Fun" Maps
• Dynamically Sized Maze

[dlight]

The amazing WaveFunctionCollapse!

it contains a huge list of papers. forks and spin-offs, of which I'll list the following academic works:

• P.C. Merrell's dissertation, Model synthesis. WFC's author based himself on it.

• WaveFunctionCollapse is ConstraintSolving in the Wild is a paper that formulates WFC as an answer set programming problem, a form of doing constraint solving as logic programs. It uses the clingo solver.

And the following software:

• Interactive version of WFC, created by the author (Windows-only)

• collapse, a Rust implementation of the overlapping model

Anyway, here's a gif:

And an Youtube video: https://youtu.be/DOQTr2Xmlz0

[dlight]

The amazing SynTex, also written by the WFC author.

About it, WFC's README says

P. F. Harrison's texture synthesis algorithm is significantly faster than WFC, but it has trouble with long correlations (for example, it's difficult for this algorithm to synthesize brick wall textures with correctly aligned bricks). But this is exactly where WFC shines, and Harrison's algorithm supports constraints. It makes sense first to generate a perfect brick wall blueprint with WFC and then run a constrained texture synthesis algorithm on that blueprint.

It has a list of references:

The algorithms are:

1. Full neighbourhood search algorithm of Scott Draves and Alexei Efros + Thomas Leung and Li-Yi Wei + Marc Levoy is probably the simplest texture synthesis algorithm imaginable.
2. K-coherent neighbourhood search of Michael Ashikhmin and Xin Tong + Jingdan Zhangz + Ligang Liu + Xi Wangz + Baining Guo + Heung-Yeung Shum takes computational burden from the synthesis to the analysis part and therefore is better suited for synthesizing large textures.
3. Resynthesis algorithm of P. F. Harrison is scale-invariant, fast, supports constraints and practically never produces completely unsatisfactory results.

A gif

And an Youtube video, Texture synthesis from examples with P. F. Harrison's algorithm

[dlight]

The amazing ConvChain, also written by the WFC author.

About it, WFC's README says

WFC algorithm supports constraints. Therefore, it can be easely combined with other generative algorithms or with manual creation. (...)

ConvChain algorithm satisfies the strong version of the condition (C2): the limit distribution of NxN patterns in the outputs it is producing is exactly the same as the distributions of patterns in the input. However, ConvChain doesn't satisfy (C1): it often produces noticeable artefacts. It makes sense to run ConvChain first to get a well-sampled configuration and then run WFC to correct local artefacts. This is similar to a common strategy in optimization: first run a Monte-Carlo method to find a point close to a global optimum and then run a gradient descent from that point for greater accuracy.

A gif:

[dlight]

There's a lot of things about maze generation algorithms on the web, such as this interactive demo.

The author of this demo actually wrote a book on this stuff, Mazes for Programmers. He also has put some content on his blog, here linked in chronological order (though I probably missed some articles):

• Maze Generation: Eller's Algorithm

• Maze Generation: Recursive Division

• Maze Generation: Wilson's algorithm

• Maze Generation: Binary Tree algorithm

• Maze Generation: Algorithm Recap

• Maze Generation: Weave mazes

• Maze Generation: More weave mazes

See also this Gamasutra article, Algorithms for making more interesting mazes

https://www.reddit.com/r/programming/comments/6hy3er/maze_generation_code_inspired_by_working_through/

This post talks how important is sparseness:

The post by FastAsUcan provides the answer. It works like so:

1. Make a perfect maze. There are a number of different algorithms for this, but they’re all fairly straightforward.

2. Make the maze sparse. Find dead end passages and fill them back in with solid rock.

3. Pick some of the remaining dead ends and cut holes in them to adjacent walls. This makes the maze imperfect. (Remember, this is a good thing!)

4. Create rooms and find good locations to place them. “Good” here means not overlapping the maze but near it so you can add a door and connect it.

The magic step, and the piece I was missing, is sparseness. A normal maze fills every single square of the world, leaving no areas where you can fit a room. The trick that Jamis and FastAsUcan do here is to carve the whole maze and then uncarve the dead ends.

[dlight]

Interesting subreddits and websites:

• /r/proceduralgeneration

[dlight]

TerrainVer: Worms-style cartoon terrain in JavaScript (discussion on HN). Cool!

It was from this that I got to know about WFC

[dlight]

Coastline generation:

Animation on /r/simulated, with comment:

Another Animation

This is a 3D visualization of the simulated erosion process that is used to generate terrain for a fantasy map generation program that I am writing. The program implementation is based on Martin O'Leary's Generating fantasy map notes. The erosion model is simple and eroded material is only carried away. Material deposition is not implemented.

Source code and generation notes: https://github.com/rlguy/FantasyMapGenerator

See specially Generating Irregular Grids to begin with it.

It has references

An image:

---

Generating fantasy maps, the work cited above. It contains interactive demos. See also this Github issue.

It cites https://en.wikipedia.org/wiki/Lloyd%27s_algorithm for relaxing Voronoi diagrams.

Related: Generating naming languages for placename generation.

(This was a spin-off of NaNoGenMo, a contest to write novels using software. Cool!)

[dlight]

Cellular Automata in IBEX, uses the RogueBasin's Cellular Automata Method for Generating Random Cave-Like Levels linked above.

Some cool map:

[dlight]

Red Blob Game's Polygonal Map Generation for Games

Image:

And Game maps and Skyrim with ideas about interesting maps.

[dlight]

On WFC, it seems the wfc crate is better maintained than collapse:

https://github.com/stevebob/wfc

[dlight]

This dude makes cool generative art, and publishes his source code:

https://twitter.com/inconvergent

https://inconvergent.net/generative/

https://inconvergent.net/generative/fractures/ <- this is specially interesting for maps. It's inspired by an algorithm for leaf venation, http://algorithmicbotany.org/papers/venation.sig2005.pdf

https://img.inconvergent.net/plot/

https://inconvergent.net/mechanical-plotter-drawings/2/

[dlight]

https://www.reddit.com/r/rust/comments/9adsg8/programmatically_generated_artwork/ this is pretty cool!

https://github.com/isaacg1/peaks

Also this: generative art library in Rust https://github.com/wgreenberg/darude

And https://github.com/dhardy/terr (which unfortunately doesn't support zero-copy conversion of heightmaps to images, bitmaps, etc) maintainer isn't receptive about making changes.

[dlight]

https://github.com/Robzz/TexSyn This looks interesting

[dlight]

https://github.com/image-rs/imageproc has a lot of cool stuff, like building blocks for an opencv-like library (haar features, integral image) and more importantly, morphological operators.

It uses https://github.com/image-rs/image as its representation. So I will begin with it as my map representation.

[dlight]

Also on image processing, https://github.com/polyfloyd/edge-detection-rs

both edge-detection and imageproc uses pretty up to date image (0.22)