[C#] A* implementatie versnellen en Bottleneck vinden

Laats heb ik een implementatie gemaakt van het A* algoritme voor mensen die hier niet bekend mee zijn, het is een pathfinding algoritme gebaseerd op Dykstra's algoritme dat telkens de buur zoekt met de beste (laagste) score en probeert vanaf daar weer de volgende buur te vinden met de beste score om zo uiteindelijk bij de finish te komen. (Om doodlopende paden te voorkomen worden telkens alle buren 'ge-scored' en in een 'nog na te kijken' lijst gezet voordat de beste buur hier uit wordt gehaald).

Ik werk met een systeem van broodkruimeltjes zoals hier mooi te zien is:
C#:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

/// <summary>     /// These are the BreadCrumbs (linked list) that we lay so we can find back our path when we reach the finish     /// </summary>     public class BreadCrumb     {         public Vector3 position;         public BreadCrumb next;         public int cost = Int32.MaxValue; //High value so that real options will always be cheaper         public BreadCrumb(Vector3 position)             : this(position, null) { }         public BreadCrumb(Vector3 position, BreadCrumb parent)         {             this.position = position; this.next = parent;         }         //This way we can correctly tell if a BreadCrumb is in a list.         public override bool Equals(object obj)         {             if (obj is BreadCrumb)             {                 return ((BreadCrumb)obj).position == this.position;             }             else             {                 return false;             }         }                  public override int GetHashCode()         {             return position.GetHashCode();         }     }

Zoals je ziet is het eigenlijk een wrapper om een Vector3 die de vorige breadcrumb vast houd even als een score. Er zijn nooit 2 breadcrumbs op dezelfde positie met een zelfde code daarom gebruiken ik de equals en getHashCode van Vector3. (Ik kon helaas geen struct gebruiken omdat je dan een oneindige loop krijgt als je zichzelf als item erin zet).

Hieronder is de code te zien die probeert dit pad te vinden, eerst had ik de score en checkneighbours delen in apparte methoden maar om ervoor te zorgen dat de code sneller wordt heb ik deze nu in deze methode gezet.

Toen ik deze code geschreven had, getest had, en gepubliceerd op mijn blogje dacht ik klaar, maar al snel wees iemand me op de snelheid van deze implementatie, gek genoeg is de code namelijk vrij traag

Zoals aan de titel te zien is, is de code helaas erg traag een pad vinden in een wereld van 10x10x10 kost in release mode op mijn processor al +-450ms. Nu heb ik wel een vermoeden waarom dit vrij traag is. Volgens een poster op mijn blog is de contains methode van list erg traag en die wordt (26*2+2)*n uitgevoerd. Nu heb ik tijdelijk List<> vervangen door HashSet<> vervangen maar hier werd de code niet erg veel sneller van, terwijl het toch de bedoeling is dat de hashset contains in O(1) uit kan voeren?

Verder heb ik heel vaak het item met de laagste score nodig, ik zat te denken aan een soort van insertion sort elke keer als ik een nieuw item in de openList stop, maar hoe zorg ik er dan voor dat ik niet elke keer de hele array moet kopiëeren die achter deze nieuwe lijst zou zitten, of uberhaupt de items deels 1 item moet verplaatsen? Ik heb helaas van te voren ook geen idee hoeveel iteraties ik nodig ga hebben en hoe groot de lijst gaat worden. Voor de huidige wereld die ik heb van 10x10x10 is 1/3 van de tiles geblocked (333) en wordt de grote while loop 665x uitgevoerd (betrekkelijk weinig als je bedenkt dat er 10^10^10 mogelijkheden zijn). Maar dat betekend dus wel 885780x Contains() en een hele hoop andere code die volgens mij vaker dan nodig wordt uitgevoerd.

Maar nu ben ik een beetje verloren, welke data typen kan ik het beste gebruiken en waar zit er nu echt ruimte voor verbetering, ik denk vooral bij de Contains() methode maar een Hashset lijkt niet te werken, wat kan ik hier dan wel het beste voor gebruiken?

(hieronder de code)
C#:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103

/// <summary>         /// Method that uses an A* algorithm to find the best path from start to end.         /// </summary>         /// <returns>The end breadcrump where each parent is a step back (so its a reversed path!)</returns>         private static BreadCrumb FindPathReversed(World world, Vector3 start, Vector3 end)         {             //The openList will contains tiles we are going to examine             //The closedList contains tile that we've already examined and made part of a path             List<BreadCrumb> openList = new List<BreadCrumb>();                         List<BreadCrumb> closedList = new List<BreadCrumb>();             Vector3 tmp;             int cost = Int32.MaxValue;             int diff = 0;             //Add the start node to the openList             BreadCrumb current = new BreadCrumb(start);             BreadCrumb finish = new BreadCrumb(end);             openList.Add(current);             //Stop if there are no more options, or if we have found the finish             while (openList.Count > 0 && !closedList.Contains(finish))             {                 current = openList[0];                 //Find the lowest cost Tile that we can consider from the openList                                                                     for (int i = 1; i < openList.Count; i++)                 {                     if (openList[i].cost < current.cost)                     {                         current = openList[i];                     }                 }                 //Switch that one over to the closed list                 openList.Remove(current);                 closedList.Add(current);                 //Find neigbours add them to the openlist and check if those who where already                 //on the openlist can be reached faster this way. Also calculate their best scores                  //surrounding is een statische Vector3[] waarin de 26 'offsets' staan naar buren staan (-1,0,0) is linker buur                 for (int i = 0; i < surrounding.Length; i++)                 {                     tmp = current.position + surrounding[i];                     if (tmp.X >= world.Left && tmp.X < world.Right &&                         tmp.Y >= world.Bottom && tmp.Y < world.Top &&                         tmp.Z >= world.Front && tmp.Z < world.Back &&                         world.PositionIsFree(tmp))                     {                         BreadCrumb node = new BreadCrumb(tmp, current);                         if (!closedList.Contains(node))                         {                                                         if (!openList.Contains(node))                             {                                 openList.Add(node);                             }                             //Do scoring                             diff = 0;                             if (current.position.X != node.position.X)                             {                                 diff++;                             }                             if (current.position.Y != node.position.Y)                             {                                 diff++;                             }                             if (current.position.Z != node.position.Z)                             {                                 diff++;                             }                                                          //double diagonal moves cost 17 (all 3 different) normal diagonal moves cost 14 (2 different).                             //Orthogonal costs 10                             switch (diff)                             {                                 case 1:                                     cost = current.cost + 10;                                     break;                                 case 2:                                     cost = current.cost + 14;                                     break;                                 case 3:                                     cost = current.cost + 17;                                     break;                             }                                                         if (cost < node.cost)   //updates the cost only if the new cost is less                              //this way new nodes and nodes already on the openlist both get correct scores                             {                                 node.cost = cost;                                 node.next = current;                             }                         }                     }                 }                         }                          //The last added node is the node containing the path!             if(closedList.Contains(finish)){                 return closedList[closedList.Count -1];             }else{                 return null; //no path found             }         }

Notes: het gaat hier om 3D pathfinding vanuit 1 node kun je naar 26 andere nodes (orthogonaal, diagonaal en 'dubbel diagonaal').

Edit: misschien handig om mijn streven hier neer te zetten, eigenlijk wil ik dat deze code op een 'moderne pc' maar 50ms nodig heeft voor een mogelijk veel grotere map, maar dan moet ik er sowieso wat meer niveau's in bouwen, ook is het aantal niet geblokkeerde nodes dan veel groter.

Edit2: interessant detail trouwens: hoe meer nodes geblokkeerd zijn (bijvoorbeeld 1 op 2) hoe sneller het algoritme is, waarschijnlijk omdat hij niet veel te kiezen heeft om het optimale pad te vinden.

Kun je niet gewoon een 3 dimensionale array gebruiken? Je geeft zelf aan dat op elke positie slechts 1 object aanwezig kan zijn. Daarnaast kun je direct controleren of de 'cel' leeg is of een object bevat.

http://xkcd.com/534/

Sorry, maar de eerste paar regels code deden me toch wel aan die comic denken

Tsja, dat krijg je als je naar een Pirates Of The Caribbean-avond gaat ipv gaat zitten n3rden

quote:

Niemand_Anders schreef op vrijdag 03 juli 2009 @ 12:04:
Kun je niet gewoon een 3 dimensionale array gebruiken? Je geeft zelf aan dat op elke positie slechts 1 object aanwezig kan zijn. Daarnaast kun je direct controleren of de 'cel' leeg is of een object bevat.

Dat kan helaas niet omdat de items die ik in de openList heb niet verwant zijn aan posities maar toevallig adjacents zijn van een van de paden die ik overweeg, voor de closed list geld hetzelfde ik kan dus niet met zekerheid zeggen welk items er al in zitten.

Meer over hoe dat werkt is hier te zien: http://www.policyalmanac.org/games/aStarTutorial.htm


De groene vierkantjes zijn items die in de openLijst zitten, blauwe items zitten in de gesloten lijst (zijn bekeken en discared of onderdeel van een goed pad) en gele items (met rode bolletjes) zijn het uiteindelijke optimale pad (deze zaten eerst in de gelostenLijst). Zoals je ziet zijn veel van de vakjes uberhaupt nog niet bekeken en is een 3d array helaas geen opties.

@yamAUchi ik zal er aan denken, gelukkig is dit geen genetisch algoritme.
@Skaah wtf? Huh? Betrapt?

roy-t wijzigde dit bericht 03-07-2009 12:11 (4%)

Buiten het feit dat ik wel wat kleine tweaks zie zoals overbodige if else constructies:
C#:

1 2 3 4 5 6 7 8

if (obj is BreadCrumb) {     return ((BreadCrumb)obj).position == this.position; } else {     return false; }

->
C#:

1 2 3

if (obj is BreadCrumb)     return ((BreadCrumb)obj).position == this.position; return false;

Wat ik ook zie is dat je een Vector3 gebruikt, waarschijnlijk zijn dit floats en voor jou toepassing is een int genoeg. Ik zou hier zelf even een struct voor schrijven (Point3D ofzo) met alleen ints. Ints zijn vele malen sneller dan floats.

Voor zoiets:
C#:

1 2 3 4 5 6 7 8

//Find the lowest cost Tile that we can consider from the openList                                                                     for (int i = 1; i < openList.Count; i++)                 {                     if (openList[i].cost < current.cost)                     {                         current = openList[i];                     }                 }

Kan je ook LINQ gebruiken (Google maar eens als je niet weet wat het is).

Waar je ook nog naar kan kijken is bij if statements bij welk gedeelte klapt ie er het snelste uit, bv:
C#:

1 2 3 4 5

tmp = current.position + surrounding[i];                     if (tmp.X >= world.Left && tmp.X < world.Right &&                         tmp.Y >= world.Bottom && tmp.Y < world.Top &&                         tmp.Z >= world.Front && tmp.Z < world.Back &&                         world.PositionIsFree(tmp))

als world.PositionIsFree(tmp) nou veel vaker false is dan de rest kan je beter deze vooraan zetten.
Misschien ook handig om het op te delen in gebieden, nu loop je vaak voor 9 stuks of meer stuks voor niks door omdat die allemaal op de world.Left/Right/Top/Back/Front/Bottom er uit lopen.

Al met al weet ik niet of dit wel de snelste manier is om dit te bepalen. Ik geloof niet dat ik het zelf op deze manier zou doen.

Heb je het programma al eens door een profiler gehaald? (Ik ken er zelf niet echt voor C#, maar ik veronderstel dat die er wel zijn.)

Ik vermoed dat dan wel een en ander duidelijk zou kunnen worden.
Er zijn twee dingen die ik zou verwachten in de resultaten bij het profilen. Je hebt eerst en vooral heel veel add en remove operaties op een List. Ik weet niet wat de complexiteit daarvan is bij de gebruikte implementatie? Ten tweede maak je ook heel veel niewe objecten aan (BreadCrumbs). Dus moest je dat enigszinds kunnen beperken zal je volgens mij ook wel winst boeken aangezien dat een relatief dure operatie is.

Maar ik zou je eerst en vooral aanraden het eens te profilen, dan kan je gericht optimaliseren.

quote:

Phyxion schreef op vrijdag 03 juli 2009 @ 12:24:
Buiten het feit dat ik wel wat kleine tweaks zie zoals overbodige if else constructies:
C#:

1 2 3 4 5 6 7 8

if (obj is BreadCrumb) {     return ((BreadCrumb)obj).position == this.position; } else {     return false; }

->
C#:

1 2 3

if (obj is BreadCrumb)     return ((BreadCrumb)obj).position == this.position; return false;

Ik kan geen C# maar dan kan dit toch ook:
C#:

1	return (obj is BreadCrumb) && ((BreadCrumb)obj).position == this.position

quote:

Mammon schreef op vrijdag 03 juli 2009 @ 13:54:
[...]

Ik kan geen C# maar dan kan dit toch ook:
C#:

1	return (obj is BreadCrumb) && ((BreadCrumb)obj).position == this.position

Geloof mij, dit wordt allemaal al gedaan door de compiler hoor. Vrij zinloos om dit te doen

quote:

Mammon schreef op vrijdag 03 juli 2009 @ 13:54:
[...]

Ik kan geen C# maar dan kan dit toch ook:
C#:

1	return (obj is BreadCrumb) && ((BreadCrumb)obj).position == this.position

Ja dat kan inderdaad ook nog Had het even snel getypt, maar je hebt gelijk

@ Snake, dat hoeft niet altijd, dat hangt helemaal af van de situatie, je kan voor de gein wel eens kijken naar de bytecode, denk dat ie wel anders is hoor.

Phyxion wijzigde dit bericht 03-07-2009 13:59 (19%)

quote:

Phyxion schreef op vrijdag 03 juli 2009 @ 13:58:
[...]

Ja dat kan inderdaad ook nog Had het even snel getypt, maar je hebt gelijk

@ Snake, dat hoeft niet altijd, dat hangt helemaal af van de situatie, je kan voor de gein wel eens kijken naar de bytecode, denk dat ie wel anders is hoor.

Mag je mij toch eens vertellen waarin jouw statement verschild van het 'geoptimaliseerde' ?

quote:

roy-t schreef op vrijdag 03 juli 2009 @ 11:52:
Laats heb ik een implementatie gemaakt van het A* algoritme voor mensen die hier niet bekend mee zijn, het is een pathfinding algoritme gebaseerd op Dijkstra's algoritme dat telkens de buur zoekt met de beste (laagste) score en probeert vanaf daar weer de volgende buur te vinden met de beste score om zo uiteindelijk bij de finish te komen. (Om doodlopende paden te voorkomen worden telkens alle buren 'ge-scored' en in een 'nog na te kijken' lijst gezet voordat de beste buur hier uit wordt gehaald).

Een willekeurige vraag. Waarom gebruik je een A* algoritme indien je geen heuristische schatting gebruikt? Nu is het namelijk niets meer dan een slecht (als in incorrect en inefficiënt) geïmplementeerde versie van Dijkstra's korste pad algoritme.

Mijn inziens heb je namelijk een probleem wanneer een bepaalde knoop a zich in de openstaande knopenlijst bevindt en je nu vanuit een knoop b, ook verbonden bent met knoop a. Jouw algoritme zal dan (op een inefficiënte wijze) bepalen dat je die knoop a niet meer moet toevoegen. Immers, de lokatie is dezelfde. Je houdt er echter geen rekening mee dat de score van a via het pad langs b een lagere kost kan hebben. Met andere woorden, je moet de score gaan aanpassen van een knoop a (in de lijst van de openstaande knopen) indien je deze via een ander pad zou willen toevoegen.

Merk op dat van zodra de current node de end node is, je toch nog alle buren gaat beschouwen. Dit is natuurlijk niet erg goed voor de prestaties.

quote:

Toen ik deze code geschreven had, getest had, en gepubliceerd op mijn blogje dacht ik klaar, maar al snel wees iemand me op de snelheid van deze implementatie, gek genoeg is de code namelijk vrij traag

Erg traag noem ik dit nu niet. Inefficiënt, dat zeker.

quote:

Volgens een poster op mijn blog is de contains methode van list erg traag en die wordt (26*2+2)*n uitgevoerd. Nu heb ik tijdelijk List<> vervangen door HashSet<> vervangen maar hier werd de code niet erg veel sneller van, terwijl het toch de bedoeling is dat de hashset contains in O(1) uit kan voeren?

Die contains is niet traag. Die contains wordt hoogstwaarschijnlijk geïmplementeerd met een lineair zoekalgoritme. Dat geeft je een tijdscomplexiteit van O(n), met n het aantal elementen in je lijst. Een HashSet heeft waarschijnlijk een tijdscomplexiteit van O(1) voor het opvragen van 1 element. De reden waarom je code toch nog traag is, ligt in de manier om te bepalen welke knoop je gaat behandelen. Dat is simpelweg hopeloos traag.

quote:

Verder heb ik heel vaak het item met de laagste score nodig, ik zat te denken aan een soort van insertion sort elke keer als ik een nieuw item in de openList stop, maar hoe zorg ik er dan voor dat ik niet elke keer de hele array moet kopiëeren die achter deze nieuwe lijst zou zitten, of uberhaupt de items deels 1 item moet verplaatsen?

Gelukkig zijn er hier voldoende datastructuren voor. Een Priority Heap zal voor jou toepassing veruit het meest eenvoudige zijn, met redelijke prestaties. De toegangstijd voor het opvragen van het item met de laagste score is van de orde log(n). Als je écht snelle code moet hebben, dan kijk je beter eens (dit raad ik ten sterkste af, tenzij je een werkende implementatie hebt in je programmeertaal) naar Binomial Heaps, Fibonacci Heaps of Radix Heaps. Fibonacci heaps hebben bijvoorbeeld een toegangstijd van O(1) voor het opvragen van het minimum. Deze datastructuur staat er echter bekend om moeilijk implementeerbaar te zijn.

quote:

Ik heb helaas van te voren ook geen idee hoeveel iteraties ik nodig ga hebben en hoe groot de lijst gaat worden. Voor de huidige wereld die ik heb van 10x10x10 is 1/3 van de tiles geblocked (333) en wordt de grote while loop 665x uitgevoerd (betrekkelijk weinig als je bedenkt dat er 10^10^10 mogelijkheden zijn). Maar dat betekend dus wel 885780x Contains() en een hele hoop andere code die volgens mij vaker dan nodig wordt uitgevoerd.

De hele idee achter A* is net dat je een heuristische afschatting voor je afstand tot je doel gaat gebruiken (die een onderschatting moet zijn) om de zoekruimte te verkleinen. Je kijkt hiervoor best eens op de wiki-pagina die je zelf aangaf.

quote:

Maar nu ben ik een beetje verloren, welke data typen kan ik het beste gebruiken en waar zit er nu echt ruimte voor verbetering, ik denk vooral bij de Contains() methode maar een Hashset lijkt niet te werken, wat kan ik hier dan wel het beste voor gebruiken?

Zoals aangegeven vervang je je openstaande knopenlijst best door een Heap. Deze datastructuren zijn zodanig ontworpen dat het opvragen van het element met de laagste waarde zeer efficiënt is. Hierdoor kun je je code voor het bepalen van het minimum weggooien. Nagaan of een element zich in een heap bevindt kan ook snel, omdat de elementen gesorteerd zijn (op waarde). Het zoeken kan dan in O(log (n)) in plaats van O(n). Verder raad ik je aan om de lijst van afgewerkte knopen te vervangen door een HashSet. Je moet immers frequent bepalen of een element in de lijst van afgewerkte knopen zit. Met een HashSet kun je dit in O(1) tijd bepalen.

quote:

Snake schreef op vrijdag 03 juli 2009 @ 13:57:
[...]

Geloof mij, dit wordt allemaal al gedaan door de compiler hoor. Vrij zinloos om dit te doen

Dat is waar maar in dit geval vind ik het leesbaarder. In andere gevallen met meerdere variabelen doe ik meestal iets in de vorm van:
code:

bool1 = this.eigenschap1 == eigenschap1;
bool2 = this.eigenschap2 == eigenschap2;
bool3 = this.eigenschap3 == eigenschap3;
bool4 = this.eigenschap4 == eigenschap4;

return bool1 && bool2 && bool3 && bool4;

Misschien minder efficient maar ik vind het wel leesbaarder

quote:

Nick The Heazk schreef op vrijdag 03 juli 2009 @ 14:13:
De hele idee achter A* is net dat je een heuristische afschatting voor je afstand tot je doel gaat gebruiken (die een onderschatting moet zijn) om de zoekruimte te verkleinen.

Dit dus. Ieder woord in deze zin is belangrijk.
Een veel gebruikte heuristic voor dit soort problemen is de Manhattan afstand (ook wel bekend als de cityblock distance). Zie wikipedia of mathworld voor verdere uitleg.

Het belangrijkste is denk ik:

quote:

roy-t schreef op vrijdag 03 juli 2009 @ 11:52:
C#:

25 26 27 28 29 30 31 32 33 34 35 36 37

current = openList[0];                 //Find the lowest cost Tile that we can consider [...]                 for (int i = 1; i < openList.Count; i++)                 {                     if (openList[i].cost < current.cost)                     {                         current = openList[i];                     }                 }                 //Switch that one over to the closed list                 openList.Remove(current);                 closedList.Add(current);

Dit is heftig inefficiënt. Gebruik een heap zoals hierboven is gezegd. Of, als je zoals hier met redelijk kleine afstanden van hele getallen werkt, kun je ook een Calendar Queue gebruiken, die is O(1). Zo te zien heb je maar 18 vakjes nodig hier (afstand 0-17); maak van BreadCrumb gelijk een doubly-linked list node die in zo'n vakje past (afhankelijk van of verwijderen en verplaatsen naar voren hier kan voorkomen; het zou zomaar kunnen dat dat niet zo is en je kunt volstaan met single linked lijstjes per vakje..).

quote:

Phyxion schreef op vrijdag 03 juli 2009 @ 12:24:
Buiten het feit dat ik wel wat kleine tweaks zie zoals overbodige if else constructies:
C#:

1 2 3 4 5 6 7 8

if (obj is BreadCrumb) {     return ((BreadCrumb)obj).position == this.position; } else {     return false; }

->
C#:

1 2 3

if (obj is BreadCrumb)     return ((BreadCrumb)obj).position == this.position; return false;

Wat ik ook zie is dat je een Vector3 gebruikt, waarschijnlijk zijn dit floats en voor jou toepassing is een int genoeg. Ik zou hier zelf even een struct voor schrijven (Point3D ofzo) met alleen ints. Ints zijn vele malen sneller dan floats.

Voor zoiets:
C#:

1 2 3 4 5 6 7 8

//Find the lowest cost Tile that we can consider from the openList                                                                     for (int i = 1; i < openList.Count; i++)                 {                     if (openList\[i].cost < current.cost)                     {                         current = openList\[i];                     }                 }

Kan je ook LINQ gebruiken (Google maar eens als je niet weet wat het is).

Waar je ook nog naar kan kijken is bij if statements bij welk gedeelte klapt ie er het snelste uit, bv:
C#:

1 2 3 4 5

tmp = current.position + surrounding\[i];                     if (tmp.X >= world.Left && tmp.X < world.Right &&                         tmp.Y >= world.Bottom && tmp.Y < world.Top &&                         tmp.Z >= world.Front && tmp.Z < world.Back &&                         world.PositionIsFree(tmp))

als world.PositionIsFree(tmp) nou veel vaker false is dan de rest kan je beter deze vooraan zetten.
Misschien ook handig om het op te delen in gebieden, nu loop je vaak voor 9 stuks of meer stuks voor niks door omdat die allemaal op de world.Left/Right/Top/Back/Front/Bottom er uit lopen.

Al met al weet ik niet of dit wel de snelste manier is om dit te bepalen. Ik geloof niet dat ik het zelf op deze manier zou doen.

Ah die overbodige if else constructie zat ik al mee in mijn maag, stom dat ik niet zag dat ik die meteen kon returnen (ik zat al te kutten met breaks.. domme ik).

Verder over je Linq voorstel, ik heb inderdaad gespeeld met linq maar helaas kun je met Max of Min alleen de waarde en niet het item bepalen, ik heb implementaties gezien van mensen die dit wel doen (extension methods) maar dat was dan uiteindelijk gewoon zo'n forloopje als dat ik 'm heb en dus niet sneller (eeerder trager). Ik hoop dat probleem op te lossen met een priority queue of insertion sort maar ik weet niet goed hoe ik dat moet implementeren.

quote: Nick The Heazk

Een willekeurige vraag. Waarom gebruik je een A* algoritme indien je geen heuristische schatting gebruikt? Nu is het namelijk niets meer dan een slecht (als in incorrect en inefficiënt) geïmplementeerde versie van Dijkstra's korste pad algoritme.

[s]

WTF, je hebt gelijk ik ben dat vergeten in mijn nette implementatie terwijl ik wel in mijn kladje had... dom dom dom dat zal inderdaad veel moves schelen, bedankt voor deze scherpe observatie.

quote:

Merk op dat van zodra de current node de end node is, je toch nog alle buren gaat beschouwen. Dit is natuurlijk niet erg goed voor de prestaties.

Daar heb je gelijk.


Damn mensen ik ziew nu dus dat ik echt een paar grote fouten heb gemaakt die ik op mijn kladje wel goed had, dom dom dom, ik zal dat eerst even fixen dit weekend (en een rectificatie zetten op mijn blog). voordat ik weer verder ga met optimaliseren.

Gebruik serieus een (Binary)Heap. Laatst moesten wij op school een routeplanner voor heel Overijssel maken. Na implementatie daarvan door een paar klasgenoeten ging het plannen van > 15 min naar < 1 seconde ofzo. Als ik het niet vergeet zal ik thuis even kijken wat ze precies gebruikt hebben.

Aantal dingetjes:

Omdat je geen list length meegeeft bij de list constructor zal deze meerdere keren groeien in de loop en alle elementen kopieeren. De default lengte is 4 dacht ik..
C#:

1	closedList.Add(current);

Probeer deze zo op te zetten dat hij er zo snel mogelijk uitklapt:
C#:

1 2 3 4

tmp.X >= world.Left && tmp.X < world.Right &&                          tmp.Y >= world.Bottom && tmp.Y < world.Top &&                          tmp.Z >= world.Front && tmp.Z < world.Back &&                          world.PositionIsFree(tmp))

bv:
C#:

1	!( tmp.X < world.left || tmp.x > world.right enz.

Vervang dit:
C#:

1 2 3 4 5 6 7 8 9 10 11 12

switch (diff)                              {                                  case 1:                                      cost = current.cost + 10;                                      break;                                  case 2:                                      cost = current.cost + 14;                                      break;                                  case 3:                                      cost = current.cost + 17;                                      break;                              }

door een array lookup:
C#:

1	cost = current.cost + diffcost[diff]

Best kans dat de compiler dat al doet..


Maar het beste is om de hele code op de schop te gooien: gebruik arrays, in plaats van de cellen sla je de cummulatieve costs op paden tussen cellen op en gooi alles om zodat je direct kunt addresseren in die arrays, alleen je huidige pad bewaar je en dat je initialiseer je op het korste pad, zonder rekening te houden met costs. In je loop ga je dat pad na en pas je aan waar nodig. Kan wel zijn dat in sommige maps dat pad niet het korste is.. dat ligt een beetje aan je maps.. indoor kamers, grote buitenruimte, de ruimte? Of dat acceptabel is ligt aan je toepassing maar het is veel sneller dan gewoon maar alles checken.

Daarnaast kun je nog alles indelen in sectors met costs als je maps heel groot worden + een groot deel van alles kan vantevoren eenmalig gedaan worden als je map redelijk statisch is.

RobLemmens wijzigde dit bericht 03-07-2009 15:09 (4%)

De standaard manieren om A-star te optimaliseren zijn door het algoritme te time-slicen (eg. de executie van het argoritme verdelen over meerdere game-ticks). Kortom, je doet een aantal iteraties van het algoritme, bijvoorbeeld 50, per iteratie van je game loop. Dit houd in dat je niet meteen je resultaat zult hebben (dat is iets waarmee je rekening zult moeten houden bij het volgen van 't pad, je wilt geen idle bot hebben wss).

De andere manier om A-star sneller te krijgen is door de zoek-actie hierarchisch uit te voeren; wat je doet is eerst een highlevel route uitrekenen. Als je meerdere kamers hebt, reken je eerst uit welke kamers je zoal moet passeren om bij je bestemming te komen en vervolgens reken je steeds de route uit van deur naar deur.

Verder kan het ook nog helpen om een goede heuristics functie te kiezen, meestal is dit de stelling van pythagoras maar als je een eenvoudig grid hebt zou je ook naar de 'manhattan distance' kunnen kijken. Die levert meestal een route op met veel minder bochten.

Als allerlaatste zou je nog kunnen overwegen om alle paden te pre-calculaten. Het enige nadeel daarvan is dat je dan geen routes dynamisch opnieuw kunt plannen, wat bijvoorbeeld handig is als je waypoints toe moet voegen of verwijderen van je graph om te gemoet te komen aan acties die gebeuren in het spel.

Verder is het inderdaad een kwestie van de goede datatypes kiezen, op een heap kun je namelijk O(1) het laagste element vinden.

PrisonerOfPain wijzigde dit bericht 04-07-2009 03:17 (4%)

Jip86, RobLemmens en PrisonerofPain,

Ook jullie bedankt voor deze goede tips, damn ik schaam me er nog steeds voor dat ik vergeten was de manhattan distance er bij te nemen, ook zie ik goede tips om het een en ander nog veel sneller te maken, helaas kan ik er dit weekend niet aan werken (op bezoek). Maar ik zal maandag of dinsdag even een betere oplossing proberen te maken en kijken hoe deze performt.

Het is trouwens niet belangrijk dat de route echt exact de korste route is, verder gaat het om een soort van Space-RTS achtig ideetje waar ik wat techdemo's voor aan het maken ben (puur hobby,ik heb geen rare illusies ). Dus weinig moeilijke routes. Wel moet ik nog gaan bedenken hoe units elkaar gaan ontwijken omdat iederen beweegt zonder elke keer het pad opnieuw uit te rekenen (misschien door nooit meer dan x stappen vooruit te denken, maarja dan moet je wel weten dat dat pad niet dood loopt. Anyway daar zal ik later aan moeten denken).

* roy-t gaat weer schamend in een hoekje (twente) zitten

quote:

RobLemmens schreef op vrijdag 03 juli 2009 @ 15:07:
Probeer deze zo op te zetten dat hij er zo snel mogelijk uitklapt:
C#:

1 2 3 4

tmp.X >= world.Left && tmp.X < world.Right &&                          tmp.Y >= world.Bottom && tmp.Y < world.Top &&                          tmp.Z >= world.Front && tmp.Z < world.Back &&                          world.PositionIsFree(tmp))

bv:
C#:

1	!( tmp.X < world.left || tmp.x > world.right enz.

Dat gaat niet werken. Bij || ga je gewoon nog door als de eerste false is. Je wel juist dat alle condities waar zijn.

Wat jij wilt gebeurt al. Quote van MSDN:

quote:

The && and || operators are conditional versions of the & and | operators:

• The operation x && y corresponds to the operation x & y, except that y is evaluated only if x is true.
• The operation x || y corresponds to the operation x | y, except that y is evaluated only if x is false.

quote:

roy-t schreef op zaterdag 04 juli 2009 @ 13:07:
Wel moet ik nog gaan bedenken hoe units elkaar gaan ontwijken omdat iederen beweegt zonder elke keer het pad opnieuw uit te rekenen (misschien door nooit meer dan x stappen vooruit te denken, maarja dan moet je wel weten dat dat pad niet dood loopt. Anyway daar zal ik later aan moeten denken).

Ook dit is makkelijk op te lossen mbv een hierarchische pathfinder; je hoeft alleen de route op locaal niveau opnieuw te plannen met de verwijderde edges. Dingen gedeeltelijk gaan plannen is alleen leuk als je time-slicing wilt toepassen. Anders zou ik er niet aan beginnen; het resultaat zal namelijk veel te veel varieren en er niet mooi uit zien.

Wat je wel kunt doen is time-slicing gebruiken en terwijl je aan het wachtten bent op het resultaat beweeg je je voertuig gewoon recht op het doel af. Zodra je je route hebt beweeg je naar de dichtbijzijnde node waar je line of sight check op werkt. (Simpel een ray casten naar de node, waarvoor je 't makkelijkst een sphere kunt nemen waarschijnlijk). Vervolgens vervolg je vanaf die node je route.

Wat je ook kun doen, als je de illusie wilt scheppen dat er iets intelligents gebeurd is De paper "Steering Behaviors For Autonomous Characters". Sowieso zitten daar behaviours tussen die het volgen van een pad vloeiender maken (andere oplossing is bezier curves + nav-mesh; dat levert wss nog beter resultaat op maar is waarschijnlijk minder geschikt voor een RTS).

PrisonerOfPain wijzigde dit bericht 05-07-2009 12:48 (16%)

quote:

Phyxion schreef op vrijdag 03 juli 2009 @ 13:58:
@ Snake, dat hoeft niet altijd, dat hangt helemaal af van de situatie, je kan voor de gein wel eens kijken naar de bytecode, denk dat ie wel anders is hoor.

Denk het niet hoor. Feitelijk doen ze namelijk allemaal *exact* hetzelfde. Een && is geen operatie, maar in feite gewoon een geneste if. Wel of geen else betekent alleen maar een extra jump aan het eind van de true-case (omdat hij dan over de false-case heen moet springen). Gezien het feit dat er toch al een return in staat boeit dat dus niet. Oftewel, zowel jouw voorstel als die van Mammon maken *letterlijk* geen verschil met het origineel.

Daarnaast, verschillende bytecode boeit niet eens. Waar je naar moet kijken is wat de JITer er van bakt.

quote:

.oisyn schreef op zondag 05 juli 2009 @ 20:21:
[...]

Denk het niet hoor. Feitelijk doen ze namelijk allemaal *exact* hetzelfde. Een && is geen operatie, maar in feite gewoon een geneste if. Wel of geen else betekent alleen maar een extra jump aan het eind van de true-case (omdat hij dan over de false-case heen moet springen). Gezien het feit dat er toch al een return in staat boeit dat dus niet. Oftewel, zowel jouw voorstel als die van Mammon maken *letterlijk* geen verschil met het origineel.

Daarnaast, verschillende bytecode boeit niet eens. Waar je naar moet kijken is wat de JITer er van bakt.

Heb even gekeken met die returns en je hebt inderdaad gelijk, maar met && zeker niet.
Hier maken we 3x een bool aan:

&&:
code:

.method public hidebysig instance bool  TestFunc() cil managed
{
  // Code size       16 (0x10)
  .maxstack  1
  .locals init ([0] bool b1,
           [1] bool b2,
           [2] bool b3)
  IL_0000:  ldc.i4.1
  IL_0001:  stloc.0
  IL_0002:  ldc.i4.0
  IL_0003:  stloc.1
  IL_0004:  ldc.i4.1
  IL_0005:  stloc.2
  IL_0006:  ldloc.0
  IL_0007:  brfalse.s  IL_000e
  IL_0009:  ldloc.1
  IL_000a:  brfalse.s  IL_000e
  IL_000c:  ldloc.2
  IL_000d:  ret
  IL_000e:  ldc.i4.0
  IL_000f:  ret
} // end of method Form1::TestFunc

vs non-&&:
code:

.method public hidebysig instance bool  TestFunc() cil managed
{
  // Code size       23 (0x17)
  .maxstack  1
  .locals init ([0] bool b1,
           [1] bool b2,
           [2] bool b3)
  IL_0000:  ldc.i4.1
  IL_0001:  stloc.0
  IL_0002:  ldc.i4.0
  IL_0003:  stloc.1
  IL_0004:  ldc.i4.1
  IL_0005:  stloc.2
  IL_0006:  ldloc.0
  IL_0007:  brfalse.s  IL_0015
  IL_0009:  ldloc.1
  IL_000a:  brfalse.s  IL_0013
  IL_000c:  ldloc.2
  IL_000d:  brfalse.s  IL_0011
  IL_000f:  ldc.i4.1
  IL_0010:  ret
  IL_0011:  ldc.i4.0
  IL_0012:  ret
  IL_0013:  ldc.i4.0
  IL_0014:  ret
  IL_0015:  ldc.i4.0
  IL_0016:  ret
} // end of method Form1::TestFunc

of iets anders geschreven in non-&& (Hier zonder wat lichtelijk overbodige returns):
code:

.method public hidebysig instance bool  TestFunc() cil managed
{
  // Code size       19 (0x13)
  .maxstack  1
  .locals init ([0] bool b1,
           [1] bool b2,
           [2] bool b3)
  IL_0000:  ldc.i4.1
  IL_0001:  stloc.0
  IL_0002:  ldc.i4.0
  IL_0003:  stloc.1
  IL_0004:  ldc.i4.1
  IL_0005:  stloc.2
  IL_0006:  ldloc.0
  IL_0007:  brfalse.s  IL_0011
  IL_0009:  ldloc.1
  IL_000a:  brfalse.s  IL_0011
  IL_000c:  ldloc.2
  IL_000d:  brfalse.s  IL_0011
  IL_000f:  ldc.i4.1
  IL_0010:  ret
  IL_0011:  ldc.i4.0
  IL_0012:  ret
} // end of method Form1::TestFunc

Overigens heb ik nog even gekeken naar het if/else geval, op Release mode wordt het weggeoptimaliseerd, op Debug mode is er wel een verschil.

Dit lijkt een enorm verschil als je naar de bytecode kijkt, maar wanneer dit in de VM wordt gerund kan dit verder geoptimaliseerd worden. Dus of er echt een verschil is op runtime betwijfel ik.

Daarnaast zijn dit soort micro-optimalisaties nooit echt nuttig. Ze leveren in verhouden heel erg weinig op. In dit geval zou ik degene kiezen die het er meest leesbaar uitziet. De compilers van vandaag zijn slim genoeg om er dan wat handigs voor de machine van te maken.

Het kiezen van een juiste implementatie (zoals het goede type priority-queue) zal wel heel veel uitmaken.