Skip to content

Instantly share code, notes, and snippets.

@rorydriscoll
Last active December 14, 2016 21:18
Show Gist options
  • Save rorydriscoll/72bcaf00087c07373cc820cc8bd63b6e to your computer and use it in GitHub Desktop.
Save rorydriscoll/72bcaf00087c07373cc820cc8bd63b6e to your computer and use it in GitHub Desktop.
Wave Function Collapse propagation
struct Block
{
__forceinline void Clear()
{
vector[0] = vector[1] = _mm_setzero_si128();
}
__forceinline void Fill()
{
vector[0] = vector[1] = _mm_set_epi64x(0xffffffffffffffff, 0xffffffffffffffff);
}
__forceinline void Add(int i)
{
members[i >> 6] |= uint64_t(1) << (i & 0b111111);
}
__forceinline void Remove(int i)
{
members[i >> 6] &= ~(uint64_t(1) << (i & 0b111111));
}
__forceinline void Union(const Block& other)
{
vector[0] = _mm_or_si128(vector[0], other.vector[0]);
vector[1] = _mm_or_si128(vector[1], other.vector[1]);
}
__forceinline void Intersect(const Block& other)
{
vector[0] = _mm_and_si128(vector[0], other.vector[0]);
vector[1] = _mm_and_si128(vector[1], other.vector[1]);
}
__forceinline bool IsMember(int i) const
{
return (members[i >> 6] & (uint64_t(1) << (i & 0b111111))) != 0;
}
__forceinline int Disjoint(const Block& other) const
{
return _mm_testz_si128(vector[0], other.vector[0]) && _mm_testz_si128(vector[1], other.vector[1]);
}
__forceinline int CountMembers() const
{
return int(__popcnt64(members[0]) + __popcnt64(members[1]) + __popcnt64(members[2]) + __popcnt64(members[3]));
}
int FindFirstSet() const
{
for (int m = 0; m < 4; ++m)
{
if (members[m] == 0)
continue;
return int(64 * m + int(__lzcnt64(members[m])));
}
return -1;
}
union
{
uint64_t members[4] = { 0, 0, 0, 0 };
__m128i vector[2];
};
};
INTERNAL bool Propagate(Grid<Block>& blocks, Grid<int>& entropies, Grid<bool>& dirty, Queue<Change>& changes, const Propagator& propagator)
{
while (!changes.IsEmpty())
{
const Change change = changes.Dequeue();
// Clear the dirty flag early since it may need to go back on the queue
dirty(change.i, change.j) = false;
// Test all blocks around the block that changed to see if they have any patterns that are no
// longer compatible. We will check in a grid around the block that changed and use the precomputed
// block compatibility to determine which patterns in the neighboring blocks are still valid.
//
// A change to block r can affect 2 * Pattern::N - 1 blocks around it.
//
// *---*---*---*---*---*
// | | | | | |
// *---*---*---*---*---*
// | | | | | |
// *---*---*---*---*---*
// | | | r | | |
// *---*---*---*---*---*
// | | | | | |
// *---*---*---*---*---*
// | | | | | |
// *---*---*---*---*---*
const Block& reference = blocks(change.i, change.j);
const int n = Pattern::N - 1;
const int i0 = Max(0, change.i - n);
const int i1 = Min(blocks.w - 1, change.i + n);
const int j0 = Max(0, change.j - n);
const int j1 = Min(blocks.h - 1, change.j + n);
for (int j = j0; j <= j1; ++j)
{
for (int i = i0; i <= i1; ++i)
{
// If the block is fully resolved (i.e. the entropy is one) then it can't change, so skip it
const int old_entropy = entropies(i, j);
if (old_entropy == 1)
continue;
// Grab the root of the list of patterns which are compatible in this particular slot
Block& neighbor = blocks(i, j);
const int s = change.i - i + n;
const int t = change.j - j + n;
const Block* root = propagator.GetRoot(s, t);
// For all patterns which are still valid in the neighbor, check that there is at least one pattern in
// the reference block which is compatible. If there are none then the pattern is no longer valid for
// the neighbor.
// This loop looks a bit complicated due to the fact that I've made some performance optimizations. It's
// basically the following:
//
// for (every pattern possible)
// {
// if (neighbor has pattern && no patterns in reference are compatible)
// remove pattern from neighbor
// }
for (int m = 0; m < 4; ++m)
{
const Block* valid = root + (m * 64);
for (uint64_t mask = 1, remaining = neighbor.members[m]; remaining > 0; remaining >>= 1, mask <<= 1, ++valid)
{
if ((remaining & 0x1) != 0 && reference.Disjoint(*valid))
neighbor.members[m] &= ~mask;
}
}
// If the block entropy didn't change then neither did the block, so skip
const int new_entropy = neighbor.CountMembers();
if (old_entropy == new_entropy)
continue;
// If the block entropy drops to zero then we've arrived at a contradiction. A nearby change invalidated all options
// left for this block and so the generation has failed.
if (new_entropy == 0)
{
LOG_ERROR("Block %i, %i has no more options", i, j);
return false;
}
// The block has changed so we need to update the entropy and add it to the queue to be processed. We'll use a dirty
// grid here to prevent the block from being added multiple times to the queue. Due to the nature of the cascading
// updates, blocks may be changed multiple times. As long as the block is already on the change queue then the changes
// will eventually be picked up.
entropies(i, j) = new_entropy;
if (!dirty(i, j))
{
dirty(i, j) = true;
changes.Enqueue(i, j);
}
}
}
}
return true;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment