Pathfinding and Exploration

Question

Pathfinding and Exploration

#1 da (1 voti)

1

Ecco il mio caso d'uso:

Ho una griglia bidimensionale e ogni spazio della griglia è aperto o bloccato. Conosco l'intera griglia in anticipo e mentre attraverso la griglia esploro in un raggio di 10 unità in tutte le direzioni che non sono ostruite da un ostacolo.

Vorrei esplorare al 100% la griglia nel più breve tempo possibile. Ho difficoltà a trovare un modo per farlo.

Esempio: ecco un semplice esempio che non tiene conto del raggio di esplorazione. La griglia potrebbe sembrare comunque qualcosa. In questo semplice esempio, la domanda è quando esplori come non so di abbassare il corridoio centrale sulla destra, quindi non ho bisogno di tornare indietro dopo.

XXXXXXXXX
XOOOOOOOX
XOOOOOOOX
XOXXXXXXX
XOOOOOOOX
XXXXXXXXX

I pensieri che ho finora.

1.) Sovrapponete una serie di nodi in una griglia a una data risoluzione, diciamo 10 spazi di griglia separati.

2.) Elabora l'intera griglia per il raggio di esplorazione da quei nodi.

3.) Controlla la griglia per qualsiasi luogo che non è stato esplorato, aggiungi nodi aggiuntivi per esplorare al 100%.

4.) Potare la griglia per i nodi che possono essere rimossi e che non devono essere rimossi dall'esplorazione.

5.) Utilizzare un algoritmo del percorso spanning minimo sui restanti nodi e utilizzare quel percorso per l'esplorazione.

Mi piacerebbe un modo più semplice per realizzare questo. Qualsiasi algoritmo o approccio che potrebbe semplificare?

algorithms path-finding

posta Greg Gacura 25.02.2017 - 23:45

fonte

1 risposta

Leggi altre domande sui tag algorithms path-finding

Verifica che una libreria sia retrocompatibile Ottieni dati dal server di scarto

score 1 · Accepted Answer

Non riesco a seguire il tuo algoritmo, quindi forse il mio è lo stesso, ma ecco cosa farei, in un linguaggio semplice.

Dal punto di test, scansiona un anello intorno ad esso. Dovresti trovare almeno uno spazio aperto. In caso contrario, il punto è in scatola e il risultato è "confinato".

Con gli spazi aperti che hai trovato, fai la stessa cosa, questa volta ignorando gli spazi che sono stati trovati prima. Ciò produrrà nuovamente un numero di nuovi punti di apertura sul rettangolo attorno allo spazio attualmente valutato.

Ogni round di scansione produce una raccolta di nuovi punti aperti che vengono valutati usando di nuovo la stessa funzione, fino a quando tutti ritornano confinati o uno raggiunge il quadrato esterno che è considerato libero.