Incipient generators

.gitignore

/test
/amuletgen

amuletgen.d

import ae.utils.array;
import ae.utils.meta;

import std.algorithm.iteration;
import std.algorithm.searching;
import std.algorithm.setops;
import std.bitmanip;
import std.math;
import std.random;
import std.range;
import std.stdio;

// S, E, N, W
static immutable byte[4] dx = [0, 1, 0, -1];
static immutable byte[4] dy = [1, 0, -1, 0];

static immutable byte[4] ddx = [0, 1, 1, 0];
static immutable byte[4] ddy = [0, 0, 1, 1];

struct Array2D(T)
{
	size_t width;
	@property size_t height() const { return data.length / width; }

	T[] data;

	this(size_t width, size_t height)
	{
		this.width = width;
		this.data = new T[width * height];
	}

	T[] row(size_t y) { return data[y * width .. (y + 1) * width]; }

	ref T opIndex(size_t x, size_t y)
	in (x < width && y < height)
	{
		return data[y * width + x];
	}

	T get(size_t x, size_t y, T defaultValue = T.init)
	{
		if (x < width && y < height)
			return data[y * width + x];
		else
			return defaultValue;
	}

	Array2D dup()
	{
		Array2D r = this;
		r.data = r.data.dup;
		return r;
	}

	// void copyTo(ref Amulet l) { l.data[] = this.data[]; }
}

enum AmuletTile : ubyte
{
	None, // No slot
	Slot, // Component can be placed here
	Wall_SE, // ◪ corner
	Wall_NE, // ⬔ corner
	Wall_NW, // ◩ corner
	Wall_SW, // ⬕ corner
	Invalid, // Used internally
}
enum amuletTileChars = ` ◼◪⬔◩⬕`d;

// If this tile continues in a given direction
immutable ubyte[AmuletTile.Invalid] tileWalls = [
	0b0000,
	0b1111,
	0b0011,
	0b0110,
	0b1100,
	0b1001,
];

alias Amulet = Array2D!AmuletTile;

// One array element per AmuletTile vertex (i.e. one of its four corners).
// Thus, a 5x5 Amulet would correspond to a 6x6 AmuletWIP.
alias AmuletWIP = Array2D!bool;

