Pathfinding in Javascript

Ultimo articolo del mese, un maggio dedicato ad argomenti ludici, sospeso tra la storia di Dungeons & Dragons (arrivata in tempo per l’uscita della nuova versione “Next”) e la guida a Pixel Dungeon.
Articolo tecnico oggi, per la – credo – seconda volta nella vita del blog. Si torna a parlare di programmazione, dopo un accenno agli sviluppi del motore Java per i libri game, di quasi due anni fa (andato perduto nel cambio di piattaforma blog, temo).
Ci riprovo, partendo dal solito spunto.
Nel mio caso vale il detto giocando si impara.
O, meglio, giocando vien voglia di imparare.
L’ispirazione di questi giorni è proprio Pixel Dungeon e il genere roguelike.
Capita così, da sempre. Vedo qualcosa e mi chiedo come faccia a funzionare. E se sarei in grado di farla (magari meglio, ché altrimenti non c’è sfida).
Bastano poche partite, qualche giro sul web, i due argomenti che solleticano la mia curiosità sono:

– la creazione procedurale, costruire ambienti, che sia un sotterraneo o una città, in maniera casuale con funzioni che seguano determinate regole

– il pathfinding, la possibilità di determinare il percorso (se esiste) che unisce due punti di un certo insieme di nodi, ottimizzando risorse quali distanza percorsa e tempo di elaborazione

Le approccio entrambe, per la prima scrivo un po’ di codice abbastanza grezzo, che ho denominato con fantasia “Caves & Creatures” con dei diggers che, seguendo poche regole precise (derivate in parte dal Game of Life di John Conway), scavano sotterranei dalle geometrie casuali. Risultati interessanti ma nulla di eclatante, ci tornerò prossimamente.

Un esempio di generazione procedurale in C&C
Un esempio di generazione procedurale in C&C

Avendo le griglie di punti definite dal progetto C&C, decido di tentare l’implementazione di un algoritmo di pathfinding, per la precisione l’algoritmo A*.

Rimane da decidere il come (sul quando non c’è storia, la risposta è “in ogni interstizio di tempo disponibile tra tutti gli altri impegni”).
E per aggiungere un po’ di pepe alla cosa opto per un linguaggio mai toccato. Cerco qualcosa che giri su più piattaforme possibili, che non necessiti di mastodontici IDE e relativi PC ipervitaminizzati.
Il come diventa Javascript con il browser Chrome.
Sicuramente ci sono scelte più performanti di un linguaggio web interpretato da un browser, ma questo mi permette di sviluppare praticamente ovunque e su ogni cosa (addirittura sul Kindle Fire).
Arrivo a scrivere qualcosa che funziona, grezzo e molto migliorabile, ma è frutto di qualche giorno di lavoro rubato al poco sonno e ne sono parecchio orgoglioso. Lo confronto con quanto esiste già in rete e vedo soluzioni simili e molto ancora da imparare.
Ottimo, ci sarà da divertirsi.

Intanto – perché qua non ci facciamo mancare nulla – aggiungo l’utilizzo della piattaforma di versioning GitHub, per mettere i file online. Argomento che meriterebbe un trattamento a parte, e che esula parecchio dagli scopi di questo articolo.
Il repository pubblico è questo.

Il pathfinding in Javascript al lavoro
Il pathfinding in Javascript al lavoro

Sul come funzioni l’algoritmo A* ci sono pagine e pagine in ogni lingua e sito possibili, compreso Wikipedia in italiano, alla quale rubo il pezzo di pseudocodice dal quale sono partito, esposto più sotto.

Si tratta di una logica di ricerca che sfrutta il percorso già fatto (ha quindi potremmo dire memoria della strada fatta) e una stima di quello ancora da fare, per determinare il prossimo nodo da attraversare nella griglia. Un approccio interessante, non pensate? Vedo quanto mi è costato arrivare fin dove sono, e calcolo a occhio quanto mi costerà arrivare fino a destinazione, a seconda delle scelte possibili.
Non lo facciamo spesso?

function A*(start,goal)
  closedset := the empty set % The set of nodes already evaluated.
  openset := set containing the initial node % The set of tentative nodes to be evaluated.
  g_score[start] := 0 % Distance from start along optimal path.
  came_from := the empty map % The map of navigated nodes.
  h_score[start] := heuristic_estimate_of_distance(start, goal)
  f_score[start] := h_score[start] % Estimated total distance from start to goal through y.
  while openset is not empty
    x := the node in openset having the lowest f_score[] value
    if x = goal
      return reconstruct_path(came_from,goal)
    remove x from openset
    add x to closedset
    foreach y in neighbor_nodes(x)
      if y in closedset
        continue
      tentative_g_score := g_score[x] + dist_between(x,y)
      if y not in openset
        add y to openset
        tentative_is_better := true
      elseif tentative_g_score < g_score[y]
        tentative_is_better := true
      else
        tentative_is_better := false
      if tentative_is_better = true
        came_from[y] := x
      g_score[y] := tentative_g_score
      h_score[y] := heuristic_estimate_of_distance(y, goal)
      f_score[y] := g_score[y] + h_score[y]
  return failure

Come sempre accade in informatica, tutto è migliorabile. Da una prima versione a due liste sono passato a una che utilizza solo la openList, mentre la closedList è incorporata nella matrice di ricerca.

Da scegliere con cura i costi di spostamento, per il movimento lineare e diagonale, e la funzione H() che stima la distanza tra il punto in esame e quello di arrivo. Ho fatto alcune prove e ho optato per la funzione Manhattan, cioè la somma del quadrato delle distanze sugli assi, tra il punto attuale (x,y) e l’obiettivo (xt,yt).

H(x,y) = D * ( abs(x-xt) + abs(y-yt) )

Con una matrice 128×128 e una densità di ostacoli del 52%, i tempi di attraversamento della diagonale si attestano entro i 15ms. A 256×256 si raggiungono i 40ms. Sono anche molto importanti i tempi di non raggiungimento, ovviamente molto più alti. Ho riportato quelli che, dai test, risultano i valori medi dei tempi massimi, dove quasi l’intera griglia è scansita senza risultato.

Grid     Target    Blocked
64x64    1-9ms     40ms
128x128  7-15ms    180ms
256x256  30-40ms   2500ms
512x512  80-120ms  8200ms

Come dicevo all’inizio, l’algoritmo così come il linguaggio in sé mi erano del tutto sconosciuti, quindi sicuramente è possibile migliorare sia l’implementazione che la codifica.
Qualsiasi suggerimento in tal senso è il benvenuto, anzi potete direttamente modificare il codice online.

Print Friendly

Vuoi rispondere?