Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Setup:
- 1. Create a voxel grid, and build a list of cells which are cubes on the grid with a voxel at each corner. Each cell is a WFC tile and the value of the 8 corners represents the constraints for that tile.
- 2. Initialise WFC - each cell stores a list of tiles (I call these prototypes) that fit the current configuration of the voxel grid. Initially, this means the bottom row of voxels will have value 1 (ground) and the rest 0 (empty). So, the bottom row of cells will only allow prototypes with 1111-0000 (bottom-top) corners.
- 3. Calculate entropy for each cell.
- 4. Cache the current wave state (the list of available prototypes within each cell), and entropy state.
- 5. I also set every empty cell to be 'inactive'. WFC doesn't propagate changes to inactive cells, which will be most cells until the the voxel grid starts getting populated with non-0.
- 6. Run WFC which basically just collapses all the active ground cells to ground.
- # On voxel grid change:
- 1. Restore to the previous cached wave and entropy state (super quick memcpy).
- 2. Set the value of the selected voxel to 1 (for simplicity - this can be any value as long as there are tiles to support the configuration of voxels. E.g. I have buildings on 2, and I plan to add foliage on 3).
- 3. On each of the 8 cells that have that voxel as a corner, update the list of supported prototypes (those that match the configuration of the 8 voxel corners).
- 4. Activate and calculate entropy for the affected cells.
- 5. Update the wave and entropy cache with the changes.
- 6. Run WFC again.
- # WFC Step:
- 1. Collapse the lowest entropy cell (I actually don't use Shannon here, but rather distance from the changed voxel, closest are collapsed first).
- 2. Simple WFC propagation (not AC-4) where the collapsed cell is added to the stack and we remove possible prototypes from all neighbors which are no longer supported.
- 3. Run until there are are no active un-collapsed cells.
- # Notes:
- * Each prototype actually defines an extra set of constraints, which allow variation between tiles that have the same voxel-space configuration. E.g. to take a Townscaper example, a roof tile could collapse to a variant with half a chimney, so its neighbor needs to be constrained to have the other half. This is an extra flag per voxel in each direction and packed into the same int used for the voxel value when comparing prototypes for compatibility, so it doesn't have any extra cost.
- * Cost scales pretty linearly with the amount of active cells, so as the voxel space increases in size, things get slower. I haven't really pushed this past ~100, with a few hundred prototypes, but performance isn't a big concern yet. Also, between runs of WFC the majority of tiles don't change at all so even if WFC takes a few frames to finish, it might not be noticeable since the mesh is only updated if the collapsed prototype in that cell changes.
- * I am burst compiling the WFC step code (in Unity), which provides massive speed-up. I'd say if you're not doing this already, it's a must.
Advertisement
Add Comment
Please, Sign In to add comment