Regarding the slow down, I've done some more testing and I have it nailed down now, OpenGL is blocking on SwapBuffers()
This latest misinformation brought to you by my passing 64 bit integers to sprintf(). The numbers I was looking at for swapBuffers() were infact the numbers for render3d(). But render2d() also blows up at the same time, everything will be running smoothly, then the renderer will choke, sort itself out, repeat...
bah... I'm giving up on this for now, I'll never get anything done if I keep chasing this thing.
Better Paths, Dirt Cheap!So, back to the pathfinder, I'm happy that it goes suitably fast now, so I thought I'd look at trying to improve the path quality a bit. Glest's A* algorithm (which isn't very A* like) returns bad paths primarily because it tries to shoot straight at the target, and if something gets in the way, it just edges it's way around, whereas proper A* will be consider many many more positions, and can hence realise there's a better way around the obstacle. Full blown A* is out of the question though, for too 'expensive'.
I've been reading 'Near Optimal Hierarchical Path-Finding' [Adi Botea et al] in preparation for phase 2 of the overhaul, while that's not happening just yet, I did notice that they (optionally) 'smooth' their paths, to improve quality, by replacing sub-optimal path pieces with straight lines. Sounded good to me, and it would fix up most of our dodgy paths. Unfortunately they only really dedicated a paragraph to explaining this in the paper, so I downloaded the source and had peek... Yuck. I thought they might have come up with cool and efficient means to do this, but I'm now guessing rather it was an 'afterthought' and tacked on.
Then I thought, this thing is pretty fast... why not run it twice for each search ?
Shown below is on such search, the yellow cells are those on the path from the start to the destination, the red ones are the path from the destination to the start, yellow and red ones are on both paths.

So, run it once each way, where they diverge start counting how long each segment is, and pick the better one to 'stitch in' to our final 'solution' path, voila, quality paths...

I haven't timed it much yet, but calculating a path from one corner of "Conflict" (64x64 map, [that's 128x128 cells though]) to the other took just over 2ms on my 'first go', the return journey was almost bang on 3ms [on a 2GHz AMD Turion64x2, release build]. So it's still quick enough for our purposes I think.
I'm calling Phase One complete. (barring bugfixes, of course)...
It'll be on the SVN tomorrow probably, just need to make sure it all compiles under linux.