Well, screw them. I'm already unstable and there's no way the symptoms are gonna flare any worse than my neighbor's car, which I just finished setting on fire.*
Besides, this is literally the first time I've actually wanted to work in several months.
At the moment, I'm working on refining a rather hideous and hackish implementation of A* pathfinding, which was one of the last things I did before the little nervous breakdown episode. (I don't recommend that tour, by the way. Try a nice vacation package to the sixth level of Hell instead, it'll be more pleasant.)
I started out with a straight naive implementation of A*, literally ripped from the textbook description of the algorithm. (In fact, Wikipedia's description is virtually identical to the implementation method I used.)
Now, I used to be a C guy, but I've long since become spoiled by higher level languages. I'm working predominantly in C++ these days, which means I can't be stuffed to mess around with things like manual memory allocation just to make a little pathfinding algorithm more efficient. (And we're going to need a pretty damn efficient implementation, for reasons I will not elaborate on.)
Bottom line, my first implementation was... bad. It involved a std::priority_queue which contained special structs; each struct instance held a std::vector of nodes connected in a path, as well as the total travel cost of that path. The priority queue would be updated and paths shuffled around repeatedly, basically exactly as the pseudocode description suggests.
This made the implementation horrendously inefficient in terms of heap space. By my rough guess, even pathing through a simple 6-node test graph would require on the order of 100 reallocations and copies.
Clearly, this sucks.
I set out initially to just clean up the little helper structs and the containers a bit to minimize copies. Along the way, I recalled a couple of small tricks from the last time I wrote an A* implementation from scratch - back in my C days. This time, I've adapted those tricks into C++ to end up with a really nice, clean implementation that's both easy to follow (assuming you know how A* works to begin with) and quite efficient.
I'm still putting some finishing touches on it (including a couple possible more improvements), and of course it needs complete testing; but once it's all set, I'll post the code and details of how the improvements work.
I doubt it'll be revolutionary news to anyone with any significant game coding experience, since the tricks are obvious and pretty standard (at least for optimization-minded ex-C-hackers like me). Even still, it should hopefully be useful for people who are doing their first A* implementation, or otherwise working with a naive implementation. If nothing else, it's another little droplet into the ocean of open source.
Plus, I know I can count on all you actual C++ coders around here to tear it apart for me and find all the idiotic mistakes [grin]
* Disclaimer for the paranoid: I'm being really careful with this. If a little sleep deprivation does indeed create problems, I swear I won't do it again. Also, I didn't set my neighbor's car on fire.
It was his dog.
