Pathfinder: Pathfinding A e Ricerca Percorsi

Documentazione – BeeEngine

v2.8.0

BeePathfinder — Documentazione Tecnica

A* e flow field su griglia: find / track / follow, catalogo gioco.pathfinder

📁 Panoramica

BeePathfinder è il navigatore. Vive in src/core/BeePathfinder.js, il barrel lo re-esporta con BeePath e BEE_PATH_DEFAULTS. Non è steering con raggio, non è un navmesh, non è un chase in linea retta. Tiene una griglia (celle + ostacoli), cerca un cammino A* da cella a cella e, se vuoi, un flow field verso un goal. Senza questo l’AI 2D resta pattuglia o inseguimento dritto.

Quello che non è: un collider, un body, un smoother LOS. Il path è una lista di centri-cella. follow scrive worldX/worldY (o x/y) verso il waypoint corrente. La fisica e le collisioni restano fuori.

BeeEngine crea un navigatore: this.pathfinder = new BeePathfinder(). gioco.setGrid(grid) chiama pathfinder.useGrid(grid). Una tilemap o una matrice cruda si agganciano a mano con useTilemap / useCells.

import { BeeEngine, BeeGrid } from ‘beeengine’; const gioco = new BeeEngine(‘testCanvas’, 800, 600); gioco.setGrid(new BeeGrid(25, 18, 32)); const nav = gioco.pathfinder; const path = nav.find(hunter, target); nav.follow(hunter, path, dt, hunter.speed); nav.chase(hunter, target, dt); // track + follow, path su hunter.path

📁 Tre fonti: grid, tilemap, cells

Prima di find serve una mappa. Ogni use* azzera #blocked, fa #bump (sale version) e rialloca i buffer A* / flow. Una sola fonte alla volta: useGrid stacca la tilemap, useTilemap stacca la grid.

Ingresso	Dimensioni	Camminabile
`useGrid(grid, originX, originY)`	`grid.cols` / `rows` / `cellSize`	`grid.getCell(col, row) === walkable` (default `0`). `null` (fuori) è solido.
`useTilemap(tilemap)`	`tilemap.cols` / `rows` / `tileSize`	`tilemap.isSolidTile(col, row) !== true`. Origine = `tilemap.worldX/Y`.
`useCells(data, cols, rows, cellSize, ox, oy)`	argomenti espliciti	`data[row][col] === walkable`, o la funzione `walkable(value, col, row)`.

walkable può essere un numero (confronto stretto) o una funzione. Su tilemap la funzione non entra: vince isSolidTile. configure({ walkable }) cambia il predica ma non alza version — i path già in cache restano.

📁 Integrazione BeeGrid

BeeGrid è la geometria: matrice data[riga][colonna], API setCell(c, r, val) / getCell(c, r). Il pathfinder legge getCell a ogni ricerca, quindi un muro scritto sulla grid è visibile al prossimo find.

setCell non avvisa il navigatore. track riusa il path se goal e path.version sono uguali. Un muro nuovo sulla grid, senza setBlocked e senza un altro useGrid, lascia track sul vecchio corridoio. Per invalidare: setBlocked, clearBlocked, o riagganciare la fonte.

worldToCell / cellToWorld stanno sul pathfinder, non sulla grid. I punti mondo sono il centro della cella ((col + 0.5) * cellSize). L’origine di default è (0, 0); su tilemap è worldX/Y della mappa.

📁 A* — find e findCells

find(start, goal, out) converte gli argomenti in celle e chiama findCells. Accetta { col, row } oppure un oggetto con x/y (e opzionali worldX/worldY, width/height): usa il centro, come BeeEntity.

Una ricerca: bound e goal camminabile, heap octile o Manhattan, ricostruzione sui parent. Se il budget scade, found resta false — niente path parziale.

