[C#] A* implementatie versnellen en Bottleneck vinden

[roy-t]

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#:

    /// <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#:

        /// <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.

[Niemand_Anders]

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.

[yamAUchi]

http://xkcd.com/534/

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

[Skaah]

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

[roy-t]

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?

[ Voor 4% gewijzigd door roy-t op 03-07-2009 12:11 ]

[Phyxion]

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

C#:

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

->

C#:

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#:

  //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#:

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.

[bomberboy]

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.

[Mammon]

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#:

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

->

C#:

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

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

C#:

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

[Snake]

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

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

C#:

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

[Phyxion]

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

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

C#:

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.

[ Voor 19% gewijzigd door Phyxion op 03-07-2009 13:59 ]

[Snake]

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' ?

[Nick The Heazk]

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.

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.

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.

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.

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.

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.

[Mammon]

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

[CAPSLOCK2000]

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.

[pedorus]

Het belangrijkste is denk ik:

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

C#:

                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..).

[roy-t]

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#:

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

->

C#:

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#:

  //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#:

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.

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.

[jip_86]

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.

[RobLemmens]

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#:

                closedList.Add(current); 

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

C#:

                        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#:

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

Vervang dit:

C#:

                            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#:

                           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.

[ Voor 4% gewijzigd door RobLemmens op 03-07-2009 15:09 ]

[PrisonerOfPain]

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.

[ Voor 4% gewijzigd door PrisonerOfPain op 04-07-2009 03:17 ]

[roy-t]

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

[jip_86]

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

C#:

                        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#:

!( 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:

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.

[PrisonerOfPain]

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).

[ Voor 16% gewijzigd door PrisonerOfPain op 05-07-2009 12:48 ]

[.oisyn]

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.

[Phyxion]

.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.

[Marcj]

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.

[.oisyn]

Phyxion schreef op zondag 05 juli 2009 @ 20:59:
[...]

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

Het had fijn geweest als je ook de sourcecode erbij had gezet. Ik gok namelijk dat je dit hebt geschreven:

C#:

bool func(bool a, bool b, bool c)
{
    if (a)
    {
        if (b)
        {
            if (c)
            {
                return true;
            }
            return false;
        }
        return false;
    }
    return false;
}

In plaats van:

C#:

bool func(bool a, bool b, bool c)
{
    if (a)
    {
        if (b)
        {
            return c;
        }
        return false;
    }
    return false;
}

Dit komt namelijk veel meer overeen met de && versie, en dit is ook exact de situatie uit deze topic (waar ((BreadCrumb)obj).position == this.position werd geretourneerd ipv dat die ook werd getest in een if). En als je goed kijkt naar de gegenereerde instructies van dit tweede voorbeeld en de mogelijke codepaden die een interpreter zou nemen, dan zie je dat de uiteindelijke uitgevoerde instructies exact identiek zijn (dit geldt ook voor jouw versie 2 en 3).

De reden waarom het in debug en release verschilt is omdat je breakpoints wilt kunnen plaatsen. Op het moment dat die bytecode weg wordt gecompileerd kan dat niet meer. Het moge duidelijk zijn dat de code gegenereerd in debug configurations natuurlijk sowieso onbelangrijk is voor performance measurements.

[ Voor 51% gewijzigd door .oisyn op 05-07-2009 23:00 ]

[Phyxion]

.oisyn schreef op zondag 05 juli 2009 @ 22:50:
[...]

Het had fijn geweest als je ook de sourcecode erbij had gezet. Ik gok namelijk dat je dit hebt geschreven:

C#:

bool func(bool a, bool b, bool c)
{
    if (a)
    {
        if (b)
        {
            if (c)
            {
                return true;
            }
            return false;
        }
        return false;
    }
    return false;
}

In plaats van:

C#:

bool func(bool a, bool b, bool c)
{
    if (a)
    {
        if (b)
        {
            return c;
        }
        return false;
    }
    return false;
}

Dit komt namelijk veel meer overeen met de && versie, en dit is ook exact de situatie uit deze topic (waar ((BreadCrumb)obj).position == this.position werd geretourneerd ipv dat die ook werd getest in een if). En als je goed kijkt naar de gegenereerde instructies van dit tweede voorbeeld en de mogelijke codepaden die een interpreter zou nemen, dan zie je dat de uiteindelijke uitgevoerde instructies exact identiek zijn (dit geldt ook voor jouw versie 2 en 3).

De reden waarom het in debug en release verschilt is omdat je breakpoints wilt kunnen plaatsen. Op het moment dat die bytecode weg wordt gecompileerd kan dat niet meer. Het moge duidelijk zijn dat de code gegenereerd in debug configurations natuurlijk sowieso onbelangrijk is voor performance measurements.

Ik had de niet geoptimaliseerde versie ongeveer zoals je eerste block, de twee was echter dit:

C#:

if (a)
   if (b)
      if (c)
          return true;
return false;

Gebruik je echter && dan scheelt het toch, dus dit:

C#:

return a && b && c;

En debug is inderdaad geen goed meetsysteem, maar als je even geen brackets gebruikt om nops tegen te gaan zie je dat de debug er wel verschil in aan brengt, maar op release het zo slim is dat het meteen goed wordt omgezet

[Not Pingu]

CAPSLOCK2000 schreef op vrijdag 03 juli 2009 @ 14:33:
[...]


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.

Manhattan distance is al niet meer zo handig als je ook diagonale stappen toelaat. Gebruik gewoon Euclidean distance (maw. de stelling van Pythagoras).

[roy-t]

Not Pingu schreef op maandag 06 juli 2009 @ 09:31:
[...]


Manhattan distance is al niet meer zo handig als je ook diagonale stappen toelaat. Gebruik gewoon Euclidean distance (maw. de stelling van Pythagoras).

Ik ga vanmiddag hier weer mee verder, maar ik vraag me wel af hoe je dit oplost in 3D, in 2D kun je makkelijk pythagoras gebruiken, maar hoe zit het in 3D? Ik kan natuurlijk 2D Pythagoras + verschil z doen, maarja dat is maar net iets beter dan manhattan. Hmmm.

[Marcj]

Pythogoras werkt in 3D net zo als in 2D:

D² = dx² + dy² + dz²

[PrisonerOfPain]

roy-t schreef op maandag 06 juli 2009 @ 11:07:
[...]


Ik ga vanmiddag hier weer mee verder, maar ik vraag me wel af hoe je dit oplost in 3D, in 2D kun je makkelijk pythagoras gebruiken, maar hoe zit het in 3D? Ik kan natuurlijk 2D Pythagoras + verschil z doen, maarja dat is maar net iets beter dan manhattan. Hmmm.

Pythagoras is enorm eenvoudig, je pakt gewoon de lengte van de edge tussen twee punten.

code:

Vector3 start;
Vector3 end;

float distance = (end - start).Length();

Mocht je gaan optimaliseren kun je in squared distance space gaan werken; dat scheelt in iedergeval een sqrt-aanroep in je distance heuristic. Dan hoef je alleen maar LengthSquared() te gebruiken ipv Length().

[ Voor 15% gewijzigd door PrisonerOfPain op 06-07-2009 12:25 ]

[roy-t]

PrisonerOfPain schreef op maandag 06 juli 2009 @ 12:23:
[...]


Pythagoras is enorm eenvoudig, je pakt gewoon de lengte van de edge tussen twee punten.

code:

Vector3 start;
Vector3 end;

float distance = (end - start).Length();

Mocht je gaan optimaliseren kun je in squared distance space gaan werken; dat scheelt in iedergeval een sqrt-aanroep in je distance heuristic. Dan hoef je alleen maar LengthSquared() te gebruiken ipv Length().

Doh! Bedankt voor de tip, ik zal even kijken of ik LengthSquared kan gebruiken, zou opzich moeten kunnen.

[Not Pingu]

