Creazione di un algoritmo per un campo di gioco

Question

Attualmente sto cercando un modo per verificare se ogni campo è raggiungibile e in tal caso se c'è un modo per raggiungere ogni campo senza utilizzare un campo due volte. Il mio attuale pensiero è di provare solo ad iniziare in ogni direzione e usare i campi usati come nuovi muri. Se il robot si blocca, si riavvia e va in un'altra direzione. Ma non sono sicuro che funzioni. E la performance? Funziona anche questo?

Il mondo/i muri e la posizione del robot sono casuali. Il robot non deve usare un campo, che ha usato prima.

Ecco un'immagine di esempio.

Answer 1

A seconda dell'ingresso, è possibile utilizzare uno breadth first search algorithm che ricerca nel mondo la posizione di partenza dei robot come radice dell'albero. Tipicamente con BFS ti ricordi quali "nodi" o tessere in questa particolare situazione hai già visto. Quando l'algoritmo termina, è possibile verificare se l'elenco dei nodi visitati è uguale all'elenco dei nodi che si desidera raggiungere.

Penso che potreste fare questo se per ogni tessera sapete quali sono i nodi adiacenti (per riferimento per esempio).

Answer 2

Questo problema può essere modellato come una questione di connettività in un grafico in cui possiamo eseguire Depth First Search una volta sul tuo labirinto e trovare tutte le posizioni raggiungibili dalla posizione di partenza dove se una qualsiasi posizione che non è un muro/blocco e non visitato dopo aver eseguito DFS, non puoi raggiungere questa posizione dalla posizione di partenza seguendo un percorso nel tuo labirinto.

In sostanza, è necessario rappresentare ogni posizione del gioco come un nodo in un grafico in cui ogni nodo ha contrassegni per le sue pareti nord, est, sud e ovest. Quando si desidera visitare una posizione adiacente tramite un bordo, è possibile farlo solo se il muro delle posizioni adiacenti non è rivolto nella direzione da cui si sta provando a venire. Quindi tutto ciò che devi fare è apportare una modifica all'algoritmo DFS in modo tale che tu possa visitare/chiamare dfs su un nodo adiacente se non c'è un muro.

void explore(Node position) 
{ 
    position.visited = true 

    while(position.hasUnvisitedDirection()) 
    { 
     //random unvisited direction 
     int direction = position.getDirection(); 

     if(direction == WEST && !west(node).visited && !position.westWall) 
      explore(west(node)); 

     if(direction == EAST && !east(node).visited && !position.eastWall) 
      explore(east(node)); 

     if(direction == SOUTH && !south(node).visited && !position.southWall) 
      explore(south(node)); 

     if(direction == NORTH && !north(node).visited && !position.northWall) 
      explore(north(node)); 

    } 
} 

Qui facciamo una modifica al DFS in che selezionare una posizione non visitato casuale ad ogni posizione che visitiamo. Le chiamate east(Node), north(Node) ecc. Restituirebbero la posizione est, nord rispettivamente del nodo passato, facendo attenzione ai casi limite nella griglia (è piuttosto intuitivo se si modella il grafico come array 2D).

Successivamente vogliamo verificare se il grafico ha solo un componente fortemente connesso e questo sarà il caso se c'è un solo salto nel nostro DFS, cioè avremo un singolo albero nella prima foresta di ricerca di profondità e ogni la posizione sarà raggiungibile dalla nostra posizione di partenza che è ciò che desideri. In caso contrario, quei nodi non visitati dopo l'esecuzione di DFS non saranno raggiungibili e sarà possibile verificare tali posizioni dopo se l'algoritmo restituisce false. Così il seguente dovrebbe raggiungere questo obiettivo:

boolean isConnected(Graph g, Node startPosition) 
{ 
    int jumps = 0; 
    for (Node node : g.nodes()) 
    { 
     if(!node.visited) 
     { 
      jumps++; 
      if(jumps > 1) return false; 
      else explore(position); 
     } 
    } 

    return true; 
} 

Depth first search può essere utilizzato per generate e risolvere labirinti come indicato sopra.

Answer 3

La raggiungibilità di tutte le celle è semplice, basta una matrice booleana "raggiungibile" per ogni cella, propagare informazioni sulla connessione a partire dalla posizione di partenza del robot, assicurarsi che tutte le celle finiscano contrassegnate. Questo è lineare per le dimensioni del mondo, quindi nessun problema lì.

Per il percorso non ridondante, in pratica è necessario un euristico, poiché come già menzionato in altre risposte il problema del percorso hamiltoniano è NP. Quindi scrivi una traversata BFS o DFS dello spazio di ricerca cercando percorsi vincenti.

