pathways: 2D placement search - never overlap, fill nearby voids (edge-aligned candidates, packing cost)

2 files changed, 48 insertions, 49 deletions

diff --git a/public/app.js b/public/app.js
index 181c583..4325292 100644
--- a/public/app.js
+++ b/public/app.js
@@ -74,69 +74,67 @@ function baseRect(w, h, from, dir) {
   return { x: from.x - w - GAP, y: from.y + (from.h - h) / 2, w, h }
 }
 
-function slackScore(rect, slide) {
-  let lo = -Infinity
-  let hi = Infinity
+function sideGap(rect, dx, dy) {
+  let g = Infinity
   for (const t of tiles.values()) {
     const r = t.rect
-    if (slide === "x") {
-      if (r.y + r.h <= rect.y - GAP || rect.y + rect.h <= r.y - GAP) continue
-      if (r.x + r.w <= rect.x) lo = Math.max(lo, r.x + r.w)
-      else if (r.x >= rect.x + rect.w) hi = Math.min(hi, r.x)
+    if (dx !== 0) {
+      if (r.y + r.h <= rect.y || r.y >= rect.y + rect.h) continue
+      const gap = dx < 0 ? rect.x - (r.x + r.w) : r.x - (rect.x + rect.w)
+      if (gap >= 0 && gap < g) g = gap
     } else {
-      if (r.x + r.w <= rect.x - GAP || rect.x + rect.w <= r.x - GAP) continue
-      if (r.y + r.h <= rect.y) lo = Math.max(lo, r.y + r.h)
-      else if (r.y >= rect.y + rect.h) hi = Math.min(hi, r.y)
+      if (r.x + r.w <= rect.x || r.x >= rect.x + rect.w) continue
+      const gap = dy < 0 ? rect.y - (r.y + r.h) : r.y - (rect.y + rect.h)
+      if (gap >= 0 && gap < g) g = gap
     }
   }
-  const start = slide === "x" ? rect.x : rect.y
-  const end = slide === "x" ? rect.x + rect.w : rect.y + rect.h
-  const gLo = lo === -Infinity ? 0 : start - lo
-  const gHi = hi === Infinity ? 0 : hi - end
-  return Math.max(0, gLo) + Math.max(0, gHi)
+  return g
+}
+
+function packGap(rect, w, h) {
+  const cap = Math.max(w, h) * 2
+  const g = [
+    sideGap(rect, 0, -1),
+    sideGap(rect, 0, 1),
+    sideGap(rect, -1, 0),
+    sideGap(rect, 1, 0),
+  ]
+  let sum = 0
+  for (const v of g) sum += v === Infinity ? cap : v
+  return sum
 }
 
 function placeRect(w, h, from, dir) {
   const base = baseRect(w, h, from, dir)
   if (!collides(base)) return base
-  const horiz = dir === "N" || dir === "S"
-  const slide = horiz ? "x" : "y"
-  const fixed = horiz ? base.y : base.x
-  const slide0 = horiz ? base.x : base.y
-  const at = (c) => (horiz ? { x: c, y: fixed, w, h } : { x: fixed, y: c, w, h })
-  let nearest = null
-  for (let k = 1; k < 1000; k++) {
-    for (const off of [k * 2, -k * 2]) {
-      if (!collides(at(slide0 + off))) {
-        nearest = at(slide0 + off)
-        break
-      }
-    }
-    if (nearest) break
-  }
-  if (!nearest) return base
-  const cands = new Map()
-  cands.set(horiz ? nearest.x : nearest.y, nearest)
+
+  const xs = new Set([base.x])
+  const ys = new Set([base.y])
   for (const t of tiles.values()) {
     const r = t.rect
-    const lines = horiz
-      ? [r.x - w - GAP, r.x + r.w + GAP, r.x + (r.w - w) / 2]
-      : [r.y - h - GAP, r.y + r.h + GAP, r.y + (r.h - h) / 2]
-    for (const c of lines) {
-      const rect = at(c)
-      if (!collides(rect)) cands.set(c, rect)
-    }
+    xs.add(r.x - w - GAP)
+    xs.add(r.x + r.w + GAP)
+    xs.add(r.x + (r.w - w) / 2)
+    ys.add(r.y - h - GAP)
+    ys.add(r.y + r.h + GAP)
+    ys.add(r.y + (r.h - h) / 2)
   }
+
   let best = null
-  let bestScore = Infinity
-  for (const [c, rect] of cands) {
-    const score = slackScore(rect, slide) + 0.35 * Math.abs(c - slide0)
-    if (score < bestScore) {
-      best = rect
-      bestScore = score
+  let bestCost = Infinity
+  for (const x of xs) {
+    for (const y of ys) {
+      const rect = { x, y, w, h }
+      if (collides(rect)) continue
+      const dist = Math.abs(x - base.x) + Math.abs(y - base.y)
+      const cost = dist + 0.2 * packGap(rect, w, h)
+      if (cost < bestCost) {
+        bestCost = cost
+        best = rect
+      }
     }
   }
-  return best || nearest
+  return best
 }
 
 function addTile(info, rect) {
@@ -235,6 +233,7 @@ async function moveFrom(id, dir) {
   const info = photoInfo.get(targetId) || (tiles.get(targetId) && tiles.get(targetId).info)
   if (!info) return
   const rect = placeRect(tileW(info), tileH(info), from, dir)
+  if (!rect) return
   addTile(info, rect)
   setCurrent(targetId, rect)
 }
diff --git a/public/index.html b/public/index.html
index fd89634..9e937f4 100644
--- a/public/index.html
+++ b/public/index.html
@@ -5,7 +5,7 @@
   <meta name="viewport" content="width=device-width, initial-scale=1">
   <meta name="color-scheme" content="dark">
   <title>pathways</title>
-  <link rel="stylesheet" href="/app.css?v=3">
+  <link rel="stylesheet" href="/app.css?v=4">
 </head>
 <body>
   <main id="stage">
@@ -16,6 +16,6 @@
     <p>four paths, one per direction. walk them.</p>
     <button id="start">start</button>
   </div>
-  <script src="/app.js?v=3"></script>
+  <script src="/app.js?v=4"></script>
 </body>
 </html>