LengthSquared kan zolang je het alleen gebruikt om te vergelijken met andere lengtes in kwadraat. Dus als heuristiek voldoet het, maar niet om je daadwerkelijke pad op te meten oid.

[.oisyn]

Phyxion schreef op maandag 06 juli 2009 @ 08:25:
[...]

Ik had de niet geoptimaliseerde versie ongeveer zoals je eerste block, de twee was echter dit:

C#:

if (a)
   if (b)
      if (c)
          return true;
return false;

Gebruik je echter && dan scheelt het toch, dus dit:

C#:

return a && b && c;

Zoals ik al zei, in de eerste variant return je true, in de tweede variant return je c. Als je de eerste variant schrijft als

C#:

if (a)
    if (b)
        return c;

Dan zijn ze exact identiek. En deze variant is ook zoals ie in deze topic staat, namelijk:

C#:

if (obj is BreadCrumb)  // if (a)
    return ((BreadCrumb)obj).position == this.position;  // return b;

[ Voor 11% gewijzigd door .oisyn op 06-07-2009 14:04 ]

[Phyxion]

.oisyn schreef op maandag 06 juli 2009 @ 14:02:
[...]

Zoals ik al zei, in de eerste variant return je true, in de tweede variant return je c. Als je de eerste variant schrijft als

C#:

if (a)
    if (b)
        return c;

Dan zijn ze exact identiek. En deze variant is ook zoals ie in deze topic staat, namelijk:

C#:

if (obj is BreadCrumb)  // if (a)
    return ((BreadCrumb)obj).position == this.position;  // return b;

Hm, inderdaad, je hebt gelijk Eigenlijk raar dat dat niet weggeoptimaliseerd wordt,

C#:

if (b)
   return true;

zou gewoon return b kunnen zijn in zulke gevallen, ik had verwacht dat dat ook wel meegenomen zou worden.

[.oisyn]

Bytecode wordt niet zo heel erg geoptimaliseerd. Daarom is het ook veel belangrijker wat de JITer er uiteindelijk van maakt.

[roy-t]

Hmm vandaag is even lekker bezig geweest met mieren en ervoor gezorgd dat A* nu correct is geimplementeerd, ontzettend dom van me om de heuristiek te vergeten (H score). Dat scheelde al een hoop tijd ook de Binary (Min) Heap maakte het een en ander sneller, even als wat tweaks aan ifjes en de score. Van een Vector3 (floats) naar een eigen gemaakte Point3D gaan scheelde niet heel veel maar alles is leuk als je het heel erg veel wilt gaan gebruiken .

Door nu gekwadrateerde scores te gebruiken kan ik ook de diff score (recht = 10, schuin is 14, schuin omhoog is 17). Veranderen naar 10,10,10 waarbij er dus voor elke 'diff' gewoon 10 opgeteld kan worden zonder array lookups of switches.

De tijd om in een 10x10x10 wereld een route van 0,0,0 naar 9,5,8 te vinden is nu gemiddeld 23ms (in release natuurlijk). t.o.v. 600ms eerst, een hele verbetering natuurlijk maar eigenlijk valt me het nog ietsjes tegen, dit is zeker werkbaar maar eigenlijk had ik gehoopt op zo'n 5 á 6ms.

Het is nu erg moeilijk om de bottleneck te vinden met gratis tools, sommige dingen die je denkt te kunnen versnellen zoals bijvoorbeeld een contains methode in de MinHeap binary search te laten gebruiken ipv. gewoon een loopje maken het juist net weer ietsjes trager. Ik vroeg me af of iemand nog een optie zag om deze code te optimaliseren, zelf heb ik er een paar een naar gekeken nadat de implementatie goed was, en hier en daar wat geschaafd maar ik krijg het zelf niet sneller. (Ik weet niet of het handig is om ook de MinHeap te laten zien? Deze is niet door mij gemaakt, maar alleen aangepast om een contains methode te hebben en de methode variabelen lokaal gemaakt0.

C#:

private static BreadCrumb FindPathReversed(World world, Point3D start, Point3D 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                        
            MinHeap2<BreadCrumb> openList = new MinHeap2<BreadCrumb>(256);
            MinHeap2<BreadCrumb> closedList = new MinHeap2<BreadCrumb>(128);
            BreadCrumb node;
            Point3D tmp;
            int cost;
            int diff;

            //Add the start node to the openList
            BreadCrumb current = new BreadCrumb(start);
            current.cost = 0;
            BreadCrumb finish = new BreadCrumb(end);
            openList.Add(current);

            //Stop if there are no more options
            while (openList.Count > 0)
            {                
                //because we are using a minheap we can just get the lowest scoring item
                //extract also removes it from the openlist                
                current = openList.ExtractFirst();
                //Switch that one over to the closed list                
                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
                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))
                    {
                        node = new BreadCrumb(tmp);
                        if (!closedList.Contains(node))
                        {
                            //Do scoring
                            diff = 0;
                            if (current.position.X != node.position.X)
                            {
                                diff += 10;
                            }
                            if (current.position.Y != node.position.Y)
                            {
                                diff += 10;
                            }
                            if (current.position.Z != node.position.Z)
                            {
                                diff += 10;
                            }
                            cost = current.cost + diff + node.position.GetDistanceSquared(end) * 10;
                            if (cost < node.cost)   //updates the cost only if the new cost is less                             
                            {
                                node.cost = cost;
                                node.next = current;
                            }

                            if (!openList.Contains(node))                            
                            {
                                if (node.Equals(finish)) //immediately stop when we find a good path
                                {
                                    node.next = current;
                                    return node;
                                }
                                openList.Add(node);
                            }                            
                        }
                    }
                }
            }
            return null; //no path found
        }                             

[Phyxion]

Je kan wel eens wat profilers proberen (ANTS Profiler heeft een 14 dagen trial).

[kasper_vk]

In het kader van de micro-optimalisaties, vraag ik me af of je de is-operator niet wilt vermijden indien mogelijk.
Overweeg daarom om je equals-methode aan te passen in:

C#:

public override bool Equals(object obj)
{
    BreadCrumb that = obj as BreadCrumb;
    return (that != null) && this.equals(that);
}

public bool Equals(BreadCrumb that)
{
    return that != null &&  that.position == this.position;
}

Waarom denk ik dat dit helpt?
Omdat bij a.equals(b) (met a is een BreadCrumb) de bovenste variant alleen aangeroepen zal worden wanneer @runtime niet zeker is dat b ook een BreadCrumb is. Als dit wel zeker is, zal de runtime omgeving direct de onderste variant aanroepen wat je de kosten van de as-operator (en de omringende if-else) bespaart.
In jouw variant zou ik hoedanook de combinatie van de is-operator gevolgd door een cast vervangen door gebruik van de as-operator, dat levert je zeker al besparing op.

Aangezien de equals methode nogal eens aangeroepen zal worden, kan een kleine verbetering hier toch meetbare resultaten geven.

[Soultaker]

Drie dingen. Ten eerste, hoe time je? Als het opstarten en uitvoeren van het hele proces 23ms duurt, zegt dat weinig over de executietijd van je algoritme. De Java VM starten duurt zo 100ms en dan heb je nog geen code geladen; ik weet niet precies hoe dat met C# zit, maar ik kan me voorstellen dat er soortgelijke overhead optreedt. Een algoritme moet je dus testen op grotere invoer zodat de totale runtime in de orde van enkele seconden zit en je de overhead van de JIT compiler enzo wat uitgesmeerd hebt over een zinnigere run. (Je kunt ook simpelweg dezelfde testcase 100 keer uitvoeren ofzo.)

Ten tweede, hoe heb je je Contains methode nu geïmplementeerd? Een binary heap ondersteunt geen efficiënte zoekoperatie; als je nu dus gewoon de hele (impliciete?) boom doorzoekt is dat niet bijster efficiënt.