Amulet makeAmulet(int targetSlotCount)
{
	auto size = cast(int)sqrt(float(targetSlotCount)) + 7;
	auto amulet = AmuletWIP(size, size);
	auto amulet2 = amulet.dup; // Candidate
	auto amulet3 = Amulet(size - 1, size - 1); // Post-processed candidate
	auto visited = amulet.dup; // For reachability check

	foreach (y; 1 .. size - 1)
		foreach (x; 1 .. size - 1)
			amulet[x, y] = true;

	auto maxTries = size * size * 10;
	int numTries;
tryLoop:
	while (numTries < maxTries)
	{
		numTries++;
		amulet2.data[] = amulet.data[];

		// Remove a vertex from an edge.
		{
			auto candidates =
				cartesianProduct(
					iota(0, size),
					iota(0, size),
				)
				.filter!(pair =>
					amulet[pair[0], pair[1]] &&
					iota(4).any!(d => !amulet[
						pair[0] + dx[d], 
						pair[1] + dy[d],
					])
				)
			;
			auto numCandidates = candidates.walkLength;
			auto candidate = candidates.drop(uniform(0, numCandidates)).front;
			amulet2[candidate[0], candidate[1]] = false;
		}

		// foreach (y; 0 .. size - 1)
		// 	writeln(amulet2.row(y).map!(c => " @"[c]));

		// Render vertices into slots
		foreach (y; 0 .. size - 1)
			foreach (x; 0 .. size - 1)
			{
				amulet3[x, y] = {
					static immutable AmuletTile[1 << 4] lookup = [
						AmuletTile.None   , AmuletTile.None   , AmuletTile.None   , AmuletTile.None   ,
						AmuletTile.None   , AmuletTile.Invalid, AmuletTile.None   , AmuletTile.Wall_SE,
						AmuletTile.None   , AmuletTile.None   , AmuletTile.Invalid, AmuletTile.Wall_SW,
						AmuletTile.None   , AmuletTile.Wall_NW, AmuletTile.Wall_NE, AmuletTile.Slot   ,
					];
					return iota(4)
						.map!(d => amulet2[x + ddx[d], y + ddy[d]]) // get vertex
						.reduce!((a, b) => (a << 1) | b) // to bitmask
						.I!(b => lookup[b]) // to tile
					;
				}();
				if (amulet3[x, y] == AmuletTile.Invalid)
					continue tryLoop;
			}

		// foreach (y; 0 .. amulet3.height)
		// 	writeln(amulet3.row(y).map!(c => amuletTileChars[c]));

		bool changes;
		do
		{
			changes = false;

			// Convert corners to diagonal walls
			foreach (y; 1 .. size - 1)
				foreach (x; 1 .. size - 1)
					if (amulet3[x, y] == AmuletTile.Slot)
					{
						auto dir = iota(4)
							.map!(d => amulet3[x + dx[d], y + dy[d]])
							.map!(tile => tile ? 1 : 0)
							.reduce!((a, b) => (a << 1) | b)
							.I!(dirs => [0b1100, 0b0110, 0b0011, 0b1001].indexOf(dirs));
						if (dir >= 0)
						{
							amulet3[x, y] = cast(AmuletTile)(AmuletTile.Wall_SE + dir);
							changes = true;
						}
					}

			// Delete weird corners
			foreach (y; 0 .. size - 1)
				foreach (x; 0 .. size - 1)
					if (amulet3[x, y] >= AmuletTile.Wall_SE)
						foreach (d; amulet3[x, y] - AmuletTile.Wall_SE .. amulet3[x, y] - AmuletTile.Wall_SE + 2)
						{
							// writeln("I am ", amuletTileChars[amulet3[x, y]]);
							// writefln("Dir is %s (%+d, %+d)", d, dx[d % $], dy[d % $]);
							auto neighbor = amulet3[x + dx[d % $], y + dy[d % $]];
							// writeln("Neighbor is ", amuletTileChars[neighbor]);
							auto neighborWalls = tileWalls[neighbor];
							auto wallTowardsMe = (neighborWalls >> ((d + 2) % 4)) & 1;
							// writeln("Wall is ", wallTowardsMe);
							if (!wallTowardsMe)
							{
								amulet3[x, y] = AmuletTile.None;
								changes = true;
							}
						}

			// Delete dead ends
			foreach (y; 0 .. size - 1)
				foreach (x; 0 .. size - 1)
					if (amulet3[x, y] == AmuletTile.Slot)
					{
						auto emptyNeighbors = iota(4)
							.map!(d => amulet3[x + dx[d], y + dy[d]])
							.filter!(tile => tile == AmuletTile.None)
							.walkLength;
						if (emptyNeighbors >= 3)
						{
							amulet3[x, y] = AmuletTile.None; // John Conway sends his regards
							changes = true;
						}
					}

			// Delete unreachable
			{
				auto nonEmptyTiles =
					cartesianProduct(
						iota(0, size - 1),
						iota(0, size - 1),
					)
					.filter!(pos => amulet3[pos[0], pos[1]] != AmuletTile.None);

				if (!nonEmptyTiles.empty)
				{
					visited.data[] = false;

					void scan(int x, int y)
					{
						if (visited[x, y])
							return;
						visited[x, y] = true;
						auto tile = amulet3[x, y];
						auto walls = tileWalls[tile];
						foreach (d; 0 .. 4)
							if (walls & (1 << d))
								scan(x + dx[d], y + dy[d]);
					}

					scan(nonEmptyTiles.front[0], nonEmptyTiles.front[1]);

					foreach (y; 0 .. size - 1)
						foreach (x; 0 .. size - 1)
							if (!visited[x, y] && amulet3[x, y] != AmuletTile.None)
							{
								amulet3[x, y] = AmuletTile.None;
								changes = true;
							}
				}
			}

		} while (changes);

		// foreach (y; 0 .. amulet3.height)
		// 	writeln(amulet3.row(y).map!(c => amuletTileChars[c]));


		bool ok = {
			return true;
		}();

		if (!ok)
			continue tryLoop;

		auto currentSlotCount =
			cartesianProduct(
				iota(0, size - 1),
				iota(0, size - 1),
			)
			.filter!(pair =>
				amulet3[pair[0], pair[1]] == AmuletTile.Slot
			)
			.walkLength;

		if (currentSlotCount < targetSlotCount)
			continue; // We overshot

		if (currentSlotCount == targetSlotCount)
			return amulet3; // Perfect match

		// Keep going
		amulet.data[] = amulet2.data[];
		numTries = 0;

		// foreach (y; 0 .. size - 1)
		// 	writeln(amulet.row(y).map!(c => " ·"d[c]));
		// foreach (y; 0 .. amulet3.height)
		// 	writeln(amulet3.row(y).map!(c => amuletTileChars[c]));

	}

	return makeAmulet(targetSlotCount); // retry from scratch
}

void main()
{
	auto seed = uniform!uint();
	// seed = 428002652;
	writeln(seed);
	rndGen.seed(seed);

	auto amulet = makeAmulet(30);
	foreach (y; 0 .. amulet.height)
		writeln(amulet.row(y).map!(c => amuletTileChars[c]));
}

test.d

import ae.utils.meta;

import std.algorithm.iteration;
import std.algorithm.searching;
import std.random;
import std.range;
import std.stdio;

static immutable byte[4] dx = [0, 1, 0, -1];
static immutable byte[4] dy = [1, 0, -1, 0];

enum minimumThickness = 4;
enum maxAspectRatio = 3;
enum maxRoomTries = 200;

struct Array2D(T)
{
	size_t width;
	@property size_t height() const { return data.length / width; }

	T[] data;

	this(size_t width, size_t height)
	{
		this.width = width;
		this.data = new T[width * height];
	}

