Implementare un algorithm di routes stella (A *) in una mappa grande e bassa prestazione

Sto utilizzando questa A star (A *) Pathfinder.java per calcolare e generare la mia rotta in un'applicazione per la mappa Android. https://github.com/xSmallDeadGuyx/SimpleAStar/blob/master/Pathfinder.java

La dimensione della mappa è grande, size intorno a 8000×8000, quando utilizzo la stella A star Pathfinder.java per calcolare l'itinerario da un punto all'altro nella mappa.

  • Osservazione dell'occhio di OpenCV su Android
  • Creazione dynamic di più TextViews in LinearLayout
  • Servizio Android
  • Gesto di fling e Webview in Android
  • Come analizzare l'object json con gson basato su SerializedName dinamico in Android
  • Includi il progetto Java come libreria
  • Il Pathfinder A star calcola 1 per 1 e viene utilizzato nella grande mappa (8000×8000), la velocità di esecuzione / calcolo è abbastanza bassa / lenta (non efficiente). Ho cercato di aumentare il calcolo a 100 per 100, funziona bene, ma il path path non è liscia in curva.

    C'è comunque per migliorare la prestazione del calcolo del path con l'algorithm a stella A o qualunque altra suggerimento per risolvere il problema? Ho bisogno di aiuto per risolvere il problema.

    One Solution collect form web for “Implementare un algorithm di routes stella (A *) in una mappa grande e bassa prestazione”

    Implementazione: Se stai cercando una revisione del codice, inserisci il codice di lavoro su CodeReview.StackExchange.com. Probabilmente possono dare alcuni suggerimenti di ottimizzazione.

    Algoritmo: qui sono diverse considerazioni da una prospettiva algoritmica.

    Innanzitutto, dare un'occhiata alla tua euristica. Se le stime euristiche sono troppo basse, A * degenerizza l'algorithm di Dikstra. Se le stime euristiche troppo alte, A * degenera ad una Best First Search avida. A * con un euristico ammissibile siede da qualche parte al centro: produce un path ottimale, ma mantenendo l'ottimizzazione costa un tempo di calcolo aggiuntivo. Se sei disposto a sacrificare l'ottimizzazione, puoi select un euristico che talvolta sovrastima la distanza rispetto all'objective. In tal modo, i routes non sono garantiti per essere ottimali, ma l'avidità dell'algorithm potrebbe ridurre i tempi di esecuzione.

    Inoltre, se il mondo è statico (cioè il layout è noto a priori ), è ansible pre-calcolare molte informazioni per accelerare la ricerca. Esistono diversi algoritmi per eseguire questo task. Le paludi sono un approccio che pre-calcola regioni che tendono a essere ricercate in modo inutile (cioè le paludi). A less che non viaggiano o escono da una palude, le regioni non devono essere ricercate in fase di runtime. La velocità accelerata attribuita alle paludi dipende fortemente dalla topografia del mondo; mappe più ingannevoli (cioè quelle che tendono a condurre la ricerca verso le paludi) hanno molto a beneficio.

    Un altro approccio è quello di utilizzare un approccio gerarchico di percorrenza come HPA * . Questo potrebbe avere notevoli incrementi di performance su una mappa grande come la tua (8000×8000, yikes). HPA * opera raggruppando le regioni in cluster locali collegati e calcolando i costi per attraversare i limiti del cluster a priori . Quindi, la ricerca procede in più livelli: lo sforzo di alto livello concentra la ricerca sfruttando i costi pre-calcolati e lo sforzo a basso livello determina il path esatto che verrà utilizzato.

    Inoltre, esistono algoritmi per ridurre il numero di nodes esplorati da A * sfruttando le caratteristiche dell'ambiente in fase di runtime. Ad esempio, Jump Point Search (JPS) sfrutta il fatto che i grafici di griglia (come quelli utilizzati) mostrano spesso simmetrie. Se il movimento nel tuo mondo ha un costo costante, il JPS può "ignorare" molti nodes nella ricerca e ridurre i tempi di ricerca per una notevole quantità. Ho visto ridurre il tempo di ricerca A * di 24 volte, altri hanno visto più di un miglioramento di 30 volte.

    Una nota finale: da quello che posso dire, stai utilizzando routes L1 (cioè direzioni 4-cardinali). Puoi avere molto da guadagnare preprocessando i routes tra waypoint e utilizzando un euristico differenziale. Vedere questo articolo per una demo e la discussione di un'attuazione JavaScript qui .

    Link aggiuntivi:

    • Ottime visualizzazioni di JPS in azione
    • Maggiori informazioni per JPS
    • Variazioni di A *
    • Amit's A * Pages: la migliore risorsa A * che conosco
    • Come accelerare un post A *
    L'Android è un fan Android di Google, tutto su telefoni Android, Android Wear, Android Dev e applicazioni Android Games e così via.