packages/grid-iterators/src/diamond-square.ts
import type { FnU2 } from "@thi.ng/api";
import { defBitField } from "@thi.ng/bitfield/bitfield";
/**
* Yields iterator of 2D grid coordinates based on the recursive Diamond Square
* algorithm. The given `exp` is a power of 2 exponent and the resulting
* coordinates (in both directions) will be in the closed [0..2^exp] interval
* (i.e. each axis is always a power-of-2 plus 1).
*
* @remarks
* Reference: https://en.wikipedia.org/wiki/Diamond-square_algorithm
*
* @example
* ```ts tangle:../export/diamond-square.ts
* import { diamondSquare } from "@thi.ng/grid-iterators";
*
* // generate coords for a 17x17 grid
* console.log(
* [...diamondSquare(4)]
* );
* // [
* // [0, 0], [16, 0], [16, 16], [0, 16], [8, 0], [8, 16],
* // [16, 8], [0, 8], [8, 8], [4, 0], [12, 0], [12, 16],
* // [4, 16], [8, 4], [8, 12], [4, 8], [12, 8], [0, 4],
* // ...
* // ]
* ```
*
* @param exp
*/
export function* diamondSquare(exp: number) {
const size = 1 << exp;
const size1 = size + 1;
const s2 = size >> 1;
let res = size;
const idx = defBitField(size1 * size1);
const acc: number[][] = [];
const $: FnU2<number, void> = (x, y) => {
!idx.setAt(x + y * size1) && acc.push([x, y]);
};
$(0, 0);
$(res, 0);
$(res, res);
$(0, res);
yield* acc;
while (res > 1) {
const r2 = res >> 1;
for (let y = 0; y <= s2; y += res) {
const y1 = y + r2;
const y2 = y + res;
for (let x = r2; x <= s2; x += res) {
acc.length = 0;
const x1 = x - r2;
const x2 = x + r2;
$(x, y);
$(size - x, y);
$(size - x, size - y);
$(x, size - y);
$(x2, y1);
$(size - x2, y1);
$(size - x2, size - y1);
$(x2, size - y1);
$(x, y2);
$(size - x, y2);
$(size - x, size - y2);
$(x, size - y2);
$(x1, y1);
$(size - x1, y1);
$(size - x1, size - y1);
$(x1, size - y1);
$(x, y1);
$(size - x, y1);
$(size - x, size - y1);
$(x, size - y1);
yield* acc;
}
}
res = r2;
}
}