|
My brain is built of paths and slides and ladders and lasers and I have invited all of you to enter its pavilion. My brain, as you enter, will smell of tangerines and brand-new running shoes.
| Thursday, September 27, 2007 |
  Not my best week ever. | 
Posted - 9/27/2007 7:36:48 PM | I think there's something wrong with this milk... it tastes like cow nipple.
Also, my car is now lightly damaged, thanks to some dumbass teenage kid who chucked a ball out into the street. Guy in front of me slams on brakes, I slam on brakes/attempt to swerve, I hit guy. Dumbass kid promptly grabs his ball and disappears without so much as finding out if anyone is hurt.
So now I have to go get the hood replaced, and lube up for the shafting that the insurance company's going to give me. Gotta love getting a premium hike because someone else's inbred offspring is out terrorizing the streets.
There is, of course, an easy solution to all this. I'm going to go back to playing Halo 3 all day, and attempt to forget about it.
There may also be alcohol involved.
| |
| Friday, September 7, 2007 |
| Yayy insomnia! | |
Posted - 9/7/2007 3:58:21 AM | So, thanks in part to several cups of Waffle House coffee earlier this evening, I'm pulling an all-nighter - the first in a while. Technically I'm not supposed to do this anymore. My doctors say that it can destabilize me and cause "symptom flare-ups."
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 
* 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.
| |
In locus hic, omnes res dementes sunt.
|
| S | M | T | W | T | F | S | | | | | | | 1 | 2 | 3 | 4 | 5 | 6 | | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | | 28 | 29 | 30 | | | | | | |
OPTIONS
Track this Journal
ARCHIVES
July, 2009
June, 2009
May, 2009
April, 2009
March, 2009
February, 2009
January, 2009
October, 2008
September, 2008
August, 2008
July, 2008
June, 2008
May, 2008
April, 2008
March, 2008
February, 2008
January, 2008
December, 2007
November, 2007
October, 2007
September, 2007
August, 2007
July, 2007
June, 2007
May, 2007
April, 2007
March, 2007
February, 2007
January, 2007
December, 2006
November, 2006
October, 2006
September, 2006
August, 2006
July, 2006
June, 2006
May, 2006
April, 2006
March, 2006
February, 2006
January, 2006
December, 2005
November, 2005
October, 2005
|
