boristhebrave/debroglie

DeBroglie is a C# library implementing the Wave Function Collapse algorithm with support for additional non-local constraints, and other useful features.

DeBroglie

DeBroglie is a C# library implementing the Wave Function Collapse algorithm with support for additional non-local constraints, and other useful features.

Wave Function Collapse (WFC) is an constraint-based algorithm for generating new images that are locally similar to a sample bitmap. It can also operate on tilesets, generating tilemaps where the tile adjacency fits a specification.

Unlike the original WFC implementation, De Broglie has full backtracking support, so can solve arbitrarily complicated sets of constraints. It is still optimized towards local constraints.

Features

• "Overlapped" model implementation of WFC
• Non-local constraints allow you to specify other desired properties of the result
• Backtracking support - the original WFC implementation immediately give up when a contradiction occurs.
• supports 2d tiles, hexs, and 3d voxels

Usage

See https://boristhebrave.github.io/DeBroglie/

Release Notes

See docs/articles/release_notes.md

Copyright

Code is covered by the MIT license.

debroglie's Issues

Plans for Generated Tiles feature?

Hey, firstly thanks for your hard work on this library, I've been having a blast with it recently on unity.

My setup right now is a pipeline that operates on TileBase as sample value, for both input and output (i.e. a reference unity tilemap is used to generated an output unity tilemap).

I'd love to take advantage of the generated tiles feature for symmetry, however when doing so I get

InvalidCastException: Specified cast is not valid.
(wrapper castclass) System.Object.__castclass_with_cache(object,intptr,intptr)
DeBroglie.TilePropagator.ToValueArray[T] (T undecided, T contradiction) (at Assets/Plugins/DeBroglie/TilePropagator.cs:493)

The cast happens here:

DeBroglie/DeBroglie/TilePropagator.cs

Line 491 in 29a1273

value = (T)tileModelMapping.PatternsToTilesByOffset[o][pattern].Value;

Honestly, I didn't expect this to really work in the first place though. It seems there would need to be some API by which you tell DeBroglie how to generate tiles which are rotations of other tiles. For example, bitmap data can be rotated, but for Unity Tilemap tiles, you just want to store some metadata about how the tile is rendered in the tilemap (Specifically, tile.transform).

I was wondering if you had thoughts on how this should be handled? I would be happy to help contribute.

Question: how could I give backtrack a run times upper limit

1. I use backtrack to generate path, and in unity it always stuck.
   I have known backtrack will explore the entire space.
   And I want to add a limit to stop backtrack if it has backtracked too many times.
   How could I do ?

2. I have set rotate and reflect, any tips to get backtrack more efficient? A big sample?

Thanks a lot

Is there a way to see what triggers a contradiction?

I'm trying to use an overlap model to generate a map, but I keep getting contradictions. When i inspect the propagator I can see that it doesn't backtrack at all, so i assume that something is wrong with my map and constraints which is fair. But it's really tough to debug when all the information i get is "Contradiction". Is there a way to get more information?

Thanks :)

Deque is empty

I sometimes get the exception
System.Exception: Deque is empty at DeBroglie.Wfc.WavePropagator.Step() at DeBroglie.Wfc.WavePropagator.Run() at DeBroglie.TilePropagator.Run()

This is on an AdjecentModel with one CountConstraint and a manual Select() to insert '0' tiles on the border. It's pretty rare though, have happened twice over 2 hours of playing around.

A possibility of probability?

Is it possible to control explicitly the probabilities of the appearance of the tiles?
I'm sorry, I just started working with the library and just beginning to understand how it works, I may have missed the obvious.

For example I want to tie the probability to a cell value - for example, brightness or something else. I want to tie the probability of the appearance of the tiles to the value of the grid.

Discord link is not working in FAQ section

https://boristhebrave.github.io/DeBroglie/articles/faq.html

Edge Types for Topologies

At the moment, all locations of a topology are identical. We need a feature where certain edges of a topology can be marked up in some way, and they behave differently with respect to propagation. There's two main cases for this.

1. Meshes
   If the edge between two cells could convey a notion of rotation then we could have topologies where each location is a face on a mesh.

2. Better mask handling
   This is kinda fiddly to explain, but at the moment, masks interact weirdly with the Overlapping model. In the precense of masked out locations, we could mark up nearby edges so that patterns propogate differently, specifically they no longer require that adjacent patterns agree on the value of a nearby tile, if that tile is masked.

DeBroglie.Console crashes when following the Introduction tutorial

I get a NPE whenever I try to run the executable (2.0 release) by dragging the following JSON file into it:

