const cellsize = 24;

let half_cellsize;

const num_rows = 40;

const num_cols = 60;

let UI_SIZE = 4;

​

// const algorithm = "Random"; // random, CA, bsp, noise, ...

// const RAND_FILL_CHANCE = 0.8;

​

// const algorithm = "Open";

const algorithm = "CA";

const RAND_FILL_CHANCE = 0.58;

const CA_ITERATIONS = 5000;

const CA_NEIGHBORS = 4;

​

let fill_perc = -1.0;

let open_cells;

let checked_cells;

​

let start_cell;

let done = false;

​

let dirs = [

  [-1, -1],

  [0, -1],

  [1, -1],

  [-1, 0],

  [1, 0],

  [-1, 1],

  [0, 1],

  [1, 1],

];

​

// try checking flood fill

function setup() {

  createCanvas(cellsize * num_cols, cellsize * num_rows + UI_SIZE * cellsize);

​

  half_cellsize = cellsize / 2;

​

  textSize(cellsize);

  textFont("Courier");

  textAlign(LEFT, CENTER);

​

  noStroke();

​

  grid = initializeGrid(grid);

​

  open_cells = [];

  if (algorithm == "Open") ret = setupOpen(grid);

  else if (algorithm == "Random") ret = setupRandom(grid);

  else if (algorithm == "CA") ret = setupCA(grid);

​

  grid = ret[0];

  open_cells = ret[1];

​

  start_cell = random(open_cells);

  grid[start_cell.r][start_cell.c].visited = true;

  queue.push(start_cell);

​

  checked_cells = [];

​

  console.log(grid);

}

​

function draw() {

  background(220);

​

  if (!done) floodFill();

​

  drawGrid();

  drawUI();

}

​

function drawUI() {

  let active = "running";

  if (done) active = "finished";

​

  textAlign(LEFT);

​

  fill(20);

  // noStroke();

  let y = height - UI_SIZE * cellsize;

  rect(0, y, width, UI_SIZE * cellsize);

​

  y += cellsize;

​

  fill(220);

  text(`Algorithm: ${algorithm} // Status: ${active}`, 10, y);

​

  y += cellsize;

​

  text(

    `Fill percent: ${fill_perc.toFixed(2)}% // Row: ${start_cell.r} // Col: ${

      start_cell.c

    } // Q length: ${queue.length}`,

    10,

    y

  );

​

  y += cellsize;

  text("Generation x, Individual y", 10, y);

}

​

function drawGrid() {

  textAlign(CENTER);

​

  for (let r = 0; r < num_rows; r++) {

    for (let c = 0; c < num_cols; c++) {

      if (grid[r][c].visited) {

        fill(color(255, 0, 255, 180));

        rect(c * cellsize, r * cellsize, cellsize, cellsize);

        noFill();

      }

​

      fill(20);

      text(

        grid[r][c].cell,

        c * cellsize + half_cellsize,

        r * cellsize + half_cellsize

      );

    }

  }

}

​

function initializeGrid(g, empty = false) {

  g = [];

  for (let r = 0; r < num_rows; r++) {

    g[r] = [];

    for (let c = 0; c < num_cols; c++) {

      g[r][c] = {};

​

      if (r == 0 || c == 0 || r == num_rows - 1 || c == num_cols - 1)

        g[r][c].cell = "#";

      else {

        if (!empty) g[r][c].cell = "#";

        else g[r][c].cell = " ";

      }

      g[r][c].visited = false;

    }

  }

  return g;

}

​

function setupOpen(g) {

  let oc = [];

​

  for (let r = 0; r < num_rows; r++) {

    for (let c = 0; c < num_cols; c++) {

      if (r == 0 || r == num_rows - 1 || c == 0 || c == num_cols - 1)

        g[r][c].cell = "#";

      else {

        g[r][c].cell = " ";

        oc.push({ r: r, c: c });

      }

    }

  }

  return [g, oc];

}

​

function setupRandom(g) {

  let oc = [];

​

  for (let r = 0; r < num_rows; r++) {

    for (let c = 0; c < num_cols; c++) {

      if (r == 0 || r == num_rows - 1 || c == 0 || c == num_cols - 1)

        g[r][c].cell = "#";

      else {

        if (random() > RAND_FILL_CHANCE) g[r][c].cell = "#";

        else {

          g[r][c].cell = " ";

          oc.push({ r: r, c: c });

        }

      }

    }

  }

  return [g, oc];

}

​

// https://abitawake.com/news/articles/procedural-generation-with-godot-creating-caves-with-cellular-automata

