Costruisci una mappa con blocchi di città e strada

Question

Costruisci una mappa con blocchi di città e strada

#1 da (2 voti)

2

Esiste un modello di progettazione o un algoritmo ben noto per costruire una mappa semplice con strade e blocchi di città?

Per avere un'idea di quale sia il mio obiettivo, descrivo alcuni dei vincoli e il contesto:

una matrice che rappresenta una mappa (rettangolare)
pochi possibili blocchi di città rappresentati come rettangoli (ad esempio, 4x3, 5x2, 1x6)
poche dimensioni stradali possibili (ad es. 1, 2)
non sono mai collegati, il che significa che c'è sempre una strada tra loro

il risultato sarebbe un array come questo:

111101111100110
111101111100110
111100000000110
000001110000110
000001110000000
...

dove, ad esempio, "1" sono i blocchi e "0" sono le strade.

Quello che intendo fare è mettere un blocco dove è possibile, quindi circoscrivere con le strade e andare avanti. Questo sarebbe ok, ma potrebbe portare ad un posto dove i blocchi non si adattano.

Vorrei sapere se c'è qualcosa nello stato dell'arte di tali algoritmi.

design-patterns algorithms

posta donnadulcinea 10.05.2014 - 21:57

fonte

1 risposta

Leggi altre domande sui tag design-patterns algorithms

Spostare la nostra applicazione web da un ambiente di sviluppo Windows in ambiente Linux senza soluzione di continuità A quale livello l'HDBC di Haskell è pigro?

score 2 · Answer 1

La maggior parte degli algoritmi genererà una mappa generata in modo casuale basata esclusivamente su un seme. Non valuterebbe mai la mappa e quindi non garantisce una buona esperienza utente.

Poiché hai menzionato che vorresti creare un generatore di mappe " state of the art ", la prima cosa che mi viene in mente è algoritmi genetici . Tale algoritmo creerebbe molte mappe diverse, basate su una combinazione di geni sottostante. Ad ogni iterazione, ogni mappa verrebbe valutata e migliorata. (il pool genico può essere esattamente la stessa rappresentazione della tua matrice sopra - ciò che è anche bello di questo è che non avrai un tale effetto block city - a meno che non sia quello che vuoi, allora puoi codificarlo anche in questo modo).

Per implementare questo, tutto ciò che serve è un algoritmo di valutazione (per ogni mappa data). Se riesci a trovare un tale algoritmo di valutazione e lasci che questo processo di generazione della mappa passi attraverso un paio di iterazioni / evoluzioni (ad esempio 100), ti ritroverai con alcune mappe davvero interessanti.

Un algoritmo di valutazione (fitness) consisterebbe in qualcosa tipo:

penalty = how many roads are too close to one another +
how many cities are too close to one another

Ho semplificato la formula di cui sopra, dovrebbe essere un po 'più simile alla somma di quanto una città sia vicina l'una all'altra + la somma di quanto vicino ... ecc

then fitness = 1/penalty

Ho fatto una rapida ricerca su: "algoritmo genetico e generatore di mappe" e ho trovato alcuni risultati che affermano:

"In questo articolo introduciamo un generatore di mappe procedurali per un gioco di strategia in tempo reale (RTS) .Il componente principale di questo generatore è un algoritmo genetico dedicato alla creazione e all'evoluzione di mappe bilanciate, ovvero mappe in cui nessun giocatore ha qualche vantaggio relativo alla mappa rispetto ad altri giocatori. "

link