Algoritmo di individuazione dei percorsi per i treni

Question

Sto provando a trovare una soluzione per il rilevamento dei percorsi in un gioco di treni in cui esistono diversi tipi di biforcazioni. Voglio che il treno vada da una ferrovia all'altra, tutto è implementato eccetto il path-finding.

Ho bisogno di ottenere un elenco di binari in modo che il treno possa seguire. Ora, il problema è come ottengo la lista.

• Ho provato A *, non ha funzionato perché smette di cercare se il nodo (rail) è già visitato. Questo è un problema, perché forse il modo per raggiungere un punto è attraversando il percorso più lungo.
• Riempimento di piena, questa volta non ha smesso di cercare se già visitato, il problema è come ricostruire il percorso e come si sceglie che non può tornare indietro.

Il fatto è che ci sono casi in cui il treno deve passare attraverso una sbarra più volte per raggiungere la sua destinazione.

Qualche idea?

Il punto di partenza è A, fine B. Come si vede il percorso verde è il modo in cui dovrebbe viaggiare. Il cerchio balck sono le rotaie che il treno farà più di una volta, in questo caso 2 volte.

E ovviamente, è necessario venire da 2 nero per arrivare a 3 rosso. Non puoi semplicemente andare 1black-> 2red-> 1red-> 3red.

Answer 1

Guardando questa immagine

Sembra che il tuo problema sarebbe rappresentato da un ben directed graph. Dare ad ogni fermata e ad ogni nodo due nodi nel grafico, uno per ciascuna direzione del treno. Dijkstra's algorithm funziona perfettamente su grafici diretti, quindi una volta che hai il problema in quella forma, il resto è facile.

Quindi, ad esempio, nell'immagine sopra, a partire da A, passiamo a junction 1. Da lì, c'è solo un posto dove spostarsi, junction 2, quindi ci sarebbe una freccia da A ->junction 1 e una freccia da junction 1 ->junction 2. Indipendentemente dalla scelta che fai, ti ritrovi allo junction 1, ma spostandoti nella direzione opposta, quindi creiamo un nodo separato da lì.Da lì, hai la possibilità di andare a A o B.

Si noti che ho rimosso uno dei 's J1, dal momento che è superfluo (c'è solo un posto dove andare).

Se il treno si ferma e si gira alle fermate come A, possiamo collegare questi due nodi per i bordi in entrambe le direzioni, o semplicemente combinarli in un nodo.

È possibile assegnare i pesi dei bordi per specificare le distanze.

Answer 2

Il riempimento dell'inondazione dovrebbe davvero fare la cosa (l'ho usato in un caso simile) - ma devi solo lavorare con interruttori e segmenti attentamente.

Gli algoritmi devono essere autorizzati a passare lo stesso segmento in direzione diversa, ma non nella stessa. Cioè ogni segmento dovrebbe essere considerato come due separati.

di ricostruire il percorso che si dovrebbe assegnare i numeri ai segmenti mentre li inondazioni, in modo che ogni raggiungibile da N-1 è contrassegnato con N - poi mentre tornare indietro, monitoraggio segmenti dovrebbe essere fatto in modo che i numeri in costante diminuiscono di uno.

È davvero una specie di BFS.