function setupCA(g) {

  let oc = [];

  let ret = setupRandom(g);

  g = ret[0];

  // dig caves

  for (let _ = 0; _ < CA_ITERATIONS; _++) {

    g = runCA(g);

  }

  // get caves

  // connect caves

  for (let r = 0; r < num_rows; r++) {

    for (let c = 0; c < num_cols; c++) {

      if (g[r][c].cell == " ") oc.push({ r: r, c: c });

    }

  }

  return [g, oc];

}

​

function runCA(g) {

  let _r = int(random(1, num_rows-1));

  let _c = int(random(1, num_cols-1));

  let wall_cnt = 0;

  for (let d of dirs) {

    let nr = _r + d[1];

    let nc = _c + d[0];

    if (nr >= 0 && nr <= num_rows-1 && nc >= 0 && nc <= num_cols-1) {

      if (g[nr][nc].cell == "#") wall_cnt++;

    }

  }

  if (wall_cnt > CA_NEIGHBORS) g[_r][_c].cell = "#";

  else if (wall_cnt < CA_NEIGHBORS) g[_r][_c].cell = " ";

  return g;

}

​

// https://www.roguebasin.com/index.php/Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels

// function setupCA(g) {

//   let oc = [];

​

//   // initial setup with random

//   let ret = setupRandom(g);

//   let ng = ret[0];

//   for (let _ = 0; _ < CA_GENERATIONS; _++) {

//     ng = runCA(ng);

//   }

​

//   for (let r = 0; r < num_rows; r++) {

//     for (let c = 0; c < num_cols; c++) {

//       if (ng[r][c].cell == " ") oc.push({r:r, c:c});

//     }

//   }

​

//   return [ng, oc];

// }

​

// function runCA(g) {

//   let new_g;

//   new_g = initializeGrid(new_g, true);

​

//   //The basic idea is to fill the first map randomly, then repeatedly create new maps using the 4-5 rule: a tile becomes a wall if it was a wall and 4 or more of its eight neighbors were walls, or if it was not a wall and 5 or more neighbors were

//   for (let r = 0; r < num_rows; r++) {

//     for (let c = 0; c < num_cols; c++) {

//       let num_walls = 0;

//       for (let d of dirs) {

//         let nc = c + d[0];

//         let nr = r + d[1];

​

//         if (nc >= 0 && nc <= num_cols-1 && nr >= 0 && nr <= num_rows-1) {

//           if (g[nr][nc].cell == "#") num_walls++;

//         }

//       }

​

//       // if wall and 4+

//       if (g[r][c].cell == "#" && num_walls < 4) new_g[r][c].cell = "#";

//       // if not wall and 5+

//       if (g[r][c].cell == " " && num_walls < 5) new_g[r][c].cell = "#";

​

//       if (g[r][c].cell == "#" && num_walls == 0) new_g[r][c].cell = " ";

//       if (num_walls >= 5) new_g[r][c].cell = " ";

//     }

//   }

​

//   return new_g;

// }

​

function checkValidity(cell) {

  if (

    cell.r < 0 ||

    cell.r > num_rows - 1 ||

    cell.c < 0 ||

    cell.c > num_cols - 1

  )

    return false;

  else {

    if (grid[cell.r][cell.c].cell == "#" || grid[cell.r][cell.c].visited)

      return false;

  }

  return true;

}

​

let queue = [];

// https://stackoverflow.com/questions/21865922/non-recursive-implementation-of-flood-fill-algorithm

// https://www.freecodecamp.org/news/flood-fill-algorithm-explained-with-examples/

function floodFill() {

  if (queue.length > 0) {

    let cell = queue.pop();

    grid[cell.r][cell.c].visited = true;

​

    checked_cells.push(cell);

    fill_perc = (checked_cells.length / open_cells.length) * 100;

​

    // console.log(cell, grid[cell.r][cell.c])

​

    for (let dir of dirs) {

      let next_dir = { r: cell.r + dir[1], c: cell.c + dir[0] };

​

      // console.log(queue.indexOf(next_dir))

​

      if (

        next_dir.c > 0 &&

        next_dir.c < num_cols - 1 &&

        next_dir.r > 0 &&

        next_dir.r < num_rows - 1

      ) {

        if (

          !grid[next_dir.r][next_dir.c].visited &&

          grid[next_dir.r][next_dir.c].cell != "#"

        ) {

          let valid = true;

          for (let q of queue) {

            if (q.r == next_dir.r && q.c == next_dir.c) {

              valid = false;

              break;

            }

          }

          if (valid) queue.push(next_dir);

        }

      }

      // if (checkValidity(next_dir) && queue.indexOf(next_dir) < 0)

      //   queue.push(next_dir);

    }

  } else {

    done = true;

  }

}

​

function keyPressed() {

  if (key == "p") console.log(grid);

}

​