Wave Function Collapse propagation

Generator.cpp

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;
}