[C++] Path finder

[vdvleon]

Hallo iedereen,

Ik ben begonnen met mijn eerste game. Het is wel simpel, maar ik gebruik SDL voor het grafische gedeelte, voor de keyboard input. Dus ik leer er wel veel van.

Het gaat om een doolhof spel. Heel simpel. Je hebt gewoon een doolhof met begin en eind punt. Jij als speler bestuurd dan een blokje die je dan vervolgends van start naar eind moet sturen.

Maar toen lijk mij het leuk om hier wat aan toe te voegen, en wat meer denk werk voor mij te leveren, namelijk een path finder. Dus extra functionaliteit die voor jouw de weg kan vinden (voor als je er niet uit komt ).

De code die ik nu heb werkt wel gewoon, maar is eigenlijk gewoon heel recht toe recht aan, niks intelligents. Het lijkt mij nu een uitdaging om te kijken hoe je het 'snelste' path kan vinden.

Ik maak nu gebruik van een recursive findPath functie. Deze kijkt steeds voor 4 richtingen (left, right, up, down) of deze uiteindelijk een resultaat geeft. Hij controleerd dan natuurlik voor elk blokje of deze buiten de map ligt, een muur is, of als je er al bent geweest.

Wat zou het beste zijn? Gewoon alle mogelijke oplossingen zoeken en dan de kortste pakken, of gewoon echt slimmer naar het doolhof kijken?

[JeRa]

Het ligt nogal aan de opbouw van je doolhof. Je zou bijvoorbeeld Dijkstra (de (nogal logge) basis) of A* (A-star, een uitbreiding met een voorkeur voor paden die dichter bij het eindpunt liggen) kunnen bekijken, maar als je een behoorlijk random doolhof hebt dan kan een fill algoritme (wat je nu doet) net zo goed werken.

[YopY]

Je huidige opzet klinkt inderdaad veel als Dijkstra. Een iets optimalere methode zou de eerder genoemde A* zijn.

Maar je zou eens kunnen kijken naar de verschillende algoritmen zoals beschreven op Wikipedia: Pathfinding.

[vdvleon]

Wel interesant onderwerp. Ik zou deze algoritmes eens bestuderen.

edit:

Ik moet wel zeggen, mijn methode, zoals hij nu is, is niet de snelste route, maar als ik alle mogelijkheden zou langsgaan natuurlijk wel.

[ Voor 54% gewijzigd door vdvleon op 17-07-2009 01:38 ]

[Verwijderd]

Er is laatst een topic over A* langsgekomen, wellicht dat je er nuttige informatie uit kunt destilleren: \[C#] A* implementatie versnellen en Bottleneck vinden

[CAPSLOCK2000]

vdvleon schreef op vrijdag 17 juli 2009 @ 01:33:

Ik moet wel zeggen, mijn methode, zoals hij nu is, is niet de snelste route, maar als ik alle mogelijkheden zou langsgaan natuurlijk wel.

Jouw methode kost zo veel rekenwerk dat je hem niet in een spel kan gebruiken. Bij meer dan een handvol punten gaat het zo'n beetje oneindig lang duren. Je kan geen 20 minuten gaan wachten tot de computer een route heeft geplanned.
Gebruik A* dat is de normale oplossing voor dit probleem.

[vdvleon]

Ik ga eerst eens kijken of het op mijn manier kan, en als dat inderdaad te sloom is... dan ga ik eens goed kijken naar A*. Maar je kan wel aardig filteren op mijn manier hoor. Je houd gewoon voor elk gevonden weg bij hoe lang hij is. Als tijdens het zoeken al blijkt dat de route langer is dan de gevonden route dan kapt hij die gewoon af en gaat weer verder totdat hij wel een kortere route heeft gevonden. Totdat hij helemaal klaar is. Dan heeft hij de kortste route. Hopelijk is dit een beetje snel

[Verwijderd]

je kan ook het dead-end fill algoritme gebruiken:

scan de array op zoek naar een "dead end"
dead end gevonden? maak het vakje zwart
herhalen totdat er geen dead ends meer bestaan, het overgebleven pad is de oplossing (kunnen er meer zijn)

[DrClaw]

omdat je een doolhof hebt gebouwd, dat niet verandert terwijl de speler van A naar B aan het lopen is, kun je je snelste pad algoritme bij het genereren van je doolhof al berekenen, en opslaan. Hiervoor kun je het domste algoritme bouwen dat er is, zolang het maar een oplossing geeft. Je berekent het toch vantevoren, en niet realtime.

Voor zover ik kan bedenken, is het dan het makkelijkst om je algoritme gewoon bij het einde te laten beginnen, en dan recursief voor elke buur te zeggen, dat de afstand tot het einde == 1 + de kleinste waarde van zn buren.

Als je dan in het spelletje de speler een hint wil geven, dan kijk je even naar alle buren rondom de player, en kiest daar de richting met het kleinste getal uit.

[vdvleon]

Mijn methode werkt nu goed. In een doolhof gaat het bereken heel snel. Maar in een open landschap met irritante obstakels word de tijd al gauw veel groter.

DrClaw schreef op vrijdag 17 juli 2009 @ 13:42:
omdat je een doolhof hebt gebouwd, dat niet verandert terwijl de speler van A naar B aan het lopen is, kun je je snelste pad algoritme bij het genereren van je doolhof al berekenen, en opslaan. Hiervoor kun je het domste algoritme bouwen dat er is, zolang het maar een oplossing geeft. Je berekent het toch vantevoren, en niet realtime.

Je hebt gelijk, dat zou ik inderdaad kunnen doen.

Ik ga misschien nu dan eens proberen om ook een A* implementatie te maken.

@darkstone

En hoe moet je dat doen met rotondes dan?

code:

 XXXXX
XX   X
   X X
XX   X
 XXXXX

Dit is een dead-end, maar het detecteren is (voor mij) wel lastig

[ Voor 10% gewijzigd door vdvleon op 17-07-2009 16:49 ]

[Verwijderd]

ik geloof dat er ergens een algoritme was om de loops te verwijderen, misschien kan je dat gebruiken

de loops kan je trouwens makkelijk vinden met flood fill

[CAPSLOCK2000]

vdvleon schreef op vrijdag 17 juli 2009 @ 13:08:
Ik ga eerst eens kijken of het op mijn manier kan, en als dat inderdaad te sloom is... dan ga ik eens goed kijken naar A*. Maar je kan wel aardig filteren op mijn manier hoor. Je houd gewoon voor elk gevonden weg bij hoe lang hij is. Als tijdens het zoeken al blijkt dat de route langer is dan de gevonden route dan kapt hij die gewoon af en gaat weer verder totdat hij wel een kortere route heeft gevonden. Totdat hij helemaal klaar is. Dan heeft hij de kortste route. Hopelijk is dit een beetje snel

Als je dat al hebt dan ben je al halverwege je A* implementatie.
Wat je nog moet toevoegen is een (onder)schatting van de afstand naar je doel. De manhattan distance is daar voor heel geschikt.
Vervolgens kijk naar de lengte van de route dusver plus de afstand tot het doel. De route die het kortste is werk je verder uit.

[roy-t]

CAPSLOCK2000 schreef op vrijdag 17 juli 2009 @ 17:54:
[...]


Als je dat al hebt dan ben je al halverwege je A* implementatie.
Wat je nog moet toevoegen is een (onder)schatting van de afstand naar je doel. De manhattan distance is daar voor heel geschikt.
Vervolgens kijk naar de lengte van de route dusver plus de afstand tot het doel. De route die het kortste is werk je verder uit.

Ik snap niet waarom je het wiel opnieuw uit probeert te vinden met een eigen algoritme wat mogelijk werkt maar waarvan niet bewezen is dat het altijd het (op 1 stap na) optimale pad vind. A* is helemaal niet moeilijk met een goed voorbeeld, zie het A* optimaliseren topic wat pas nog is langs geweest, op het einde staat oa deze link: http://royalexander.wordp...sion-a-pathfinding-in-3d/ (mijn blog). Waar ik alle tips uit dat topic aan elkaar knoop voor een snelle C# versie van A*. Deze is vrij makkelijk in C++ te implementeren je hoeft maar wat kleine dingen aan te passen. (Met dank aan veel tweakers hier trouwens).

A* werkt zowel voor doolhoven als open velden en heeft geen last van loops.

Overigens ipv manhattan distance is het vaak beter om Pythagoras te gebruiken als heuristic, Manhattan distance laat alles net ietsjes verder weg lijken en door die bias duurt het soms iets langer om de jiste route te vinden.

Het is beide makkelijk te implementeren
Manhattan: H=deltaX+deltaY
Pythagoras: H^2=deltaX^2+deltaY^2.

Het is trouwens handig om een snel algoritme te hebben wat at runtime even de route kan uitrekenen, omdat je dan ook later geblokeerde routes kunt toevoegen (bijvoorbeeld door een explosie of doordat een speler in die gang staat).

Edit: nu ik mijn post even opnieuw leest klinkt dit niet zo aardig terwijl ik zelf o zo vaak schuldig ben aan dingen opnieuw uit vinden, ik probeer je gewoon te helpen om niet dezelfde fouten te maken die ik al o zo vaak gemaakt heb, aan de andere kant zonder het zelf te proberen en mogelijk fouten te maken zullen mensen nooit snappen waarom ze het anders moeten aanpakken

[ Voor 9% gewijzigd door roy-t op 17-07-2009 19:31 ]

[vdvleon]

No problemo hoor. Ik wou gewoon voor me zelf kijken hoe je dit soort dingen aan pakt programmeer technisch. Ik heb wel een volledig, 100% werkend systeem gemaakt. Maar niet het snelste. Ik weet zeker dat hij altijd de kortste weg vind.

Ik ga denk ik nu ook een PathFinder2 maken, de A* veriant. Kijken of deze het ook goed en vooral sneller werkt.

[JeRa]

@roy-t

Wellicht is de Manhattan distance juist wel de goede heuristic voor A*, aangezien een doolhof vaak over rechte stukken pad gaat en niet zozeer in een rechte lijn tussen hok A en B... qua performance is die natuurlijk ook een stuk beter.

Verder is de keuze voor een path finding algorithm overigens erg afhankelijk van de vorm van je doolhof... (zoals ik al zei in mijn eerdere post). Genereer je de doolhoven automatisch? Zo ja, wat zijn dan de karakteristieken? Algoritmes gebaseerd op Dijkstra proberen meestal de voorkeur te geven op paden die dichter bij het eindpunt liggen, iets wat in een doolhof niets hoeft te betekenen...

[vdvleon]

Ik heb nu een variant gemaakt gebasseerd op A*. Ik heb eigenlijk gewoon bijna direct de pseudo code overschreven van wikipedia en het werkt in 1 keer helemaal goed. Altijd de kortste route. Nu alleen nog eff kijken hoe snel het is en door testen.

[roy-t]

vdvleon schreef op zaterdag 18 juli 2009 @ 05:29:
Ik heb nu een variant gemaakt gebasseerd op A*. Ik heb eigenlijk gewoon bijna direct de pseudo code overschreven van wikipedia en het werkt in 1 keer helemaal goed. Altijd de kortste route. Nu alleen nog eff kijken hoe snel het is en door testen.

Ah ja, dat is dus zeker nog erg veel te versnellen zoals ik dus ook uitvond .

JeRa schreef op vrijdag 17 juli 2009 @ 19:59:
@roy-t

Wellicht is de Manhattan distance juist wel de goede heuristic voor A*, aangezien een doolhof vaak over rechte stukken pad gaat en niet zozeer in een rechte lijn tussen hok A en B... qua performance is die natuurlijk ook een stuk beter.

Verder is de keuze voor een path finding algorithm overigens erg afhankelijk van de vorm van je doolhof... (zoals ik al zei in mijn eerdere post). Genereer je de doolhoven automatisch? Zo ja, wat zijn dan de karakteristieken? Algoritmes gebaseerd op Dijkstra proberen meestal de voorkeur te geven op paden die dichter bij het eindpunt liggen, iets wat in een doolhof niets hoeft te betekenen...

Doh ja, daar had ik helemaal niet aan gedacht voor doolhoven is Manhattan natuurlijk perfect .

[Bozozo]

Ik ben hier zelf mee bezig geweest de afgelopen maanden. Kan het niet laten om even te stoeven: Flash implementatie van A*. Rekentijd minder dan 1 milliseconde, zelfs als de route onmogelijk is en dus alle vakjes moeten worden nagegaan.

Ik ga de broncode alleen niet prijsgeven want er zit best veel werk in. Een paar tips:
- gebruik geen dynamische lists maar maak gewoon de lists zo groot dat je altijd genoeg ruimte hebt (dwz even groot als het aantal nodes).
- leg een onzichtbare rand bezette nodes om de hele kaart heen. Dat is _veel_ sneller dan telkens controleren of een buurcel wel bestaat.
- gebruik een binairy heap voor het bijhouden van de beste score (google!)

Achteraf gezien is het implemeteren van A* best makkelijk. Het uitvoeren van de route, met meerdere bewegende units tegelijk, is veel lastiger.

[vdvleon]

Bozozo schreef op zaterdag 18 juli 2009 @ 14:38:
Ik ga de broncode alleen niet prijsgeven want er zit best veel werk in. Een paar tips:
- gebruik geen dynamische lists maar maak gewoon de lists zo groot dat je altijd genoeg ruimte hebt (dwz even groot als het aantal nodes).
- leg een onzichtbare rand bezette nodes om de hele kaart heen. Dat is _veel_ sneller dan telkens controleren of een buurcel wel bestaat.
- gebruik een binairy heap voor het bijhouden van de beste score (google!)

Bedankt voor de tips. Ik maak nu wel gebruik van dynamische lists. Maar bijv. de f, g en h lists zijn gewoon int**, maar de cameFrom is een std::map<int, vdPoint> (waar bij de int voor de index staat die vanaf de cordinaat samen met de width en height berekend kan worden om het beter sorteer baar te maken. En de Points list, dus de open en closed list zijn wel std::vector<vdPoint>. Kan ik dan beter deze bool* maken ofsow. (Dus de open en closed list samen voegen, en true voor open en false voor closed gebruiken?).

Ik ga anders ook eens een timer functie toe voegen, dan kan ik temisnte kijken hoe lang alles duurt.

En nog een vraagje, is de heuristic en de distance functie eigenlijk niet het zelfde? heuristic berekend toch alleen hemelsbreed de korste weg. Maar dat doet distance toch ook?

C++:

int heuristic(const vdPoint& point1, const vdPoint& point2);
int distance(const vdPoint& point1, const vdPoint& point2);

[ Voor 12% gewijzigd door vdvleon op 18-07-2009 16:04 ]

[Bozozo]

De heuristic is niets anders dan een algoritme dat een lagere waarde moet geven naarmate een node dichter bij het eindpunt ligt. De hemelsbrede afstand is daar een voorbeeld van, evenals de som van het aantal kolommen en rijen dat je nog moet reizen.

Feitelijk is de heuristic de intelligentie van je algoritme. Je kunt ook A* gebruiken om bijvoorbeeld een schaakcomputer te maken, maar dan moet je dus weten of een bepaalde zet je dichter bij de overwinning brengt. En dat is bij schaken een stuk moeilijker dan bij pathfinding

[vdvleon]

Dus je kan je heuristic zo maken dat deze bijv. voor bepaalde velden een moeilike doorlaatbaarheid is, dus een veld met een hogere cost, zodat hij misschien beter via een andere kant kan gaan omdat deze weg makkelijker loopt. Bij wijzen van spreken?

Ik heb btw een testje gedaan met mijn code. Voor een veld van 100 x 100 waar random hokjes dicht zijn, duurt het < 1 sec, gemiddlet ongveer 0,6 sec ofsow. Is dit een slechte score?

De volgende punten heb ik nog niet gedaan:

- leg een onzichtbare rand bezette nodes om de hele kaart heen. Dat is _veel_ sneller dan telkens controleren of een buurcel wel bestaat.
- gebruik een binairy heap voor het bijhouden van de beste score (google!)

edit:

Ik heb nu wel de onzichtbare rand er om heen gezet. Dat doe ik als volgt:

- Ik maak een map aan die 2 extra hoog en breed is
- Ik zet daar in de buitenste rand alles op closed
- Dan copy ik voor elke x,y in de originele map naar de nieuwe map met x=x+1 en y=y+1
- Ik update de x,y voor elke cordinaat (dus start en einde), x=x+1, y=y+1
- Ik zoek de weg (zonder x<0 y<0 etc. controle)
- Op einde update ik de x,y voor de gevonden weg (x=x-1, y=y-1)

Dit werkt gewoon. Maar omdat deze extra stappen zelf al zo veel extra tijd kosten, hebben deze uiteindelijk geen voordeel. Of moet ik bij het 'ontwerpen' van de mappen zelf al rekening houden met die extra rand?

[ Voor 33% gewijzigd door vdvleon op 18-07-2009 18:06 ]

[Bozozo]

vdvleon schreef op zaterdag 18 juli 2009 @ 17:28:
Dus je kan je heuristic zo maken dat deze bijv. voor bepaalde velden een moeilike doorlaatbaarheid is, dus een veld met een hogere cost, zodat hij misschien beter via een andere kant kan gaan omdat deze weg makkelijker loopt. Bij wijzen van spreken?

Het idee is goed ja. Je kunt bijvoorbeeld gras duurder maken dan beton. Je verandert dan wel de cost (meestal g genoemd) en niet de heuristic (h).

Ik heb btw een testje gedaan met mijn code. Voor een veld van 100 x 100 waar random hokjes dicht zijn, duurt het < 1 sec, gemiddlet ongveer 0,6 sec ofsow. Is dit een slechte score?

Ik ben iets sneller in flash, maar niet veel. Maar je moet toch wel een stuk sneller kunnen zijn in C++ hoor. Als je met zo'n groot grid werkt wordt pure A* zoals je merkt nogal traag... in een RTS ofzo moet je dan slimme trucjes gaan toepassen maar voor jou is dat niet zo nodig.

Tot slot, als je geen voordeel haalt uit die extra rand heeft het geen zin om dat te implementeren natuurlijk. Het is wel vreemd, want voor mijn scheelde aanzienlijk.

edit: in jouw geval haal je weinig/geen verbetering omdat je in een doolhof maar 1 keer de route berekent. Als je vaker routes berekent hoef je maar 1 keer het aangepaste array te definiëren.

[ Voor 7% gewijzigd door Bozozo op 18-07-2009 20:33 ]

[Verwijderd]

Ik heb nu wel de onzichtbare rand er om heen gezet. Dat doe ik als volgt:

- Ik maak een map aan die 2 extra hoog en breed is
- Ik zet daar in de buitenste rand alles op closed
- Dan copy ik voor elke x,y in de originele map naar de nieuwe map met x=x+1 en y=y+1
- Ik update de x,y voor elke cordinaat (dus start en einde), x=x+1, y=y+1
- Ik zoek de weg (zonder x<0 y<0 etc. controle)
- Op einde update ik de x,y voor de gevonden weg (x=x-1, y=y-1)

Dit werkt gewoon. Maar omdat deze extra stappen zelf al zo veel extra tijd kosten, hebben deze uiteindelijk geen voordeel. Of moet ik bij het 'ontwerpen' van de mappen zelf al rekening houden met die extra rand?

je hoeft hem maar 1 breder te maken, als je compiler tenminste niet zeurt over het out-of-bounds geraken van de array...

[vdvleon]

"- gebruik een binairy heap voor het bijhouden van de beste score (google!)"

Zou ik hier voor ook de std::priority_queue voor kunnen gebruiken?

[Bozozo]

Dat lijkt me wel ja... lijkt een speciaal data type te zijn voor deze toepassing.

[MSalters]

Waarschijnlijk wel. Bekijk welke operaties je nodig hebt, en kijk of je die kunt mappen op de methods van een priority_queue.

[roy-t]

vdvleon schreef op zondag 19 juli 2009 @ 13:50:
"- gebruik een binairy heap voor het bijhouden van de beste score (google!)"

Zou ik hier voor ook de std::priority_queue voor kunnen gebruiken?

'
Al deze tips stonden ook in het andere topic, plus info waarom je maar 1 list hoefde te gebruiken (je openlist).

Zorg ervoor dat opzoeken of iets in de openlist O(1) is, zoeken of iets in de closedList zit O(1) is (met booleans op de nodes zelf) dat adden van een item naar de openlist O(log n) is en degene met de beste score pakken van de openList ook O(1). Elk datatype dat dat kan is geschikt .

@ TS, verder over die Flash A* code waarvan de bron niet vrijgegeven wordt atm, een precies dezelfde implementatie staat dus gewoon hier op t.net met downloadbare code op mijn blog heb je daar nu naar gekeken? Je zegt alleen dat je de code van wikipedia hebt dus ik neem aan van niet.

[vdvleon]

Ik ben toch afgezien van de priority_queue. Ik heb wel mijn eigen versie gemaakt die de 'lowest f' zoekt zodra er gegevens veranderen . Als het goed is heb ik dit zo efficiënt mogelijk gedaan.

Om een path te vinden in een map van 100x100 waar bij (dmv. een rand functie) als het goed is 1 op de 7 hokjes dicht zijn (willekeurig gekozen natuurlijk), heeft hij daar gemiddeld (100 keer achter elkaar op de zelfde map gezocht) 577.553 ms voor nodig. Dus iets meer als een halve seconden. Is dit een beetje netjes? Of moet ik nog meer optimalizeren.

Ik heb de extra rand er om heen weg gehaald. Ik weet niet hoe het kwam, maar als ik die rand gebruikte werd het juist trager (zelfs als ik het maken van de rand zelf niet mee tel).

edit:

@ roy-t
[quote]Zorg ervoor dat opzoeken of iets in de openlist O(1) is, zoeken of iets in de closedList zit O(1) is (met booleans op de nodes zelf) dat adden van een item naar de openlist O(n log n) is en degene met de beste score pakken van de openList ook O(1). Elk datatype dat dat kan is geschikt .[/quote

Ik heb nog geen informatica gestudeerd (begint toevallig wel over 1,5 maand ofsow ;P ) en weet niet precies waar je het over hebt. Ik toevallig wel op mijn studie 1 keer mee gelopen, en toen hadden ze het hier wel over, maar weet niet meer precies hoe dat zat. Maar het ging over de aantal cycles die de cpu nodig had om dat desbetreffende stukje code uit te voeren (ofsow iets) ?

[ Voor 33% gewijzigd door vdvleon op 19-07-2009 18:20 ]

[roy-t]

vdvleon schreef op zondag 19 juli 2009 @ 17:59:
Ik ben toch afgezien van de priority_queue. Ik heb wel mijn eigen versie gemaakt die de 'lowest f' zoekt zodra er gegevens veranderen . Als het goed is heb ik dit zo efficiënt mogelijk gedaan.

Om een path te vinden in een map van 100x100 waar bij (dmv. een rand functie) als het goed is 1 op de 7 hokjes dicht zijn (willekeurig gekozen natuurlijk), heeft hij daar gemiddeld (100 keer achter elkaar op de zelfde map gezocht) 577.553 ms voor nodig. Dus iets meer als een halve seconden. Is dit een beetje netjes? Of moet ik nog meer optimalizeren.

Ik heb de extra rand er om heen weg gehaald. Ik weet niet hoe het kwam, maar als ik die rand gebruikte werd het juist trager (zelfs als ik het maken van de rand zelf niet mee tel).

edit:

@ roy-t
[quote]Zorg ervoor dat opzoeken of iets in de openlist O(1) is, zoeken of iets in de closedList zit O(1) is (met booleans op de nodes zelf) dat adden van een item naar de openlist O(n log n) is en degene met de beste score pakken van de openList ook O(1). Elk datatype dat dat kan is geschikt .[/quote

Ik heb nog geen informatica gestudeerd (begint toevallig wel over 1,5 maand ofsow ;P ) en weet niet precies waar je het over hebt. Ik toevallig wel op mijn studie 1 keer mee gelopen, en toen hadden ze het hier wel over, maar weet niet meer precies hoe dat zat. Maar het ging over de aantal cycles die de cpu nodig had om dat desbetreffende stukje code uit te voeren (ofsow iets) ?

Het gaat om de tijdscomplexiteit. Als je N items hebt hoe lang duurt het dan om een bepaalde actie over die N items uit te voeren. O(1) betekend dus dat er precies 1 instructie nodig is om iets te vinden. Het sorteren van een array met behulp van bubble sort (2 geneste for lussen) is dus O(n^2) want je moet n^2 items langs om ze te sorteren.

Zorg er dus voor dat de O(..) zo klein mogelijk is voor alle opties, en vooral voor het checken of iets in een lijst zit (omdat je dat per 'beste' tile zo'n 8 keer doet terwijl bijvoorbeeld de laagste score zoeken maar 1x voorkomt per 'beste' tile).

Meer info: Wikipedia: Big O notation

[vdvleon]

Dat zit wel goed. Mijn open/close list werkt gewoon zo:

C++:

char open[s]; // s = width*height van map

open[N] = 0; // closed
open[N] = 1; // open
open[N] = 2; // niet in beide lists

Dus kijken of iets in open list zit is gewoon: if(open[index])
Dus O(1) lijkt mij dan.

Om de lowest f te zoeken kan O(0) zijn of O(s*N) (met s width*height en N de stappen in for loop etc.) ofsow. Namelijk als er niets is verandert met de open list en de f values, dan returned hij gewoon de laatste lowest f value, maar als er iets is verandert met open of een f value, dan word, aan de hand van wat er precies - waar - verandert, bepaald wat de nieuwe lowest f waarde is.

edit:

Om dit pad te vinden: http://vdvleon.xs4all.nl/path.txt (map is 250x250) had hij 23,4 sec nodig. Dit was op een laptop van 2 x 2.0 Ghz. Is dit een beetje een nette tijd? De X'jes stellen muren voor, en de +'jes het pad (duh).

[ Voor 19% gewijzigd door vdvleon op 19-07-2009 19:17 ]

[Bozozo]

Ik heb wel mijn eigen versie gemaakt die de 'lowest f' zoekt zodra er gegevens veranderen .

Als je daarmee bedoelt dat je je array sorteert, dan verspil je veel rekentijd en kun je echt beter naar binairy heaps kijken. Kost even een half uurtje om het concept te begrijpen maar het levert daarna snel resultaat.

[farlane]

roy-t schreef op zondag 19 juli 2009 @ 18:33:
O(1) betekend dus dat er precies 1 instructie nodig is om iets te vinden.

Is het niet meer in de trend van "constante tijd" ? De notatie zegt verder toch niet veel over hoe lang die tijd is of wat er precies gedaan wordt in die tijd.

[vdvleon]

Bozozo schreef op zondag 19 juli 2009 @ 20:28:
[...]

Als je daarmee bedoelt dat je je array sorteert, dan verspil je veel rekentijd en kun je echt beter naar binairy heaps kijken. Kost even een half uurtje om het concept te begrijpen maar het levert daarna snel resultaat.

Ik sorteer de array niet.

C++:

int vdF::lowestFIndex(char* open){
    int i;
    
    // Need sort?
    if(_needSort){
        _needSort = false;
        
        // Find lowest
        _lowest = -1;
        for(i=0; i<_size; i++){
            if(_lowest==-1 && open[i]==1){
                _lowest = i;
            }
            if(open[i]==1 && _f[i]<_f[_lowest]){
                _lowest = i;
            }
        }
    }
    
    return _lowest;
}

Dit zou nog aardig mee vallen verwacht ik. De var _needSort is alleen true als je echt niet zeker bent of er een lagere _lowest (index) beschikbaar is.

C++:

void vdF::update(int index, char* open){
    // Not open anymore?
    if(_lowest==index && open[index]!=1){
        _needSort = true;
        return;
    }
    
    // Lower f?
    if(_f[index]<_f[_lowest]){
        _lowest = index;
        return;
    }
}

Het lijkt mij juist dat dit sneller is dat een kant-en-klare container (met auto sorteer methode). Namelijk die sorteert de hele lijst, deze sorteerd niks, maar zoekt alleen de laagste. (ik kan het fout hebben).

[Nick The Heazk]

farlane schreef op zondag 19 juli 2009 @ 20:32:
Is het niet meer in de trend van "constante tijd" ? De notatie zegt verder toch niet veel over hoe lang die tijd is of wat er precies gedaan wordt in die tijd.

Ja. De grootte-ordenotatie verbergt steeds een constante c (onafhankelijk van de probleemgrootte). Zonder formeel te neuzelen komt het er op neer dat als een algoritme een uitvoeringstijd heeft van O( f(n) ), met f(n) een functie en n de invoergrootte, dan zal het aantal instructies dat in het slechtse geval zal moeten uitgevoerd worden kleiner dan of gelijk zijn aan c * f(n), waarbij n groter is dan een n_0, die ook weer onafhankelijk moet zijn van n.

Edit:

vdvleon schreef op zondag 19 juli 2009 @ 20:36:

C++:

knipperdeknip

Het lijkt mij juist dat dit sneller is dat een kant-en-klare container (met auto sorteer methode). Namelijk die sorteert de hele lijst, deze sorteerd niks, maar zoekt alleen de laagste. (ik kan het fout hebben).

Dit zoeken naar het laagste element vergt relatief veel tijd. Bovendien ga je deze operatie meerdere malen moeten herhalen tijdens het zoeken naar het optimale pad. Deze opmerking werd ook reeds gemaakt in roy-t's topic, waar je ook al naar verwezen werd door Worteltaart; zie onder.

Verwijderd schreef op vrijdag 17 juli 2009 @ 08:36:
Er is laatst een topic over A* langsgekomen, wellicht dat je er nuttige informatie uit kunt destilleren: \[C#] A* implementatie versnellen en Bottleneck vinden

Zoals in dat topic ook werd opgemerkt is de selectie van de datastructuren cruciaal voor een efficiënte implementatie van A* (naast een goede heuristiek natuurlijk). Een heap datastructuur is speciaal ontworpen om efficiënt het element op te vragen met de kleinste waarde, net hetgeen je nodig hebt voor A*. Zelf datastructuren ontwerpen is natuurlijk leuk, evenals een eigen implementatie van een heap. Echter, indien dit niet je doelstelling is, kijk je best naar standaardoplossingen. De STL bibliotheek bied je immers al een make_heap methode e.d. aan.

[ Voor 73% gewijzigd door Nick The Heazk op 19-07-2009 20:53 . Reden: Toevoegingen, spelling ... ]

[vdvleon]

Ok, dan kijk ik eens daar naar.
Ik moet wel eerst eff duidelijk hebben hoe ik dat dan moet gaan toepassen.

Ik heb nu dus (als ik mijn geinproviseerde heap weg haal):

C++:

// === niet originele versie ===

int s = map->getSize().getSurface(); // oppervlakte van map, width *  height
char open[s];
int f[s], g[s], h[s], i, opens, index, endIndex, tmp;

// init
for(i=0; i<s; i++){
    open[i] = 2; // 2 = unused
}
index = start.getIndex(map->getSize()); // y * size.width + x
endIndex = end.getIndex(map->getSize());
open[index] = 1; // 1 = in open list
opens = 1;
g[index] = 0;
f[index] = h[tindex] = heuristic(start, end);

while(opens>0){
    // Find lowest f
    tmp = INT_MAX;
    for(i=0; i<s; i++){
        if(open[i]==1 && f[i]<tmp){
            tmp = f[i];
            index = i;
        }
    }

    // Rest van code
    // ...
}

Ik kan dan wel heel leuk een vector aan maken (en die met heap sorteren). Maar hoe moet ik dit dan indelen.
Namelijk bij het indelen moet er ook gekeken worden of de index van de f waarde in de open array wel 1 is.

Of moet ik zo iets doen:

C++:

struct Item{
    int index;
    int f;
};
std::vector<Item> open;

// En dan de open var dmv van een heap sorteren.

// En voor close
bool closed[s]; // en als je dan wilt kijken of hij in close bestaat:  if(closed[index])

?

[roy-t]

farlane schreef op zondag 19 juli 2009 @ 20:32:
[...]


Is het niet meer in de trend van "constante tijd" ? De notatie zegt verder toch niet veel over hoe lang die tijd is of wat er precies gedaan wordt in die tijd.

Ja dat klopt, ik heb het even krom verteld zie ik nu, instructie moet je ook wat ruimer lezen in dat stuk trouwens.

@TS

Zoals al aangegeven is een heap gewoon veel sneller, waarom? Zonder te sorteren moet je elke iteratie de goedkoopste zoeken door een loop van O(n). (toevoegen is O(1) in dit geval). Als je een heap hebt die sorteert elke keer als je een item toevoegt (en hij instert/sort met een complexiteit van O(log n). is dat een stuk sneller dan O(n), dus de container gesorteerd houden is sneller (let wel dat een Binary heap wat speciale truukjes gebruikt om goed te sorteren).

Verder is je algoritme nog vrij langzaam, ik heb het even getest en over 100 runs in een ruimte van 250x250x1 (waar mijn algo iets minder optimaal is aangezien de 3d checks nu gedaan worden maar niet nodig zijn) Doe ik gemiddeld 194ms (mili seconden, dus 123x sneller ) over het vinden van een pad (nb: heb gewoon random muurtjes laten plaatsen, 1op de 3.33 vakjes was een muurtje). 20 seconden is dan toch best wel langzaam.

Omdat je dat nog steeds niet gedaan hebt wil ik je er toch nog een keer vriendelijk op wijzen om het andere A* topic even door te nemen, veel wordt hier nu gewoon dubbel verteld en dat zou eigenlijk niet nodig moeten zijn .

[vdvleon]

Ok, ik geef toe:P

Ik maak nu ook gebruik van de STL: make_heap, pop_heap, push_heap en sort_heap.

Ik gebruik het zo:
Ik maak gebruik van een appart class die het 'f' gedeelte regelt: vdF.
In deze class bevind zich een variable: int* _f; Deze houd alle 'f values' voor elk cordinaat.
In de class bevind zich ook de variable _lowestF. Dit is een vector die dmv. make_heap, etc. gesorteerd word. Als een f waarde word veranderd en de index van die f waarde (dus bij welke cordinaat deze hoord) nog niet in de _lowestF bevind word deze toegevoegd (en word dus ook push_heap aangeroepen) en word sort_heap aangeroepen. Als je de functie shift aanroept, dan word de laagste f waarde uit de lijst gehaalt (en word pop_heap aangeroepen). Al deze acties zijn niet zo zwaar behalve de sort_heap. Dmv van callgrind ben ik er achtergekomen dat deze 69% van alle tijd in neemt. Hoe los ik dit op? Hoe zorg ik er voor dat als een f value word geweigd dat niet de sort_heap hoeft worden aangeroepen?

[pedorus]

vdvleon schreef op maandag 20 juli 2009 @ 03:22:
Ik maak nu ook gebruik van de STL: make_heap, pop_heap, push_heap en sort_heap.

Ik zou zeggen, gooi alles gewoon weg en begin opnieuw. 10+ seconden, of zelfs 100ms is te veel voor dit probleem gok ik zo, en volgens mij heb je ook echt geen sorteer operaties, of afstands-heuristieken nodig. Ik neem aan dat iedere stap gewoon de manhattan-afstand kost, en dat je steeds vier kanten op kan.

Wat je volgens mij nodig hebt is een 2d-array met waarde -1 oid voor onbezochte nodes, iets anders (zeg -2) voor muren, en een nodenummer (>=0) voor nodes die bezocht zijn. Verder heb je gewoon een lijstje met nodes waar je nu bent ('current'), wat begint met alleen de startnode. Vervolgens ga je hetvolgende schema in:

1. Ga alle buren af van de nodes in current, en kijk of ze op -1 staan in de 2d-array. Indien ja, bezoek ze vanaf deze node door de waarde in de 2d-array te zetten, en voeg ze toe aan next. Als je de eindnode tegenkomt, heb je de snelste route gevonden. De lengte van die route is gelijk aan het aantal keer dat je deze stap hebt doorlopen, maar dat kun je gewoon reconstrueren met de node-nummers in je 2d-array.
2. current:=next. next:=<leeg>. Ga naar 1, behalve als current leeg is, dan is er geen oplossing.

Volgens mij is dit algoritme O(n), met n het aantal vakjes in je doolhof. Zou best kunnen dat dit 'fast-marching' heet of nog een andere mooie naam heeft, maar daarvoor ben ik er niet genoeg in thuis.

[vdvleon]

Lol, dat bedacht ik me zelf ook al. Ik ben nu inderdaad over nieuw begonnen. Eens verder kijken dan de standaart vector en map. Eens kijken naar wat set, etc. zijn.

[pedorus]

vdvleon schreef op maandag 20 juli 2009 @ 05:02:
Lol, dat bedacht ik me zelf ook al. Ik ben nu inderdaad over nieuw begonnen.

Vaak een goed idee.

Eens verder kijken dan de standaart vector en map. Eens kijken naar wat set, etc. zijn.

Ehh, ik zie niet echt in wat set zou kunnen bijdragen. In het algoritme dat ik voorstel zit alleen een simpele (2d-)array, en current & next kunnen waarschijnlijk het beste gewoon vectors zijn.

[Nick The Heazk]

vdvleon schreef op maandag 20 juli 2009 @ 03:22:
Ok, ik geef toe:P

Ik maak nu ook gebruik van de STL: make_heap, pop_heap, push_heap en sort_heap.

Ik gebruik het zo:
Ik maak gebruik van een appart class die het 'f' gedeelte regelt: vdF.
In deze class bevind zich een variable: int* _f; Deze houd alle 'f values' voor elk cordinaat.
In de class bevind zich ook de variable _lowestF. Dit is een vector die dmv. make_heap, etc. gesorteerd word. Als een f waarde word veranderd en de index van die f waarde (dus bij welke cordinaat deze hoord) nog niet in de _lowestF bevind word deze toegevoegd (en word dus ook push_heap aangeroepen) en word sort_heap aangeroepen. Als je de functie shift aanroept, dan word de laagste f waarde uit de lijst gehaalt (en word pop_heap aangeroepen). Al deze acties zijn niet zo zwaar behalve de sort_heap. Dmv van callgrind ben ik er achtergekomen dat deze 69% van alle tijd in neemt. Hoe los ik dit op? Hoe zorg ik er voor dat als een f value word geweigd dat niet de sort_heap hoeft worden aangeroepen?

Waarom zou je sort_heap willen aanroepen . De bedoeling van een heap is net dat het kleinste (of grootste) element op een zeer snelle wijze kan opgevraagd worden. Voor A* ben je helemaal niet geïnteresseerd in een gesorteerde rij, die sort_heap produceert, je wil gewoon het minimum bepalen. Dit minimum bepaal je met pop_heap.

pedorus schreef op maandag 20 juli 2009 @ 04:11:
Ik zou zeggen, gooi alles gewoon weg en begin opnieuw.

Dat zou ik dus niet zeggen. In het vorige topic zijn we ook vertrokken met een uitvoeringstijd die in de grootte-orde lag van een aantal seconden. Bleek dat A* niet correct geïmplementeerd werd; de heuristische afschatting ontbrak. Dit had een enorme impact op de uitvoeringstijd en het algoritme dat jij hieronder gaat beschrijven, verschilt niet veel van roy-t's initiële, incorrecte, algoritme.

10+ seconden, of zelfs 100ms is te veel voor dit probleem gok ik zo, en volgens mij heb je ook echt geen sorteer operaties, of afstands-heuristieken nodig. Ik neem aan dat iedere stap gewoon de manhattan-afstand kost, en dat je steeds vier kanten op kan.

De uitvoeringstijd van de TS is inderdaad aan de hoge kant en heeft inderdaad geen sorteeroperatie nodig. Een afstandsheuristiek is onontbeerlijk indien je problemen wil oplossen die wat groter zijn dan "belachelijk klein". De heuristische afschatting wordt immers gebruikt om een erg groot deel van de zoekruimte uit te kunnen sluiten.

Wat je volgens mij nodig hebt is een 2d-array met waarde -1 oid voor onbezochte nodes, iets anders (zeg -2) voor muren, en een nodenummer (>=0) voor nodes die bezocht zijn. Verder heb je gewoon een lijstje met nodes waar je nu bent ('current'), wat begint met alleen de startnode. Vervolgens ga je hetvolgende schema in:
[...]
Volgens mij is dit algoritme O(n), met n het aantal vakjes in je doolhof. Zou best kunnen dat dit 'fast-marching' heet of nog een andere mooie naam heeft, maar daarvoor ben ik er niet genoeg in thuis.

Breadth-first search is de naam. Zulk een algoritme gebruik je eigenlijk alleen maar ... wel ... eigenlijk is dat algoritme zodanig simplistisch dat je het nergens meer zult tegenkomen. Tenzij alle mogelijke vormen van heuristische afschatting ontbreken. "Zelfs" bij schaken gebruikt men geen breadth-first search, dat is gewoon hopeloos traag. Als je er over nadenkt is het heel logisch dat je geen breadth-first search gebruikt bij schaken; de zoekruimte neem exponentiëel toe en je gaat die volledig ende naïef verkennen met een breadth-first search.

[Bozozo]

Zo'n breadth-first search wordt ook wel Dijkstra's algoritme (D*) genoemd, en is A* met 0 als heuristic voor elke cel. Het betekent simpelweg dat je paden die in de richting van het einddoel leiden geen voorkeur geeft.

Het grappige is dat doolhoven (dus een map waarbij een belachelijke omweg moet worden genomen om het einddoel te bereiken) een van de voornaamste toepassingen zijn van D*, juist omdat je verwacht een omweg te moeten nemen. In het geval van de TS zal een heuristic (of het nou manhattan of pythagoras is) dus weinig toevoegen, of misschien zelfs een beetje vertragen wegens de benodigde rekentijd.

offtopic:
Een andere toepassing van D* is een pad zoeken naar een onbekend einddoel, zoals de dichtstbijzijnde resources voor een harvester.

[Nick The Heazk]

Bozozo schreef op maandag 20 juli 2009 @ 11:28:
Zo'n breadth-first search wordt ook wel Dijkstra's algoritme (D*) genoemd, en is A* met 0 als heuristic voor elke cel. Het betekent simpelweg dat je paden die in de richting van het einddoel leiden geen voorkeur geeft.

Dijkstra's algoritme is geen breadth-first search. Het algoritme van Dijkstra is ook niet gelijk aan D*. A* zonder heuristiek is ook geen breadth-first search. Bij alle voorgenoemde algoritmen ga je voorkeur geven aan knopen met een lagere kost. Bij breadth-first doe je dit niet. Je neemt hier impliciet aan--al is dit niet onlogisch--dat de kost van een stap uniform is. Dit hoeft niet zo te zijn, ook niet in een doolhof-spel. Als de kost van een stap overal uniform is, dan vallen al deze algoritmen inderdaad samen. In het algemeen geldt dat echter niet.

Het grappige is dat doolhoven (dus een map waarbij een belachelijke omweg moet worden genomen om het einddoel te bereiken) een van de voornaamste toepassingen zijn van D*, juist omdat je verwacht een omweg te moeten nemen. In het geval van de TS zal een heuristic (of het nou manhattan of pythagoras is) dus weinig toevoegen, of misschien zelfs een beetje vertragen wegens de benodigde rekentijd.

Als een heuristic niets toevoegt, dan wijst dat eerder op een slechte selectie van de heuristiek. In een doolhof, waarbij er ongeveer even veel bewandelbare vakjes als muren zijn, kun je ook goede heuristieken bedenken.

Ik geef een voorbeeld. De heuristiek van een vakje is gelijk aan het aantal stappen dat je kan nemen zonder ooit een keuze te moeten maken tussen een of meerdere paden. Voor de heuristische waarde van een keuzepunt neem je de Manhattan-afstand. Indien je pad doodloopt neem je als heuristische waarde oneindig. Men gaat eenvoudig na dat dit een admissible heuristiek is.

A* zal alvast nooit meer werk vergen dan een breadth-first search in termen van het aantal knopen dat geïnspecteerd wordt, voorwaar de heuristische afschatting een onderschatting is.

[ Voor 27% gewijzigd door Nick The Heazk op 20-07-2009 12:33 ]

[Janoz]

roy-t schreef op zondag 19 juli 2009 @ 23:41:
Als je een heap hebt die sorteert elke keer als je een item toevoegt (en hij instert/sort met een complexiteit van O(n log n).

O(n log n) is minder efficient dan O(n). Een insert in een heap is echter ook geen O(n log n), maar O(log n), met als bijkomend voordeel dat de tree altijd het efficiëntst gebalanceerd is.

[roy-t]

Janoz schreef op maandag 20 juli 2009 @ 13:41:
[...]


O(n log n) is minder efficient dan O(n). Een insert in een heap is echter ook geen O(n log n), maar O(log n), met als bijkomend voordeel dat de tree altijd het efficiëntst gebalanceerd is.

Damn, je hebt gelijk, ik zal ergens in de war zijn geweest, scherp gezien!

[Bozozo]

Naar aanleiding van dit topic heb ik mijn eigen code nog eens bekeken. Ik heb een indexOf weg kunnen poetsen en wat optimalisaties gedaan (o.a. Math.abs vervangen door een bitwise variant).

Rekentijd teruggebracht tot ~1ms voor mogelijke paden ~10ms voor onmogelijke paden op een map van 96x48.

Flash Pathfinder

Source van de pathfinder: natuurlijk geen javascript maar er is geen actionscript highlighter op got

JavaScript:

// Flash AS3 Pathfinder
// Written by Arno van den Brink
//
// Requires Flash Player 10
// Use as you please

public class PathFinder {

    private var xCells:uint;
    private var yCells:uint;
    private var numCells:uint;
    private var booleanGrid:Vector.<Boolean>;
    private var neighborFinder:Vector.<int> = new Vector.<int>(4,true);
    
    //create a boolean grid of size horizontalCells x verticalCells. True means the cell is occupied (inaccessible)
    public function PathFinder(horizontalCells, verticalCells) {            
        
        this.xCells = horizontalCells+2;
        this.yCells = verticalCells+2;
        this.numCells = this.xCells*this.yCells;
        this.booleanGrid = new Vector.<Boolean>(this.numCells,true);
        
        // this array is used to find neighboring nodes in the A* algorithm.
        // note that it can easily be expanded to 8 members if you want to allow diagonal movement.
        this.neighborFinder = Vector.<int>([-this.xCells,-1,1,this.xCells]);    
        
        // build a ring of inaccessible cells around the map
        for (var i:uint = 0; i < this.xCells; i++) {
            for (var j:uint = 0; j < this.yCells; j++) {
                if (i==0 || i==this.xCells-1 || j==0 || j==this.yCells-1) this.booleanGrid[this.xCells*j+i] = true;
            }
        }
    }
    
    // convert an internal cell number to an external cell number
    private function convertI2E(INr):uint {
        var y:uint = int(INr/this.xCells);
        var x:uint = INr%this.xCells;
        return (y-1)*(this.xCells-2)+x-1;
    }
    
    // convert an external cell number to an internal cell number
    private function convertE2I(ENr):uint {
        var y:uint = int(ENr/(this.xCells-2));
        var x:uint = ENr%(this.xCells-2);
        return (y+1)*this.xCells+x+1;
    }
    
    // get accessibility of a cell (cellNr = external cell nr)
    public function getAccessibility(cellNr:uint):Boolean {
        return !this.booleanGrid[this.convertE2I(cellNr)];
    }
    
    // toggle accessibility of a cell (cellNr = external cell nr)
    public function toggleAccessibility(cellNr:uint):void {
        var IntCellNr:uint = this.convertE2I(cellNr);
        this.booleanGrid[IntCellNr] = !this.booleanGrid[IntCellNr];
    }
    
    // faster replacement of Math.abs()
    private function fastAbs(x:int):uint {
        return (x ^ (x >> 31)) - (x >> 31);
    }
    
    // compute a route from start cell (sc) to target cell (tc) using A*.  (sc and tc both external cell numbers)
    //   returns the route in the form [next cell, cell after that, ..., target cell] in external cell numbers
    public function computeRoute(sc:uint,tc:uint):Vector.<uint> {

        // local variables
        var startCell:uint = convertE2I(sc);                                    // Convert external cell number to internal cell number 
        var targetCell:uint = convertE2I(tc);                                   //   (internal grid contains border of dummy occupied cells)
        var targetX:uint = uint(targetCell%xCells);                             // Cache this (used in heuristic)
        var targetY:uint = uint(targetCell/xCells);                             // Cache this (used in heuristic)        
        var route:Vector.<uint> = new Vector.<uint>;                            // return value
        var gScore:Vector.<Number> = new Vector.<Number>(this.numCells,true);   // cost from start along optimal path
        var hScore:Vector.<Number> = new Vector.<Number>(this.numCells,true);   // minimum cost of remaining path
        var fScore:Vector.<Number> = new Vector.<Number>(this.numCells,true);   // minimum cost of total path
        var closed:Vector.<Boolean> = new Vector.<Boolean>(this.numCells,true); // set to true for evaluated elements to prevent double work
        var cameFrom:Vector.<uint> = new Vector.<uint>(this.numCells,true);     // breadcrumb trail
        var openList:Vector.<uint> = new Vector.<uint>(this.numCells,true);     // binairy heap of nodes to be evaluated, e.g. all encountered neighbors
        var itemsInOpenList:uint = 1;                                           // actual items in the heap
        var bestCell:uint;                                                      // current best guess
        var m:uint;                                                             // heap iterator
        var n:uint;                                                             // heap iterator
        var two_n:uint;                                                         // store 2n as its used so often
        var temp:uint;                                                          // swapping buffer
        var neighborgScore:Number;                                              // reserve memory spot for this often used variable
        
        // initialize heap and heuristics
        openList[1] = startCell;
        hScore[startCell] = heuristic(startCell);
        
        // start algorithm and keep going until all nodes are evaluated. Finding the target will break the loop.
        while(itemsInOpenList > 0) {
            
            // get next best guess from start of binairy heap and return route if its the target
            bestCell = openList[1];
            if (bestCell == targetCell)
                return retraceRoute();

            // move current cell to closed list ("I've been completely evaluated")
            closed[bestCell] = true;
            
            // Manage binairy heap:
            //  - Copy last item to front (overwriting the first item, which is currently in use as bestCell)
            //  - Sink new first item into the heap
            //  - Decrease virtual length of the heap by one (virtually popping original last item)
            openList[1] = openList[itemsInOpenList];
            itemsInOpenList--;
            m = 1;
            n = 2;
            while(n!=m) {
                n = m;
                two_n = n << 1; //bitshifting equals multiplication by 2 but is somewhat faster
                if (two_n + 1 <= itemsInOpenList) {
                    if (fScore[openList[n]] >= fScore[openList[two_n]])
                        m = two_n;
                    if (fScore[openList[m]] >= fScore[openList[two_n+1]])
                        m = two_n+1;
                }
                else if (two_n <= itemsInOpenList && fScore[openList[n]] >= fScore[openList[two_n]])
                    m = two_n;
                if (n!=m) {
                    temp = openList[n];
                    openList[n] = openList[m];
                    openList[m] = temp;
                }
            }
            
            // Evaluate neighbors of bestCell: find their g, h and f scores and place them on the open list
            for (var i:uint = 0; i < 4; i++) {
                
                // use precalculated list to find neighbors: neighborFinder is Vector.<int>([-this.xCells,-1,1,this.xCells]), using internal grid
                var neighborCell:uint = bestCell + neighborFinder[i];
                
                // skip cell if its occupied or already evaluated
                if (this.booleanGrid[neighborCell] || closed[neighborCell]) continue;
                
                // neighbor costs one extra move
                neighborgScore = gScore[bestCell] + 1;
                
                // if neighbor has no calculated heuristic score is must be completely new,
                //   so add it to the open list and calculate its heuristic.
                // Also add it to the binairy heap and bubble it up in a moment
                if (hScore[neighborCell] == 0) {
                    itemsInOpenList++;
                    openList[itemsInOpenList] = neighborCell;
                    m = itemsInOpenList;
                    hScore[neighborCell] = heuristic(neighborCell);
                }
                // if neighbor is not new, but current route to it is faster than old route,
                // bubble it up in the binairy heap
                else if (neighborgScore < gScore[neighborCell]) {
                    m = openList.indexOf(neighborCell);
                }
                // else: neighbor is old, and a quicker route to it had already been evaluated
                else
                    continue
                
                // calculated scores of new cell, and update the breadcrumb trail
                gScore[neighborCell] = neighborgScore;
                fScore[neighborCell] = gScore[neighborCell] + hScore[neighborCell];
                cameFrom[neighborCell] = bestCell;
                
                // bubble up neighbor in binairy heap
                while (m!=1) {
                    n = m >> 1; // a bit faster than n = int(m/2)
                    if (fScore[openList[m]] <= fScore[openList[n]]) {
                        temp = openList[n];
                        openList[n] = openList[m];
                        openList[m] = temp;
                    }
                    m = n;
                }
            }
        }
        
        // if the program ends up here, all options are exhausted.
        // Find closest reacheable cell instead. That's the cell with the lowest heuristic,
        //              and the lowest cost in case of multiple items of the  same heuristic.
        bestCell = startCell;
        for (var b:uint = 0; b < numCells; b++) {
            if(hScore[b]!=0 && hScore[b] <= hScore[bestCell])
                if (hScore[b] == hScore[bestCell]) {
                    if (gScore[b] < gScore[bestCell])
                        bestCell = b
                }
                else
                    bestCell = b;
        }
        
        // Return route to closest reachable cell to target, or an empty route if no movement is needed
        if (bestCell != startCell) 
            return retraceRoute();
        else
            return route;
        
        // Heuristic function: Manhatten distance. fastAbs is the bitshift alternative to Math.Abs, and is a lot faster in AS3
        function heuristic(cellNr):Number {
            return fastAbs(targetX - cellNr%xCells) + fastAbs(targetY - int(cellNr/xCells));
        }
        
        // Retrace breadcrumb trail to construct route. Convert cell numbers back to external grid (without surroundig border of occupied cells).
        function retraceRoute():Vector.<uint> {
            while(bestCell!=startCell) {
                route.unshift(convertI2E(bestCell));
                bestCell = cameFrom[bestCell];
            }
            return route;
        }
    }       
}

edit:
Source toch maar gegeven... misschien heeft iemand er iets aan.

[ Voor 123% gewijzigd door Bozozo op 20-07-2009 20:02 ]

[pedorus]

Nick The Heazk schreef op maandag 20 juli 2009 @ 10:20:
Dat zou ik dus niet zeggen. In het vorige topic zijn we ook vertrokken met een uitvoeringstijd die in de grootte-orde lag van een aantal seconden. Bleek dat A* niet correct geïmplementeerd werd; de heuristische afschatting ontbrak. Dit had een enorme impact op de uitvoeringstijd en het algoritme dat jij hieronder gaat beschrijven, verschilt niet veel van roy-t's initiële, incorrecte, algoritme.

Het grootste probleem zat toen in het gebruik van verkeerde datastructuren en het 'handmatig' daarin zoeken van nodes, waardoor een O(nlog(n)) probleem O(n^2) of zelfs slechter werd. Het algoritme dat ik voorstel is O(n), dus dat lijkt me onvergelijkbaar. Het is in principe exact hetzelfde als het normale geadapteerde Dijkstra algoritme dat meestal met een Fibonacci heap of Binary heap wordt gedaan. Enkel in dit geval zul je nodes met maximaal 2 waardes in je heap hebben zitten, dus daar kan op worden geoptimaliseerd.

Bij een goed doolhof heeft A* natuurlijk totaal geen zin, zoals Bozozo al terecht opmerkt. En dat plain A* nooit meer werk zal vergen, zoals Nick opmerkt, is simpelweg niet waar, aangezien de heuristische functie evalueren gewoonweg tijd kost, waardoor het evalueren van nodes veel meer tijd kost. Daarnaast zorgt die heuristiek er voor dat je meer dan 2 verschillende waardes in je heap hebt zitten, waardoor je al snel een normale heap nodig hebt die tenminste 1 operatie O(log(n)) heeft, ipv een voor alle benodigde operaties O(1) heap, zoals ik die hier voorstel (O(1) amortized time ivm eventueel vergroten van vector, wat meestal niet nodig zal zijn in een doolhof). Random x% vakjes bezetten is trouwens ook iets heel anders dan een echt doolhof; in dit geval zou ik wel voor iets als A* gaan, ja...

[vdvleon]

Ik heb nu mijn eigen heap implementatie af. Kijken of ik nu mijn path finder eromheen kan bouwen, en hopelijk nu wel goed en snel. Volgens mij ga ik nu de goede kant op.

Alleen vraag ik mij af, hoe kan je dmv van een template en compare functie mee geven.

dus:

C++:

class Comp{
    public:
        bool operator()(const vdTile& a, const vdTile& b){
            return a < b;
        }
};

template<class Comparator> class vdTileHeap{
    private:
        Comparator comp;

        // ...
};

vdTileHeap<Comp> heap;
heap.insert(a tile);
heap.insert(a second tile); // etc.

fout: there are no arguments to ‘comp’ that depend on a template parameter, so a declaration of ‘comp’ must be available

[ Voor 63% gewijzigd door vdvleon op 20-07-2009 16:25 ]

[vdvleon]

Ik heb hem werken hoor, eindelijk.

Even wat gegevens:

Map: 400 x 400
Clipping: aan (dus mag diagonaal, dus gebruik sqrt)
Gemiddelde tijd: 42.477 ms (eerste 10 keer ongeveer ~ 90ms, de rest ~35 ms)

Resultaat: http://vdvleon.xs4all.nl/map400.txt

Persoonlijk lijkt mij dit niet heel slecht.

Gebruik nu mijn eigen 'heap' systeem:

C++:

class vdTileHeap{
    private:
        typedef std::vector<vdTile> Tiles;
        Tiles _heap;
        
        bool compare(const vdTile& l, const vdTile& r);
        
    public:
        void insert(const vdTile& tile);
        vdTile remove(const vdTile& tile) throw(vdException);
        vdTile shift();
        int size() const;
        bool empty() const;
};

// Insert:
void vdTileHeap::insert(const vdTile& tile){
    Tiles::iterator item, it;
    vdTile tmp;

    // Add at bottom
    item = _heap.insert(_heap.begin(), tile);

    // Find position
    for(it=item+1; it!=_heap.end(); it++){
        // Swap?
        if(compare(*item, *it)){
            tmp = *item;
            *item = *it;
            *it = tmp;
            item = it;
        }else{
            break;
        }
    }
}

Ik kan vast nog wat dingen optimalizeren, Dus ik ben nog even bezig

[Bozozo]

Dat is inderdaad niet slecht.

Je hebt wel door dat je geen echte binairy heap gebruikt? Probeer het als je zin hebt eens echt te implementeren (zie voor een voorbeeld Google of in mijn code regel 104-128) en kijk eens hoeveel winst je haalt?

[roy-t]

vdvleon schreef op maandag 20 juli 2009 @ 19:27:
Ik heb hem werken hoor, eindelijk.

Even wat gegevens:

Map: 400 x 400
Clipping: aan (dus mag diagonaal, dus gebruik sqrt)
Gemiddelde tijd: 42.477 ms (eerste 10 keer ongeveer ~ 90ms, de rest ~35 ms)

Resultaat: http://vdvleon.xs4all.nl/map400.txt

Persoonlijk lijkt mij dit niet heel slecht.

Gebruik nu mijn eigen 'heap' systeem:

C++:

class vdTileHeap{
    private:
        typedef std::vector<vdTile> Tiles;
        Tiles _heap;
        
        bool compare(const vdTile& l, const vdTile& r);
        
    public:
        void insert(const vdTile& tile);
        vdTile remove(const vdTile& tile) throw(vdException);
        vdTile shift();
        int size() const;
        bool empty() const;
};

// Insert:
void vdTileHeap::insert(const vdTile& tile){
    Tiles::iterator item, it;
    vdTile tmp;

    // Add at bottom
    item = _heap.insert(_heap.begin(), tile);

    // Find position
    for(it=item+1; it!=_heap.end(); it++){
        // Swap?
        if(compare(*item, *it)){
            tmp = *item;
            *item = *it;
            *it = tmp;
            item = it;
        }else{
            break;
        }
    }
}

Ik kan vast nog wat dingen optimalizeren, Dus ik ben nog even bezig

Oeh prima die is sneller dan de mijne now we're getting somewhere!

[pedorus]

vdvleon schreef op maandag 20 juli 2009 @ 19:27:
Ik heb hem werken hoor, eindelijk.

Even wat gegevens:

Map: 400 x 400
Clipping: aan (dus mag diagonaal, dus gebruik sqrt)
Gemiddelde tijd: 42.477 ms (eerste 10 keer ongeveer ~ 90ms, de rest ~35 ms)

Resultaat: http://vdvleon.xs4all.nl/map400.txt

Als diagonaal ook mag krijg je natuurlijk een andersoortig probleem Maar zie ik nu rechtsonder vrij duidelijk een omweg en klopt er dus iets niet?

[vdvleon]

Ja, inderdaad. Het lijkt wel of hij eerst helemaal de zelfde x waarde wilt hebben, en dan pas om laag gaat ofsow. Ik zou niet weten hoe ik dat moet oplossen.

[pedorus]

Nou ja, schuin naar rechtsonder doe je ook een soort paardesprongen, ipv dat je schuin gaat...

Als dit met A* is, dan kun je bij het testen de heuristische functie ook eens op 0 zetten. (Als je zo de hele map over gaat, levert A* ook niet eens zo heel veel voordeel op, hooguit zo'n factor 2 denk ik doordat je nu schuin kan, en alleen maar een vertraging bij manhattan-afstanden)

[Bozozo]

Op dit soort relatief open maps durf ik wel te zeggen dat de heuristic iets toevoegt hoor.

Over de omweg; heb je de cost van een schuine neighbor wel op sqrt(2) gezet?

[Hydra]

YopY schreef op vrijdag 17 juli 2009 @ 01:31:
Je huidige opzet klinkt inderdaad veel als Dijkstra. Een iets optimalere methode zou de eerder genoemde A* zijn.

Niet in het geval van een doolhof. Het voordeel van A* is dat je bij een correcte implementatie een voorkeur hebt voor de juiste richting. Je zoekt dus de juiste kant op. En dat gaat je niet lukken met een doolhof. Gewoon een flood-fill werkt dan eigenlijk 't beste.

Edit: spuit 11.

[Deikke]

Ik weet niet wat sneller zou zijn in een doolhof, aangezien je zowel bij flood fill als a* over precies dezelfde nodes zal moeten komen, en dus in beide gevallen de verkeerde route zowieso zal nemen. Dijkstra's algoritme zou de kortste route op moeten leveren, maar a* zou het snelste de route vinden. (Lees: even snel of sneller dan Dijkstra)

Een optie is ook om de heuristic lichter mee te tellen dan de al afgelegde route (onderschatten), hierdoor geef je de voorkeur weer aan nodes die dichter bij de bron liggen.

[ Voor 5% gewijzigd door Deikke op 21-07-2009 12:19 . Reden: Niet overschatten, maar onderschatten. ]

[Bozozo]

Deikke schreef op dinsdag 21 juli 2009 @ 11:55:
[...] Dijkstra's algoritme zou de kortste route op moeten leveren, maar a* zou het snelste de route vinden. (Lees: even snel of sneller dan Dijkstra) [...]

A* zal het minste nodes evalueren. Of dat ook sneller is hangt helemaal af van de rekentijd die wordt verbruikt door de heuristic.

Ik vermoed dat A* sneller is in kleine doolhoven, en D* in grote. Stel dat je van de linksonder naar rechtsboven moet navigeren in een doolhof van grootte lxb. Er moeten uiteindelijk l+b meer stappen naar rechts of naar boven worden gezet dan naar links of naar beneden om het einddoel te bereiken. Tijdens deze stappen zorgt A* ervoor dat je minder nodes hoeft te evalueren, omdat het de voorkeursrichting (rechts of boven) eerst onderzoekt. Echter, naarmate het doolhof groter wordt schaalt het aantal nodes met l*b zodat het aantal bespaarde nodes (evenredig met l+b) relatief kleiner wordt. De extra rekentijd die de heuristic van A* vergt zal dan gaan domineren over de rekentijd die wordt bespaard door minder nodes te bezoeken, zodat D* goedkoper wordt.

[Nick The Heazk]

pedorus schreef op maandag 20 juli 2009 @ 16:06:
Het grootste probleem zat toen in het gebruik van verkeerde datastructuren en het 'handmatig' daarin zoeken van nodes, waardoor een O(nlog(n)) probleem O(n^2) of zelfs slechter werd. Het algoritme dat ik voorstel is O(n), dus dat lijkt me onvergelijkbaar.

De tijdscomplexiteit van A* is sterk afhankelijk van de gekozen heuristiek. Het aantal knopen dat A* zal inspecteren ten opzichte van breadth-first ligt over het algemeen veel lager. Ik denk niet dat je zomaar kan stellen dat beiden onvergelijkbaar zijn. Een zorgvuldig geïmplementeerde A* heeft immers maar O(log n) bewerkingen nodig om het minimum op te halen (Fibonacci heap) en maar O(1) nodig om te bepalen of een knoop al bezocht werd of niet (hashtabel).

Bij een goed doolhof heeft A* natuurlijk totaal geen zin, zoals Bozozo al terecht opmerkt.

Dat zou ik niet zo stellig durven beweren. Een goede doolhof stel je gewoon voor door een grafe. Voor elke bewandelbare tegel introduceer je een knoop. Vervolgens heb je weer een gewone zoekboom waarin A* weer rustig zijn ding kan doen. De algemene eigenschappen van zoekalgoritmes blijven hier van toepassing. Indien je doolhof niet veel opsplitsingen bevat (waar er meerdere paden samenkomen), dan kan A* misschien wel een overkill zijn. Een gewone breadth-first search, zoals jij die voorstelt, zal dan waarschijnlijk wel efficiënter werken.

De moeilijkheid voor het gebruik van A* in een echte doolhof ligt hem in de keuze van een geschikte heuristiek. Zoals door jou al werd aangedragen is een Manhattan-afstand niet noodzakelijk een geschikte heuristiek. Daar geef ik je gelijk in. Echter, men lijkt hier te vergeten dat er verschillende heuristieken mogelijk zijn. De uitdaging ligt erin om een goede en eenvoudig te berekenen heuristiek te verzinnen voor een doolhof spel. De heuristiek die ik eerder voorstelde zou een startpunt kunnen zijn. Zelf heb ik totaal geen idee hoe deze heuristiek het er vanaf zou brengen in een echte doolhof.

En dat plain A* nooit meer werk zal vergen, zoals Nick opmerkt, is simpelweg niet waar, aangezien de heuristische functie evalueren gewoonweg tijd kost, waardoor het evalueren van nodes veel meer tijd kost.

Mijn formulering is inderdaad te ambigu. Ik bedoelde dat A* nooit meer knopen zal inspecteren dan breadth-first search op dezelfde grafe, voorwaar de heuristiek admissible is. Over de rekentijd heb ik me niet uitgesproken.

Daarnaast zorgt die heuristiek er voor dat je meer dan 2 verschillende waardes in je heap hebt zitten, waardoor je al snel een normale heap nodig hebt die tenminste 1 operatie O(log(n)) heeft, ipv een voor alle benodigde operaties O(1) heap, zoals ik die hier voorstel (O(1) amortized time ivm eventueel vergroten van vector, wat meestal niet nodig zal zijn in een doolhof).

Zou je dat eens kunnen toelichten?

Random x% vakjes bezetten is trouwens ook iets heel anders dan een echt doolhof; in dit geval zou ik wel voor iets als A* gaan, ja...

Dat klopt. Ik zou voor beiden A* gebruiken, maar met verschillende heuristieken. Jij zou twee verschillende algoritmes gebruiken (een voor random en een voor een "echte"). Mogelijk is het jouwe sneller op een echte doolhof. Ik zal echter minder werk hebben om m'n doolhofspelletje aan te passen naar verschillende soorten tegels en verschillende topologiën. Zo zijn er altijd wel afwegingen te maken .

[vdvleon]

Hij werkt nu goed, maar af en toe gebeuren er nog wel rare dingen:

code:

     X +   X  X XX      
  X  X +X    X  X            
X     X +   X    X X    
       X +++            
 X       X+X+    X      
 X       XXX+XX         
   X X       +  X  X

Ik denk dat hij daar, op regel 4, eerst 1 naar rechts gaat, dan diagonaal naar beneden, weer recht omhoog, en 1 naar rechts, en weer verder. Maar waarom doet hij dit, en hoe los ik het op?

De cost bereken ik zo:

C++:

// Cost
cost = 5;
if(_clipping && tileA.x!=tileB.x && tileA.y!=tileB.y){ // Kijkt of diagonaal is
    cost = 7;
}

Voor de heuristic:

C++:

if(_clipping){
    long x = abs(point2.x-point1.x);
    long y = abs(point2.y-point1.y);
    return (long)ceil(sqrt(x*x + y*y)*10.0);
}
return (abs(point2.x-point1.x) + abs(point2.y-point1.y))*5; // no diagonal

Ik gebruik eigenlijk voor de cost van een diagonaal 1.4, maar omdat ik met hele getallen werk heb ik voor cost=1 5 genomen, en voor cost=1.4 7. (7/5 = 1.4). Omdat zeker wil weten dat de heuristic buiten deze cost range blijft is deze maal 10 (bij _clipping) en omdat, als clipping uit staat, de cost toch 5 is, maal 5 bij no clipping.

[pedorus]

Nick The Heazk schreef op dinsdag 21 juli 2009 @ 15:05:
De tijdscomplexiteit van A* is sterk afhankelijk van de gekozen heuristiek.

Klopt, enkel jammer dat er vaak niet zo veel keuzes zijn, zeker niet bij manhattan-afstanden. Soms zijn verbeteringen mogelijk door van te voren dingen te berekenen, bijvoorbeeld dmv de driehoeksongelijkheid, maar dat zie ik hier niet direct.

Het aantal knopen dat A* zal inspecteren ten opzichte van breadth-first ligt over het algemeen veel lager.

Bij manhattan-afstanden en het van linksboven naar rechtsonder doorlopen van een lege 2d-grid zul je in beide gevallen (bijna) alle nodes inspecteren. Dijkstra zal dan sneller zijn dan A* (bij gelijke implementatie-vaardigheden).

Zou je dat eens kunnen toelichten?

Een Fibonacci heap is O(log n) voor bepaalde operaties. Een heap die simpelweg bestaat uit 2 single linked lists, voor maximaal 2 waardes die voorkomen is O(1) voor alle hier gebruikte operaties. Nadeel daarvan is enkel dat je dus nodes met maximaal 2 verschillende waardes erin kan hebben.

Ik zal echter minder werk hebben om m'n doolhofspelletje aan te passen naar verschillende soorten tegels en verschillende topologiën. Zo zijn er altijd wel afwegingen te maken .

Hou er rekening mee dat ik hier al goede een A*-implementatie, een Fibonacci heap en een binary heap heb liggen die ik enkel even hoef aan te passen (kan helaas niet sharen ivm copyright). Vervolgens is mijn voorstel voor bij Manhattan-afstanden inderdaad een (behoorlijke) aanpassing daarvan, waarschijnlijk maak ik die dan zelfs even helemaal apart, maar zoveel werk is dat echt niet.

vdvleon schreef op dinsdag 21 juli 2009 @ 16:39:
Ik denk dat hij daar, op regel 4, eerst 1 naar rechts gaat, dan diagonaal naar beneden, weer recht omhoog, en 1 naar rechts, en weer verder. Maar waarom doet hij dit, en hoe los ik het op?

Glazen bol is stuk Misschien dat je de oude reisafstand tot de huide node niet meeneemt, en/of een bepaalde evaluatievolgorde gebruikt waardoor je dit krijgt?

Ik gebruik eigenlijk voor de cost van een diagonaal 1.4, maar omdat ik met hele getallen werk heb ik voor cost=1 5 genomen, en voor cost=1.4 7. (7/5 = 1.4). Omdat zeker wil weten dat de heuristic buiten deze cost range blijft is deze maal 10 (bij _clipping) en omdat, als clipping uit staat, de cost toch 5 is, maal 5 bij no clipping.

Waarom niet gewoon doubles? En waarom niet gewoon een cost van 1 bij geen clipping?

[Bozozo]

vdvleon schreef op dinsdag 21 juli 2009 @ 16:39:
Hij werkt nu goed, maar af en toe gebeuren er nog wel rare dingen:

code:

     X +   X  X XX      
  X  X +X    X  X            
X     X +   X    X X    
       X +++            
 X       X+X+    X      
 X       XXX+XX         
   X X       +  X  X

Ik denk dat hij daar, op regel 4, eerst 1 naar rechts gaat, dan diagonaal naar beneden, weer recht omhoog, en 1 naar rechts, en weer verder. Maar waarom doet hij dit, en hoe los ik het op? [...]

Dat is wel een serieuze fout hoor. Als je een nieuwe buurman vindt zijn er vier opties:
1. Node is bezet --> overslaan
2. Node is zelf al eens uitgeprobeerd als 'beste optie' (hij staat op de closed list) --> overslaan
3. Node is al eens geïdentificeerd als buurman tijdens een vorig pad, maar niet uitgeprobeerd als beste optie (hij staat op de open list) --> overslaan, tenzij het huidige pad sneller is dan het vorige pad (lagere cost). In dit geval de oude cost overschrijven met de nieuwe, en de node navenant verschuiven in de open list.
4. Node is niet bezet en volkomen nieuw --> toevoegen aan de open list

Ik vermoed dat je optie 3 vergeet. Deze mogelijkheid is trouwens de reden dat je de gScore (totale cost vanaf startpunt) van elke node moet onthouden. Volgens mij beweerde iemand in dit topic dat dat niet hoeft, maar dat klopt dus niet.

[ Voor 3% gewijzigd door Bozozo op 21-07-2009 18:03 ]

[vdvleon]

Ik heb alles overnieuw gemaakt in Flash (AS3).
Ik heb dit hem dit keer wat dynamischer gemaakt, zodat je hem makkelijk kan uitbreiden.

Even vooraf: (pseudo code)

code:

Point{
  x,
  y
}
Tile : Point{
  g,
  h,
  f
}
Neighbor : Point{
  cost
}

Voor het A* systeem gebruik ik dit:

• Initializeer (open list /closed list, etc.). open is een binary heap met Tile's (tile is een Point (x,y) plus een f, g en h waarde)
• Voeg start toe aan open
• Loop zolang als open niet leeg is:
  • Haal tile uit open (dus tile met laagste f waarde) en plaats in hem closed
  • Kijk of tile == end, zo ja, stop, bereken path (reconstruct dmv. cameFrom) en geef path terug
  • Voor elke buur (buur functie berekent ook cost):
    • In closed? ignore
    • Bereken g: g = tile.g + neighbor.cost
    • Kijk of hij in open list zit:
      
      
      zo ja en g < neighbor.g:
      neighbor.g = g
      
      
      zo nee:
      neighbox.g = g en voeg toe aan open
      
      
      
      Voor beide situaties word aan het einde opgeslagen: cameFrom[neighbor] = tile
      
      Als de g waarde van een tile word geupdate word automatisch de f waarde geupdate dmv f = g + h

Om de buren op te halen gebruik ik dit:

JavaScript:

// Normal directions
neighbors.push(new Neighbor(point.x-1, point.y, 1)); // left
neighbors.push(new Neighbor(point.x+1, point.y, 1)); // right
neighbors.push(new Neighbor(point.x, point.y-1, 1)); // down
neighbors.push(new Neighbor(point.x, point.y+1, 1)); // up

// Diagonal directions
neighbors.push(new Neighbor(point.x-1, point.y-1, 1.42)); // left up
neighbors.push(new Neighbor(point.x+1, point.y-1, 1.42)); // right up
neighbors.push(new Neighbor(point.x-1, point.y+1, 1.42)); // left down
neighbors.push(new Neighbor(point.x+1, point.y+1, 1.42)); // right down

// Voor Neighbor is het eerste argument x, 2e y, en 3e cost

Deze neighbors worden gefiltert dmv van:

JavaScript:

// Check if valid
for(i=0; i<neighbors.length; i++){
    if(map.getAtPoint(neighbors[i])==Map.Open){
        result.push(neighbors[i]);
    }
}

Als een Tile word aangemaakt word aan het begin de h berekent:

JavaScript:

// Heuristic: (manhattan)
return abs(_end.x-point.x) + abs(_end.y-point.y);

Ik weet niet of ik iets fout doe, maar er gebeurd dit:
http://vdvleon.xs4all.nl/pathfinder.png

Wat doe ik fout

[Verwijderd]

vdvleon schreef op woensdag 22 juli 2009 @ 03:55:
Als een Tile word aangemaakt word aan het begin de h berekent:

JavaScript:

// Heuristic: (manhattan)
return abs(_end.x-point.x) + abs(_end.y-point.y);

Ik weet niet of ik iets fout doe, maar er gebeurd dit:
http://vdvleon.xs4all.nl/pathfinder.png

Wat doe ik fout

Je heuristic klopt niet. Voor A* moet de heuristic altijd te laag (of precies goed) zijn, in jouw geval is je heuristic hoger dan de minimale afstand. Stel je moet van 0,0 naar 5,5, jou heuristic geeft dan 10 aan terwijl de minimale afstand 5*1.42 (met jouw sqrt(2) gerekend) is, wat neerkomt op +- 9. Je heuristic zal dus ongeveer dit moeten zijn:

JavaScript:

var diagonal = min(abs(_end.x - point.x), abs(_end.y - point.y));
var straight = max(abs(_end.x - point.x), abs(_end.y - point.y)) - diagonal;
return diagonal * 1.42 + straight;

[Bozozo]

Ik ben heel benieuwd naar de snelheid van jouw implementatie. Als je met objecten gaat werken en dynamische arrays dan vertraagt de boel (vermoed ik) enorm tov mijn algoritme. Maar doe wat je niet laten kunt

[roy-t]

pedorus schreef op dinsdag 21 juli 2009 @ 17:05:
[...]
Waarom niet gewoon doubles? En waarom niet gewoon een cost van 1 bij geen clipping?

Waarom doubles als alle scores *10 of 100 het op integers houd, dat rekent voor de CPU veel sneller . (Of houd als je pythagoras gebruikt alles gewoon in kwadraten dat is nog makkelijker).


Verder, waarom heb je het nu opnieuw geschreven in AS3? Er was niets mis met je C++ implementatie, waarschijnlijk eventjes nog wat aanpassen en het had gewerkt.

Als het een heuristiek probleem is probeer dan eens Pythagoras (C^2=A^2+B^2).

[vdvleon]

Ik ben ook in AS3 begonnen zodat ik het beter kan toepassen (in een game ofsow) en omdat je dat wat makkelijker het resultaat dynamisch kan tonen.

Ik ben een echte OOP fan , maar misschien moet ik eens kijken of ik alles kan omschrijven.

En ik gebruik geen dynamische arrays.

JavaScript:

var inOpen:Vector.<Boolean> = new Vector.<Boolean>(size, true); // dus maak een array van type boolean aan die de grote size heeft en die fixed is.

Maar je hebt trouwens gelijk, ik heb voor de heap wel een dynamische array Dat moet ik nog even zo aanpassen dat hij fixed is en dan maar een apparte length var aanmaken.

[Bozozo]

Vergeet niet dat je het eerste item op heap[1] moet zetten en niet op heap[0]. Anders gaat het sinken / bubblen van items verkeerd.

edit: oh en een inOpen list heeft geen zin. hScore == 0 geeft je hetzelfde resultaat.

[ Voor 25% gewijzigd door Bozozo op 22-07-2009 15:15 ]

[pedorus]

roy-t schreef op woensdag 22 juli 2009 @ 12:30:
Waarom doubles als alle scores *10 of 100 het op integers houd, dat rekent voor de CPU veel sneller . (Of houd als je pythagoras gebruikt alles gewoon in kwadraten dat is nog makkelijker).

Iets met "premature optimization is the root of all evil". Waarschijnlijk ook grotendeels achterhaald trouwens, doubles zijn steeds sneller gaan werken. Ik snap trouwens ook niet waarom je 1.42 zou gebruiken ipv echt sqrt(2).

Ik ben het wel eens met Bobozo dat zeer veel objecten gebruiken weer een beetje het andere uiterste is. Maar goed, ik ben niet bekend met de snelheid van objecten in AS3, misschien is het snel zat.

[vdvleon]

Bozozo schreef op woensdag 22 juli 2009 @ 15:14:
edit: oh en een inOpen list heeft geen zin. hScore == 0 geeft je hetzelfde resultaat.

Ik sla de h score op in de tile objects zelf. Dus dat heeft in mijn geval alleen maar snelheid's verlies omdat hij dat steeds in de open list moet gaan zoeken naar die desbetreffende tile.

En over die _heap[1] voor eerste gebruiken had ik al rekening mee gehouden:P

Verwijderd schreef op woensdag 22 juli 2009 @ 09:37:
[...]

Je heuristic klopt niet. Voor A* moet de heuristic altijd te laag (of precies goed) zijn, in jouw geval is je heuristic hoger dan de minimale afstand. Stel je moet van 0,0 naar 5,5, jou heuristic geeft dan 10 aan terwijl de minimale afstand 5*1.42 (met jouw sqrt(2) gerekend) is, wat neerkomt op +- 9. Je heuristic zal dus ongeveer dit moeten zijn:

JavaScript:

var diagonal = min(abs(_end.x - point.x), abs(_end.y - point.y));
var straight = max(abs(_end.x - point.x), abs(_end.y - point.y)) - diagonal;
return diagonal * 1.42 + straight;

Dit is nog steeds niet de oplossing, hij blijft rare uitspattingen hebben, hij word er alleen veel trager door.

[PrisonerOfPain]

pedorus schreef op dinsdag 21 juli 2009 @ 17:05:
Een Fibonacci heap is O(log n) voor bepaalde operaties. Een heap die simpelweg bestaat uit 2 single linked lists, voor maximaal 2 waardes die voorkomen is O(1) voor alle hier gebruikte operaties. Nadeel daarvan is enkel dat je dus nodes met maximaal 2 verschillende waardes erin kan hebben.

Pas in de orde van 10.000 of 100.000 word een fibonacci heap echt practisch omdat het een enorm hoge constant heeft voor al die operaties. Ondanks dat 't op papier (Big-O) er prachtig uit ziet, is het in de praktijk geen practische oplossing.

Persoonlijk heb ik voor mijn open-list gewoon een std::set gebruikt, alle operaties (get-best, remove-best, en empty) zijn O(1), enkel contains en add zijn O(log n) wat op zich prima is in de meeste gevallen. Voor de closed-list gebruik ik gewoon een hashmap omdat die O(1) operaties heeft voor zowel add als contains.

Een andere oplossing, een die in AI Wisdom 3 beschreven word, de cheap-list, is om voor de open-list een mix tussen sorted en unsorted datastructure te gebruiken. Wat ze in dat geval doen is de laagste 15 items in de sorted list te houden en anders in de unsorted list. Vanwegen het data access patroon van A-star werkt dat schijnbaar prima.

Die manier van opslaan lost het probleem op dat je of een spike hebt bij get-best omdat je een linear search moet doen in een unsorted list of een spike hebt bij contains/add omdat je dan logarithmische operaties hebt. Bij de cheap-list is je get-best operatie O(1) omdat je de beste node (bijna) altijd uit de sorted list kunt halen terwijl je add en contains O(log n) waarbij n = 15, of O(1) als je buiten de range van je sorted datastructure zit.

[ Voor 14% gewijzigd door PrisonerOfPain op 23-07-2009 16:40 ]

[roy-t]

pedorus schreef op woensdag 22 juli 2009 @ 16:36:
[...]

Iets met "premature optimization is the root of all evil". Waarschijnlijk ook grotendeels achterhaald trouwens, doubles zijn steeds sneller gaan werken. Ik snap trouwens ook niet waarom je 1.42 zou gebruiken ipv echt sqrt(2).

Ik ben het wel eens met Bobozo dat zeer veel objecten gebruiken weer een beetje het andere uiterste is. Maar goed, ik ben niet bekend met de snelheid van objecten in AS3, misschien is het snel zat.

Nouja het gaat hier natuurlijk om een zo snel mogelijke A* implementatie te maken, ik vind het niet echt premature optimization eigenlijk, verder stel ik in de post die jij quote ook voor om gewoon in kwadraten te blijven werken dat is namelijk een stuk sneller dan telkens sqrt(2) te doen (wat een vrij dure operatie is nog steeds).

Ook zijn doubles en floats niet zo heel duur meer in mijn code merk ik toch zeker een verschil van 35% als ik ipv met gekwadrateerde getallen met getallen werk die floats of doubles zijn en waarvoor ik telkens sqrt moet doen dus ja het kan gewoon heel veel schelen (naat wat ifjes en een while loopje is de score berekening eigenlijk een vrij groot deel van de code, het is geen mini optimalisatie).

PrisonerOfPain schreef op donderdag 23 juli 2009 @ 16:35:
[...]

Persoonlijk heb ik voor mijn open-list gewoon een std::set gebruikt, alle operaties (get-best, remove-best, en empty) zijn O(1), enkel contains en add zijn O(log n) wat op zich prima is in de meeste gevallen. Voor de closed-list gebruik ik gewoon een hashmap omdat die O(1) operaties heeft voor zowel add als contains.

Als je in een element zelf bijhoud in welke lijst hij zit is contains ook O(1) dus dan is alleen add nog maar O(log n) en is het dus lekker snel (was jij niet diegene die mij dit tip had gegeven )?

C#:

public class pathnode
{
    bool onOpenList = false;
    bool onClosedList = false;

   //etc..
}

[ Voor 22% gewijzigd door roy-t op 23-07-2009 17:54 ]

[PrisonerOfPain]

roy-t schreef op donderdag 23 juli 2009 @ 17:52:
Als je in een element zelf bijhoud in welke lijst hij zit is contains ook O(1) dus dan is alleen add nog maar O(log n) en is het dus lekker snel (was jij niet diegene die mij dit tip had gegeven )?

C#:

public class pathnode
{
    bool onOpenList = false;
    bool onClosedList = false;

   //etc..
}

Dat was ik zeker :-) en de meeste implementaties kunnen zich die optimalisatie ook veroorloven; een time-sliced implementatie zoals die waar ik nu mee werk kan dat echter niet omdat je dan node data deelt tussen verschillende instances van je pathfinder. Waarschijnlijk is het me daarom even ontgaan. Desalniettemin is de cheap-list een mooie middenweg.

[roy-t]

PrisonerOfPain schreef op donderdag 23 juli 2009 @ 20:17:
[...]


Dat was ik zeker :-) en de meeste implementaties kunnen zich die optimalisatie ook veroorloven; een time-sliced implementatie zoals die waar ik nu mee werk kan dat echter niet omdat je dan node data deelt tussen verschillende instances van je pathfinder. Waarschijnlijk is het me daarom even ontgaan. Desalniettemin is de cheap-list een mooie middenweg.

Ah ja dat probleem was ik zelf nog niet tegen gekomen, ook een interessante natuurlijk .

[Bozozo]

Ik zou je nogmaals willen afraden om met een array van objecten te werken in AS, tenzij je optimalisatie niet belangrijk vindt. Een pathfinding algoritme is constant bezig om scores te lezen, schrijven en vergelijken. Die operaties gaan (in Flash) veel langzamer als ze via een object verlopen. Getters/setters gebruiken maakt het alleen maar erger.

Wat data ter illustratie (wederom AS en geen JS):

JavaScript:

//prepare variables
var elements:int = 10000;
var collection1:Vector.<int> = new Vector.<int>(elements,true);
var collection2:Vector.<node> = new Vector.<node>(elements,true);
for(var i2:int = 0; i2<elements; i2++) {
    collection2[i2] = new node();
}
//note: node is a class containing only 'public var val:int;'


//Following code fragments were executed 100 times.
//This was repeated 25 times, providing average and sdev per run.
//Code was compiled for release (rather then debug).


//Overhead measurement

for(var i:int = 0; i<elements; i++) {
    ;
}
//Average execution time: 0.03 ms (standard deviance 133%)


//Reading

for(var i:int = 0; i<elements; i++) {
    collection1[i];
}
//Average execution time: 0.08 ms (standard deviance 36%)

for(var i:int = 0; i<elements; i++) {
    collection2[i].val;
}
//Average execution time: 0.74 ms (standard deviance 6%)


//Writing

for(var i:int = 0; i<elements; i++) {
    collection1[i] = 1;
}
//Average execution time: 0.11 ms (standard deviance 29%)

for(var i:int = 0; i<elements; i++) {
    collection2[i].val = 1;
}
//Average execution time: 1.06 ms (standard deviance 4%)


//Reading + Writing

for(var i:int = 0; i<elements; i++) {
    collection1[i] = collection1[i];
}
//Average execution time: 0.11 ms (standard deviance 29%)

for(var i:int = 0; i<elements; i++) {
    collection2[i].val = collection2[i].val;
}
//Average execution time: 1.89 ms (standard deviance 40%)

[PrisonerOfPain]

vdvleon schreef op maandag 20 juli 2009 @ 19:27:
Ik kan vast nog wat dingen optimalizeren, Dus ik ben nog even bezig

Een insert aan het begin van een std::vector verloopt in lineare tijd; enkel aan het eind is 'ie O(1). Daarom kun je waarschijnlijk beter een std::deque met push_front gebruiken (die is wel constant time), of je heap andersom sorteren.

Vervolgens ga je in lineare tijd je element op de goede plek in de heap plaatsen. Bij een correcte heap implementatie zoals std::set gebeurt deze gehele operatie (insert, sort) in O(log n) tijd in plaats van O(n) zoals je nu hebt. Of eigenlijk O(1.5 n) in de algemene case.

[vdvleon]

Ik heb nu ook al een versie gemaakt in php (). Dat het steeds niet 100% procent werkt komt steeds waarschijnlijk door gebrek van kennis van de betreffende programmeer taal. Want namelijk de versie die ik heb geschreven in PHP werkt wel fout loos.

Een online voorbeeld: http://veendesign.nl/projects/vdPathFinder/

Omdat ik php gebruik is hij niet echt snel, maar ik ben nu wel overgestapt van objects naar C types (ik bedoel int's, bool's etc.).

Je gebruikt hem zo:

PHP:

<?php
// Map
$size = new vdSize(80, 60);
$map = new vdMap($size);
// .. Vul je map met muren etc.

// Path finder
$pathfinder = new vdPathFinder($map);

// Zoek path, met meerdere cordinaten
$path = $pathfinder->findPath(array(new vdPoint(0, 0), new vdPoint(30, 32), new vdPoint(69, 59)));

// Show path
print_r($path);
?>

De functie findPath zet de coördinaten om in index-en. Vervolgens berekent hij dmv. de functie findSubPath alle paden van index naar index. Het resultaat converteert hij weer naar echte x,y coördinaten.

Bij dit voorbeeld gebruik ik Smart Clipping. Dat houd in, hij mag diagonaal als de 2 punten waar hij langs gaat ook open zijn.

edit:

Ik heb wat toevoegingen gedaan. Hij werkt nu ook met meerdere type ondergrond.
Bijv. open heeft een cost van 1, gras 2, grind 3, en modder 4. Dus hij heeft altijd de voorkeur voor 'open'.

[ Voor 8% gewijzigd door vdvleon op 28-07-2009 15:03 ]