	T[] row(size_t y) { return data[y * width .. (y + 1) * width]; }

	ref T opIndex(size_t x, size_t y)
	in (x < width && y < height)
	{
		return data[y * width + x];
	}

	Level dup()
	{
		Level r = this;
		r.data = r.data.dup;
		return r;
	}

	// void copyTo(ref Level l) { l.data[] = this.data[]; }
}

alias Level = Array2D!int;

Level makeLevel(int w, int h)
{
	auto level = Level(w, h);
	auto level2 = level.dup;

	foreach (x; 0 .. w)
		level[x, 0] = level[x, h-1] = 1;
	foreach (y; 0 .. h)
		level[0, y] = level[w-1, y] = 1;

	int numTries;
tryLoop:
	while (numTries < maxRoomTries)
	{
		numTries++;
		level2.data[] = level.data[];

		auto x0 = uniform(1, w - 1);
		auto y0 = uniform(1, h - 1);
		foreach (y; y0 - 1 .. y0 + 1 + 1)
			foreach (x; x0 - 1 .. x0 + 1 + 1)
				if (level2[x, y])
					continue tryLoop;

		auto d1 = uniform(0, 4);
		int d2;
		if (numTries < maxRoomTries / 2)
			d2 = (d1 + 1) % 4;
		else
			d2 = uniform(0, 3).I!(d => d >= d1 ? d + 1 : d);
		level2[x0, y0] = 1;

		int[2][] walls;
		foreach (di, d; [d1, d2])
		{
			auto x = x0;
			auto y = y0;
			// while (x >= 0 && y >= 0 && x < w && y < h)
			while (true)
			{
				x += dx[d];
				y += dy[d];
				if (level2[x, y])
					break;
				level2[x, y] = 1;
				walls ~= [x, y];
			}
		}

		walls.randomShuffle();
		// Out of all the walls that we placed, pick one to turn into a door
		auto validDoors = walls
			.filter!(pos =>
				iota(4)
				.map!(d => level2[pos[0] + dx[d], pos[1] + dy[d]])
				// A wall can be a wall if:
				.I!(tiles =>
					// 1. It is not on a corner (has free space on opposite sides)
					tiles
					.map!(tile => tile ? 1 : 0)
					.reduce!((a, b) => (a << 1) | b)
					.I!(dirs => dirs == 0b0101 || dirs == 0b1010)
					&&
					// 2. It is not next to another door
					tiles.all!(tile => tile != 2)
				)
			)
		;
		if (validDoors.empty)
			continue;
		auto door = validDoors.front;
		level2[door[0], door[1]] = 2;

		bool ok = {
			// Check that there are no double walls,
			// or gaps with just one space
			bool check(int x, int y, byte dx, byte dy)
			{
				bool last = !!level2[x, y];
				int runningCount;

				bool flush()
				{
					if (last == 0)
					{
						if (runningCount < minimumThickness)
							return false;
					}
					else
					{
						if (runningCount == 2)
							return false;
					}
					return true;
				}

				while (x < w && y < h)
				{
					auto curr = !!level2[x, y];
					if (curr != last)
					{
						if (!flush()) return false;
						last = curr;
						runningCount = 0;
					}
					runningCount++;
					x += dx;
					y += dy;
				}
				if (!flush()) return false;
				return true;
			}

			foreach (x; 0 .. w)
				if (!check(x, 0, 0, +1))
					return false;
			foreach (y; 0 .. h)
				if (!check(0, y, +1, 0))
					return false;

			// Check that doors are valid
			foreach (x0; 0 .. w)
				foreach (y0; 0 .. h)
					if (level2[x0, y0] == 2)
					{
						auto dirs =
							iota(4)
							.map!(d => level2[x0 + dx[d], y0 + dy[d]])
							.map!(tile => tile ? 1 : 0)
							.reduce!((a, b) => (a << 1) | b);
						if (dirs != 0b0101 && dirs != 0b1010)
							return false;
					}

			// Check that there are no extremely narrow rooms
			foreach (x0; 0 .. w)
				foreach (y0; 0 .. h)
				{
					if (level2[x0, y0])
						continue;

					int[2] space; // distance to walls on each axis
					foreach (d; 0 .. 4)
					{
						auto x = x0;
						auto y = y0;
						while (level2[x, y] == 0)
						{
							x += dx[d];
							y += dy[d];
							space[d % 2]++;
						}
					}

					if (space[0] > space[1] * maxAspectRatio ||
						space[1] > space[0] * maxAspectRatio)
						return false;
				}

			return true;
		}();

		if (!ok)
			continue tryLoop;
			
		level.data[] = level2.data[];
		numTries = 0;
	}

	return level;
}

void main()
{
	// rndGen.seed(706072314);
	auto seed = uniform!uint();
	writeln(seed);
	rndGen.seed(seed);

	writef("\uFEFF");
	auto level = makeLevel(50, 50);
	foreach (y; 0 .. level.height)
		writeln(level.row(y).map!(c => " #·"d[c]));
}