Implement glyph detection on the server side

This seems to work, but it's only been verified via debugging prints,
(that is, the server isn't yet _doing_ anything with the glyph
detection that a client can actually see).

diff --git a/scribe.js b/scribe.js
index f008bd2d8e05dd454c2e213d730b2f379397684f..7d508c1ca123f7a33944b37cf748430efc32123a 100644 (file)
--- a/scribe.js
+++ b/scribe.js
@@ -12,6 +12,186 @@ class Scribe extends Game {
     };
   }
 
+  find_connected_recursive(recursion_state, position) {
+
+    if (position < 0 || position >= 9)
+      return;
+
+    if (recursion_state.visited[position])
+      return;
+
+    recursion_state.visited[position] = true;
+
+    if (recursion_state.mini_grid[position] !== recursion_state.target)
+      return;
+
+    recursion_state.connected[position] = true;
+
+    /* Left */
+    if (position % 3 !== 0)
+      this.find_connected_recursive(recursion_state, position - 1);
+    /* Right */
+    if (position % 3 !== 2)
+      this.find_connected_recursive(recursion_state, position + 1);
+    /* Up */
+    this.find_connected_recursive(recursion_state, position - 3);
+    /* Down */
+    this.find_connected_recursive(recursion_state, position + 3);
+  }
+
+  /* Find all cells within a mini-grid that are 4-way connected to the
+   * given cell. */
+  find_connected(mini_grid, position) {
+    const connected = Array(9).fill(false);
+
+    /* If the given cell is empty then there is nothing connected. */
+    if (mini_grid[position] === null)
+      return connected;
+
+    const cell = mini_grid[position];
+
+    let recursion_state = {
+      mini_grid: mini_grid,
+      connected: connected,
+      visited: Array(9).fill(false),
+      target: cell,
+    };
+    this.find_connected_recursive(recursion_state, position);
+
+    return connected;
+  }
+
+  /* Detect whether the given cell belongs to a glyph. */
+  detect_glyph(mini_grid_index, position) {
+    const mini_grid = this.state.squares[mini_grid_index];
+    const connected = this.find_connected(mini_grid, position);
+
+    /* Now that we have a set of connected cells, let's collect some
+     * stats on them, (width, height, number of cells, configuration
+     * of corner cells, etc.).
+     */
+    let min_row = 2;
+    let min_col = 2;
+    let max_row = 0;
+    let max_col = 0;
+    let count = 0;
+
+    for (let i = 0; i < 9; i++) {
+      const row = Math.floor(i/3);
+      const col = i % 3;
+
+      if (! connected[i])
+        continue;
+
+      count++;
+
+      min_row = Math.min(row, min_row);
+      min_col = Math.min(col, min_col);
+      max_row = Math.max(row, max_row);
+      max_col = Math.max(col, max_col);
+    }
+
+    const width = max_col - min_col + 1;
+    const height = max_row - min_row + 1;
+
+    /* Corners, (top-left, top-right, bottom-left, and bottom-right) */
+    const tl = connected[3 * min_row + min_col];
+    const tr = connected[3 * min_row + max_col];
+    const bl = connected[3 * max_row + min_col];
+    const br = connected[3 * max_row + max_col];
+
+    const count_true = (acc, val) => acc + (val ? 1 : 0);
+    const corners_count = [tl, tr, bl, br].reduce(count_true, 0);
+    const top_corners_count = [tl, tr].reduce(count_true, 0);
+    const bottom_corners_count = [bl, br].reduce(count_true, 0);
+    const left_corners_count = [tl, bl].reduce(count_true, 0);
+    const right_corners_count = [tr, br].reduce(count_true, 0);
+
+    let two_corners_in_a_line = false;
+    if (top_corners_count    === 2 ||
+        bottom_corners_count === 2 ||
+        left_corners_count   === 2 ||
+        right_corners_count  === 2)
+    {
+      two_corners_in_a_line = true;
+    }
+
+    let zero_corners_in_a_line = false;
+    if (top_corners_count    === 0 ||
+        bottom_corners_count === 0 ||
+        left_corners_count   === 0 ||
+        right_corners_count  === 0)
+    {
+      zero_corners_in_a_line = true;
+    }
+
+    /* Now we have the information we need to determine glyphs. */
+    let is_glyph = undefined;
+    switch (count) {
+    case 1:
+      /* Single */
+      is_glyph = true;
+      break;
+    case 2:
+      /* Double */
+      is_glyph = true;
+      break;
+    case 3:
+      /* Line */
+      is_glyph = (width === 3 || height === 3);
+      break;
+    case 4:
+      /* Pipe, Squat-T, and 4-block, but not Tetris S */
+      is_glyph = two_corners_in_a_line;
+      break;
+    case 5:
+      if (width !== 3 || height !== 3 || ! connected[4])
+      {
+        /* Pentomino P and U are not glyphs (not 3x3) */
+        /* Pentomino V is not a glyph (center not connected) */
+        is_glyph = false;
+      }
+      else if (corners_count === 0 || two_corners_in_a_line)
+      {
+        /* Pentomino X is glyph Cross (no corners) */
+        /* Pentomino T is glyph T (has a row or column with 2 corners) */
+        is_glyph = true;
+      } else {
+        /* The corner counting above excludes pentomino F, W, and Z
+         * which are not glyphs. */
+        is_glyph = false;
+      }
+      break;
+    case 6:
+      /* 6-Block has widht or height of 2. */
+      /* Bomber, Chair, and J have 3 corners occupied. */
+      if (width === 2 || height === 2 || corners_count === 3)
+        is_glyph = true;
+      else
+        is_glyph = false;
+      break;
+    case 7:
+      /* Earring and U have no center square occupied */
+      /* H has 4 corners occupied */
+      /* House has a row or column with 0 corners occupied */
+      if ((! connected[4]) || corners_count === 4 || zero_corners_in_a_line)
+        is_glyph = true;
+      else
+        is_glyph = false;
+      break;
+    case 8:
+      /* Ottoman or O */
+      if (corners_count === 4)
+        is_glyph = true;
+      else
+        is_glyph = false;
+      break;
+    case 9:
+      is_glyph = true;
+      break;
+    }
+  }
+
   /* Returns true if move was legal and added, false otherwise. */
   add_move(player, move) {
 
@@ -58,6 +238,8 @@ class Scribe extends Game {
     state.squares[i][j] = state.team_to_play;
     state.moves.push(move);
 
+    this.detect_glyph(i, j);
+
     if (state.team_to_play.id === 0)
       state.team_to_play = this.teams[1];
     else