Overigens implementeer ik Dijkstra/A* zelf meestal quick-and-dirty met een geordende set in plaats van een heap; echt optimaal is dat niet (zoals Nick the Heazk al aangaf) maar het fijne is dat je een aantal verschillende operaties relatief efficiënt (allemaal log N) uit kunt voeren:

• toestanden toevoegen
• minimum toestand vinden/verwijderen
• testen of een toestand voorkomt

Ten derde, en misschien wel belangrijkste: ben je er zeker van dat je het algoritme nu correct hebt geïmplementeerd? Het lijkt er op dat het mogelijk is dat items meerdere keren in zowel de open als de closed list terecht kunnen komen met verschillende scores. Klopt dat? Zo nee, waarom niet? (Hangt waarschijnlijk samen met de comparator die gebruikt wordt voor de heaps...)

(Ten vierde: is OpenList.Count wel een constante-tijd operatie en niet toevallig een lineaire? Is er geen Empty methode die hier beter geschikt is?)

[Phyxion]

Soultaker schreef op dinsdag 07 juli 2009 @ 09:36:
Drie dingen. Ten eerste, hoe time je? Als het opstarten en uitvoeren van het hele proces 23ms duurt, zegt dat weinig over de executietijd van je algoritme. De Java VM starten duurt zo 100ms en dan heb je nog geen code geladen; ik weet niet precies hoe dat met C# zit, maar ik kan me voorstellen dat er soortgelijke overhead optreedt. Een algoritme moet je dus testen op grotere invoer zodat de totale runtime in de orde van enkele seconden zit en je de overhead van de JIT compiler enzo wat uitgesmeerd hebt over een zinnigere run. (Je kunt ook simpelweg dezelfde testcase 100 keer uitvoeren ofzo.)

Ten tweede, hoe heb je je Contains methode nu geïmplementeerd? Een binary heap ondersteunt geen efficiënte zoekoperatie; als je nu dus gewoon de hele (impliciete?) boom doorzoekt is dat niet bijster efficiënt.

Overigens implementeer ik Dijkstra/A* zelf meestal quick-and-dirty met een geordende set in plaats van een heap; echt optimaal is dat niet (zoals Nick the Heazk al aangaf) maar het fijne is dat je een aantal verschillende operaties relatief efficiënt (allemaal log N) uit kunt voeren:

• toestanden toevoegen
• minimum toestand vinden/verwijderen
• testen of een toestand voorkomt

Ten derde, en misschien wel belangrijkste: ben je er zeker van dat je het algoritme nu correct hebt geïmplementeerd? Het lijkt er op dat het mogelijk is dat items meerdere keren in zowel de open als de closed list terecht kunnen komen met verschillende scores. Klopt dat? Zo nee, waarom niet? (Hangt waarschijnlijk samen met de comparator die gebruikt wordt voor de heaps...)

(Ten vierde: is OpenList.Count wel een constante-tijd operatie en niet toevallig een lineaire? Is er geen Empty methode die hier beter geschikt is?)

Count wordt bijna altijd bijgehouden in Lists.
Overigens kan je ook zelf een lijst maken als je altijd het laagste item nodig hebt. Deze kan je best bijhouden in een variabele en bij een insert/add vergelijken met de huidige.

[.oisyn]

Phyxion schreef op dinsdag 07 juli 2009 @ 09:44:
[...]

Count wordt bijna altijd bijgehouden in Lists.

Daar heb je het al . Sowieso is het aan te raden om bij het testen of een container leeg is altijd de Empty property te gebruiken als die bestaat ipv Count == 0. Dat een List een O(1) Count operatie heeft hoeft helemaal niet zo logisch te zijn. Met splice operaties wil je juist dat Count O(n) is, zodat de splices zelf in O(1) gedaan kunnen worden (anders moet tijdens een splice alsnog over de elementen gewandeld worden om de count te updaten)

En niet om te zeuren, maar is het echt nodig om een hele reactie te quoten als je alleen reageert op de laatste alinea, die bovendien ook nog eens recht boven je eigen post staat?

Soultaker schreef op dinsdag 07 juli 2009 @ 09:36:
Overigens implementeer ik Dijkstra/A* zelf meestal quick-and-dirty met een geordende set in plaats van een heap; echt optimaal is dat niet (zoals Nick the Heazk al aangaf) maar het fijne is dat je een aantal verschillende operaties relatief efficiënt (allemaal log N) uit kunt voeren:

• toestanden toevoegen
• minimum toestand vinden/verwijderen
• testen of een toestand voorkomt

Je zou ook kunnen overwegen om gebruik te maken van de combinatie van binary heap (of eigenlijk: priority queue, de binary heap is alleen maar de onderliggende opslagmethode) en hashtable. Vooral als het testen of een toestand voorkomt veel vaker gebruikt wordt dan de overige twee operaties (maar daarvoor ken ik A* niet goed genoeg)

[roy-t]

kasper_vk schreef op dinsdag 07 juli 2009 @ 09:35:
In het kader van de micro-optimalisaties, vraag ik me af of je de is-operator niet wilt vermijden indien mogelijk.
Overweeg daarom om je equals-methode aan te passen in:

C#:

public override bool Equals(object obj)
{
    BreadCrumb that = obj as BreadCrumb;
    return (that != null) && this.equals(that);
}

public bool Equals(BreadCrumb that)
{
    return that != null &&  that.position == this.position;
}

Waarom denk ik dat dit helpt?
Omdat bij a.equals(b) (met a is een BreadCrumb) de bovenste variant alleen aangeroepen zal worden wanneer @runtime niet zeker is dat b ook een BreadCrumb is. Als dit wel zeker is, zal de runtime omgeving direct de onderste variant aanroepen wat je de kosten van de as-operator (en de omringende if-else) bespaart.
In jouw variant zou ik hoedanook de combinatie van de is-operator gevolgd door een cast vervangen door gebruik van de as-operator, dat levert je zeker al besparing op.

Aangezien de equals methode nogal eens aangeroepen zal worden, kan een kleine verbetering hier toch meetbare resultaten geven.

Ik heb nu n.a.v. jouw tip een tweede equals operatie gemaakt (de eerste equals is een override en die kan ik niet in zoverre aanpassen zonder dat generics in de soep, die equals wordt dus altijd aangeroepen als het om een breadcrumb gaat en dat lijkt weer net heel iets sneller te gaan).

Soultaker schreef op dinsdag 07 juli 2009 @ 09:36:
Drie dingen. Ten eerste, hoe time je? Als het opstarten en uitvoeren van het hele proces 23ms duurt, zegt dat weinig over de executietijd van je algoritme. De Java VM starten duurt zo 100ms en dan heb je nog geen code geladen; ik weet niet precies hoe dat met C# zit, maar ik kan me voorstellen dat er soortgelijke overhead optreedt. Een algoritme moet je dus testen op grotere invoer zodat de totale runtime in de orde van enkele seconden zit en je de overhead van de JIT compiler enzo wat uitgesmeerd hebt over een zinnigere run. (Je kunt ook simpelweg dezelfde testcase 100 keer uitvoeren ofzo.)

-Ik test door één wereld te maken en daarna in een loop 100x dit algoritme uit te voeren over het zelfde pad, hiervan houd ik elke keer de tijd bij op de volgende manier:

C#:

for (int i = 0; i < 100; i++)
            {
                DateTime start = DateTime.Now;
                BreadCrumb crumb = PathFinder.FindPath(world, Point3D.Zero, new Point3D(5, 8, 9));
                TimeSpan ts = DateTime.Now - start;
                bench[i] = ts.TotalMilliseconds;                
            }

Hierna haal ik hier het gemiddelde, het minima en het maxima uit (met de nieuwe extension methods Min, Max en Sum die ik deel door 100).

Ten tweede, hoe heb je je Contains methode nu geïmplementeerd? Een binary heap ondersteunt geen efficiënte zoekoperatie; als je nu dus gewoon de hele (impliciete?) boom doorzoekt is dat niet bijster efficiënt.

