Bypass dell'ostacolo in ambiente 2d

Question

Bypass dell'ostacolo in ambiente 2d

#1 da (5 voti)
#2 da (1 voti)

3

Per questa griglia 2d (il quadrato nero non è penetrabile, il quadrato bianco è):

Vogliotrovareilpercorsocheconsentedispostareunoggettosuunpuntoiniziale(x:18,y:18)suunpuntofinale(x:1,y:1),quadratoperquadrato.Immaginachequestooggettosiaunaformicaounrobot,quindi:

Puòsoloconoscereladirezionedelsuoobiettivo,ladistanzadalsuoobiettivoeseintorno(1quadrato)ilquadratoèpenetrabileomeno.L'oggettopuòconservarelamemoriadelsuopercorso,seèbypassatoperchéprecedentementebloccato,ecc...

A(x:18,y:18),ladirezioneantXè(x:-1,y:-1)vettore,ladistanzadaXè18square,vector(x:-1,y:-1)èpenetrabile).
A(x:17,y:17),ladirezioneantXè(x:-1,y:-1)vettore,ladistanzadaXè17square,vector(x:-1,y:-1)èpenetrabile).
...
A(x:11,y:11),ladirezioneantXè(x:-1,y:-1)vettoriale,ladistanzadaXè11square,vector(x:-1,y:-1)ènotpenetrable).

Manonpuòsaperealtrecose.QuindinonpossiamousarequiunalgoritmoA*ol'algoritmodiDijkstra.Immaginachel'oggettosiaunrobotnellatuacasa.Puòtestareogniposizionecomel'algoritmodiDijkstra,macivorrannoduesettimaneperbypassareunasedia.

QualealgoritmopuòessereutilizzatopertrovareilpercorsodaSaXsenza"camminare" su un quadrato nero, in base alle limitazioni "ant" / "robot"?

Ne scrivo alcuni, ma con alcuni problemi come la difficoltà a seguire "wall" e
gira in tondo ...

UPDATE : dopo la risposta di Karl Bielefeldt, scrivo alogithm disponibile qui e procuding: MODIFICA : Finalmente non uso l'ispirazione A *, ma "segui l'ispirazione del muro"

Sei libero di puntare e suggerire miglioramenti!

algorithms artificial-intelligence robotics

posta bux 08.07.2015 - 19:10

fonte

2 risposte

1

Sembra che tu stia cercando un algoritmo A * ~~o Dijkstra~~ .

A seconda della lingua con cui si sta lavorando, è probabile che siano già state create delle librerie che è possibile utilizzare per queste. Ecco alcuni algoritmo Pseudocode per A * ~~e un esempio per l'algoritmo di Dijkstra~~

EDIT: Anche se Dijkstra funzionerebbe tecnicamente, non sarebbe altrettanto efficiente come dovrebbe essere.

risposta data 08.07.2015 - 19:24

fonte

Leggi altre domande sui tag algorithms artificial-intelligence robotics

Posto migliore per convertire un oggetto in un altro oggetto Gestione della radice aggregata con la gerarchia degli oggetti profondi

score 5 · Accepted Answer

Se ti è permesso di ricordare i dati passati, A * è davvero la soluzione migliore. L'ho utilizzato su la sfida di Google Ant Ant di Google , che ha solo un piccolo raggio di visualizzazione.

La principale differenza con un campo visivo limitato è che si sta camminando molto di più solo per esplorare, ma ciò è inevitabile. A * ti fornirà una lista abbastanza buona di dove esplorare, senza dover visitare l'intera mappa.

Per divertimento, ho codificato una soluzione per il tuo esempio. Quello che segue è l'output:

(18,18)
(17,17)
(16,16)
(15,15)
(14,14)
(13,13)
(12,12)
(11,11)
(11,10)
(10,11)
(9,12)
(8,13)
(8,14)
(8,13)
(9,12)
(10,11)
(11,10)
(12,9)
(13,9)
(13,10)
(13,11)
(14,12)
(15,11)
(15,10)
(15,9)
(15,8)
(14,7)
(13,6)
(12,5)
(11,4)
(10,3)
(9,2)
(8,1)
(7,0)
(6,1)
(5,1)
(4,1)
(3,1)
(2,1)
(1,1)

real    0m0.404s
user    0m0.727s
sys     0m0.040s

È persino più efficiente di quanto immaginassi. Solo 40 mosse, quando l'ideale con una vista onnipotente della mappa sarebbe 25. Puoi vedere che segue le tue frecce in un primo momento, esplora un po 'lungo il muro verso il Nord-Ovest, poi gira intorno e segue il muro fino a sfuggire alla rientranza , dopo di che è quasi un colpo dritto. Potrebbe anche essere migliorato ulteriormente modificando i pesi su celle non visibili per essere proporzionali alla distanza dalla posizione corrente.