Come trovare tutti i percorsi possibili con una lunghezza specifica nel tabellone esagonale?

Question

Come trovare tutti i percorsi possibili con una lunghezza specifica nel tabellone esagonale?

#1 da (1 voti)
#2 da (1 voti)

1

Al momento sto sviluppando un gioco semplice in Unity.

Ho ottenuto un tabellone composto da esagoni. Diciamo che il punto rosso è il giocatore.

Ora voglio mostrare all'utente quali campi può andare, a seconda del numero che ha tagliato. L'utente non deve poter inserire un esagono più volte in una sola mossa.

Esiste un algoritmo per risolvere questo problema di percorso? Ho trovato solo algoritmi che hanno affermato se esiste una connessione tra due nodi, ma nessun algoritmo per ottenere tutte le mosse possibili.

game-development path path-finding

posta Leo V 08.03.2018 - 14:51

fonte

2 risposte

Leggi altre domande sui tag game-development path path-finding

DDD Scheduling Flights Rendere le conversioni di tipo più leggibili

score 1 · Answer 1

Sì, infatti la maggior parte degli algoritmi che controllano se c'è una connessione tra due nodi grafici calcola anche quale sia la connessione . È solo questione di non scartare le informazioni utilizzate per esprimere il giudizio si / no e invece di restituirle.

Gli algoritmi di individuazione dei percorsi sono quasi sempre ricorsivi in natura: se il nodo di destinazione è adiacente, la risposta è sì, in caso contrario verifica (tramite una chiamata automatica) se è adiacente a uno di quelli adiacenti, ecc. percorso significa semplicemente restituire un percorso parziale su ogni chiamata, che alla fine si risolve in un percorso completo se la chiamata di livello superiore ha esito positivo.

score 1 · Answer 2

La migliore risorsa per algoritmi a griglia esagonale che abbia mai letto è questo articolo di Red Blob Games , e ha una intera sezione sull'intervallo di movimento . Dice:

If there are obstacles, the simplest thing to do is a distance-limited flood fill (breadth first search).

L'esatta implementazione dipenderà dal sistema di coordinate che hai scelto per rappresentare la tua griglia esadecimale, ma in pratica troverai tutti gli esagoni che sono uno spostamento, quindi da quella lista puoi trovare tutti gli esagoni che sono due si allontana, e così via ...