A * Ricerca punto di salto - come funziona davvero la potatura?

Question

Mi sono imbattuto nello Jump Point Search e mi sembra piuttosto carino. Tuttavia, non sono sicuro di come le loro regole di potatura funzionano davvero. Più in particolare, nella figura 1, si afferma che

possiamo potare subito tutti i vicini di grigio in quanto questi possono essere raggiunti in modo ottimale dal genitore di x, senza mai passare per il nodo x

Tuttavia, questo sembra un po 'in disaccordo Nella seconda immagine, il nodo 5 potrebbe essere raggiunto passando prima attraverso il nodo 7 e saltando x interamente attraverso un percorso simmetrico, ovvero, 6 -> x -> 5 sembra essere simmetrico a 6 -> 7 -> 5. Questo sarebbe lo stesso di come il nodo 3 può essere raggiunto senza passare attraverso x nella prima immagine. In quanto tale, non capisco come queste due immagini non siano del tutto equivalenti, e non solo le versioni ruotate l'una dell'altra.

In secondo luogo, mi piacerebbe capire come questo algoritmo possa essere generalizzato a un volume di ricerca tridimensionale.

Answer 1

Capisco che si tratti di priorità. Per enumerare ogni percorso non simmetrico, devi enumerare tutti i nodi, ma in realtà non importa quale percorso scegli, perché sono simmetrici. Quindi gli autori hanno deciso di andare con la diagonale-prima- cioè, qualsiasi movimento diagonale appare sempre prima di qualsiasi movimento rettilineo in un percorso. Ecco perché la scala ha più nodi tagliati, perché deve essere presente dopo che tutte le diagonali sono state prese in considerazione.

Answer 2

La seconda immagine viene visualizzata in modo errato. Se guardi il testo che segue: "In entrambi i casi possiamo immediatamente eliminare tutti i vicini grigi poiché questi possono essere raggiunti in modo ottimale dal genitore di x senza mai passare attraverso il nodo x".

Enfasi su "entrambi i casi".

In termini di applicazione del concetto a uno spazio tridimensionale (o diamine, anche uno spazio n-dimensionale), questo algoritmo non è diverso da A * in quanto si tratta semplicemente di una trama di nodi e connessioni. La dimensionalità è interamente a tua discrezione.

Answer 3

Sì, JPS è dolce ma limitata a mappe con vincoli specifici:

1. La mappa deve rappresentare una griglia.
2. Tutte le celle accessibili nella griglia devono avere lo stesso costo trasversale.
3. L'agente in movimento deve avere 8 direzioni di spostamento possibili: 4 direzioni cardinali e 4 diagonali.

La chiave per l'algoritmo è che tali vincoli permettono alcune ipotesi chiave:

1. Il percorso geometrico breve tra due punti (in assenza di ostacoli) è anche un percorso di costo minimo.
2. Un percorso a costo minimo tra due punti (in assenza di ostacoli) non deve avere più di un cambio di direzione.

Tali presupposti consentono l'algoritmo di ignorare le opzioni di percorso simmetrici e operare come segue:

1. Quando si viaggia in una direzione cardinale avete solo bisogno di prendere in considerazione un cambio di direzione quando si incontra un ostacolo in uno dei le posizioni illustrate nei documenti. Questi punti in cui un cambio di direzione deve essere considerato sono i "Jump Points".
2. Quando si viaggia in diagonale è necessario considerare un cambio di direzione solo quando un punto di salto può essere "visto" in una delle due direzioni cardinali "rivolte in avanti", sempre come illustrato nei documenti.