Control over which solutions are more likely to be found first, or 'soft constraints'

[spencerflem]

Another question better fit for a mailing list / solution space -

I've been messing around with WFC Procedural Generation of mazes using DeBroglie and one of the nice features it has is that you can specify a heuristic for which values along the search tree get selected first.

Some use cases are mentioned in this article on constraint based tile generators. Specifically: using a weights to make some values more common than others and using a priority list to generate more consistent results.

A related thing is used in the later parts of Map Generation Speedrun where optimization statements like #maximize are used to control which of many possible consistent levels is the one the user sees. (Though this seems less useful to me, and the author seems to agree. For random generation, I don't want something globally maximized often.)

In general, is any sort of 'soft constraint' like optimization, or way of affecting the nondeterminism of the exploration algorithm an intended feature of Dusa, or is that better handled outside of Dusa using the API?

Thanks!

[robsimmons]

In some cases (like #maximize) I am inclined to say that the API is the right way to do this, but I'd also be interested in command-line options.

Soft constraints are... well... hard in Dusa's architecture and design. It's not hard to throw a priority queue into the implementation, but actually making it meaningful for programmers to express and understand what's going on without understanding implementation details is a challenge in my experience — I'd welcome more examples of where you see this being done well if you've got them. This is certain to be a lower priority than the next set of planned improvements for optimizing state space exploration. (Which also don't have a timeline at present, unfortunately!)

[spencerflem]

I'm much more familiar with WFC than with Logic Programming, so all my examples will come from there (and maybe that's a good reason not to add any of these features!) I'm still trying to figure out exactly how WFC compares to Logic Programming in general and Dusa in specific with no grand insights yet.

How DeBroglie works is that there is two places for configuration: Tile Selection, and Tile Picking.
The general loop is pretty similar to Dusa's -

1. Pick a tile,
2. Set that tile to a value that hasn't yet been ruled out.
3. Propagate constraints
4. If the board is no longer valid, backtrack some amount and try again

In the traditional WFC algorithm, picking a tile is done using "Least Entropy", as opposed to Dusa's "Choose Randomly", or Model Synthesis's "In Order - Left to Right, Top to Bottom". In this video by the Townscaper guy he talks about choosing tiles outwards in for generating an island, so that a constraint can be added that the ocean starts at zero height and new tiles picked must be at least as tall as its neighbors, making a naturally somewhat cone shaped island. From my own experiments making mazes, it generated a lot faster if the next tile picked to be resolved was at the end of a path.

(This sort of behavior doesn't seem to map as nicely when what's being picked isn't a tile but instead an abstract attribute - truthfully I don't know how it would be implemented)

Once a tile is picked, in the traditional WFC algorithm as well as in Model Synthesis, there are weights that influence which tile is more likely to be picked. For example, a plains might have grass tiles be 10x more likely to be placed than a tree tile, compared to a forest where they are equally likely. This has a big effect on what generated maps tend to look like, and is key to the "given an input image" texture-synthesis style which tries to recreate the general feel of an image by seeing what tiles tend to be next to other tiles.

The other one mentioned in the article and implemented in DeBoglie is Priority Queue which is used in Townscaper to allow for specific patterns to have consistent results. That is to say: although the entire map is getting regenerated after every change to the underlying constraints, the same tiles will consistently get picked unless something dramatic happens to rule it out. It also means that players can work towards specific patterns - such as a tower of two white tiles followed by another color followed by white will always make a lighthouse. While the player can't choose to have something else be part of the constraint solution they also can predict what the output will be while still allowing the random generation to handle the details.

(This seems more easily fit in to Dusa to me and for the weighted graphs version it can already be hacked around by having ten different possible 'plains' tiles and merging them together after generation has finished at the cost of some efficiency)

In general though, if procedural generation is a goal, ideally the solution space is very unconstrained and there's a lot of possible levels etc. to be generated so that the algorithm doesn't get bogged down in too much backtracking. So from there, control over which specific output is more likely out of a huge range of coherent levels is important.

[spencerflem]

Oh!
& I probably can't help too much as I'm fairly new to Constraint Satisfaction, Logic Programming and Dusa, and don't have an academic background in CS past a BS,

but if there's anything I can do for the language that doesn't mess with your plans let me know!