A* algoritme in Java(of een ander pathfinding)

[wasigh]

Hallo mensen voor een programma waar ik mee bezig ben heb ik een pathfinding algoritme nodig wat automatisch het kortse pad vind.

(bijvoorbeeld unit's verplaatsing in RA2)

Nu zijn hier al veel algoritmes voor bedacht Zoals het Dijkstra kortste Pad, en het A*(a-star)Alleen nu mijn probleem, hoe implementeer ik het op de meeste efficiente manier in java?

Ik maak nu gebrui van een array waar alle punten opgeslagen worden die al geweest zijn (bij een oppervlakte van 20*20 heeft deze array al een grote van 400 . En hoe kan ik zorgen dat hij vooral in de goede richting zoekt?

Als iemand het weet. graag. De source code is een beetje groot om te posten hier

Ik heb dus al een werkend algoritme maar wil hem graag versnellen.
Een ander pathfinding algoritme is ook welkom

[Janoz]

Ik denk dat je het beste voor een nieuwe datastructuur kunt gaan... Aangezien (bv) het dijkstra algoritme van graven uitgaat, kun je dit het beste ook implementeren. Maak dus een datastructuur die met certices werkt die verbonden zijn met edges. Als je echt een raster nodig hebt kun je het raster gebruiken om 'pointers' naar de vertices in te plaatsen.

[Tsjipmanz]

http://www.math.grin.edu/~rebelsky/Courses/CS152/98S/Outlines/outline.49.html

Hier staan verschillende shortest-path-algoritmes waaronder die van Dijkstra (en misschien zelfs wel een voorbeeld in Java).

suc6

[wasigh]

mm Ik heb op de site gekeken maar omdat ik heel veel paden heb +- 400 * 4 lijkt me het dijkstra algoritme me geen goed idee.

nog andere sugegsties:?

[Tsjipmanz]

Als je erg goed kan programmeren zou je kunnen proberen een ingewikkelde datastructuur voor een graaf kunnen proberen.

Een Dijkstra-implementatie dmv van een priority queue en een fibonacci-heap blijkt namelijk bij grote aantallen nodes de snelste ( http://www.comp.nus.edu.sg/~leonghoe/USRPreport-txt.html ), maar ik denk dat dit vrij pittige koek is.

Snelste algoritmes op dit moment zijn van
O(n* Sqrt(log(n)))

Ik weet niet hoe dit bij Dijkstra zit, maar ik denk dat je er niet onderuit kan.

[Janoz]

Het is mischien makkelijk als we ook de layout van je grid weten.. Is het van het type 'doolhof' (eventuele doorgang naar links rechts onder boven), of is het meer een vlak waarvan sommige hokjes niet toegankelijk zijn (je zou bijvoorbeeld in een rechte lijn kunnen bewegen, mits er geen obstakels tussen zitten)

Maakt nogal uit voor het bruikbare algoritme.

Dijkstra en andere algoritme gaan meer van een 'straten structuur' (edges) met 'kruispunten' (vertices).. Maar bij de hierboven genoemde indelingen kun je beter andere algoritmes gebruiken..
Some more info please..

[wasigh]

Ik ga in eerste instantie uit van een oppervlak van 20 * 20 hokjes(deze zijn variabel natuurlijk) Met daarop een aantal obstakels.
Dan is het de bedoeling dat de korste route van punt A(bv 2,2) Naar B(19,19) gegeven wordt (diagonaal bewegen is niet mogelijk)

Nu is de snelste weg makkelijk uit te rekenen met bijv de richtingCoefficient. Maar dan heb nog de obstakels waar je omheen moet.

Om het de kortste route uit te rekenen maak ik gebruik van een Soort A* algortime.

// Algortime
pre: punt A != punt B

Stap 1: zoek de aangrijzende punten van het beginpunt. Geef de allemaal de waarde van het beginpunt + 1;
Stap 2: voer die punten toe aan lijst. Punten mogen niet dubbel in deze lijst staan.
stap 3: Als een van de actuele punten Punt B stopt het algoritme
Stap 4: haal volgende punt van lijst
Stap 5: is lijst leeg dan stopr het algoritme. Geen weg gevonden. Anders begint het opnieuw

// einde algoritme
Het zijn dus eigenlijk geen graven waar ik mee werk.

Het algortime werkt, Alleen maak ik voor het opslaan van die punten gebruik van een Array van int's Deze array is nu al max 400 groot!
Stel je voor bij een oppervlakte van 1000 by 1000. Daarom vroeg ik me af:

A: Is er misschien een slimmere manier op die punten op te slaan(een Stack of List lijkt me niet makkelijk voor het checken of een waarde al voorkomt)
B: Is er voor deze situatie misschien een beter algoritme te bedenken dat in 98% van de gevallen het kortse vind..