Genera a caso un grafico diretto su una griglia

Question

Genera a caso un grafico diretto su una griglia

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

11

Sto provando a generare casualmente un grafico diretto allo scopo di creare un puzzle game simile ai rompicapo di ghiaccio di Pokemon.
Questo è essenzialmente ciò che voglio essere in grado di generare casualmente: link .

Devo essere in grado di limitare la dimensione del grafico in una dimensione xey. Nell'esempio indicato nel link, sarebbe limitato a una griglia 8x4.
Il problema che sto incontrando non è la generazione casuale del grafico, ma la generazione casuale di un grafico, che posso mappare correttamente in uno spazio 2D, poiché ho bisogno di qualcosa (come una roccia) sul lato opposto di un nodo, per renderlo visivamente ha senso quando smetti di scivolare. Il problema con questo è che a volte la roccia finisce nel percorso tra altri due nodi o forse su un altro nodo stesso, il che causa la rottura dell'intero grafico.

Dopo aver discusso il problema con alcune persone che conosco, siamo giunti a un paio di conclusioni che potrebbero portare a una soluzione.

Includere gli ostacoli nella griglia come parte del grafico durante la costruzione.
Inizia con una griglia completamente piena e disegna un percorso casuale e cancella i blocchi che faranno funzionare quel percorso.

Il problema diventa quindi capire quali sono da eliminare per evitare di introdurre un percorso aggiuntivo, più breve. Stavamo anche pensando che un algoritmo di programmazione dinamica potrebbe essere utile, anche se nessuno di noi è troppo abile nel creare algoritmi di programmazione dinamica dal nulla. Qualsiasi idea o riferimento su ciò che viene ufficialmente chiamato questo problema (se si tratta di un problema grafico ufficiale) sarebbe molto utile.

Ecco alcuni esempi di ciò che ho realizzato fino ad ora posizionando casualmente blocchi e generando il grafico di navigazione dall'inizio / fine scelto. L'idea (come descritto nel link precedente) inizia con la S verde e vuoi arrivare al verde F. Lo fai muovendo su / giù / sinistra / destra e continui a muoverti nella direzione scelta fino a quando non colpisci un parete. In queste immagini, il grigio è un muro, il bianco è il pavimento e la linea viola è la lunghezza minima dall'inizio alla fine, e le linee nere e i punti grigi rappresentano i possibili percorsi.

Ecco alcuni esempi negativi di grafici generati casualmente:

Eccoalcuniesempidigraficigeneraticasualmente(omodificatimanualmente):

Ho anche notato che quelli più impegnativi quando si gioca in questo modo come un puzzle sono quelli che hanno molti nodi di alto grado lungo il percorso minimo.

language-agnostic random graph

posta Talon876 18.01.2012 - 01:59

fonte

3 risposte

Leggi altre domande sui tag language-agnostic random graph

Come modularizzare e impacchettare una libreria Javascript sul lato client oggi? Qual è la relazione tra interpreti meta-circolari, macchine virtuali e aumento delle prestazioni?

score 2 · Answer 1

è ghiaccio, ti sposterai a meno che non colpisci uno scoglio.
l'unico modo per cambiare direzione è colpire una roccia.
se colpisci una roccia devi cambiare direzione.
sono buoni, per ovvi motivi.
possono esserci più avvii e più fini.

Proprietà più avanzate:

le celle senza rocce adiacenti non sono raggiungibili (alcune possono essere attraversate)
anche i muri sono rocce, se li rimuovi puoi decidere di avvolgere.
puoi utilizzare le griglie secondarie come pattern ("piastrellatura" 3x3, 3x4, 5x5, ... ecc.)
puoi sovrapporre una tessera MxN di un puzzle in cima all'area MxN non traversabile e aggiungere una pietra per reindirizzare dentro / fuori da essa.
la rotazione o la simmetria di una tessera può essere interessante
puoi espandere una tessera inserendo righe / colonne ghiacciate

Esempio:

S=start, E=end, o=rock, .=ice

3 . 2 o        3 . . 2 o         . . . . . o o
4 . . E   ~=   4 . . . E   ~=    . . . . . 2 E
o . . .        o . . . .         . . . . . . .
S . 1 o        S . . 1 o         S . . . . 1 o

esempio di combinazione di tessere:

3 . . 2 o       o 2 . . 3      3 . . 2 o 7 . . 6
4 . . . E   +   E . . . 4  =   4 . . . . . . . 5
o . . . .       . . . . o      o . . . . . . . o
S . . 1 o       o 1 . . S      S . . 1 o 8 . . E

ti potrebbe piacere il gioco Tsuro , utilizza le tessere per generare una scacchiera casuale.

score 0 · Answer 2

Forse il reverse engineering potrebbe aiutarti se ne hai bisogno.

Se esiste una sola soluzione per ogni problema, puoi probabilmente generare un grafico basato sulla risposta univoca. Questo non richiede di fare programmazione dinamica o addirittura saltare la forza bruta e optare per una generazione metodica.

Puoi occupartene:

Mantenere un grafico MxN pronto
creazione di una / più soluzioni (s)
facendo una domanda intorno ad esso se si tratta di un singolare problema di soluzione
se ci sono più soluzioni al problema, puoi ripetere il sopra la procedura in modo tale che l'iterazione corrente non lo faccia inibire un'altra soluzione.

Anche se sarà necessario progettare un dispositivo in base alla complessità del problema e alla dimensione del problema che genererà questa domanda per te. Non andare solo per la forza bruta. Prova invece un algoritmo randomizzato. Questo potrebbe aiutarti.

score 0 · Answer 3

Che ne dici di un altro approccio? Inizia con un labirinto vuoto e aggiungi blocchi come questo:

Blocco e blocco finale a caso.
Fai 1-3 passi "scorrevoli" in direzione casuale (ma non di ritorno) e con lunghezza casuale (*). Posiziona un blocco dopo ogni passaggio (per fermare la diapositiva).
Trova un percorso più breve verso l'uscita. Se ci sono troppi segmenti (difficoltà di basso livello), prendi un segmento casuale del percorso e dividilo con un blocco. Altrimenti, posiziona un blocco come nel passaggio 1 e esci.
Ripeti 1 con cautela (*): quando scegli la lunghezza di un passo scorrevole, fallo in modo che il blocco che hai inserito non chiuda il percorso precedente.

Tocco finale: trova il percorso più breve con l'algoritmo che hai fornito. Prendi nota di tutte le celle che vengono utilizzate e inizia a riempire il resto in modo casuale, ogni volta assicurandoti che il percorso più breve non si accorci.

C'è un avvertimento nel secondo passaggio, quando non puoi mettere l'ultimo blocco in modo che non attraversi i percorsi usati, ma vedo due soluzioni: muovi il blocco finale in anticipo o annulla alcuni passaggi e prova ancora una volta.

E un altro pensiero per la lunghezza casuale dei passaggi scorrevoli: potresti volerlo scegliere in modo che un blocco posizionato in precedenza venga riutilizzato, a condizione che i percorsi non si sovrappongano.