1. boundStart/goal in mappa. Goal non camminabile → path vuoto. Start su un muro è legale.
2. A*Heap binario, closed set, costi 1 / √2. Heuristic ammissibile e consistente.
3. reconstructCatena parent dal goal. Celle + punti centro, length in pixel.
4. BeePathfound, version, goalCol/Row. Pronto per follow.

Buffer typed (Uint32 / Float64 / Int32) e uno stamp per non azzerare ad ogni search. maxIterations default 8000: oltre, la ricerca esce e found è false. Passa out un BeePath già tuo per non allocare.

📁 Diagonali, cornerCut, heuristic

Default diagonal: true, cornerCut: false. Ortho costa 1, diagonale costa Math.SQRT2. Con cornerCut: false una diagonale è legale solo se entrambe le celle ortogonali sono camminabili: non si taglia l’angolo tra due muri. I test coprono il caso 2×2 ([[0,1],[1,0]] → niente path; cornerCut: true → sì).

Heuristic: Manhattan (dx + dy) se le diagonali sono spente; octile (max + (√2 − 1) * min) se sono accese. Allineata ai costi, quindi ammissibile e consistente: il closed set non riapre i nodi e il path è ottimo sulla griglia.

📁 Celle bloccate

setBlocked(col, row, true) mette un ostacolo runtime (porta, corpo, spawn) sopra la grid/tilemap. false lo toglie. clearBlocked() svuota il Set. Tutti e tre fanno #bump: version sale, il flow field si invalida, track ricalcola.

