Feasible pathfinder - prototype, as in non-production ready code

Da vi igår nat stykkede en pathfinding funktion sammen, var det uden at overveje dens effektivitet. Spillet bliver imidlertid yderst afhængig af at monstre bliver i stand til at finde vej uden at skulle stå og tænke sig om i længere tid af gangen. Ved at bruge getTimer() funktionen i ActionScript har vi fået optimeret spillet således at det sjældent tager mere end et par millisekunder at finde vej fra den ene side af kortet til det andet - en situation som oftest ikke en gang bliver relevant.

For at teste algoritmen autogenerede vi et tilfældigt kort (dog med et på faste vægge) og placerede et start- og slutpunkt tilfældige steder på kortet. Derefter målte vi, hvor lang tid det tog for computeren at finde vej. For at få en bedre idé om hastigheden lod vi computeren lave 20 kort, for derefter at finde vej i dem. Tiden for disse 20 kort blev lagt sammen. Denne proces blev gentaget 20 gange for at finde en gennemsnitlig beregningstid på de 20 kort.

Resultatet blev at computeren kunne finde vej på 20 kort i løbet af omkring 25 millisekunder.

Dette resultat er nået uden voldsom optimering - faktisk vidste vores forsøg at optimering på den kortstørrelse vi opererede med, betød en væsentligt længere beregningstid! Den endelige implementering blev en forsimplet udgave af Dijkstra's algoritme.