In beginning the simulation code of my city builder over the past few weeks, I’ve run into some difficulties with integers that quite surprised me. For a variety of reasons, I want to ensure that the simulation code is absolutely completely deterministic, regardless of platform, compiler, machine, or any other variable. While I’d need to do further research to properly justify this statement in all its details, my impression is that this is much easier to guarantee if one sticks to integer computations, avoiding floating point representations of numbers.
Of course, if one uses just integers in all computations (or even the somewhat fancier fixed point variants), then loss of precision becomes more important to deal with, whereas with floating point numbers, one can often get by ignoring such details. Division in particular is the prime culprit. (more…)
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…)
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.