# Fun with A* Optimizations

After fighting with some silly bugs, and fiddling with map generation and the data structures used to represent the map, I finally reached the point last week where I could begin to assess performance.  It was immediately obvious that the pathfinding algorithm was the bane of my program’s execution.  Something absurd like 98% of the running time was dedicated to pathfinding.  The subsequent operation of following the paths found and adding to congestion was trivial in comparison.

To more effectively focus on just pathfinding, I created a new project that was designed to run two different pathfinding algorithms over the exact same list of origin/destination pairs, and collect both timing data and algorithmic data on each.  One of the pathfinding algorithms would generally be a baseline that I had already tested, and the second would involve some form of experimental tweaking.

The tweaks came in two flavors, which I’ll call technical and algorithmic.  The technical tweaks were not intended to change behavior significantly, but were only for improving the performance of the operations already being done.  The algorithmic tweaks on the other hand were intended to make the A* algorithm behave very differently, with the intention of making it intelligently consider fewer nodes along the way to finding an acceptable path.  (Under normal operation for the types of maps I’m dealing with, a basic A* algorithm will consider a large number of nodes that it eventually decides aren’t part of the final best path.  It would be nice to just ignore those nodes altogether, but to do that perfectly, the algorithm would need to see into the future.)

By the end, I was able to calculate around 12,000 paths per second on a grid-like map of highways, major roads, and minor roads that was roughly 100 square miles (260 square kilometers)  in size.  Each path on average was about 7 miles long, and took roughly 7.5 minutes to travel.  Larger maps shouldn’t  really affect the speed nearly as much as longer paths would.  As long as most paths stay around 7 miles in length, the same speeds should remain achievable on larger maps.  (The bigger difficulty would largely come from more paths needing to be computed, as there would probably be more people moving around.)

Below is a (perhaps excessively detailed) chronology of tweaks that I went through over the past week.  As a summary, though, I’ll note the following takeaways: (more…)

# Slightly Imperfect Pathfinding

I took a walk in the snow and promptly realized what my pathfinding issue was.  Essentially, the algorithm was going out of its way to intentionally find a bad path.

More precisely, (more…)

# Severely Imperfect Pathfinding

stupidly long path

Over the past week, I’ve been working on a traffic simulation prototype in order gauge the feasibility of various levels of simulation detail, given typical computation and memory limits of a consumer computer.  I’ve made some progress on getting an initial unoptimized representation of the data structures needed, and visualizing the results of basic pathfinding.

But as is usual for me, although my first attempt at writing the A* algorithm for this particular data representation doesn’t violate any legalities of following the graph edges, it most definitely does not reliably find an optimal path, as the image here demonstrates.  Three quick right turns would be sufficient, but nope, it has to go through an intersection, make a left turn at another intersection, then a couple of right turns, go back through the intersection where it turned left, through the first intersection that it originally passed, right by its starting point, a final intersection right turn, and then it arrives at its destination.  Brilliant!

You can examine some other silly paths on the prototype page.  Now to find out what’s causing this absurdity.