Build a One‑Stroke Puzzle Game with Auto‑Graph Recognition

Background

The one‑stroke puzzle originates from Euler’s Seven Bridges of Königsberg problem. In graph‑theoretic terms, a connected graph has an Eulerian trail that traverses every edge exactly once without repetition.

Game implementation

Base map rendering

Levels are defined through a configuration interface. Two representation options exist:

Point notation – stores an ordered list of vertex coordinates.

Line notation – stores unordered line segments as pairs of endpoints.

Example configuration for a five‑point star using point notation:

levels: [
  {
    name: "Five‑Star",
    coords: [
      {x: Ax, y: Ay},
      {x: Bx, y: By},
      {x: Cx, y: Cy},
      {x: Dx, y: Dy},
      {x: Ex, y: Ey},
      {x: Ax, y: Ay}
    ]
  }
]

Using line notation the same level looks like:

levels: [
  {
    name: "Five‑Star",
    lines: [
      {x1: Ax, y1: Ay, x2: Bx, y2: By},
      {x1: Bx, y1: By, x2: Cx, y2: Cy},
      {x1: Cx, y1: Cy, x2: Dx, y2: Dy},
      {x1: Dx, y1: Dy, x2: Ex, y2: Ey},
      {x1: Ex, y1: Ey, x2: Ax, y2: Ay}
    ]
  }
]

Line notation is preferred because it does not require storing a solved path.

Interactive drawing

The user draws a path by touching vertices. Two problems must be solved:

Detect whether a touch is on a vertex.

Determine whether the touched vertex can be connected to the currently selected vertex.

Collecting vertex coordinates from the line data:

let coords = [];
lines.forEach(({x1, y1, x2, y2}) => {
  if (!isExist(x1, y1)) coords.push([x1, y1]);
  if (!isExist(x2, y2)) coords.push([x2, y2]);
});

Touch‑move listener (simplified):

easel.addEventListener("touchmove", e => {
  let x0 = e.targetTouches[0].pageX,
      y0 = e.targetTouches[0].pageY;
  let r = radius * 2; // enlarged detection radius
  for (let [x, y] of coords) {
    if (Math.sqrt(Math.pow(x - x0, 2) + Math.pow(y - y0, 2)) <= r) {
      if (canConnect(x, y)) {
        // draw line logic here
      }
      break;
    }
  }
});

Each vertex stores a list of valid connection points derived from the level’s line data. Only vertices that are not already linked ("unconnected valid points") are considered for new connections.

Automatic image recognition

An auto‑recognition plugin scans a bitmap of the puzzle, extracts dominant colors, and identifies vertices and edges.

Color table extraction

let imageData = ctx.getImageData();
let data = imageData.data;
let clrs = new Map();
for (let i = 0, len = data.length; i < len; i += 4) {
  let [r, g, b, a] = [data[i], data[i+1], data[i+2], data[i+3]];
  let key = `rgba(${r},${g},${b},${a})`;
  let value = clrs.get(key) || {r,g,b,a,count:0};
  clrs.has(key) ? ++value.count : clrs.set(key, value);
}

The three most frequent colors correspond to background, edges, and vertices. By ignoring the background and selecting the second‑most and third‑most frequent colors, the algorithm determines edge and vertex colors.

Vertex detection

The algorithm scans pixels, records vertex‑color pixels, clears them, and continues. Small spurious vertices caused by compression are merged:

for (let i = 0, len = vertexes.length; i < len - 1; ++i) {
  let vertexA = vertexes[i];
  if (vertexA === undefined) continue;
  for (let j = 0; j < len; ++j) {
    let vertexB = vertexes[j];
    if (vertexB === undefined) continue;
    if (isCross(vertexA, vertexB)) {
      vertexA = merge(vertexA, vertexB);
      delete vertexB;
    }
  }
}

This merging yields accurate vertex detection even on lossy images.

Edge detection

For each pair of vertices, the algorithm samples N points along the line (where N = distance / (2 * R), R being the vertex radius). If all sampled pixels match the edge color, the segment is accepted:

for (let i = 0, len = vertexes.length; i < len - 1; ++i) {
  let {x: x1, y: y1} = vertexes[i];
  for (let j = i + 1; j < len; ++j) {
    let {x: x2, y: y2} = vertexes[j];
    let S = Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
    let N = S / (2 * R);
    let stepX = (x2 - x1) / N, stepY = (y2 - y1) / N;
    while (--N) {
      if (!isBelongLine(x1 + N * stepX, y1 + N * stepY)) break;
    }
    if (N === 0) lines.push({x1, y1, x2, y2});
  }
}

This approach avoids false positives when three vertices are collinear but only two are actually connected.

Performance optimisation

Scanning a full‑size image (e.g., 750 × 1334) processes roughly 4 million values. Down‑scaling the canvas reduces the pixel array size by the square of the scaling factor:

let resolution = 4;
let [width, height] = [img.width / resolution >> 0, img.height / resolution >> 0];
ctx.drawImage(img, 0, 0, width, height);
let imageData = ctx.getImageData();
let data = imageData.data;

Scaling by 4 reduces the array size 16‑fold, providing a substantial speed boost.

Usage recommendations

The auto‑recognition tool works well for the author’s own images but may struggle with arbitrary user‑uploaded graphics. It is advisable to expose it as a separate utility that generates level JSON files.

Demo page: https://leeenx.github.io/OneStroke/src/onestroke.html

Auto‑recognition tool: https://leeenx.github.io/OneStroke/src/plugin.html

Repository: https://github.com/leeenx/OneStroke

Game core source: https://github.com/leeenx/OneStroke/blob/master/src/script/onestroke.es6

Plugin source: https://github.com/leeenx/OneStroke/blob/master/src/script/oneStrokePlugin.es6