Algoritmo di generazione del labirinto multiplayer ottimale

Question

Sto lavorando a un semplice gioco multiplayer in cui 2-4 giocatori sono posti in punti separati in un labirinto e devono raggiungere un punto obiettivo. Generare un labirinto in generale è molto semplice, ma in questo caso l'obiettivo del gioco è quello di raggiungere l'obiettivo prima di tutti gli altri e non voglio che l'algoritmo di generazione favorisca drasticamente un giocatore rispetto agli altri.

Quindi sto cercando un algoritmo di generazione di labirinti in cui il percorso ottimale per ciascun giocatore dal punto di partenza all'obiettivo non sia più del 10% in più di passi rispetto al percorso medio. In questo modo i giocatori sono più o meno in condizioni di parità. Qualcuno può inventare un tale algoritmo?

(Ho un'idea così com'è, ma non è ben pensata e sembra molto meno che ottimale - la pubblicherò come risposta.)

Answer 1

Un'alternativa alla risposta di freespace sarebbe quella di generare un labirinto casuale, quindi assegnare a ogni cella un valore che rappresenta il numero di mosse per raggiungere la fine del labirinto (puoi decidere di fare entrambe le cose contemporaneamente se decidi di iniziare da la fine'). Quindi scegli una distanza (forse la più alta con n punti a quella distanza?) E posiziona i giocatori ai quadrati con quel valore.

Answer 2

Che ne dici di selezionare prima la posizione dei giocatori e l'obiettivo e un percorso di uguale lunghezza e poi costruire un labirinto rispettando i percorsi definiti? Se i percorsi non si intersecano, dovrebbe funzionare facilmente, presumo

Answer 3

Mi avvicinerei a questo impostando l'obiettivo e il punto di ingresso di ciascun giocatore, quindi generando percorsi di lunghezza simile per ciascuno di essi verso l'obiettivo. Quindi inizierei ad aggiungere falsi rami lungo questi percorsi, facendo attenzione a evitare il collegamento ai percorsi di altri giocatori o facendo in modo che un ramo si ricolleghi al percorso. Quindi essenzialmente ogni ramo è un vicolo cieco.

In questo modo, garantisci che i percorsi sono simili in lunghezza. Tuttavia, ciò non consentirà ai giocatori di interagire tra loro. Puoi comunque inserirlo, creando collegamenti tra i rami in modo tale che i punti di ingresso dei rami su entrambi i percorsi siano a una distanza simile dall'obiettivo. E su questo ramo puoi diramare più vicoli ciechi per divertimento e profitto :-)

Answer 4

La soluzione più semplice che posso trovare è quella di generare casualmente un intero labirinto come normale, quindi scegliere casualmente il punto obiettivo e i punti di partenza del giocatore. Fatto ciò, calcola il percorso più breve da ciascun punto di partenza all'obiettivo. Trova la media e inizia a 'levigare' (rimuovi / sposta le barriere - non so come funzionerà) i percorsi che sono significativamente al di sopra di esso, fino a quando tutti i percorsi si trovano all'interno del margine corretto. Inoltre, potrebbe essere possibile prendere quelli che sono significativamente al di sotto della media e inserire ulteriori barriere.

Answer 5

Scegli il tuo punto di uscita da qualche parte nel mezzo

Inizia da qui i tuoi N percorsi, aggiungendo 1 a ciascun percorso per loop, fino a quando sono lunghi quanto vuoi che siano.

Ci sono i tuoi N punti di partenza e hanno tutti la stessa lunghezza.

Aggiungi ulteriori rami al di fuori delle linee, fino a quando il labirinto non è pieno.