Ho usato la seguente euristica che scala piuttosto bene sul "cavallo da scacchiera" dove con un "cavaliere" di scacchi devi coprire tutte le posizioni sulla scacchiera. Se lo guardi in una luce topologica, è davvero lo stesso problema del tuo.

Così, l'euristica:

• in ogni cella contare il numero di modi che si possono ottenere fuori di esso. Memorizza queste informazioni in una matrice. Quindi una cella centrale ottiene 4, una cella accanto a un muro solo 3 ecc ...
• in ogni punto di decisione del DFS, seleziona la cella successiva come quella con il minor numero di uscite (Questo è il nocciolo del euristico)
• se due celle adiacenti sono a 1 all'uscita uscente, backtrack, il problema è morto questo ramo
• quando si immette un decremento cella uscite delle celle adiacenti

risciacquo e ripetere

Questo è solo guidare l'esplorazione, che rimane ad alta complessità complessiva se si è ar e sfortunato.

Intuitivamente, è meglio andare in aree con meno uscite in questo momento, dal momento che sarà più difficile tornare da loro più tardi. Le 2 celle con 1 regola di uscita sono solo un'ottimizzazione, ma è in grado di potare grosse sottostrutture che sono buone. Puoi anche tornare indietro se rilevi celle non visitate con 0 uscite a seconda di dove posizioni il test.

Ho avuto questa euristica facilmente sputando molte soluzioni anche su scacchiere più grandi rispetto al classico 8x8.

Answer 4

Ho implementato qualcosa come questo here per risolvere un enigma noto come "Il giro del cavaliere". Credo che il problema dovrebbe coinvolgere quasi la stessa logica con alcune modifiche minori.

Piuttosto che parlare di traversate, cercherò di renderlo più accessibile - Da un punto qualsiasi, per rispondere alla domanda "qual è la prossima mossa migliore?" vuoi fare un passo in più e chiedi: "qual è il fattore più limitante?" In questo caso, il fattore più limitante, in base alle tue prossime mosse disponibili, è quanti mosse sono disponibili da ciascuna di quelle mosse. Ognuna delle tue prossime mosse disponibili avrà il suo set di mosse disponibili. La prossima mossa disponibile (s) con il minor numero di mosse disponibili successive sono i fattori più limitanti.

Quindi, per esempio, diciamo che ho mosse x, yez disponibili. Sia x che z hanno 2 mosse disponibili e y hanno 3 mosse disponibili successive - vuoi spostarti su xoz (non dovrebbe importare quale tu decida in modo da poterlo randomizzare come ho fatto nel mio codice).

Perché ha senso? Pensaci in un altro modo: le prossime mosse disponibili (x, yez nel nostro esempio) sono tutte le macchie che devi raggiungere ad un certo punto! Le prossime mosse disponibili per x, y e z potrebbero anche essere considerate come ottenere INDIETRO su x, yoz. Dal momento che ci sono un minor numero di modi per tornare a x e z, si potrebbe anche andare a uno di essi ora. Se x, ad esempio, avesse solo 1 mossa successiva disponibile (tutte le altre condizioni invariate), x sarebbe la tua unica opzione valida (e come ottimizzazione potresti immediatamente passare alla prossima mossa disponibile di x perché sai che c'è solo 1).

Il codice che ho fornito ha un sacco di cose di cui non devi preoccuparti, ma dovrebbe essere autonomo, quindi dovresti essere in grado di inserirlo in una pagina JSFiddle o html e dovrebbe funzionare. Le funzioni relative alla tua domanda sono getPossibleMoves, getAvailableMoves e getBestNextMove (e tutte le funzioni che chiamano queste funzioni). I punti di interpolazione nella funzione getPossibleMoves sono correlati a D3 e non qualcosa di cui devi preoccuparti. La funzione calcola semplicemente tutte le mosse possibili, in base alle regole di come un cavaliere può muoversi, da un punto (con le proprietà xey) e poi valuta semplicemente ognuno di questi punti per vedere se sono in conflitto. Non dovrebbe essere troppo difficile modificare questa funzione per adattarsi alle mosse consentite dal tuo robot e dovrai anche aggiornare la funzione che controlla se il punto è in grado di disabilitare anche i punti in cui ci sono muri.

di responsabilità: ho buttato questo codice insieme per divertimento quindi non è ottimizzato o con qualsiasi mezzo un ottimo esempio di pratiche di codifica in JavaScript

notare anche questo è solo un modo per risolvere questo problema. Ci sono certamente altri modi per risolverlo, ma questo è il modo più diretto che conosco per farlo.