Ik heb de Contains methode eerst quick 'n dirty geimplementeerd met een lineaire search, later heb ik dit aangepast naar een Binary search maar die bleek een stuk trager te zijn, na wat onderzoeken bleek dat deze versie van een MinHeap niet alles in volgorde zet maar er wel voor zorgt dat het laagste getal voor aan staat (dat heb ik gechecked door tijdelijk de interne array public te maken en via een lineaire search eerst de kleinste cost te vinden en daarna te kijken of die ook gevonden word).

Overigens implementeer ik Dijkstra/A* zelf meestal quick-and-dirty met een geordende set in plaats van een heap; echt optimaal is dat niet (zoals Nick the Heazk al aangaf) maar het fijne is dat je een aantal verschillende operaties relatief efficiënt (allemaal log N) uit kunt voeren:

• toestanden toevoegen
• minimum toestand vinden/verwijderen
• testen of een toestand voorkomt

Toestanden toevoegen is op dit moment O(n) O(log(n)) (tenminste als ik heel eerlijk ben snap ik de add methode niet exact, ik gebruik de binaryheap implementatie van ( http://www.koders.com/csh...A6D6F2A43A.aspx?s=MinHeap die ik lichtjes heb aangepast (zorgen dat variabelen minder vaak gereserveerd hoeven worden en Contains er in). minimum vinden is O(1) en testen of een toestand voorkomt is ook O(n).

Ten derde, en misschien wel belangrijkste: ben je er zeker van dat je het algoritme nu correct hebt geïmplementeerd? Het lijkt er op dat het mogelijk is dat items meerdere keren in zowel de open als de closed list terecht kunnen komen met verschillende scores. Klopt dat? Zo nee, waarom niet? (Hangt waarschijnlijk samen met de comparator die gebruikt wordt voor de heaps...)

Dat kan niet voorkomen, de comparator vergelijkt namelijk alleen op positie, score en parent worden niet mee genomen. Als een item al in de openList zat (zelfde positie heeft als nieuwe item) dan wordt deze niet nogmaals toegevoegd aan de openList (contains check). Wel word er gekeken of er via het huidige pad sneller daar gekomen kan worden zoja wordt die score aangepast.

Voor de closedList geld hetzelfde (alleen daar worden scores niet opnieuw voor berekend).

(Ten vierde: is OpenList.Count wel een constante-tijd operatie en niet toevallig een lineaire? Is er geen Empty methode die hier beter geschikt is?)

OpenList.Count returned gewooon count; deze wordt netjes bijgehouden.

quote: .Oisyn

Je zou ook kunnen overwegen om gebruik te maken van de combinatie van (of eigenlijk: priority queue, de binary heap is alleen maar de onderliggende opslagmethode) en hashtable. Vooral als het testen of een toestand voorkomt veel vaker gebruikt wordt dan de overige twee operaties (maar daarvoor ken ik A* niet goed genoeg)

Dat klinkt erg interessant, ExtractFirst wordt maar 1x per iteratie gedaan, Add wordt 1x~26x per iteratie gedaan. Contains wordt 26~52x per iteratie gedaan. Het lijkt er dus op dat de meest efficientste operatie (ExtractFirst) eigenlijk het minste wordt uitgevoerd. Ik snap alleen niet helemaal hoe jij je de combinatie hashtable+priorityqueue+binary heap voor je ziet. (Nu komen we ook echt op een vlak waar ik me nog niet mee bezig gehouden heb voor normale toepassingen waar ik aan werk hoef je meestal niet verder dan List )


Edit: verder heb ik ook het grote 'if blok' wat checked of een positie legaal is weggehaald en verplaatst naar de world class zodat jue niet de properties hoeft te gebruiken maar dat de world zelf bepaald of een positie legaal is en zoja checked of die vrij is. Al deze micro optimalisaties ten spijt is de snelheid niet echt omhoog gegaan (gemiddeld 22ms, min 19ms).

[ Voor 4% gewijzigd door roy-t op 07-07-2009 11:06 ]

[Soultaker]

roy-t schreef op dinsdag 07 juli 2009 @ 10:58:
Ik heb de Contains methode eerst quick 'n dirty geimplementeerd met een lineaire search, later heb ik dit aangepast naar een Binary search maar die bleek een stuk trager te zijn [..]

Trager is niet je grootste probleem; het werkt niet eens.

.. minimum vinden is O(1) en testen of een toestand voorkomt is ook O(n).

Minimum verwijderen is O(log N) denk ik. Maar het probleem is dus het lineaire zoeken; dat is gewoon de bottleneck in je huidige implementatie daar moet je wat aan doen.

Dat kan niet voorkomen, de comparator vergelijkt namelijk alleen op positie, score en parent worden niet mee genomen.

OK, ook prima.

.oisyn schreef op dinsdag 07 juli 2009 @ 10:21:
Je zou ook kunnen overwegen om gebruik te maken van de combinatie van binary heap (of eigenlijk: priority queue, de binary heap is alleen maar de onderliggende opslagmethode) en hashtable. Vooral als het testen of een toestand voorkomt veel vaker gebruikt wordt dan de overige twee operaties (maar daarvoor ken ik A* niet goed genoeg)

Dit is een goede methode, maar er kleeft een nadeel aan: niet alle priority queues supporten het verwijderen (of updaten) van items in de queue (de C++ priority_queue niet, bijvoorbeeld). Dit hoeft geen probleem te zijn; als je een graaf hebt met weinig edges pleur je gewoon alle buren in de queue (en dan moet je oppassen dat je ze toch maar één keer verwerkt door na het extracten te checken of het huidige gewicht wel beter is dan de voorlopige waarde), maar als je veel impliciete edges hebt (zoals ook in het probleem van de TS: in principe werkt hij met een volledige graaf) kan die overhead onwenselijk zijn.

Dan kun je dus wel weer een meer fancy heap implementatie zoeken/schrijven natuurlijk, en daar is ook niets mis mee, maar het is i.m.o. wel aardig om met simpelere datastructuren te beginnen.

[ Voor 44% gewijzigd door Soultaker op 07-07-2009 11:44 ]

[kasper_vk]

roy-t schreef op dinsdag 07 juli 2009 @ 10:58:
[...]


Ik heb nu n.a.v. jouw tip een tweede equals operatie gemaakt (de eerste equals is een override en die kan ik niet in zoverre aanpassen zonder dat generics in de soep, die equals wordt dus altijd aangeroepen als het om een breadcrumb gaat en dat lijkt weer net heel iets sneller te gaan).

2 dingen:
De truuk werkt inderdaad niet, omdat ik vergeten was dat BreadCrumb dan ook de interface IEquatable<T> moet implementeren (my bad). In de documentatie van List<T> staat namelijk:

The List<(Of <(T>)>) class uses both an equality comparer and an ordering comparer.

* Methods such as Contains, IndexOf, LastIndexOf, and Remove use an equality comparer for the list elements. The default equality comparer for type T is determined as follows. If type T implements the IEquatable<(Of <(T>)>) generic interface, then the equality comparer is the Equals(T) method of that interface; otherwise, the default equality comparer is Object..::.Equals(Object).

Tweede ding: wat bedoel je met
de eerste equals is een override en die kan ik niet in zoverre aanpassen zonder dat generics in de soep loopt ?

[ Voor 2% gewijzigd door kasper_vk op 07-07-2009 12:02 . Reden: linkje naar MSDN docs van List<T> toegevoegd ]

[Zoijar]

Als je 3d grid groot is kan je het opslaan als space-filling curve. Dat zorgt ervoor dat je memory locality veel beter wordt en daardoor het aantal cache misses omlaag gaat. Die micro-optimalisaties hebben waarschijnlijk geen enkel nut; waar het meestal om draait is het aantal cache misses.

[roy-t]

kasper_vk schreef op dinsdag 07 juli 2009 @ 11:41:
[...]

2 dingen:
De truuk werkt inderdaad niet, omdat ik vergeten was dat BreadCrumb dan ook de interface IEquatable<T> moet implementeren (my bad). In de documentatie van List<T> staat namelijk:

[...]


Tweede ding: wat bedoel je met
de eerste equals is een override en die kan ik niet in zoverre aanpassen zonder dat generics in de soep loopt ?

Ah my bad, in een list gebruikt de contains de equals methode die je override (omdat je inherit van Object), in de MinHeap is dit niet het geval, ik bedoelde dat ik de signature niet aan kon passen omdat ik hem override maar dat was een beetje nutteloze informatie.

quote: Soultaker

Minimum verwijderen is O(log N) denk ik. Maar het probleem is dus het lineaire zoeken; dat is gewoon de bottleneck in je huidige implementatie daar moet je wat aan doen.

Doh, natuurlijk die nuance op verwijderen en vinden is belangrijk. .

Maar hmm ik ga morgen is aan de slag met proberen van het vinden van een betere methode voor contains./ een andere datastructuur daarbij

@Zoijar

Ik heb even opgezocht wat een Space Filling Curve is, ik snap dat op die manier je punten dus als een lijn (curve) kan weergeven waardoor de buren altijd maar 1 stapje in geheugen ver weg zijn (als je ze allemaal in 1x na gaat). Maar hoe dit nu echt voordeel geeft zie ik niet meteen. Ook houd je toch chache misses omdat je soms naar rechts gaat en soms naar links (en de curve zelf staat op 1 bepaalde manier geoorderd).

[ Voor 15% gewijzigd door roy-t op 07-07-2009 12:02 ]

[Zoijar]

roy-t schreef op dinsdag 07 juli 2009 @ 11:58:
@Zoijar

Ik heb even opgezocht wat een Space Filling Curve is, ik snap dat op die manier je punten dus als een lijn (curve) kan weergeven waardoor de buren altijd maar 1 stapje in geheugen ver weg zijn (als je ze allemaal in 1x na gaat). Maar hoe dit nu echt voordeel geeft zie ik niet meteen. Ook houd je toch chache misses omdat je soms naar rechts gaat en soms naar links (en de curve zelf staat op 1 bepaalde manier geoorderd).

Het gaat erom dat een locatie en al zijn buren dan in een enkele cacheline passen (of misschien 2). Als je dan dus een locatie ophaalt uit geheugen, en vervolgens al zijn buren afscanned, dan staan al die buren al in de cache. Het hoeft niet direct naast elkaar te staan, als het maar binnen de 64-256 bytes oid valt, afhangend van de grootte van je cache lines.

De meeste optimalisaties bestaan tegenwoordig uit "locality of reference" optimalisaties. Dat zie je ook bijvoorbeeld bij raytracers: alles draait om cache misses te minimaliseren. Ik heb je code verder niet helemaal doorgelezen, dus dit was meer een algemeen idee.

[Nick The Heazk]

roy-t schreef op dinsdag 07 juli 2009 @ 10:58:
-Ik test door één wereld te maken en daarna in een loop 100x dit algoritme uit te voeren over het zelfde pad, hiervan houd ik elke keer de tijd bij op de volgende manier:

C#:

for (int i = 0; i < 100; i++)
            {
                DateTime start = DateTime.Now;
                BreadCrumb crumb = PathFinder.FindPath(world, Point3D.Zero, new Point3D(5, 8, 9));
                TimeSpan ts = DateTime.Now - start;
                bench[i] = ts.TotalMilliseconds;                
            }

Hierna haal ik hier het gemiddelde, het minima en het maxima uit (met de nieuwe extension methods Min, Max en Sum die ik deel door 100).

Pleur het starten en stoppen van je timer eens buiten de lus en deel dan door het aantal iteraties. Dat geeft veel nauwkeurigere tijdsmetingen indien de tijden zo klein zijn.

Ik heb de Contains methode eerst quick 'n dirty geimplementeerd met een lineaire search, later heb ik dit aangepast naar een Binary search maar die bleek een stuk trager te zijn, na wat onderzoeken bleek dat deze versie van een MinHeap niet alles in volgorde zet maar er wel voor zorgt dat het laagste getal voor aan staat (dat heb ik gechecked door tijdelijk de interne array public te maken en via een lineaire search eerst de kleinste cost te vinden en daarna te kijken of die ook gevonden word).

Daar ligt dus je probleem, zoals Soultaker ook reeds aangaf. In je inwendige lus ga je steeds de contains methode oproepen op de closedList en openList. Dit is natuurlijk erg kostbaar als je nog eens gaat lineair zoeken. Blijkbaar heb ik me ook vergist; het zoeken naar een willekeurig element in een heap kan niet in O( lg n ). Je kunt wel iets beter dan gewoon lineair zoeken, maar het maken van deze aanpassing zal waarschijnlijk geen significante verbetering opleveren.

Zoals door .oisyn werd aangedragen is het geen slecht idee om de openList te implementeren met behulp van twee datastructuren (hierdoor creëer je natuurlijk een O(n) overhead in je geheugengebruik). Je gebruikt een heap datastructuur om het minimum te bepalen in O( lg n ) (of O(1), afhankelijk van het soort heap dat je gebruikt) bewerkingen. Een hashmap kun je vervolgens gebruiken om in O(1) bewerkingen te bepalen of een element zich in de openList bevindt. Aangezien je deze operatie veelvuldig nodig hebt, kan zulk een dubbele datastructuur een belangrijke verbetering in de uitvoeringstijd geven (maar waarschijnlijk niet eens merkbaar op de kleine problemen die jij gebruikt; kijk eens naar het verschil op een 100x100 grid).

Zoals ik eerder al opmerkte, maak je een betere kans om de uitvoeringstijd te verbeteren door de closedList te implementeren als een hashtable. Je moet immers enkel bepalen of een element zich in de closedList bevindt. Met een hashtable kan dit in O(1) in tegenstelling tot de O(n) die je nu hebt. Verder vergt het toevoegen aan de closedList in jouw implementatie een totaal aantal bewerkingen van de orde n lg n. Met een hashtable kan het met een totaal van O(n) bewerkingen.

Dat klinkt erg interessant, ExtractFirst wordt maar 1x per iteratie gedaan, Add wordt 1x~26x per iteratie gedaan. Contains wordt 26~52x per iteratie gedaan. Het lijkt er dus op dat de meest efficientste operatie (ExtractFirst) eigenlijk het minste wordt uitgevoerd. Ik snap alleen niet helemaal hoe jij je de combinatie hashtable+priorityqueue+binary heap voor je ziet. (Nu komen we ook echt op een vlak waar ik me nog niet mee bezig gehouden heb voor normale toepassingen waar ik aan werk hoef je meestal niet verder dan List )

Zoals hierboven.

Al deze micro optimalisaties ten spijt is de snelheid niet echt omhoog gegaan (gemiddeld 22ms, min 19ms).

Zoals Zoijar ook al aangaf boeit het voor geen meter welke micro-optimalisaties je nu al zou willen toepassen. Op dit moment is het overduidelijk dat de trage uitvoeringstijd een gevolg is van een slechte selectie van algoritmen en datastructuren. Alle mirco-optimalisaties die sommigen voorstellen, vallen onder het kopje "premature optimization", hetgeen meteen ook "the root of all evil" is, althans volgens een prominente computerwetenschapper.

Edit: Wat Zoijar ook aangeeft met betrekking tot efficiënt gebruik van de cache-hiërarchie is ook belangrijk. Deze problemen zullen op dit soort kleine problemen waarschijnlijk nog geen belangrijke impact hebben op de uitvoeringstijd (omdat het meeste toch wel in het cache past, mbv prefetching). Men moet hier zeker rekening mee houden, maar waarschijnlijk is het nu nog niet het geschikte moment. Zoals Soultaker hier onder mij ook al aangeeft. /me Is weer eens te traag.

[ Voor 5% gewijzigd door Nick The Heazk op 07-07-2009 12:25 ]

[Soultaker]

(Ik vind Zoijar's voorstel om de geheugentoegang te optimaliseren anders ook al een behoorlijke micro-optimalisatie terwijl de TS in z'n binnenste lus nog een O(N) operatie uitvoert die O(log N) of O(1) kan zijn!)

[ Voor 7% gewijzigd door Soultaker op 07-07-2009 12:20 . Reden: ik kan echt niet typen ]

[pedorus]

roy-t schreef op dinsdag 07 juli 2009 @ 11:58:
Maar hmm ik ga morgen is aan de slag met proberen van het vinden van een betere methode voor contains./ een andere datastructuur daarbij

Dit is inderdaad het belangrijkste. Die keren dat je Contains gebruikt moeten naar O(1) dmv een hashtable (dictionary), of gewoon een 3d array (beter bij wereldomspannende routes). ClosedList kan gecombineerd worden met OpenList als Dictionary, eventueel met een tagje voor gesloten nodes, maar dat hoeft niet perse aangezien de kosten van gesloten nodes toch al altijd lager zijn. Van OpenList moet je ook een Heap hebben, zoals je die nu al hebt. Nodes zitten dus zowel in die O(1)-lookup structuur als in de Heap, zodat je ze makkelijk kan opzoeken en eventueel een DecreaseKey kan doen. Wat je niet moet hebben is dat je de Heap af moet gaan zoeken naar een node. Opzoeken moet en kan gewoon O(1) zijn, ook als je de een DecreaseKey-operatie gaat doen en de Node in de heap verplaatst moet worden.

Enkel het gekke is dat de Heap die je nu gebruikt geeneens een DecreaseKey aankan. Het algoritme dat je nu hebt kan weinig met A* te maken hebben. Die vergelijking met node.cost doet waarschijnlijk ook niks omdat je vergelijkt met de oneindige kosten van een nieuwe node? In het geval van Dijkstra was dat geen probleem in dit geval, maar met A* kun je een verschil in route krijgen. Als testje kun je trouwens current.cost+diff eens weglaten op regel 54, want ik geloof dat de kortste weg toch niet echt boeide. Of dat een goed idee is, hangt van de wereld af; dit lijkt me vooral goed werken als er alleen kleine, losse obstakels zijn.

Aangezien je niet zo heel veel verschillende scores hebt, op zeer gelijkmatige afstand, zou hier een calendar queue best wel eens O(1) ipv O(log(n)) performance kunnen geven. Zo'n calendar queue is hier gewoon een array, met per afstand een vakje, en in ieder vakje een (doubly-)linked list met bijbehorende nodes. Hier heb je maar zo'n 10*10*10=1000 vakjes nodig als je de vakjes niet hergebruikt, en je geen gekke omweg hoef te maken. Die kun je zeer snel afwerken natuurlijk. Ik ga er hier trouwens even vanuit dat je manhattan-distances gebruikt, het kan natuurlijk ook zijn dat de huidige score-berekening niet klopt, of dat ik scheef aan het kijken ben.

Let er namelijk op dat als a=b+c geldt niet perse a^2=b^2+c^2 ook geldt he.. Daarnaast, aangezien scorediff alleen van i afhangt, kun je misschien netzogoed wel scorediff even van te voren berekenen... Het kan dan gelijk bij surroundings zitten. Aan de andere kant is is dit een microoptimalisatie. Waarom trouwens 10 en niet gewoon 1?

Die if-jes op de boundaries van world kunnen naar positionIsFree toe, waar je waarschijnlijk een 3d array gebruikt waar boundaries opnieuw worden gecheckt. Als je Length gebruikt heeft .NET door dat dit niet opnieuw hoeft (misschien nu ook trouwens, ongetest, sowieso is dit een micro-optimalisatie).

Als je de finish tegenkomt, dan hoeft dit niet perse te zeggen dat je de snelste oplossing hebt, dat gebeurd namelijk pas als je de finish tegenkomt als node bij ExtractFirst. Die vergelijking staat dus fout.

Verder zou je gebruik kunnen maken van verschillende surroundings, afhankelijk van hoe je bij een node bent gekomen. Teruggaan, of naar een van de vakjes gaan die ook vanaf de vorige node bereikbaar zijn is onzin. In surroundings kun je naast de kosten dan gelijk een 'nextSurroundings' hebben die in de BreadCrumb opgeslagen wordt.

offtopic:
Sorry, verhaal is te lang geworden

[Zoijar]

Soultaker schreef op dinsdag 07 juli 2009 @ 12:19:
(Ik vind Zoijar's voorstel om de geheugentoegang te optimaliseren anders ook al een behoorlijke micro-optimalisatie terwijl de TS in z'n binnenste lus nog een O(N) operatie uitvoert die O(log N) of O(1) kan zijn!)

Heb ik verder niet op gelet Memory access lijkt overigens een micro optimalisatie, maar kan code soms echt 5 keer zo snel maken.

[riezebosch]

roy-t schreef op dinsdag 07 juli 2009 @ 10:58:
[...]
-Ik test door één wereld te maken en daarna in een loop 100x dit algoritme uit te voeren over het zelfde pad, hiervan houd ik elke keer de tijd bij op de volgende manier:

C#:

for (int i = 0; i < 100; i++)
            {
                DateTime start = DateTime.Now;
                BreadCrumb crumb = PathFinder.FindPath(world, Point3D.Zero, new Point3D(5, 8, 9));
                TimeSpan ts = DateTime.Now - start;
                bench[i] = ts.TotalMilliseconds;                
            }

Tip: System.Diagnostics.Stopwatch.

C#:

StopWatch sw = StopWatch.StartNew();
...
sw.Stop();
sw.Elapsed;

[Nick The Heazk]

pedorus schreef op dinsdag 07 juli 2009 @ 12:31:
Dit is inderdaad het belangrijkste. Die keren dat je Contains gebruikt moeten naar O(1) dmv een hashtable (dictionary), of gewoon een 3d array (beter bij wereldomspannende routes). ClosedList kan gecombineerd worden met OpenList als Dictionary, eventueel met een tagje voor gesloten nodes, maar dat hoeft niet perse aangezien de kosten van gesloten nodes toch al altijd lager zijn. Van OpenList moet je ook een Heap hebben, zoals je die nu al hebt. Nodes zitten dus zowel in die O(1)-lookup structuur als in de Heap, zodat je ze makkelijk kan opzoeken en eventueel een DecreaseKey kan doen. Wat je niet moet hebben is dat je de Heap af moet gaan zoeken naar een node. Opzoeken moet en kan gewoon O(1) zijn, ook als je de een DecreaseKey-operatie gaat doen en de Node in de heap verplaatst moet worden.

Strakke observatie. Door voor de openList en closedList een hashtable te voorzien, waarbij de nodes uitgebreid worden met een tag, kun je er dus voor zorgen dat je (bijna) geen geheugenoverhead hebt. Daarnaast blijft het voordeel van de snelle toegangen behouden.

Enkel het gekke is dat de Heap die je nu gebruikt geeneens een DecreaseKey aankan. Het algoritme dat je nu hebt kan weinig met A* te maken hebben.

Eveneens een alerte observatie. De TS update bijvoorbeeld ook niet de score indien een knoop reeds in de openList zit. Dit is net de operatie die men met een decreaseKey operatie zal willen bewerkstelligen (omdat de score nu afneemt).

Ik ga er hier trouwens even vanuit dat je manhattan-distances gebruikt, het kan natuurlijk ook zijn dat de huidige score-berekening niet klopt, of dat ik scheef aan het kijken ben.

Ik vraag me eigenlijk ook af waar de heuristische schatting nu wordt toegevoegd? Mijn inziens gaat het algoritme van de TS zo snel omdat men bij de eerste keer dat men het einde tegenkomt, stopt (zoals pedorus ook opmerkte).. Ah daar (regel 54, laatste term).

Als je de finish tegenkomt, dan hoeft dit niet perse te zeggen dat je de snelste oplossing hebt, dat gebeurd namelijk pas als je de finish tegenkomt als node bij ExtractFirst. Die vergelijking staat dus fout.

Correct. Laat dit nu overigens een belangrijke bron van overhead zijn. Eigenlijk zijn we hier allen weer met premature optimizations bezig, mezelf incluis. Voordat je daar ook maar aan mag denken, ga je best eerst na dat je algoritme correct werk. Merk trouwens op dat als je deze test verwijdert, je huidige implementatie met een heap wel goed is; je moet immers niet meer nagaan of een bepaald element al dan niet in de openList zit.

Verder zou je gebruik kunnen maken van verschillende surroundings, afhankelijk van hoe je bij een node bent gekomen. Teruggaan, of naar een van de vakjes gaan die ook vanaf de vorige node bereikbaar zijn is onzin. In surroundings kun je naast de kosten dan gelijk een 'nextSurroundings' hebben die in de BreadCrumb opgeslagen wordt.

Voor een correcte implementatie van A* zal dat niet zoveel uitmaken; je kan in O(1) tijd bepalen dat het niet zinvol is om die knoop opnieuw toe te voegen aan de openList, omdat deze toch al in de closedList zit. Het elimineren van deze voorganger is ook een O(1) operatie, maar mogelijk een met een kleinere constante.

[roy-t]

pedorus schreef op dinsdag 07 juli 2009 @ 12:31:
[...]

Dit is inderdaad het belangrijkste. Die keren dat je Contains gebruikt moeten naar O(1) dmv een hashtable (dictionary), of gewoon een 3d array (beter bij wereldomspannende routes). ClosedList kan gecombineerd worden met OpenList als Dictionary, eventueel met een tagje voor gesloten nodes, maar dat hoeft niet perse aangezien de kosten van gesloten nodes toch al altijd lager zijn. Van OpenList moet je ook een Heap hebben, zoals je die nu al hebt. Nodes zitten dus zowel in die O(1)-lookup structuur als in de Heap, zodat je ze makkelijk kan opzoeken en eventueel een DecreaseKey kan doen. Wat je niet moet hebben is dat je de Heap af moet gaan zoeken naar een node. Opzoeken moet en kan gewoon O(1) zijn, ook als je de een DecreaseKey-operatie gaat doen en de Node in de heap verplaatst moet worden.

Goede tip . Ik heb van de ClosedList een HashSet<> gemaakt en de gemiddelde executie tijd ging meteen met 9ms naar beneden (1/3 er af). Als ik dat zelfde kan fixen met de OpenList (ga ik nu mee pielen) dan ben ik waar ik wil zijn .

Edit: Ik heb ook de MinHeap aangepast om zowel een HashSet<> als zichzelf te gebruiken, hiermee heb ik nog bijna 1/4 van de laatste executie tijd er af weten te halen, Contains is nu dus 'altijd' O(1), misschien dat er nog iets te winnen is met mijn manier van hashen (ik gebruik gewoon toString().getHashCode(); Maar nu kan ik iig in gemiddeld 11ms (min 8ms) een 10x10x10 gebied doorzoeken, natuurlijk probeer ik er nog wat uit te persen maar dit is wel ongeveer zo snel als ik het wil hebben .

Enkel het gekke is dat de Heap die je nu gebruikt geeneens een DecreaseKey aankan. Het algoritme dat je nu hebt kan weinig met A* te maken hebben. Die vergelijking met node.cost doet waarschijnlijk ook niks omdat je vergelijkt met de oneindige kosten van een nieuwe node? In het geval van Dijkstra was dat geen probleem in dit geval, maar met A* kun je een verschil in route krijgen. Als testje kun je trouwens current.cost+diff eens weglaten op regel 54, want ik geloof dat de kortste weg toch niet echt boeide. Of dat een goed idee is, hangt van de wereld af; dit lijkt me vooral goed werken als er alleen kleine, losse obstakels zijn.

Nee dit wordt af en toe vergeleken met int.maximum, maar je komt ook items tegen die al in de closed list zitten (dus al een score hebben) dan controleer je (puur A* zover ik weet btw). Of je dat hokje goedkoper kan berijken vanaf het huidige pad, vandaar de vergelijking van scores.

Current.cost+diff weglaten lijkt me ook zeer onverstanding omdat je dan in de score niet mee neemt hoe duur het was om daar te komen, maar alleen mee neemt hoe duur het is om bij het einde te komen (geschat). Dit gooit het hele idee van F=G+H weg wat je in A* standaard hebt. (G is dus current.cost+diff, wat de kosten is om van de start daar te komen) en H is heuristieke schatting om op het einde te komen. Ik gebruik trouwens geen Manhattan distance maar pythagoras over 3D zoals hier boven voorgesteld werd. (Kon je mogelijk zien aan de GetDistanceSquared en het feit dat de diff scores niet 1, 1.4, 1.7 zijn maar 10, 20, 30 (+10 voor elke diff) wat de kwadraten daar van zijn (alles *10 om ints te houden ipv floats).

Aangezien je niet zo heel veel verschillende scores hebt, op zeer gelijkmatige afstand, zou hier een calendar queue best wel eens O(1) ipv O(log(n)) performance kunnen geven. Zo'n calendar queue is hier gewoon een array, met per afstand een vakje, en in ieder vakje een (doubly-)linked list met bijbehorende nodes. Hier heb je maar zo'n 10*10*10=1000 vakjes nodig als je de vakjes niet hergebruikt, en je geen gekke omweg hoef te maken. Die kun je zeer snel afwerken natuurlijk.
Daarnaast, aangezien scorediff alleen van i afhangt, kun je misschien netzogoed wel scorediff even van te voren berekenen... Het kan dan gelijk bij surroundings zitten. Aan de andere kant is is dit een microoptimalisatie. Waarom trouwens 10 en niet gewoon 1?

Dat klopt ik zou idd scorediff van i kunnen laten afhangen, dat zou weer net wat ifjes schelen en is zeker het proberen waard, *10 is een oud artefact van toen ik nog niet de squared distances gebruikte, dat kan ik idd even weghalen.

Die if-jes op de boundaries van world kunnen naar positionIsFree toe, waar je waarschijnlijk een 3d array gebruikt waar boundaries opnieuw worden gecheckt. Als je Length gebruikt heeft .NET door dat dit niet opnieuw hoeft (misschien nu ook trouwens, ongetest, sowieso is dit een micro-optimalisatie).

Zoals aangegeven is dit al gebeurd .

Als je de finish tegenkomt, dan hoeft dit niet perse te zeggen dat je de snelste oplossing hebt, dat gebeurd namelijk pas als je de finish tegenkomt als node bij ExtractFirst. Die vergelijking staat dus fout.

Klopt dit kan precies 1 stapje verkeerd gaan, je kunt immers nog de score verbeteren via andere buren in die lus, echter kan dit alleen verkeerd gaan als je andere scores per stap hebt, de maximale afwijking in score is in mijn geval dus 2. (rechte stap versus 'dubbel schuin'). Ik heb er expliciet voor gekozen om dit niet bij ExtractFirst te doen omdat het perfecte pad niet mijn doel is, maar een erg goed pad wel. En nu kan ik de check of het de finish is minder vaak doen, en kan ik hem doen als er al een Breadcrumb van gemaakt is wat allemaal weer net ietsjes scheeld, dit had ik er wel even bij mogen zeggen trouwens .

Verder zou je gebruik kunnen maken van verschillende surroundings, afhankelijk van hoe je bij een node bent gekomen. Teruggaan, of naar een van de vakjes gaan die ook vanaf de vorige node bereikbaar zijn is onzin. In surroundings kun je naast de kosten dan gelijk een 'nextSurroundings' hebben die in de BreadCrumb opgeslagen wordt.

Daar zou ik ook even naar kunnen kijken, bedankt voor je tips!

[ Voor 6% gewijzigd door roy-t op 07-07-2009 13:14 ]

[PrisonerOfPain]

roy-t schreef op dinsdag 07 juli 2009 @ 12:58:
[...]


Goede tip . Ik heb van de ClosedList een HashSet<> gemaakt en de gemiddelde executie tijd ging meteen met 9ms naar beneden (1/3 er af). Als ik dat zelfde kan fixen met de OpenList (ga ik nu mee pielen) dan ben ik waar ik wil zijn .

In princiepe hoef je de Contains functie niet eens aan te roepen; meestal word er gewoon met een boolean flag bijgehouden in de nodes zelf of je in de openlist of closedlist staat. Zoals je de code op deze manier is geimplementeerd gaat 't niet lukken (je new-ed iedere keer de BreadCrum ipv dat je ze hergebruikt).

Verder loop je door surroundings heen, wat een member variabele is (ik ga er om die reden van uit dat daar de hele world in staat). Wat je wellicht beter kunt doen is per node de omliggende nodes opslaan (hoef je maar een keer te doen), dat zal ook in zoektijd schelen.

[roy-t]

PrisonerOfPain schreef op dinsdag 07 juli 2009 @ 13:47:
[...]


In princiepe hoef je de Contains functie niet eens aan te roepen; meestal word er gewoon met een boolean flag bijgehouden in de nodes zelf of je in de openlist of closedlist staat. Zoals je de code op deze manier is geimplementeerd gaat 't niet lukken (je new-ed iedere keer de BreadCrum ipv dat je ze hergebruikt).

Verder loop je door surroundings heen, wat een member variabele is (ik ga er om die reden van uit dat daar de hele world in staat). Wat je wellicht beter kunt doen is per node de omliggende nodes opslaan (hoef je maar een keer te doen), dat zal ook in zoektijd schelen.

surroundings is gewoon een statische array waarin Point3D's staan als in -1,0,0 voor het item links van de node, dus telkens huidigePoint3D + surrounding[i] is een buur. Het is dus niet zo dat de hele wereld daar in staat, verder kan ik kijken of ik niet telkens die breadcrumbs hoef te newen en dan daar in kan stellen in welke lijst ze zitten. Dat zou het een en ander nog weer wat beter te maken

Edit: dat newen zorgt er zelfs voor dat er nu een klein foutje in zit (paden verbeteren) even fixen

Edit2: Na het fixen van dat new foutje en het weggooien van de closedList en de extra HashSet in de MinHeap door deze te vervangen door "OnClosedList en onOpenList" is de code nog weer een stuk omhoog gegaan qua snelheid. Om nog maar weer dezelfde benchmark erbij te houden: de tijd om in een 10x10x10 veld van 0,0,0 naar 9,5,8 te gaan is nu gemiddeld: 1.3ms min: 0ms (<1ms dus).

Dat is echt prachtig, harsstikke bedankt voor al die goede tips, er zaten echt dingen bij waar ik zelf nooit aan gedacht had. De volledige broncode en implementatie zal ik zo op mijn blog zetten zodat iedereen die denkt daar nog wat aan te hebben hem meteen kan downloaden (zal hier ook even een direct linkje en blogpost linkje neer pleuren).

(artikel staat hier: http://royalexander.wordp...sion-a-pathfinding-in-3d/ direct download link staat hier: http://cid-64e785655f2eee...c/XNA3/AStar3DUpdated.zip )

[ Voor 32% gewijzigd door roy-t op 07-07-2009 17:04 ]

[PrisonerOfPain]

roy-t schreef op dinsdag 07 juli 2009 @ 13:55:
[...]
Om nog maar weer dezelfde benchmark erbij te houden: de tijd om in een 10x10x10 veld van 0,0,0 naar 9,5,8 te gaan is nu gemiddeld: 1.3ms min: 0ms (<1ms dus).

Let wel op want dit is zo ongeveer het optimale geval (de route komt practisch een op een overeen met je heuristic). Waarschijnlijk kun je beter zoiets testen omdat het compleet het tegenovergestelde resultaat geeft van je heuristic in bijna alle gevallen.

code:

............s|e.........
.----------------------.
.............|..........
.............|..........
.............|..........
.............|..........
.----------------------.
........................

Waarbij s en e respectievelijk het start en eindpunt van je route zijn

[ Voor 10% gewijzigd door PrisonerOfPain op 07-07-2009 17:27 ]

[roy-t]

PrisonerOfPain schreef op dinsdag 07 juli 2009 @ 17:24:
[...]


Let wel op want dit is zo ongeveer het optimale geval (de route komt practisch een op een overeen met je heuristic). Waarschijnlijk kun je beter zoiets testen omdat het compleet het tegenovergestelde resultaat geeft van je heuristic in bijna alle gevallen.

code:

............s|e.........
.----------------------.
.............|..........
.............|..........
.............|..........
.............|..........
.----------------------.
........................

Waarbij s en e respectievelijk het start en eindpunt van je route zijn

Bedankt voor de tip, dat is idd een veel betere bench, zal 'm zodadelijk even uit testen .

[djexplo]

Heb je weleens gekeken naar "Fast Marching" ? Is ook een variant van Dijkstra's algoritme maar dan voor 2D en 3D uniform grids (plaatjes)
Ik heb zelf c-code (en Matlab code) geschreven voor dit probleem inclusief een supersnelle unsorted binary tree. Voor 2D kost dit een seconde of minder, voor 3D [256 256 256] +-30 seconden.
http://www.mathworks.com/matlabcentral/fileexchange/24531
Wikipedia: Fast marching method

[PrisonerOfPain]

djexplo schreef op dinsdag 07 juli 2009 @ 18:51: Voor 2D kost dit een seconde of minder, voor 3D \[256 256 256] +-30 seconden.

30 Seconden is veel te lang voor iets dat real-time uitgevoerd moet worden. Beter kun je dan kijken naar iets als HPA-star; een hierarchische vorm van A-star. Volgens de paper heeft 'ie 10% van de executie tijd nodig heeft van de klassieke A-star, ten kostte van 1% precisie.

[roy-t]

djexplo schreef op dinsdag 07 juli 2009 @ 18:51:
Heb je weleens gekeken naar "Fast Marching" ? Is ook een variant van Dijkstra's algoritme maar dan voor 2D en 3D uniform grids (plaatjes)
Ik heb zelf c-code (en Matlab code) geschreven voor dit probleem inclusief een supersnelle unsorted binary tree. Voor 2D kost dit een seconde of minder, voor 3D \[256 256 256] +-30 seconden.
http://www.mathworks.com/matlabcentral/fileexchange/24531
Wikipedia: Fast marching method
[afbeelding]

Ik heb net even mijn code geprobeerd maar voor een map van 256, 256, 256 is mijn huidige A* code zelfs iets sneller (natuurlijk had ik niet het maze dat jij had, maar in de maps waar ik het voor wil gaan gebruiken zullen vrij weinig obstructies zijn).

Hoe houd Fast Marching zich in vrij lege ruimtes? (Voor wat ik zag op internet zijn het bijna allemaal mazes die er mee opgelost worden).

@PrisonerOfPain

Ooh HPA* -90% executie tijd versus -1% precisie klinkt erg interessant voor grotere maps, die zal ik zeker ook eens bekijken.

[djexplo]

Hoe houd Fast Marching zich in vrij lege ruimtes? (Voor wat ik zag op internet zijn het bijna allemaal mazes die er mee opgelost worden).

Fast Marching geeft voor een ruimte met 1 waarde, bijna de exacte afstand van punten tot elkaar zoals berekend met b.v. Pythagoras.

Als je de Fast Marching zou stoppen als je het eind punt hebt bereikt inplaats voor het hele volume de afstand uit te rekenen ben je waarschijnlijk ook binnen enkele seconden klaar voor 3D.