{
    "src": "sewers.png",
    "dest": "generated-sewers.png",
    "model": {
        "type": "overlapping",
        "n": 3
    },
    "periodicInput": true,
    "periodic": true,
    "symmetry": 8
}

This is the stack trace:

Unhandled Exception: System.NullReferenceException: Object reference not set to an instance of an object.
   at DeBroglie.Console.Export.BitmapExporter.Export(TileModel model, TilePropagator propagator, String filename, DeBroglieConfig config, ExportOptions exportOptions) in C:\Users\Adam\Documents\Programming\Programming 2018\DeBroglie\DeBroglie.Console\Export\BitmapExporter.cs:line 66
   at DeBroglie.Console.Export.Exporter.Export(TileModel model, TilePropagator tilePropagator, String filename, DeBroglieConfig config, ExportOptions exportOptions) in C:\Users\Adam\Documents\Programming\Programming 2018\DeBroglie\DeBroglie.Console\Export\Exporter.cs:line 17
   at DeBroglie.Console.ItemsProcessor.ProcessItem() in C:\Users\Adam\Documents\Programming\Programming 2018\DeBroglie\DeBroglie.Console\ItemsProcessor.cs:line 343
   at DeBroglie.Console.ItemsProcessor.Process(String filename) in C:\Users\Adam\Documents\Programming\Programming 2018\DeBroglie\DeBroglie.Console\ItemsProcessor.cs:line 458
   at DeBroglie.Console.Program.Main(String[] args) in C:\Users\Adam\Documents\Programming\Programming 2018\DeBroglie\DeBroglie.Console\Program.cs:line 16

This bug does not happen with the 1.0 release, so I suppose that the introduction still needs to be updated.

Negative adjacency rule?

While exploring this tool I was not yet able to find a 'negative' adjacency rule. I realize that simply not defining a rule would potentially cause it to not apply but in my case I'm not seeing a way to deal with an issue.

            var tile1 = new Tile("█");
            var tile2 = new Tile(" ");

            var model = new AdjacentModel(directions: DirectionSet.Cartesian2d);
            var tiles = new[] { tile1, tile2 };

            model.AddAdjacency(tiles, tiles, 1, 0, 0);
            model.AddAdjacency(tiles, tiles, 0, 1, 0);

            model.SetFrequency(tile1, 1);
            model.SetFrequency(tile2, .25);

What I'd like to see is a way to disable diagonal directions. Not sure if this is possible with the way the adjacency system is designed but I'll continue exploring. Currently I'm building a quick and dirty constraint to deal with this - though extending the connected constraint might be the better way to go.

Just wondering about the adjacency system and if I'm missing a negative rule, or the ability to remove a previously configured rule.

Does rotation affect path Constraints?

I use path with index 2, and get this

And I config rotation with:

{
    "rotationTreatment": "generated",
    "rotationalSymmetry": 6,
    "reflectionalSymmetry": true,
}

and I will get this:

I can't understand what happened here...
I know there is no need to rotate here. But I have another sample need rotate, and generated.
So I want use a simiple sample to see what's wrong.

Any help? Thanks a lot.

"Pinning" and filling around existing content?

In this example I have created a custom constraint that uses Select() to "pin" areas (cyan regions) of my output such that it has to be present in its exact configuration in another generation:

Cyan regions remain in new output:

This works fine, because each cyan region contains tiles that do not contradict with the rules of the input model. However if I attempt to pin a region that does not follow the rules on its interior:

I get an immediate contradiction after the Select call since the pinned region has water tiles next to water tiles and that is not defined in the input model.

If I wanted to make this work I could of course add water next to water in my model. The downside is that now my output will contain lakes. I see two potential options as an enhancement that might allow for this:

• #2 if supported/added support - For each interior point in a pinned region, explicitly add a hole in the output. Edges of the pinned regions must not cause a contradiction still. This is perfectly reasonable IMHO.
• Via a call to AddSample, explicitly add water next to water, but somehow give it an output probability of 0, thus ensuring lakes wouldn't show up.
• In the pinning constraint Check method, search for any region in the output that matches the interior of the pinned area. This seems really, really intensive.

Do any of these sound like reasonable solutions?

Expectations on backtracking time/performance?

I've implemented both the adjacent and overlapping models into Unity's Tilemap system and I've recreated this example:

Every five or so runs of the overlapping model generation process I get stuck in a seemingly endless generation process. When I check the backtrack count it's in the millions, and I end up just canceling the operation as it never seems to complete (I've waited 10's of minutes on a high powered system).

I know the backtracking algorithm in the worst case will search the entire problem space, but should I expect such behavior in this example? My tilemap output size is only 40x40.

Can't use the NearbyTracker

