Pathfinding gioco 2D in Java?

Question

Attualmente sto scrivendo un gioco Java molto semplice basato sull'idea di Theme Hospital.

Sono abbastanza nuovo in Java e attualmente sto studiando all'università il mio primo anno. Ho fatto Java per quasi due anni a questa parte, ma sto finalmente dedicando il mio tempo a un progetto decente.

Sono al punto in cui ho bisogno di creare una persona (paziente) per essere ricoverata in ospedale. Devono andare alla reception, poi all'ufficio GP, e poi tornare alla loro posizione di partenza.

Ho esaminato il percorso A *, ma a me sembra molto complicato. Capisco come funziona, ma non sono sicuro di come implementarlo nel mio gioco.

Finora, l'utente può posizionare una reception e costruire l'ufficio di un GP. Ognuno di questi ha un "punto di utilizzo" che sarà il posto dove il paziente deve arrivare. I quadrati della griglia possono essere solo pieni o no, non ci sarà nessun terreno diverso.

Sono riluttante a incollare qualsiasi codice ancora, poiché è disordinato perché ho imparato molte nuove tecniche da fare con la GUI negli ultimi mesi. Il mio piano è di arrivare al traguardo 1, facendo andare il paziente alla scrivania, poi all'ufficio e poi via. Una volta che avrò questo, aggiusterò di più il codice.

Ho visto molte implementazioni di A * e molti tipi diversi. Qualcuno può darmi un punto di partenza con cui posso lavorare? Dovrei provare ad adattare un set già scritto di classi, o provare a scrivere il mio da zero?

Answer 1

Si desidera A *, è l'implementazione ottimale per la ricerca di percorsi basata sulla griglia.

Questo potrebbe aiutare a uscire:

http://www.cokeandcode.com/main/tutorials/path-finding/

EDIT: Il collegamento precedente è un bene per entrambi come un insieme implementabile delle classi e come guida per la personalizzazione del percorso di trovare metodi per soddisfare la vostra soddisfazione .

Answer 2

Il libro AI for Game Developers ha una spiegazione molto buona di A *. Oggi stavo per scrivere un'implementazione ... se lo farò, lancerò il codice qui.

Il codice è terminato, è troppo grande per essere inserito qui, quindi è possibile prenderlo da: https://chaos.bcit.ca/svn/public/astar/ (certificato autofirmato, ma il server non fa nulla di male).

Ho seguito lo pseudo-codice nel libro per la maggior parte, ma ho reso tutto molto più orientato agli oggetti di qualsiasi cosa abbia visto finora per A *.

Hai un labirinto costituito da piastrelle. Ogni tessera ha una posizione e un ostacolo (nulla se non ci sono ostacoli).

È possibile utilizzare un PathFinder (come AStar) per trovare il percorso più breve tra una determinata posizione di inizio e di fine. Ottieni un percorso indietro che include le tessere che devi attraversare per andare dall'inizio alla fine.

È possibile modificare il calcolo euristico fornendo un diverso Calcolatore euristico (quello corrente controlla solo se c'è un ostacolo o meno e calcola il numero più breve di tessere da passare, è possibile aggiungere pesi a ostacoli diversi per istanza se non ti piace il default).

Il codice è sotto licenza LGPL, quindi se si apportano modifiche e si distribuisce l'app è necessario rendere disponibili le modifiche. Sentiti libero di inviare segnalazioni di errori/correzioni all'indirizzo email nel commento della licenza (presente in ogni intestazione).

I'll (never did) andare in giro a commentarlo dopo gli esami, ma penso che sia abbastanza semplice.

Answer 3

Naturalmente imparerai molto sul rilevamento dei percorsi se scrivi la tua implementazione. Ma passerai anche molto tempo a farlo.

Controlla la libreria JGraphT che tratta i grafici in generale, ha una bella API e supporta gli algoritmi di percorso più corti more oltre a A *.

Answer 4

Questo è il post pathfinding più informativo che ho visto fino ad oggi: http://www.ai-blog.net/archives/000152.html

Answer 5

Forse avete trovato quello che volevi, ma ecco un link con una bella spiegazione di A * pathfinding. Ho dovuto implementare A * per il mio gioco in C++ e mi ha aiutato molto a capire come funziona.

http://www.abdn.ac.uk/~csc245/teaching/CS1015/practicals/aStarTutorial.htm