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.