metodo per pathfinding specializzato?

Question

Sto lavorando su un roguelike nel mio (molto poco) tempo libero. Ogni livello sarà essenzialmente poche camere rettangolari collegati tra loro da percorsi. Voglio che i percorsi tra camere di essere naturale e vento, comunque. Ad esempio, non vorrei considerare quanto segue dall'aspetto naturale:

       B       
       X       
       X       
       X       
      XX       
     XX        
    XX         
  AXX          

Voglio davvero qualcosa di più simile a questo:

       B       
       X       
       XXXX    
          X    
          X    
          X    
          X    
  AXXXXXXXX    

Questi percorsi devono soddisfare alcune proprietà:

1. Devo essere in grado di specificare un'area all'interno della quale essi sono delimitate,
2. I deve essere in grado di parametrizzare come vento e lunghe sono,
3. Le linee non dovrebbero apparire come hanno iniziato ad un percorso e si è conclusa l'altra. Ad esempio, il primo esempio di cui sopra sembra come se fosse iniziato in A e si è conclusa in B, perché fondamentalmente cambiato le indicazioni più volte fino a quando non allineata con B e poi appena andato dritto lì.

speravo di usare A *, ma onestamente non ho idea di ciò che il mio euristica sarebbe. Ho anche pensato di utilizzare un algoritmo genetico, ma io non so come pratico che il metodo potrebbe finire.

La mia domanda è, che cosa è un buon modo per ottenere i risultati che voglio? Per favore, non solo specificare un metodo di tipo "A *" o "l'algoritmo di Dijkstra," perché ho anche bisogno di aiuto con una buona euristica.

Answer 1

Prima di poter capire come produrre i percorsi, è necessario trovare un modo più preciso di affermare ciò che si desidera. Un modo per farlo è quello di assegnare ogni percorso un punteggio, quindi cercare i percorsi ad alta punteggio. Ecco alcune domande da considerare:

1. Si preferisce lunghe corse rette per quelli a breve? Come pensate di quantificare questa preferenza? (Per ottenere un algoritmo di ricerca a convergere, sarà più facile se la funzione di scoring è non lineare.)

2. Se si vuole non andare dritto a destinazione, si può decidere di premiare passi che sono fuori dalla linea principale. Ad esempio, sul percorso da A a B, considerare ogni punto, quindi fare tre passi e calcola la direzione tra punti. Ora prendete il coseno della differenza di quella direzione e la direzione dritta da A a B. negarlo. Passi sulla linea contano -1 contro di te, passi perpendicolare sono neutri, e passi dalla linea conteggio +1 per voi.

Ecco alcuni buoni passi successivi:

• Pensare a diverse altre idee di punteggio.
• Disegna una dozzina di percorsi a mano e l'ordine rango loro da quanto ti piacciono.
• Per ogni percorso, creare una coppia di piccole variazioni a mano.
• Esegui la funzione di punteggio su tutti i percorsi. Mantenere giocherellare fino ad ottenere una funzione di scoring che ama ciò che si come.

Poi sarete pronti a pensare algoritmi di ricerca.

Answer 2

Direi pathfinding è il termine sbagliato qui: di solito che coinvolge trovare una via valida da A a B, e il problema non è il ritrovamento di quel percorso, ma nella creazione di percorsi per soddisfare il vostro scopo. Si sta deliberatamente creando percorsi sub-ottimali e la loro qualità sarà difficile da quantificare. Quindi non credo che un algoritmo di ricerca con qualsiasi euristica sarebbe la migliore soluzione per il problema. Quando si dispone di un criterio obbligatorio (un percorso di lavoro) e alcuni criteri non definiti sfocati (naturale e tortuose), è meglio iniziare da soddisfare i requisiti obbligatori e tentare di mutare verso gli altri requisiti. In questo modo si hanno sempre qualcosa che funziona.

Suggerisco, dato che sembrano preferire percorsi orizzontali e verticali svolta ad angolo retto, per iniziare con una, 2 percorso segmento retto da A a B. (A * con Manhattan distanza euristica può trovare questo per voi, ma è altrettanto facile fare un passo fuori voi stessi). Dai un punto casuale lungo uno dei due segmenti e uno dei due punti finali per quel segmento, e spostare tale sottosezione della linea parallela a se stessa da una certa distanza casuale. Quindi aggiungere i 2 segmenti di linea in più per aderire alla nuova posizione della linea per i vecchi punti di connessione. Il tuo secondo esempio mostra un'iterazione di questo algoritmo: se A è (0,0) e B è (5, 7), allora avete scelto il segmento di linea 2 (quella verticale) a caso, scelto il punto finale a (0,5 ) ed un punto medio (5,5), e spinto quella sezione a destra di 3 unità, prima di entrare il backup.

Answer 3

Ecco un'idea ---

Inizia in A e fare una mossa in una direzione casuale - sinistra, in alto o in basso. Dopo ogni mossa, lanciare un numero casuale per vedere se si accende. Diciamo che il 75% delle volte si continuare a viaggiare nella stessa direzione, e il 25% del tempo si accende. Quando si accende, girare sempre in una direzione che porta più vicino alla B. Ciò vorrà dire che se si sta spostando a sinistra oa destra, dovrete alzare, e se si sta spostando su, girare a destra / sinistra scelta in base a quanto lontano ci si trova a destra oa sinistra della porta. Inoltre, se si ha colpito uno dei confini del mondo, girare!

Non dovrebbe essere troppo difficile da codice. Ho la sensazione che si sta solo cercando di rendere questo più complicato di quanto dovrebbe essere ...