Un algoritmo Star Pathfinding Heuristic per la superficie del cubo

Question

Sto creando un snake game che viene riprodotto sulla superficie di un cubo. Attualmente usa l'algoritmo di Dijkstra per il pathfinding. Nonostante le ottimizzazioni con le strutture dati delle code set e prioritarie, è ancora un po 'troppo lento. Si nota il ritardo quando il serpente mangia un alimento e inizia a cercarne uno nuovo.

Sto cercando di farlo usare A *, ma non riesco a trovare una buona euristica. In una griglia piatta con 4 direzioni di movimento, userei la distanza di Manhattan. Ho provato a usare la distanza Manhattan 3D abs(dx) + abs(dy) + abs(dz) che non ha funzionato per una buona ragione: per il serpente, il mondo di gioco è in realtà 6 grids (corresponding to the faces of the cube) con insolite proprietà avvolgenti.

Nel codice, ogni quadrato è memorizzato in un array 2D grid[15][15]. Ci sono 6 di questi array per memorizzare ogni faccia. Quindi ogni quadrato ha una tripla (arrayX, arrayY, d) per descrivere l'offset nell'array 2D e specificare quale array. Inoltre, ogni quadrato ha una tripla che descrive la posizione spaziale dello (x, y, z).

Ecco l'area del codice di gioco in cui il pathfinding succede:

https://github.com/mhluska/Snakeception/blob/master/src/js/game.coffee#L105

Ecco il codice della libreria per A *:

https://github.com/mhluska/Stimpack/blob/master/src/js/graph.coffee#L60

Che cosa è un adeguato, euristica concisa per questo mondo di gioco?

Answer 1

Un modo per risolvere questo è, invece di fare tutto il pathfinding non appena si prende un cibo, il serpente si muove verso il lato che ha il prossimo cibo e poi, quando è su quel lato , utilizzare un algoritmo di griglia A * di base per ottenere l'alimento. In altre parole:

Ogni volta che il serpente afferra un alimento o si muove ad un nuovo lato del cubo, procedere come segue:

• Se il prodotto alimentare è sul lato cubo corrente, trovare una via per utilizzando l'algoritmo A * con euristica distanza Manhattan Manhattan
• Se l'elemento cibo si trova su un lato adiacente del cubo, trovare un percorso verso il bordo del cubo confinante con il lato corrente e il lato di destinazione utilizzando lo stesso algoritmo di tracciato .
• Se l'elemento cibo si trova sul lato opposto del cubo, trovare un percorso fuori dal lato corrente con lo stesso algoritmo di tracciamento percorso.

ciò non garantisce il percorso generale più breve, ma dovrebbe normalmente essere vicino al percorso più breve, e dovrebbe essere più veloce perché divide il Pathfinding up in più fasi e utilizza un algoritmo più efficiente per ogni fase.