La chiave è (row << 16) ^ (col & 0xffff). Fine per mappe da gioco; oltre 65536 colonne le chiavi collidono. Fuori mappa è sempre solido (#inBounds).

📁 BeePath — celle, punti, follow

Il risultato non è un array nudo. BeePath tiene cells[{col,row}], points[{x,y}] (centri mondo), found, index (waypoint corrente), goalCol/Row, version, length (somma ipotenuse). current è il punto sotto index. finished è true se non found o se l’indice è in fondo. rewind / clear sono fluent.

follow(entity, path, dt, speed) avanza di speed * dt verso il waypoint. Raggio di arrivo: cellSize * arrive (default 0.35). Entro quel raggio salta al prossimo punto — è l’unico “smoothing”: niente string-pull, niente LOS. Scrive il centro dell’entity su worldX/Y se è un number (BeeEntity), altrimenti su x/y. Non tocca vx/vy né il body. Ritorna true finché c’è un waypoint, poi false.

track(path, start, goal, out) riusa path se found, stesso goal in celle e path.version === this.version. Altrimenti rifà find. chase(entity, target, dt, options) è track + follow: salva il path su entity[options.key || 'path'], speed da options.speed o entity.speed (80).

📁 Flow field

flow(goal) è un Dijkstra dal goal (budget maxIterations * 4), poi su ogni cella prende il vicino a costo minore e normalizza (dx, dy). Un goal, tanti agenti: sampleFlow(x, y) o sampleFlow(entity) torna { x, y } o null (fuori, irraggiungibile, o flow stantio: #flowVersion !== version).

Dopo un setBlocked / use* il campo è morto finché non richiami flow. Non è A* al contrario e non scrive le entity: sei tu a fare x += dir.x * speed * dt.

nav.flow(target); const dir = nav.sampleFlow(agent); if (dir) { agent.worldX += dir.x * speed * dt; agent.worldY += dir.y * speed * dt; }

📁 Entity, motore, demo

BeeEntity espone worldX/worldY dalla transform: find / follow / chase usano il centro (world + size/2). Un POJO con solo x/y funziona uguale. La demo di stock non chiama il pathfinder; il contratto è coperto da scripts/test-beepathfinder.mjs (corridoio, muro pieno, cornerCut, tilemap solidTiles, track dopo setBlocked, follow su entity, sampleFlow).

📁 Dove è facile sbagliare

Niente path smoothing LOS. Il cammino è una spezzata sui centri cella. arrive salta il waypoint quando sei vicino, non tira una corda attraverso le celle libere. Un agent “liscio” lo fai tu (o inflati le celle se è più grosso di una tile).

setCell non invalida track. Cambia i muri e poi setBlocked / useGrid di nuovo, oppure chiama find ogni volta. configure (diagonali, walkable, arrive) non alza version.

Goal su muro → found: false. Start su muro è accettato (l’agente è già lì). Goal fuori mappa o non camminabile: path vuoto, niente fallback al vicino libero.

follow ignora la fisica. Scrive la posa. Un BeeRigidBody o un collider non vengono spinti: o navighi senza body, o copi tu la velocità.

maxIterations è un fail silenzioso. Mappa grande + goal irraggiungibile: found === false, stesso segnale di “muro pieno”. Alza il budget o controlla prima isWalkable sul goal.

Flow stantio. Dopo un bump, sampleFlow torna null finché non rifai flow. Non è un errore: è il contratto.

📁 Esempio: grid, chase, porte

import { BeeEngine, BeeGrid } from ‘beeengine’; const gioco = new BeeEngine(‘testCanvas’, 800, 600); const grid = new BeeGrid(20, 12, 32); grid.setCell(8, 4, 1); grid.setCell(8, 5, 1); gioco.setGrid(grid); const nav = gioco.pathfinder; nav.configure({ diagonal: true, cornerCut: false }); gioco.start((dt) => { nav.chase(hunter, hero, dt); }); // porta chiusa: ostacolo extra, i path in cache muoiono nav.setBlocked(8, 6, true);

📁 Riepilogo API

Fluent: configure, useGrid, useTilemap, useCells, setBlocked, clearBlocked, flow ritornano this. Default frozen: BEE_PATH_DEFAULTS (diagonal true, cornerCut false, walkable 0, maxIterations 8000, arrive 0.35).

Membro	Ritorna	Scopo
`BEE_PATH_DEFAULTS`	oggetto frozen	diagonal true · cornerCut false · walkable 0 · maxIterations 8000 · arrive 0.35.
`new BeePathfinder(options?)`	`BeePathfinder`	Navigatore vuoto. Senza `use*`, `find` torna path non found.
`cols` / `rows` / `cellSize` / `version`	`number`	Mappa corrente e generazione ostacoli. `version` parte da 1 e sale ad ogni bump.
`configure(options)`	`this`	diagonal, cornerCut, walkable, maxIterations, arrive. Non bumpa `version`.
`useGrid` / `useTilemap` / `useCells`	`this`	Fonte unica. Argomento mancante lancia. Clear blocked + bump + alloc.
`setBlocked(col, row, blocked?)` / `clearBlocked()`	`this`	Ostacoli runtime. Bump. `clearBlocked` è no-op se il Set è vuoto.
`isWalkable(col, row)`	`boolean`	Bound + blocked + tile solida o valore vs `walkable`.
`worldToCell(x, y)` / `cellToWorld(col, row)`	`{col,row}` / `{x,y}`	Pixel ↔ cella. World = centro cella + origine.
`find(start, goal, out?)` / `findCells(…)`	`BeePath`	A*. Goal non walkable o fuori → `found: false`.
`track(path, start, goal, out?)`	`BeePath`	Riusa se stesso goal e stessa version; altrimenti find.
`follow(entity, path, dt, speed)`	`boolean`	Avanza i waypoint, scrive il centro. false a fine path.
`chase(entity, target, dt, options?)`	`boolean`	track + follow. Path su `entity.path` (o `options.key`).
`flow(goal)` / `sampleFlow(x, y)`	`this` / `{x,y}\|null`	Campo verso un goal. Sample null se stantio o irraggiungibile.
`new BeePath()`	`BeePath`	cells, points, found, index, goalCol/Row, version, length. `current` / `finished` / `rewind` / `clear`.
`gioco.pathfinder` / `gioco.setGrid`	istanza / `this`	Un navigatore per motore. `setGrid` chiama `useGrid`.