Programmazione di un robot per esplorare una griglia [chiusa] - java, prestazioni, griglia, robot

Nel mio progetto sto semplicemente cercando di creare un robotche esplora la maggior parte della griglia possibile, senza percorrere due volte lo stesso percorso. Inoltre, ha un sensore per vedere se un oggetto si trova sulla sua strada (l'oggetto può essere solo in un corridoio). Ma ho problemi a cercare di evitare che il robot segua lo stesso percorso.

Ho provato a risolvere questo problema creando un 2Darray per la memorizzazione di un valore intero per ogni quadrato della griglia. Un valore pari a 0 indica che il robot non è ancora stato su quel quadrato nella griglia, un valore 1 indica che il quadrato è bloccato nella griglia e un valore 2 indica che il robot è stato su quel quadrato prima. Se il robot vede che il quadrato davanti alla sua direzione attuale ha valore 2, continuerebbe a ruotare per trovare un quadrato con un valore di 0, ma se non esiste un quadrato di valore 0 attorno al robot, allora inizia a tornare indietro.

Il mio problema può essere spiegato più chiaramente con questo esempio:

Il triangolo rappresenta il robot e il suo inizioposizione, si presume che l'angolo in basso a sinistra sia la posizione (0,0) nella mia griglia. I cerchi verdi rappresentano gli elementi che ne bloccano il percorso. Il quadrato rosso è il bersaglio del robot. Il robot può spostarsi solo su quadrati bianchi nella griglia.

Quando avvio il mio programma il robot, si muoveavanti (est poiché quella è la sua direzione attuale) fino a raggiungere l'incrocio appena prima dei cerchi verdi. Guarda avanti e rileva un oggetto lungo la strada, quindi ruota di 90 gradi in senso antiorario e verifica la presenza di un altro blocco, che si verifica nuovamente, quindi ruota di nuovo in senso antiorario. Quindi ora il robot è in posizione (0,2) in direzione ovest. Può solo spostarsi verso ovest per evitare di lasciare la griglia o di colpire un oggetto, quindi ritorna nella sua posizione iniziale ma continua ancora verso ovest. Ora continuerà a ruotare di 90 gradi in senso orario fino a quando non troverà una direzione che lo manterrà sulla griglia, cioè fino a quando non sarà di nuovo rivolto verso est. Quindi la griglia ora appare come:

Ma ora voglio ignorare andare avanti e sulstesso percorso ignorando quella direzione e ruotando di nuovo di 90 gradi in senso antiorario per affrontare il nord, in modo che il mio robot possa spostarsi a nord in un nuovo percorso. Potrei semplicemente ignorare la direzione e continuare a ruotare per trovare un nuovo percorso, ma cosa succede se sono circondato da percorsi precedenti e voglio che il mio robot torni indietro fino all'ultimo incrocio. Come posso farlo in modo efficiente. Inoltre, come posso rilevare in modo efficiente quando devo tornare indietro.

Grazie

risposte:

Risolvere la situazione nella figura 2 potrebbe essere semplice come cercare altri white quadrati attorno al robot prima di fare una mossa. Nella figura 2 il robot vedrebbe che il quadrato che sta affrontando è "oscurato" e decide di controllare tutte le altre direzioni e alla fine scoprirà che c'è un quadrato bianco vuoto a nord di lui.

Modifica: non avevo capito che fosse un vero robot.

Dal momento che l'unico modo per imparare ciò che è in una cellaè girandosi su quella cella e usando il sensore, il robot dovrà fare una certa quantità di virata, qualunque cosa tu faccia. Quando incontra un muro o un oggetto verde, dovrà girare fino a quando non trova un nuovo percorso da percorrere. È possibile ottimizzarlo ignorando le pareti del recinto. Ad esempio, quando il robot torna nella sua posizione iniziale rivolto a ovest, sai già che c'è un muro a sud perché la sua posizione delle coordinate è (0, -1), che non è valida. Questo ti permette di capire che la tessera aperta è a nord perché hai già visitato la tessera a est, richiedendo solo un turno.

Inoltre, quando il robot alla fine viaggiafino a nord, piastrella (0,6) sai che c'è un muro a nord e ad ovest a causa della sua posizione. Potresti quindi indovinare in modo intelligente che lo slot aperto deve essere ad est perché la tessera occidentale (-1,6) non è valida e (0,7) non è valida neanche.

Senza cambiare il sensore per vedere 2 blocchi oinstallando più sensori sul robot (cioè uno su ogni lato), non c'è molta più ottimizzazione che può essere fatta a causa della limitata disponibilità di informazioni.