From 82b93d9e3014d98933c3fa1b0d4bec9cf884ebe4 Mon Sep 17 00:00:00 2001 From: Carl Worth Date: Tue, 7 Jul 2020 05:36:12 -0700 Subject: [PATCH] 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). --- scribe.js | 182 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 182 insertions(+) diff --git a/scribe.js b/scribe.js index f008bd2..7d508c1 100644 --- 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 -- 2.43.0