2d/3d - DeBroglie works for both 2d and 3d generation, by selecting an appropriate Topology. Generally, most APIs accept
(x,y,z) co-ordinates - the
z value should just be 0 if you are working in 2d.
Tile - The individual units the generation algorithm works with. Tiles wrap a value of any type, but they are usually an integer index into a tileset, or a Color when working with bitmaps. The value isn't important, all relevant information about a tile is stored externally.
ITopoArray<T> - A 2d or 3d read-only array with one entry per space in the corresponding Topology. They are used as both the input and output format for the library. You can construct these with methods on TopoArray. ITopoArray objects can optionally have a mask associated with them, indicating missing values.
Models are the key way to control the generation process in DeBroglie. They specify what combinations of tiles are legal to place near each other.
Models have only have a few parameters - most information is inferred by giving them samples tilemaps.
AdjacentModel constrains which tiles can be placed adjacent to which other ones. It does so by maintaining for each tile, a list of tiles that can be placed next to it in each direction. The list is always symmetric, i.e. if it is legal to place tile B directly above tile A, then it is legal to place A directly below B.
Adding a sample to an adjacent model adds all adjacent tile pairs in the sample into the legal adjacency lists. You can also directly specify adjacent tile pairs.
The adjacenct model is very "loose" - it doesn't constrain the choice of tiles as much as the overlapping model. This makes it a good choice when the relationship between tiles is very complex, or you are adding a lot other constraints directly.
OverlappingModel constrains that every
n rectangle in the output is a copy of a rectangle taken from the sample (potentially with rotation / reflection).
The model has three parametrs,
nz which specify the dimensions of the rectangle/cuboid in the output. For convenience, you can just specify a value for
n that sets all three. Typically
n is only 2 or 3 - any larger and the algorithm can run quite slow and becomes increasingly unlikely to find a result. It also requires at least one sample - this model cannot be directly configured.
Compared to the adjacent model, the overlapping model is quite strict. This means it typically needs a larger amount of sample input to get good results, but when it does work, it can accurately reproduce many features of the samples that the adjacent model will simply scramble.
In particular, the overlapping model can detect corners, lines and junctions. In conjunction with the propogation by the Wave Function Collapse algorithm, this means that rooms and pathways will get detected and output, but with variations on the placement, size and direction.
Other model functionaltiy
As mentioned, models also track the frequency of tiles in the sample image. You can make changes to this by calling MultiplyFrequency.
Constraints are a way to make additional hard requirements about the generated output. Unlike models, constraints can be non-local, meaning they force some property of the entire image, not just within a small rectangles.
BorderConstraint class restricts what tiles can be selected in various regions of the output. It's pretty common that you want to specify the borders as being ground, or empty, or whatever, as otherwise if DeBroglie will often generate structures that lead off the edge and are clipped.
BorderConstraint only affects the initial set of tiles that can be legally placed. That means it is not doing anything except calling Ban and Select on startup, which you can also do manually. BorderConstraint is just a convenience.
BorderConstraing specifies a set of cells using a simple logic. First, an inclusion set of cells is defined by the Sides field. This field is a bit field of flags, where there is one flag for each of the boundary sides of the output area (4 in 2d, 6 in 3d). An exclusion set is defined similarly from the ExcludeSides field. To get the set of locations affected, subtract the exclusion set from the inclusion set, then optionally invert if InvertArea is set.
The PathConstraint checks that it is possible to connect several locations together via a continuous path of adjacent tiles. It does this by banning any tile placement that would make such a path impossible.
Set PathTiles to the set of tiles that are considered on the path. Any two adjacent locations with tiles in this set are connected, and if x is connected to y and y is connected to z, then x and z are also connected.
By default, PathConstraint forces all path tiles to be connect to each others. However, if you set EndPoints then instead it forces that those specific points connect to each other, but doesn't stop extra path tiles being placed.
PathConstraint does not have a great deal of lookahead, so adding it will significantly increase the amount of retries needed to get a successful generation. You may need to enable backtracking to get a successful result.
The FixedTileConstraint class forces a given location to be the specified Tile at initialization. If you don't specify a location, a random legal location is chosen.
You can use FixedTileConstraint to force certain features to always be generated.
You can define your own constraints by extending ITileConstraint. The Init method is called once per propagator run, and the Check method is called after each step, each time tiles are selected.
Inside these methods, you can call Select and Ban to control what tiles can be legally placed. You can also return Contradiction to indicate that something is wrong and generation cannot continue. Otherwise, return Undecided to indicate that generation should continue.
By default when you call Run() the WFC algorithm keeps adding tiles until it has filled every location, or until it is impossible to place a tile that satisfies all the constraints set up. It then returns Contradiction.
If you set the backtrack argument to
true when constructing the TilePropagator, then the propagator does not give up when a contradiction occurs. I will attempt to roll back the most recent tile placement, and try another placment instead. In this manner, it can explore the entire space of possible tile placements, seeking one that satifies the constraints. Contradiction is only returned if all possibilities have been exhausted.
Backtracking is very powerful and general, and can solve extremely difficult layouts. However, it can be quite slow, and consumes a great deal of memory, so it is generally only appropriate for generating small arrays.
The most common case of using DeBroglie is to generate 2d images and tile maps, however, that is not all that can be generated.
DeBroglie uses a mechanism called Topology to specify the type of area or volume to generate, what size it is, and whether it should wrap around at the edges (i.e. is it periodic). Topologies do not actually store data, they just specify the dimensions. Actual data is stored in an ITopoArray<T>.
Currently, three types of topology are supported: 2d square grid, 2d hex grid, and 3d cube grid.
The topology of the generated result is inferred from the input samples. When using the command line tool the topology of the input is based on the file being read. But as a C# library, samples are passed as ITopoArray<T> objects.
So you must directly call the Topology constructor, and then create ITopoArray<T> objects using the methods on TopoArray. There's also many shortcut methods that don't require a topology if you just want to work with square grids.
Hexagonal topologies use a convention of "pointy side up". The x-axis moves to the right, and the y-axis moves down and to the left. This means the library generates rhombus shaped output. Additionally, periodic input / output is not supported.
Using the Tiled format for import/export of hexagonal tilemaps is recommended, as most software doesn't have support for hexagons. DeBroglie comes with TiledUtil to facilitate converting between ITopoArray<T> objects and Tiled maps.
When using the overlapping model, the constraints are based on
n rhombus shapes, rather than
Handling rotation of the input sample is a complex topic, and is discussed in a separate article.