I tried copy/pasting the private class NearbyTracker from the SeparationConstraint, but I realize it's referencing a boatload of internal classes. Any particular reason why this class isn't public?

What I'm trying to do is create a custom constraint so that tiles of type X cannot be within Y tiles of type Z.

Exception while running propagator: Deque is empty

Hey BorisTheBrave,

I've been running into the above mentioned exception with a backtracking setup. I'm using the C# library and not the console application, if that makes any difference at all.
The backtracking depth is set to infinite (though this also happens with any finite depth set), and I'm using multiple constraints.
However the map is definitely generatable, as I only get this exception sometimes, and other times an output is produced.

Do you happen to know what's causing this?

This is the stacktrace:

  at DeBroglie.Wfc.Deque`1[T].Pop () [0x00010] in <4ff1c6a8afd84a669432e1334eba5546>:0 
  at DeBroglie.Wfc.WavePropagator.Step () [0x0013c] in <4ff1c6a8afd84a669432e1334eba5546>:0 
  at DeBroglie.Wfc.WavePropagator.Run () [0x00000] in <4ff1c6a8afd84a669432e1334eba5546>:0 
  at DeBroglie.TilePropagator.Run () [0x00000] in <4ff1c6a8afd84a669432e1334eba5546>:0

Cheers

No idea if the algorithm is stuck, have crashed, or just takes a long time

Would love to be able to toggle some kind of console output when running so that i can get an insight into how the algorithm is progressing, just so i know that it's actually doing something!

sample ,run_all.py, get error "Writing hexmini.tmx", in osx

...
Writing docs/output/pathway_overlapping.png
Running docs/hexmini.json
Reading docs/hexagonal-mini.tmx
Processing docs/output/hexmini.tmx
Writing docs/output/hexmini.tmx

Unhandled Exception: System.IndexOutOfRangeException: Index was outside the bounds of the array.
   at DeBroglie.Topo.TopoArray1D`1.Get(Int32 index) in /Users/mac/game/DeBroglie/DeBroglie/Topo/TopoArray1D.cs:line 23
   at DeBroglie.TilePropagator.<>c__DisplayClass41_0.<ToArray>b__0(Int32 index) in /Users/mac/game/DeBroglie/DeBroglie/TilePropagator.cs:line 548
   at DeBroglie.Topo.TopoArray.CreateByIndex[T](Func`2 f, ITopology topology) in /Users/mac/game/DeBroglie/DeBroglie/Topo/TopoArray.cs:line 105
   at DeBroglie.TilePropagator.ToArray(Tile undecided, Tile contradiction) in /Users/mac/game/DeBroglie/DeBroglie/TilePropagator.cs:line 544
   at DeBroglie.Console.Export.TiledMapExporter.Export(TileModel model, TilePropagator tilePropagator, String filename, DeBroglieConfig config, ExportOptions exportOptions) in /Users/mac/game/DeBroglie/DeBroglie.Console/Export/TiledMapExporter.cs:line 25
   at DeBroglie.Console.Export.Exporter.Export(TileModel model, TilePropagator tilePropagator, String filename, DeBroglieConfig config, ExportOptions exportOptions) in /Users/mac/game/DeBroglie/DeBroglie.Console/Export/Exporter.cs:line 30
   at DeBroglie.Console.ItemsProcessor.ProcessItem() in /Users/mac/game/DeBroglie/DeBroglie.Console/ItemsProcessor.cs:line 201
   at DeBroglie.Console.ItemsProcessor.Process(String filename) in /Users/mac/game/DeBroglie/DeBroglie.Console/ItemsProcessor.cs:line 292
   at DeBroglie.Console.Program.Main(String[] args) in /Users/mac/game/DeBroglie/DeBroglie.Console/Program.cs:line 18
Traceback (most recent call last):
  File "run_all.py", line 11, in <module>
    subprocess.check_call(de_broglie + [filename])
  File "/usr/local/Cellar/[email protected]/3.8.3_1/Frameworks/Python.framework/Versions/3.8/lib/python3.8/subprocess.py", line 364, in check_call
    raise CalledProcessError(retcode, cmd)
subprocess.CalledProcessError: Command '['dotnet', 'run', '--project', '../DeBroglie.Console', '--no-launch-profile', '--', 'docs/hexmini.json']' returned non-zero exit status 134.

Output topography with holes?

Is it possible to have an output topography that has explicitly defined "holes" that no content should be generated for (e.g. they get treated as if they were an edge but they are in the interior of the output)?

Right now I can't seem to find anything that would allow for that. Calling Ban with all tiles or Select with a null tile via a constraint all result in a Contradiction (which I would expect).