4. Generation
The first major step in Kuf is writing a routine that randomly generates a square that will always be technically correct. Before we go through an algorithm for that, a few operations need to be defined.
4.1. Being Technically Correct
In Kuf, a technically correct pattern square is one whose
quads and subquads do not contain the patterns 0, 6, 9, or
f. A quad can be checked with kuf_quad_check
int kuf_quad_check(uint8_t quad);int kuf_quad_check(uint8_t quad)
{
quad &= 0xf;
return
quad != 0 &&
quad != 6 &&
quad != 9 &&
quad != 0xf;
}4.2. Kuf Random Number Generator
To keep generated output consistent between platforms, a simple 32-bit internal PRNG is implemented, requiring a single 32-bit integer to keep track of state.
uint32_t kuf_rand(uint32_t rng);uint32_t kuf_rand(uint32_t rng)
{
rng = (1103515245 * rng + 12345) % 2147483648;
return rng;
}kuf_rng will call kuf_rand and update the state in one
call.
uint32_t kuf_rng(uint32_t *rng);uint32_t kuf_rng(uint32_t *rng)
{
*rng = kuf_rand(*rng);
return *rng;
}4.3. Quad Generation + Operations
4.3.1. Set Bit
This static function is used to set a bit in a quad.
static uint8_t set_bit(uint8_t quad,
uint8_t pos,
uint8_t bit);static uint8_t set_bit(uint8_t quad,
uint8_t pos,
uint8_t bit)
{
if (bit) quad |= 1 << pos;
else quad &= ~(1 << pos);
return quad;
}
4.3.2. Generate a Quad
A randomly generated quad can be generated with
kuf_gen_quad. This can be any quad pattern, as long as it
isn't one of the violation patterns.
uint8_t kuf_gen_quad(uint32_t *rng);uint8_t kuf_gen_quad(uint32_t *rng)
{
uint8_t quad;
quad = (kuf_rng(rng) >> 8) & 0xf;
while (!kuf_quad_check(quad)) quad = (kuf_rng(rng) >> 8) & 0xf;
return quad;
}4.3.3. Generate a Tile
A randomly generated tile can be generated with
kuf_gen_tile. It will return a 1 or a 0.
uint8_t kuf_gen_tile(uint32_t *rng);Get the last bit in the RNG.
uint8_t kuf_gen_tile(uint32_t *rng)
{
return (kuf_rng(rng) >> 8) & 1;
}4.3.4. Generate a Pair
A randomly generated pair can be generated with
kuf_gen_pair. It will store the output in the first
2 bits.
uint8_t kuf_gen_pair(uint32_t *rng);uint8_t kuf_gen_pair(uint32_t *rng)
{
return (kuf_rng(rng) >> 8) & 0x3;
}4.3.5. Manipulate Quad Sides
Pairs can be set to a quad on one of four cardinal sides
with kuf_quad_side_set, and retrieved with
kuf_quad_side_get. This takes in a quad and one of the
sides KUF_NORTH, KUF_SOUTH, KUF_EAST, and KUF_WEST.
uint8_t kuf_quad_side_set(uint8_t quad,
uint8_t side,
uint8_t pair);
uint8_t kuf_quad_side_get(uint8_t quad, uint8_t side);uint8_t kuf_quad_side_set(uint8_t quad,
uint8_t side,
uint8_t pair)
{
pair &= 0x3;
switch (side) {
case KUF_NORTH:
quad = set_bit(quad, 0, pair & 1);
quad = set_bit(quad, 1, (pair >> 1) & 1);
break;
case KUF_SOUTH:
quad = set_bit(quad, 2, pair & 1);
quad = set_bit(quad, 3, (pair >> 1) & 1);
break;
case KUF_EAST:
quad = set_bit(quad, 1, pair & 1);
quad = set_bit(quad, 3, (pair >> 1) & 1);
break;
case KUF_WEST:
quad = set_bit(quad, 0, pair & 1);
quad = set_bit(quad, 2, (pair >> 1) & 1);
break;
}
return quad;
}uint8_t kuf_quad_side_get(uint8_t quad, uint8_t side)
{
uint8_t s;
s = 0;
switch (side) {
case KUF_NORTH:
s = quad & 3;
break;
case KUF_SOUTH:
s = (quad >> 2) & 3;
break;
case KUF_EAST:
s = ((quad >> 1) & 1) | (((quad >> 3) & 1) << 1);
break;
case KUF_WEST:
s = (quad & 1) | (((quad >> 2) & 1) << 1);
break;
}
return s;
}enum {
KUF_NORTH,
KUF_SOUTH,
KUF_EAST,
KUF_WEST
};4.3.6. Manipulate Quad Tiles
Tiles in a Quad can be set with kuf_quad_tile_set and
kuf_quad_tile_get. These take in the quad and the
intercardinal directions KUF_NORTHWEST, KUF_NORTHEAST,
KUF_SOUTHWEST, and KUF_SOUTHEAST.
uint8_t kuf_quad_tile_get(uint8_t quad, uint8_t corner);
uint8_t kuf_quad_tile_set(uint8_t quad,
uint8_t corner,
uint8_t tile);uint8_t kuf_quad_tile_get(uint8_t quad, uint8_t corner)
{
int pos;
pos = 0;
switch (corner) {
case KUF_NORTHWEST:
pos = 0;
break;
case KUF_NORTHEAST:
pos = 1;
break;
case KUF_SOUTHWEST:
pos = 2;
break;
case KUF_SOUTHEAST:
pos = 3;
break;
}
return (quad >> pos) & 1;
}uint8_t kuf_quad_tile_set(uint8_t quad,
uint8_t corner,
uint8_t tile)
{
int pos;
pos = 0;
switch (corner) {
case KUF_NORTHWEST:
pos = 0;
break;
case KUF_NORTHEAST:
pos = 1;
break;
case KUF_SOUTHWEST:
pos = 2;
break;
case KUF_SOUTHEAST:
pos = 3;
break;
}
return set_bit(quad, pos, tile & 1);
}enum {
KUF_NORTHWEST,
KUF_NORTHEAST,
KUF_SOUTHWEST,
KUF_SOUTHEAST
};4.3.7. Manipulate Quads From Squares
Quads in a square can be set and retrieved with
kuf_square_quad_get and kuf_square_quad_set. In addition
to the square, can take in a main quad like KUF_QUAD_A,
KUF_QUAD_B, KUF_QUAD_C, or KUF_QUAD_D, or one of
the subquads KUF_QUAD_AB, KUF_QUAD_AC, KUF_QUAD_BD,
KUF_QUAD_CD, and KUF_QUAD_ABCD.
uint8_t kuf_square_quad_get(uint16_t s, uint8_t pos);
uint16_t kuf_square_quad_set(uint16_t s,
uint8_t pos,
uint8_t quad);uint8_t kuf_square_quad_get(uint16_t s, uint8_t pos)
{
uint8_t quad;
quad = 0;
switch (pos) {
<<get_quads_A_B_C_D>>
<<get_quads_AB_AC_BD_CD>>
<<get_quad_ABCD>>
}
return quad;
}
uint16_t kuf_square_quad_set(uint16_t s,
uint8_t pos,
uint8_t quad)
{
switch (pos) {
<<set_quads_A_B_C_D>>
<<set_quads_AB_AC_BD_CD>>
<<set_quad_ABCD>>
}
return s;
}Quads A, B, C, and D are stored as nibbles in the 16-bit integer. These can be retrieved by masking at each 4-bit boundary.
case KUF_QUAD_A:
quad = s & 0xf;
break;
case KUF_QUAD_B:
quad = (s >> 4) & 0xf;
break;
case KUF_QUAD_C:
quad = (s >> 8) & 0xf;
break;
case KUF_QUAD_D:
quad = (s >> 12) & 0xf;
break;case KUF_QUAD_A:
s = (s & ~0xf) | quad;
break;
case KUF_QUAD_B:
s = (s & ~(0xf << 4)) | (quad << 4);
break;
case KUF_QUAD_C:
s = (s & ~(0xf << 8)) | (quad << 8);
break;
case KUF_QUAD_D:
s = (s & ~(0xf << 12)) | (quad << 12);
break;Quads AB, AC, BD, and CD get a little more challenging because they are contiguously living next to eachother in the integer they are stored in. Some "sewing" needs to happen using the previously defined quad side operations.
For AB, the east side of A becomes the west side, and the west side of B becomes the east side.
case KUF_QUAD_AB: {
uint8_t tmp;
/* east side of quad A */
tmp = kuf_quad_side_get(s & 0xf, KUF_EAST);
quad = kuf_quad_side_set(quad, KUF_WEST, tmp);
/* west side of quad B */
tmp = kuf_quad_side_get((s >> 4) & 0xf, KUF_WEST);
quad = kuf_quad_side_set(quad, KUF_EAST, tmp);
break;
}case KUF_QUAD_AB: {
uint8_t tmp;
tmp = kuf_quad_side_set(s & 0xf,
KUF_EAST,
kuf_quad_side_get(quad, KUF_WEST));
s = (s & ~0xf) | tmp;
tmp = kuf_quad_side_set((s >> 4) & 0xf,
KUF_WEST,
kuf_quad_side_get(quad, KUF_EAST));
s = (s & ~(0xf << 4)) | (tmp << 4);
break;
}For AC, the south side of A becomes the north side, and the north side of C becomes the south side.
case KUF_QUAD_AC: {
uint8_t tmp;
/* south side of quad A */
tmp = kuf_quad_side_get(s & 0xf, KUF_SOUTH);
quad = kuf_quad_side_set(quad, KUF_NORTH, tmp);
/* north side of quad C */
tmp = kuf_quad_side_get((s >> 8) & 0xf, KUF_NORTH);
quad = kuf_quad_side_set(quad, KUF_SOUTH, tmp);
break;
}case KUF_QUAD_AC: {
uint8_t tmp;
tmp = kuf_quad_side_set(s & 0xf,
KUF_SOUTH,
kuf_quad_side_get(quad, KUF_NORTH));
s = (s & ~0xf) | tmp;
tmp = kuf_quad_side_set((s >> 8) & 0xf,
KUF_NORTH,
kuf_quad_side_get(quad, KUF_SOUTH));
s = (s & ~(0xf << 8)) | (tmp << 8);
break;
}For BD, the south side of B becomes the north side, and the north side of D becomes the south side.
case KUF_QUAD_BD: {
uint8_t tmp;
/* south side of quad B */
tmp = kuf_quad_side_get((s >> 4) & 0xf, KUF_SOUTH);
quad = kuf_quad_side_set(quad, KUF_NORTH, tmp);
/* north side of quad D */
tmp = kuf_quad_side_get((s >> 12) & 0xf, KUF_NORTH);
quad = kuf_quad_side_set(quad, KUF_SOUTH, tmp);
break;
}case KUF_QUAD_BD: {
uint8_t tmp;
tmp = kuf_quad_side_set((s >> 4) & 0xf,
KUF_SOUTH,
kuf_quad_side_get(quad, KUF_NORTH));
s = (s & ~(0xf << 4)) | (tmp << 4);
tmp = kuf_quad_side_set((s >> 12) & 0xf,
KUF_NORTH,
kuf_quad_side_get(quad, KUF_SOUTH));
s = (s & ~(0xf << 12)) | (tmp << 12);
break;
}For CD, the east side of C becomes the west side, and the west side of D becomes the east side.
case KUF_QUAD_CD: {
uint8_t tmp;
/* east side of quad C */
tmp = kuf_quad_side_get((s >> 8) & 0xf, KUF_EAST);
quad = kuf_quad_side_set(quad, KUF_WEST, tmp);
/* west side of quad D */
tmp = kuf_quad_side_get((s >> 12) & 0xf, KUF_WEST);
quad = kuf_quad_side_set(quad, KUF_EAST, tmp);
break;
}case KUF_QUAD_CD: {
uint8_t tmp;
tmp = kuf_quad_side_set((s >> 8) & 0xf,
KUF_EAST,
kuf_quad_side_get(quad, KUF_WEST));
s = (s & ~(0xf << 8)) | (tmp << 8);
tmp = kuf_quad_side_set((s >> 12) & 0xf,
KUF_WEST,
kuf_quad_side_get(quad, KUF_EAST));
s = (s & ~(0xf << 12)) | (tmp << 12);
break;
}The center quad, ABCD, is composed of a tile from each main quad. Southeast A becomes Northwest. Southwest B becomes Northeast. Northeast C becomes Southwest. Northwest D becomes Southeast.
case KUF_QUAD_ABCD: {
uint8_t tmp;
/* A(SE) -> NW */
tmp = kuf_quad_tile_get(s & 0xf, KUF_SOUTHEAST);
quad = kuf_quad_tile_set(quad, KUF_NORTHWEST, tmp);
/* B(SW) -> NE */
tmp = kuf_quad_tile_get(s >> 4 & 0xf, KUF_SOUTHWEST);
quad = kuf_quad_tile_set(quad, KUF_NORTHEAST, tmp);
/* C(NE) -> SW */
tmp = kuf_quad_tile_get(s >> 8 & 0xf, KUF_NORTHEAST);
quad = kuf_quad_tile_set(quad, KUF_SOUTHWEST, tmp);
/* D(NW) -> SE */
tmp = kuf_quad_tile_get(s >> 12 & 0xf, KUF_NORTHWEST);
quad = kuf_quad_tile_set(quad, KUF_SOUTHEAST, tmp);
break;
}case KUF_QUAD_ABCD: {
uint8_t tmp;
/* Q(NW) -> A(SE) */
tmp = kuf_quad_tile_set(s & 0xf,
KUF_SOUTHEAST,
kuf_quad_tile_get(quad, KUF_NORTHWEST));
s = (s & ~0xf) | tmp;
/* Q(NE) -> B(SW) */
tmp = kuf_quad_tile_set((s >> 4) & 0xf,
KUF_SOUTHWEST,
kuf_quad_tile_get(quad, KUF_NORTHEAST));
/* Q(SW) -> C(NE) */
s = (s & ~(0xf << 4)) | (tmp << 4);
tmp = kuf_quad_tile_set((s >> 8) & 0xf,
KUF_NORTHEAST,
kuf_quad_tile_get(quad, KUF_SOUTHWEST));
s = (s & ~(0xf << 8)) | (tmp << 8);
/* Q(SE) -> D(NW) */
tmp = kuf_quad_tile_set((s >> 12) & 0xf,
KUF_NORTHWEST,
kuf_quad_tile_get(quad, KUF_SOUTHEAST));
s = (s & ~(0xf << 12)) | (tmp << 12);
break;
}enum {
KUF_QUAD_A,
KUF_QUAD_B,
KUF_QUAD_C,
KUF_QUAD_D,
KUF_QUAD_AB,
KUF_QUAD_AC,
KUF_QUAD_BD,
KUF_QUAD_CD,
KUF_QUAD_ABCD
};4.4. Square Generation
With the previously mentioned operations, a technically
correct kufic square can be generated. The function to
generate a square can be done with kuf_gen_square.
uint16_t kuf_gen_square(uint32_t *rng);uint16_t kuf_gen_square(uint32_t *rng)
{
uint16_t sq;
sq = 0;
<<generate_A>>
<<generate_AC>>
<<generate_C>>
<<generate_ABCD>>
<<generate_BD>>
<<generate_final_tiles>>
return sq;
}A square is created by generating quads and subquads in a specific order, and using the some of the information from previously generated correct quads to generate new correct quads. The order goes A, AC, C, ABCD, BD, AB, BD, B, D.
A gets generated first. This is a random quad.
sq = kuf_square_quad_set(sq, KUF_QUAD_A, kuf_gen_quad(rng));AC is a constrained subquad whose north pair is the south pair of A. The south pair of AC is generated here. A random pair will be generated. If this quad is valid, it will use it as the AC quad. Otherwise, the procedure will shift through the four other possibilities until it has found a correct quad.
The south pair of AC is set to be the north pair of C.
{
uint8_t p_s;
uint8_t p_n;
uint8_t ac;
p_s = kuf_gen_pair(rng);
p_n =
kuf_quad_side_get(
kuf_square_quad_get(sq, KUF_QUAD_A),
KUF_SOUTH);
ac = 0;
ac = kuf_quad_side_set(ac, KUF_NORTH, p_n);
ac = kuf_quad_side_set(ac, KUF_SOUTH, p_s);
if (!kuf_quad_check(ac)) {
int i;
for (i = 0; i < 4; i++) {
ac = kuf_quad_side_set(ac, KUF_SOUTH, (p_s + i) % 4);
if (kuf_quad_check(ac)) break;
}
}
sq = kuf_square_quad_set(sq, KUF_QUAD_AC, ac);
}A similar procedure is used to find the south pair of C.
{
uint8_t p_s;
uint8_t p_n;
uint8_t c;
p_s = kuf_gen_pair(rng);
p_n =
kuf_quad_side_get(
kuf_square_quad_get(sq, KUF_QUAD_AC),
KUF_SOUTH);
c = 0;
c = kuf_quad_side_set(c, KUF_NORTH, p_n);
c = kuf_quad_side_set(c, KUF_SOUTH, p_s);
if (!kuf_quad_check(c)) {
int i;
for (i = 0; i < 4; i++) {
c = kuf_quad_side_set(c, KUF_SOUTH, (p_s + i) % 4);
if (kuf_quad_check(c)) break;
}
}
sq = kuf_square_quad_set(sq, KUF_QUAD_C, c);
}At this point, quads A and C have been determined, and these components can be used to generated ABCD. The southeast tile of A and the northeast tile of C together form the west side of ABCD. The east side of ABCD is then generated to complete the quad.
{
uint8_t abcd;
uint8_t p_e;
abcd = 0;
abcd = kuf_quad_tile_set(abcd,
KUF_NORTHWEST,
kuf_quad_tile_get(
kuf_square_quad_get(sq, KUF_QUAD_A),
KUF_SOUTHEAST));
abcd = kuf_quad_tile_set(abcd,
KUF_SOUTHWEST,
kuf_quad_tile_get(
kuf_square_quad_get(sq, KUF_QUAD_C),
KUF_NORTHEAST));
p_e = kuf_gen_pair(rng);
abcd = kuf_quad_side_set(abcd, KUF_EAST, p_e);
if (!kuf_quad_check(abcd)) {
int i;
for (i = 0; i < 4; i++) {
abcd = kuf_quad_side_set(abcd, KUF_EAST, (p_e + i) % 4);
if (kuf_quad_check(abcd)) break;
}
}
sq = kuf_square_quad_set(sq, KUF_QUAD_ABCD, abcd);
}From there, things move to the right one tile to generate quad BD. The east side of ABCD is set to be the west side of BD, which in turn is used to fill in the east side and complete the quad.
{
uint8_t bd;
uint8_t abcd;
uint8_t p_e;
abcd = kuf_square_quad_get(sq, KUF_QUAD_ABCD);
bd = 0;
bd = kuf_quad_side_set(bd,
KUF_WEST,
kuf_quad_side_get(abcd, KUF_EAST));
p_e = kuf_gen_pair(rng);
bd = kuf_quad_side_set(bd, KUF_EAST, p_e);
if (!kuf_quad_check(bd)) {
int i;
for (i = 0; i < 4; i++) {
bd = kuf_quad_side_set(bd, KUF_EAST, (p_e + i) % 4);
if (kuf_quad_check(bd)) break;
}
}
sq = kuf_square_quad_set(sq, KUF_QUAD_BD, bd);
}At this point, only tiles get filled in order to complete the remaining quads. A tile is chosen at random, and if it doesn't work, it goes with the other choice.
The northeast tile of AB gets generated, which then enables the northeast tile of B to be completed.
The southeast tile of CD gets generated, which then enables the southeast tile of D to be completed.
{
uint8_t ab;
uint8_t cd;
uint8_t b;
uint8_t d;
uint8_t t;
ab = kuf_square_quad_get(sq, KUF_QUAD_AB);
sq = kuf_square_quad_set(sq, KUF_QUAD_AB, ab);
t = kuf_gen_tile(rng);
ab = kuf_quad_tile_set(ab, KUF_NORTHEAST, t);
if (!kuf_quad_check(ab)) {
ab = kuf_quad_tile_set(ab, KUF_NORTHEAST, t ? 0 : 1);
}
sq = kuf_square_quad_set(sq, KUF_QUAD_AB, ab);
b = kuf_square_quad_get(sq, KUF_QUAD_B);
t = kuf_gen_tile(rng);
b = kuf_quad_tile_set(b, KUF_NORTHEAST, t);
if (!kuf_quad_check(b)) {
b = kuf_quad_tile_set(b, KUF_NORTHEAST, t ? 0 : 1);
}
sq = kuf_square_quad_set(sq, KUF_QUAD_B, b);
cd = kuf_square_quad_get(sq, KUF_QUAD_CD);
t = kuf_gen_tile(rng);
cd = kuf_quad_tile_set(cd, KUF_SOUTHEAST, t);
if (!kuf_quad_check(cd)) {
cd = kuf_quad_tile_set(cd, KUF_SOUTHEAST, t ? 0 : 1);
}
sq = kuf_square_quad_set(sq, KUF_QUAD_CD, cd);
d = kuf_square_quad_get(sq, KUF_QUAD_D);
t = kuf_gen_tile(rng);
d = kuf_quad_tile_set(d, KUF_SOUTHEAST, t);
if (!kuf_quad_check(d)) {
d = kuf_quad_tile_set(d, KUF_SOUTHEAST, t ? 0 : 1);
}
sq = kuf_square_quad_set(sq, KUF_QUAD_D, d);
}And with that, a technically correct square is generated.
4.5. Building Up Squares From Quads
The function kuf_glue_square glues together a square
from quads A, B, C, D.
uint16_t kuf_glue_square(uint8_t a,
uint8_t b,
uint8_t c,
uint8_t d);uint16_t kuf_glue_square(uint8_t a,
uint8_t b,
uint8_t c,
uint8_t d)
{
uint16_t s;
s = 0;
s = kuf_square_quad_set(s, KUF_QUAD_A, a);
s = kuf_square_quad_set(s, KUF_QUAD_B, b);
s = kuf_square_quad_set(s, KUF_QUAD_C, c);
s = kuf_square_quad_set(s, KUF_QUAD_D, d);
return s;
}4.6. Breaking Up Squares into Quads
The function kuf_break_square will break up a square
into core quads A, B, C, D.
void kuf_break_square(uint16_t s,
uint8_t *a,
uint8_t *b,
uint8_t *c,
uint8_t *d);void kuf_break_square(uint16_t s,
uint8_t *a,
uint8_t *b,
uint8_t *c,
uint8_t *d)
{
*a = kuf_square_quad_get(s, KUF_QUAD_A);
*b = kuf_square_quad_get(s, KUF_QUAD_B);
*c = kuf_square_quad_get(s, KUF_QUAD_C);
*d = kuf_square_quad_get(s, KUF_QUAD_D);
}4.7. Block Generation
Next up is generating a technically correct block. A block is a 2x2 arrangment of squares.
4.7.1. Top Level Function
A block is generated with the function kuf_gen_block.
The output returns to 4 squares W, X, Y, and Z, which
are meant to be arranged left-right, top-bottom in a 2x2
formation.
void kuf_gen_block(uint32_t *rng,
uint16_t *pw,
uint16_t *px,
uint16_t *py,
uint16_t *pz);void kuf_gen_block(uint32_t *rng,
uint16_t *pw,
uint16_t *px,
uint16_t *py,
uint16_t *pz)
{
uint16_t w, x, y, z;
uint16_t wy;
uint16_t wxyz;
uint16_t xz;
uint16_t wx;
uint16_t yz;
w = x = y = z = 0;
<<generate_w>>
<<generate_wy>>
<<generate_y>>
<<generate_wxyz>>
<<generate_xz>>
<<generate_wx>>
<<generate_x>>
<<generate_yz>>
<<generate_z>>
*pw = w;
*px = x;
*py = y;
*pz = z;
}4.7.2. Overview
Making a block is similar to making a square, only one level higher. It begins with a technically correct square, then generating correct squares moving one quad at a time.
Before, some more terminology. Blocks are very similar in concept to squares in that they are both grouped 2x2 units of tiles.
Blocks are composed of 4 squares: moving left right top down, these squares are labelled W, X, Y, Z.
For this block synthesizer algorithm, it is assumed that square W is completed and technically correct. Using W, the algorithm generates a technically correct solution for X, Y, and Z.
Like the how square synthesizer generated intermediate quads, the block solves intermediate squares in the following order: W (provided), WY, Y, WXYZ, XZ, WX, YZ, X, Z.
A bundle of two squares is known as a wall, to distinguish it from sides of a quad.
Squares are generated by solving walls and quads. This algorithm is constricted to top, down, left, right movement. South and east are the only walls required. North east and south east are the only quads required.
4.7.3. Solvers
4.7.3.1. Wall Solver
Generating a wall in a square is known as a "wall solver". For this block algorithm, only an east east and south wall solver required. It works like this: given two quads, generate two new quads that will complete the square.
Wall solvers represent squares as 4 quads A, B, C, and D.
The inputs are the known quads, the outputs are the solved quads.
4.7.3.1.1. Eastern Wall
An eastern solver has knowns A and C, and creates a solution for b and d.
void kuf_solve_wall_east(uint32_t *rng,
uint8_t a, uint8_t c,
uint8_t *pb, uint8_t *pd);void kuf_solve_wall_east(uint32_t *rng,
uint8_t a, uint8_t c,
uint8_t *pb, uint8_t *pd)
{
uint8_t b;
uint8_t d;
uint8_t abcd;
uint8_t bd;
uint8_t ab;
uint8_t cd;
b = 0;
d = 0;
<<eastwall_ABCD_E>>
<<eastwall_BD_E>>
<<eastwall_AB_NE>>
<<eastwall_B_NE>>
<<eastwall_CD_SE>>
<<eastwall_D_SE>>
*pb = b;
*pd = d;
}Solving for the eastern wall is very similar to the
approach used in kuf_gen_square, except that A and
C are already provided. From there the quads are solved
in the following order: ABCD, BD, AB, B, CD, D.
To complete ABCD: Southeast A becomes Northwest, and Northeast C becomes Southwest. A new pair is found for the east side to create a technically valid quad.
{
uint8_t t;
abcd = 0;
t = kuf_quad_tile_get(a, KUF_SOUTHEAST);
abcd = kuf_quad_tile_set(abcd, KUF_NORTHWEST, t);
t = kuf_quad_tile_get(c, KUF_NORTHEAST);
abcd = kuf_quad_tile_set(abcd, KUF_SOUTHWEST, t);
t = kuf_gen_pair(rng);
abcd = kuf_quad_side_set(abcd, KUF_EAST, t);
if (!kuf_quad_check(abcd)) {
int i;
for (i = 0; i < 4; i++) {
abcd = kuf_quad_side_set(abcd, KUF_EAST, (t + i) % 4);
if (kuf_quad_check(abcd)) break;
}
}
}To complete BD: Northeast ABCD becomes Northwest, and Southeast ABCD becomes Southwest. A new pair is found for the east side to create a technically valid quad.
{
uint8_t t;
bd = 0;
t = kuf_quad_tile_get(abcd, KUF_NORTHEAST);
bd = kuf_quad_tile_set(bd, KUF_NORTHWEST, t);
t = kuf_quad_tile_get(abcd, KUF_SOUTHEAST);
bd = kuf_quad_tile_set(bd, KUF_SOUTHWEST, t);
t = kuf_gen_pair(rng);
bd = kuf_quad_side_set(bd, KUF_EAST, t);
if (!kuf_quad_check(bd)) {
int i;
for (i = 0; i < 4; i++) {
bd = kuf_quad_side_set(bd, KUF_EAST, (t + i) % 4);
if (kuf_quad_check(bd)) break;
}
}
}AB is first created from what is known already: the East of A becomes West. The Northeast of ABCD becomes Southeast.
AB is completed by finding the Northeast tile.
{
uint8_t t;
ab = 0;
t = kuf_quad_side_get(a, KUF_EAST);
ab = kuf_quad_side_set(ab, KUF_WEST, t);
t = kuf_quad_tile_get(abcd, KUF_NORTHEAST);
ab = kuf_quad_tile_set(ab, KUF_SOUTHEAST, t);
t = kuf_gen_tile(rng);
ab = kuf_quad_tile_set(ab, KUF_NORTHEAST, t);
if (!kuf_quad_check(ab)) {
ab = kuf_quad_tile_set(ab, KUF_NORTHEAST, t ? 0 : 1);
}
}The known parts of B: East of AB to West, Northeast of BD to Southeast.
B is completed by finding the northeast tile.
{
uint8_t t;
b = 0;
t = kuf_quad_side_get(ab, KUF_EAST);
b = kuf_quad_side_set(b, KUF_WEST, t);
t = kuf_quad_tile_get(bd, KUF_NORTHEAST);
b = kuf_quad_tile_set(b, KUF_SOUTHEAST, t);
t = kuf_gen_tile(rng);
b = kuf_quad_tile_set(b, KUF_NORTHEAST, t);
if (!kuf_quad_check(b)) {
b = kuf_quad_tile_set(b, KUF_NORTHEAST, t ? 0 : 1);
}
}The known parts of CD: South of ABCD becomes north, and Southeast of C becomes Southwest.
CD is completed by finding the southeast tile.
{
uint8_t t;
cd = 0;
t = kuf_quad_side_get(abcd, KUF_SOUTH);
cd = kuf_quad_side_set(cd, KUF_NORTH, t);
t = kuf_quad_tile_get(c, KUF_SOUTHEAST);
cd = kuf_quad_tile_set(cd, KUF_SOUTHWEST, t);
t = kuf_gen_tile(rng);
cd = kuf_quad_tile_set(cd, KUF_SOUTHEAST, t);
if (!kuf_quad_check(cd)) {
cd = kuf_quad_tile_set(cd, KUF_SOUTHEAST, t ? 0 : 1);
}
}The known parts of D: East of CD becomes West, and Southeast of BD becomes Northeast.
D is completed by finding the southeast tile.
{
uint8_t t;
d = 0;
t = kuf_quad_side_get(cd, KUF_EAST);
d = kuf_quad_side_set(d, KUF_WEST, t);
t = kuf_quad_tile_get(bd, KUF_SOUTHEAST);
d = kuf_quad_tile_set(d, KUF_NORTHEAST, t);
t = kuf_gen_tile(rng);
d = kuf_quad_tile_set(d, KUF_SOUTHEAST, t);
if (!kuf_quad_check(d)) {
d = kuf_quad_tile_set(d, KUF_SOUTHEAST, t ? 0 : 1);
}
}4.7.3.1.2. Southern Wall
A southern wall solver has knowns A and B, and creates a solution C and D.
void kuf_solve_wall_south(uint32_t *rng,
uint8_t a, uint8_t b,
uint8_t *pc, uint8_t *pd);The southern wall uses the same procedure as the eastern wall, just flipped on it's side. The quads are solved in the following order: ABCD, CD, AC, C, BD, D.
void kuf_solve_wall_south(uint32_t *rng,
uint8_t a, uint8_t b,
uint8_t *pc, uint8_t *pd)
{
uint8_t c, d;
uint8_t abcd;
uint8_t cd;
uint8_t ac;
uint8_t bd;
c = d = 0;
<<southwall_ABCD_S>>
<<southwall_CD_S>>
<<southwall_AC_SW>>
<<southwall_C_SW>>
<<southwall_BD_SE>>
<<southwall_D_SE>>
*pc = c;
*pd = d;
}Known parts of ABCD: Southeast of A becomes Northwest, and Southwest of B becomes Northeast.
The South side is generated to complete ABCD.
{
uint8_t t;
abcd = 0;
t = kuf_quad_tile_get(a, KUF_SOUTHEAST);
abcd = kuf_quad_tile_set(abcd, KUF_NORTHWEST, t);
t = kuf_quad_tile_get(b, KUF_SOUTHWEST);
abcd = kuf_quad_tile_set(abcd, KUF_NORTHEAST, t);
t = kuf_gen_pair(rng);
abcd = kuf_quad_side_set(abcd, KUF_SOUTH, t);
if (!kuf_quad_check(abcd)) {
int i;
for (i = 0; i < 4; i++) {
abcd = kuf_quad_side_set(abcd, KUF_SOUTH, (t + i) % 4);
if (kuf_quad_check(abcd)) break;
}
}
}Known parts of CD: Southwest of ABCD becomes Northwest, and Southeast of ABCD becomes Northeast.
The South side is generated to complete CD.
{
uint8_t t;
cd = 0;
t = kuf_quad_tile_get(abcd, KUF_SOUTHWEST);
cd = kuf_quad_tile_set(cd, KUF_NORTHWEST, t);
t = kuf_quad_tile_get(abcd, KUF_SOUTHEAST);
cd = kuf_quad_tile_set(cd, KUF_NORTHEAST, t);
t = kuf_gen_pair(rng);
cd = kuf_quad_side_set(cd, KUF_SOUTH, t);
if (!kuf_quad_check(cd)) {
int i;
for (i = 0; i < 4; i++) {
cd = kuf_quad_side_set(cd, KUF_SOUTH, (t + i) % 4);
if (kuf_quad_check(cd)) break;
}
}
}Known parts of AC: West of ABCD becomes East, and Southwest of A becomes Northwest.
The Southwest tile is generated to complete AC.
{
uint8_t t;
ac = 0;
t = kuf_quad_side_get(abcd, KUF_WEST);
ac = kuf_quad_side_set(ac, KUF_EAST, t);
t = kuf_quad_tile_get(a, KUF_SOUTHWEST);
ac = kuf_quad_tile_set(ac, KUF_NORTHWEST, t);
t = kuf_gen_tile(rng);
ac = kuf_quad_tile_set(ac, KUF_SOUTHWEST, t);
if (!kuf_quad_check(ac)) {
ac = kuf_quad_tile_set(ac, KUF_SOUTHWEST, t ? 0 : 1);
}
}Known parts of C: South of AC becomes North, and Southwest of CD becomes Southeast.
The Southwest tile is generated to complete C.
{
uint8_t t;
c = 0;
t = kuf_quad_side_get(ac, KUF_SOUTH);
c = kuf_quad_side_set(c, KUF_NORTH, t);
t = kuf_quad_tile_get(cd, KUF_SOUTHWEST);
c = kuf_quad_tile_set(c, KUF_SOUTHEAST, t);
t = kuf_gen_tile(rng);
c = kuf_quad_tile_set(c, KUF_SOUTHWEST, t);
if (!kuf_quad_check(c)) {
c = kuf_quad_tile_set(c, KUF_SOUTHWEST, t ? 0 : 1);
}
}Known parts of BD: East of ABCD becomes West, and Southeast of B becomes Northeast.
The Southeast tile is generated to complete BD.
{
uint8_t t;
bd = 0;
t = kuf_quad_side_get(abcd, KUF_EAST);
bd = kuf_quad_side_set(bd, KUF_WEST, t);
t = kuf_quad_tile_get(b, KUF_SOUTHEAST);
bd = kuf_quad_tile_set(bd, KUF_NORTHEAST, t);
t = kuf_gen_tile(rng);
bd = kuf_quad_tile_set(bd, KUF_SOUTHEAST, t);
if (!kuf_quad_check(bd)) {
bd = kuf_quad_tile_set(bd, KUF_SOUTHEAST, t ? 0 : 1);
}
}Known parts of D: South of BD becomes North, and Southeast of CD becomes Southwest.
The Southeast tile is generated to complete D.
{
uint8_t t;
d = 0;
t = kuf_quad_side_get(bd, KUF_SOUTH);
d = kuf_quad_side_set(d, KUF_NORTH, t);
t = kuf_quad_tile_get(cd, KUF_SOUTHEAST);
d = kuf_quad_tile_set(d, KUF_SOUTHWEST, t);
t = kuf_gen_tile(rng);
d = kuf_quad_tile_set(d, KUF_SOUTHEAST, t);
if (!kuf_quad_check(d)) {
d = kuf_quad_tile_set(d, KUF_SOUTHEAST, t ? 0 : 1);
}
}4.7.3.2. Quad Solver
Generating a quad in a square is known as a "quad solver". Only southeast and northeast quads need to be implemented. The quad solver works in the following way: given 3 known quads in the square, generate the remaining quad.
4.7.3.2.1. Northeast Quad (B)
uint8_t kuf_solve_quad_northeast(uint32_t *rng,
uint8_t a,
uint8_t c,
uint8_t d);uint8_t kuf_solve_quad_northeast(uint32_t *rng,
uint8_t a,
uint8_t c,
uint8_t d)
{
uint8_t b;
uint8_t abcd;
uint8_t bd;
uint8_t ab;
b = 0;
<<northeast_abcd>>
<<northeast_bd>>
<<northeast_ab>>
<<northeast_b>>
return b;
}Northeast quad is known as quad B.
It gets solved in the following way:
The known parts of ABCD are created with: Southeast of A to Northwest, Northeast of C to Southwest, and Northwest of D to Southeast.
Complete ABCD by finding the northeast tile.
{
uint8_t t;
abcd = 0;
t = kuf_quad_tile_get(a, KUF_SOUTHEAST);
abcd = kuf_quad_tile_set(abcd, KUF_NORTHWEST, t);
t = kuf_quad_tile_get(c, KUF_NORTHEAST);
abcd = kuf_quad_tile_set(abcd, KUF_SOUTHWEST, t);
t = kuf_quad_tile_get(d, KUF_NORTHWEST);
abcd = kuf_quad_tile_set(abcd, KUF_SOUTHEAST, t);
t = kuf_gen_tile(rng);
abcd = kuf_quad_tile_set(abcd, KUF_NORTHEAST, t);
if (!kuf_quad_check(abcd)) {
abcd = kuf_quad_tile_set(abcd, KUF_NORTHEAST, t ? 0 : 1);
}
}Known BD is comprised of the East of ABCD to West, and the Northeast of D to Southeast.
Complete BD by finding the northeast tile.
{
uint8_t t;
bd = 0;
t = kuf_quad_side_get(abcd, KUF_EAST);
bd = kuf_quad_side_set(bd, KUF_WEST, t);
t = kuf_quad_tile_get(d, KUF_NORTHEAST);
bd = kuf_quad_tile_set(bd, KUF_SOUTHEAST, t);
t = kuf_gen_tile(rng);
bd = kuf_quad_tile_set(bd, KUF_NORTHEAST, t);
if (!kuf_quad_check(bd)) {
bd = kuf_quad_tile_set(bd, KUF_NORTHEAST, t ? 0 : 1);
}
}Known AB is comprised of the North of ABCD to South, and the Northeast of A to Northwest.
Complete AB by finding the northeast tile.
{
uint8_t t;
ab = 0;
t = kuf_quad_side_get(abcd, KUF_NORTH);
ab = kuf_quad_side_set(ab, KUF_SOUTH, t);
t = kuf_quad_tile_get(a, KUF_NORTHEAST);
ab = kuf_quad_tile_set(ab, KUF_NORTHWEST, t);
t = kuf_gen_tile(rng);
ab = kuf_quad_tile_set(ab, KUF_NORTHEAST, t);
if (!kuf_quad_check(ab)) {
ab = kuf_quad_tile_set(ab, KUF_NORTHEAST, t ? 0 : 1);
}
}Known B is comprised of the north of BD to South, and the Northeast of AB to Northwest.
Complete B by finding the northeast tile.
{
uint8_t t;
b = 0;
t = kuf_quad_side_get(bd, KUF_NORTH);
b = kuf_quad_side_set(b, KUF_SOUTH, t);
t = kuf_quad_tile_get(ab, KUF_NORTHEAST);
b = kuf_quad_tile_set(b, KUF_NORTHWEST, t);
t = kuf_gen_tile(rng);
b = kuf_quad_tile_set(b, KUF_NORTHEAST, t);
if (!kuf_quad_check(b)) {
b = kuf_quad_tile_set(b, KUF_NORTHEAST, t ? 0 : 1);
}
}4.7.3.2.2. Southeast Quad (D)
uint8_t kuf_solve_quad_southeast(uint32_t *rng,
uint8_t a,
uint8_t b,
uint8_t c);uint8_t kuf_solve_quad_southeast(uint32_t *rng,
uint8_t a,
uint8_t b,
uint8_t c)
{
uint8_t d;
uint8_t abcd;
uint8_t bd;
uint8_t cd;
d = 0;
<<southeast_abcd>>
<<southeast_bd>>
<<southeast_cd>>
<<southeast_d>>
return d;
}Southeast quad is known as D. Like Northeast (B), only finding the southeast tiles.
ABCD is comprised of the southeast of A to northwest, southwest of B to northeast, northeast of C to southwest.
Complete ABCD by finding the southeast tile.
{
uint8_t t;
abcd = 0;
t = kuf_quad_tile_get(a, KUF_SOUTHEAST);
abcd = kuf_quad_tile_set(abcd, KUF_NORTHWEST, t);
t = kuf_quad_tile_get(b, KUF_SOUTHWEST);
abcd = kuf_quad_tile_set(abcd, KUF_NORTHEAST, t);
t = kuf_quad_tile_get(c, KUF_NORTHEAST);
abcd = kuf_quad_tile_set(abcd, KUF_SOUTHWEST, t);
t = kuf_gen_tile(rng);
abcd = kuf_quad_tile_set(abcd, KUF_SOUTHEAST, t);
if (!kuf_quad_check(abcd)) {
abcd = kuf_quad_tile_set(abcd, KUF_SOUTHEAST, t ? 0 : 1);
}
}BD is comprised of the east of ABCD to west, and the southeast of B to northeast.
Complete BD by finding the southeast tile.
{
uint8_t t;
bd = 0;
t = kuf_quad_side_get(abcd, KUF_EAST);
bd = kuf_quad_side_set(bd, KUF_WEST, t);
t = kuf_quad_tile_get(b, KUF_SOUTHEAST);
bd = kuf_quad_tile_set(bd, KUF_NORTHEAST, t);
t = kuf_gen_tile(rng);
bd = kuf_quad_tile_set(bd, KUF_SOUTHEAST, t);
if (!kuf_quad_check(bd)) {
bd = kuf_quad_tile_set(bd, KUF_SOUTHEAST, t ? 0 : 1);
}
}CD is comprised of the south of ABCD to north, and the southeast of C to southwest.
Complete CD by finding the southeast tile.
{
uint8_t t;
cd = 0;
t = kuf_quad_side_get(abcd, KUF_SOUTH);
cd = kuf_quad_side_set(cd, KUF_NORTH, t);
t = kuf_quad_tile_get(c, KUF_SOUTHEAST);
cd = kuf_quad_tile_set(cd, KUF_SOUTHWEST, t);
t = kuf_gen_tile(rng);
cd = kuf_quad_tile_set(cd, KUF_SOUTHEAST, t);
if (!kuf_quad_check(cd)) {
cd = kuf_quad_tile_set(cd, KUF_SOUTHEAST, t ? 0 : 1);
}
}D is comprised of the south of BD to north, and the southeast of CD to southwest.
Complete D by finding the southeast tile.
{
uint8_t t;
d = 0;
t = kuf_quad_side_get(bd, KUF_SOUTH);
d = kuf_quad_side_set(d, KUF_NORTH, t);
t = kuf_quad_tile_get(cd, KUF_SOUTHEAST);
d = kuf_quad_tile_set(d, KUF_SOUTHWEST, t);
t = kuf_gen_tile(rng);
d = kuf_quad_tile_set(d, KUF_SOUTHEAST, t);
if (!kuf_quad_check(d)) {
d = kuf_quad_tile_set(d, KUF_SOUTHEAST, t ? 0 : 1);
}
}4.7.4. The Algorithm
To begin, generate square W. This can be generated entirely
with kuf_gen_square.
w = kuf_gen_square(rng);Generate WY. Northern wall of WY (a,b) is the southern wall of W (c,d). This is fed into the southern wall solver to complete WY.
{
uint8_t a, b, c, d;
a = kuf_square_quad_get(w, KUF_QUAD_C);
b = kuf_square_quad_get(w, KUF_QUAD_D);
c = d = 0;
kuf_solve_wall_south(rng, a, b, &c, &d);
wy = kuf_glue_square(a, b, c, d);
}Generate Y. The Southern wall of WY is fed into the southern wall solver to complete Y.
{
uint8_t a, b, c, d;
a = kuf_square_quad_get(wy, KUF_QUAD_C);
b = kuf_square_quad_get(wy, KUF_QUAD_D);
c = d = 0;
kuf_solve_wall_south(rng, a, b, &c, &d);
y = kuf_glue_square(a, b, c, d);
}Generate WXYZ. The southeast of W (d) becomes the northwest (a). The northeast of Y (b) becomes the southwest (c). Together they form the Western wall of WXYZ. This is fed into the eastern wall solver to complete WXYZ.
{
uint8_t a, b, c, d;
a = kuf_square_quad_get(w, KUF_QUAD_D);
c = kuf_square_quad_get(y, KUF_QUAD_B);
b = d = 0;
kuf_solve_wall_east(rng, a, c, &b, &d);
wxyz = kuf_glue_square(a, b, c, d);
}Generate XZ. The northeast of WXYZ (b) becomes northwest (a). The southeast (d) of WXYZ becomes southwest (c). This is fed into the east wall solver to complete XZ.
{
uint8_t a, b, c, d;
a = kuf_square_quad_get(wxyz, KUF_QUAD_B);
c = kuf_square_quad_get(wxyz, KUF_QUAD_D);
b = d = 0;
kuf_solve_wall_east(rng, a, c, &b, &d);
xz = kuf_glue_square(a, b, c, d);
}Generate WX. The East of W (b,d) becomes the West (a, c). The Northeast of WXYZ (b) becomes Southeast (d).
WX is completed using the northeast quad solver.
{
uint8_t a, b, c, d;
a = kuf_square_quad_get(w, KUF_QUAD_B);
c = kuf_square_quad_get(w, KUF_QUAD_D);
d = kuf_square_quad_get(wxyz, KUF_QUAD_B);
b = kuf_solve_quad_northeast(rng, a, c, d);
wx = kuf_glue_square(a, b, c, d);
}Generate X. The East of WX (b, d) becomes the West (a, c). The Northeast of XZ (b) becomes Southeast (d).
X is completed using the northeast quad solver.
{
uint8_t a, b, c, d;
a = kuf_square_quad_get(wx, KUF_QUAD_B);
c = kuf_square_quad_get(wx, KUF_QUAD_D);
d = kuf_square_quad_get(xz, KUF_QUAD_B);
b = kuf_solve_quad_northeast(rng, a, c, d);
x = kuf_glue_square(a, b, c, d);
}Generate YZ. The East of Y (B, D) becomes West (A, C), and the Southwest of XZ (C) becomes Northeast (B).
The southeast quad of YZ is solved to complete YZ.
{
uint8_t a, b, c, d;
a = kuf_square_quad_get(y, KUF_QUAD_B);
c = kuf_square_quad_get(y, KUF_QUAD_D);
b = kuf_square_quad_get(xz, KUF_QUAD_C);
d = kuf_solve_quad_southeast(rng, a, b, c);
yz = kuf_glue_square(a, b, c, d);
}Generate Z. The East of YZ (B, D) becomes West (A, C), and the Southeast of XZ (D) becomes Northeast (B).
Z is completed using the southeast quad solver.
{
uint8_t a, b, c, d;
a = kuf_square_quad_get(yz, KUF_QUAD_B);
c = kuf_square_quad_get(yz, KUF_QUAD_D);
b = kuf_square_quad_get(xz, KUF_QUAD_D);
d = kuf_solve_quad_southeast(rng, a, b, c);
z = kuf_glue_square(a, b, c, d);
}prev | home | next