Algoritmo per trovare tutte le tessere vuote nella griglia rettangolare?

Question

Algoritmo per trovare tutte le tessere vuote nella griglia rettangolare?

#1 da (3 voti)
#2 da (0 voti)

1

Ho una griglia rettangolare di tessere quadrate, alcune delle quali sono bloccate / riempite. Inizio con una tessera casuale all'interno della griglia con le tessere bloccate, posizionate casualmente. Posso girare a passi di 90 ° e controllare se posso entrare nella tessera davanti a me, il che è possibile se la tessera davanti a me non è una tessera bloccata o il bordo della griglia. Non riesco a distinguere entrambi i casi l'uno dall'altro, non ho nemmeno coordinate e non "conosco" la mia posizione nella griglia.

Ora ho bisogno di un algoritmo per scorrere tutti i riquadri aperti della griglia. Utilizzando algoritmi di risoluzione del labirinto (per esempio Pledge) mi fa correre lungo i muri delle tessere bloccate e dei bordi della griglia, tuttavia è possibile che ci siano tessere libere che non sono adiacenti a un muro, che non vengono colpite da questi algoritmi. / p>

Che tipo di algoritmo o logica devo usare per assicurarmi di coprire tutte le tessere vuote?

Immagine di esempio:

algorithms artificial-intelligence path-finding

posta user219317 10.03.2016 - 18:09

fonte

2 risposte

0

Iniziamo scrivendo una funzione che interroga i muri circostanti.

bit field = 0
can move forward?
  if y: bit field |= 1;
rotate R
can move forward?
  if y: bit field |= 2;
rotate R
can move forward?
  if y: bit field |= 4;
rotate R
can move forward?
  if y: bit field |= 8;
rotate R

Ora puntiamo allo stesso modo in cui eravamo e abbiamo il bitfield che contiene qualcosa come 0111 o simili. Da ciò possiamo andare avanti o indietro o verso destra.

Quindi, in un campo infinito (o lavorando da dimensioni massime conosciute), metti un blocco a sinistra e dietro di noi.

  ?
? . ?
X ^ . ?
? . ?
  ?

Ora entriamo in uno di quei punti vuoti. Andiamo avanti. Il nuovo interrogatorio ci dà 1010 e aggiorniamo la mappa del mondo.

? X ?
X ^ . ?
X . . ?
? . ?
  ?

Quindi ora inseriamo in questa struttura dati le nuove informazioni sul mondo.

Ci spostiamo in un'altra posizione con ? adiacente e ripetiamo l'interrogazione dei dintorni e aggiorniamo la mappa del mondo. Se ci capita di spostarci in una posizione che non ha alcun ? di spot adiacenti, utilizziamo i nostri algoritmi di individuazione dei percorsi per raggiungere il più vicino . con un ? adiacente.

Quando non ci sono percorsi verso un . con un ? adiacente, la mappa del mondo disponibile è completa.

risposta data 10.03.2016 - 19:47

fonte

Leggi altre domande sui tag algorithms artificial-intelligence path-finding

Domanda di implementazione .NET (accesso al repository) Perché le condizioni di Coffman sono necessarie per il verificarsi di un deadlock?

score 3 · Accepted Answer

Penso che vorrai un algoritmo simile a questo . La domanda riguarda la mappatura di un "labirinto" dinamico di dimensioni illimitate, ma la soluzione che ritengo sarebbe la stessa.

L'idea di base è di registrare ogni quadrato mentre lo attraversi o controllarlo in una serie di quadrati "conosciuti", fino a quando non hai mappato ogni quadrato.

Inizia registrando dove ti trovi ( 0,0 ) in un array di knownSquares
Scegli una direzione da spostare ( 1,0 , 0,1 , -1,0 o 0,-1 )
Controlla se esiste già una nuova coordinata nella matrice di quadrati noti
1. Se sì, scegli la prossima direzione.
  - Se non c'è una nuova direzione, torna indietro di una stanza
2. Se no, aggiungi nuove coordinate alla matrice di quadrati noti e verifica se è bloccata
  - Se bloccato, imposta il flag sull'elemento in knownSquares che è bloccato e seleziona una nuova direzione
ripeti i passaggi 2-3 fino a quando non sei fuori da nuovi riquadri da visitare.

Alla fine, avresti dovuto visitare ogni "quadrato" che era disponibile per il punto di partenza e persino visualizzare graficamente i risultati del knownSquares in una griglia dell'interfaccia utente se volevi disegnare la stanza o verificare i tuoi risultati .

L'unica cosa che potrebbe causare problemi è il tracciamento dell'ordine in cui visiti le stanze, ma ciò potrebbe facilmente essere risolto da una proprietà visitOrder sull'oggetto nell'array knownSquares , o da un elenco separato se vuoi un intero trascrizione di ogni piazza visitata, nell'ordine.