Pathfinding Data Collector Optimizations

Try optimizing the pathfinder speed today. A few quick profiling showed over 80% of all A* processing time spent on the data collection class itself (SortedTreeNode), with 60% spent on searching the nodes for best value and 30% in data removal;

  1. Replace List class array with more flexible (if higher memory usage) LinkedList.
  2. Implement insertion sort (O(n)) for the data collector, so that recalling data could be done with constant O(1). A quick profiling show shifts in processing time; Node adding function (AddLeave) now take highest place at 54% processing time, with 20% of that spent in just comparing the weight values. Measured biggest spike at ~480ms with 1283 calls to AddLeave() function.
  3. Replace cumbersome IComparer class with sleeker IComparable, getting rid of another layer of function call. Weight conparison time somehow jump to 33%, but biggest spike measured at only ~300ms with only 922 calls to AddLeave(). Although the the software was experiencing Out-of-Memory problem during the test.
  4. Optimize weight data structure, replacing complex data comparison with a single integer. Node adding function (AddLeave) processing time dropped to mere 40% from 60% in the last step, and data comparison got a massive drop from 33% to 1%. Overall computation took ~200ms with over 1327 calls to AddLeave() function. I call that a success for the moment.

Overall result; Time spent on pathfinding algorithm seems to be reduced by approximately 20 – 25%


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s