The Obsession with Paths

After browsing through the GameDev.net AI forum, I've come to one conclusion, when it comes to game AI, everyone (most) are obsessed with pathfinding. To tell you the truth, I don't think much about pathfinding in the first place, considering it is one of like the first few things you learn when you take any college level AI course. Ironically, pathfinding is not that much AI than just an algorithm or heuristic to solve a problem. Hell, its more like a solution to a graph theory problem, which means its more applied math than AI. And when you talk about pathfinding, you talk about A*, which ironically is pretty dang archaic. Its a shame no one has come up with anything better, but that's not really possible, since A* is pretty optimal on its own. Technically, A* has many other merits in game theory along with other things like alpha pruning and min-max, but why every single game developer and beginner game developeris obsessed with it is beyond my comprehension.

Well, technically, I do understand why everyone is so hung up on A*, just because its optimal and fairly easy to implement, not to mention being implemented to death. A* is capable of giving you the BEST path given enough information and processing time, but the question I ask is, is it worth it? I've even heard people saying that you can just do A* to look like n steps ahead, but then.....oh well, I'd say, what's the point. There are so many other ways of doing pathfinding out there now that its actually kind of funky to be stuck with A*.

In most cases, there is no need for an absolute optimal solution. Most people don't walk straight lines towards a target anyways. So, why haven't gaming people picked up on ant colonies or tabu search even to do pathfinding? I guess some worry about computational overhead and storage overhead, etc. If you really are worried about these, then you really don't care too much about good AI. Plus, how much more space would it require? Compared to some games that have megabytes and megabytes of texture, implementing these algorithms will obly take up a few more kilobytes max of extra memory storage. Computational complexity is not an issue either. So you spare some time and crunch about 5% - 10% fewer polygons, but that's where optimization comes in on the graphics end. So you lose like 10 - 20fps in a game that runs at 120fps and where most ordinary people set their refresh rate to no more than 75Hz. Sometimes, some things just don't make too much sense for me.

"But its running at 100fps instead of 120fps, that's horrible!!!"
"Dude, the average person perceives only around 60fps and if you start seeing scanlines with your monitor set at 100Hz, you need to go outside and do something else instead of sitting in front of a monitor for 10 hours a day like me. And even I don't see scanlines at 60Hz."

But seriously though, how can we implement path finding in games with something other than A*? How do we work with Ant Colony Optimization? How do we incorporate Tabu search? What about Simulated Annealling? And where the hell am I getting these names?

More answers next time, after I finish some more coding and start procrastinating again. But don't worry, its not as bad as you think.

IDEA 3D Framework

Its been a while, but I guess no is a good time to post the IDEA 3D Framework I wrote a few weeks back, like 2 I think. So what did I learn in writing it? Never show your advisor too cool an idea because you'll just end up with more work. However, seriously, this thing is pretty dang cool. Being able to mutate a chair and manipulate it in 3D is pretty cool.

Overload....

Kind of been in overload mode through the past two weeks, so never really got more programming done beyond what I needed to write those two papers. Man, I was like a paper writing machine for a while. Now that things have died down a bit, I can go back to doing a few other things I like.

Been able to field test some of the math and container modules that I wrote before in the evacuation simulation that I recently created. It was kind of a good way to see what works and what doesn't. There seem to be a few more kinks about Visual C++ that I never noticed before. Strange issues with pointers and destructors. Better look into that. But I found that one of the down side in working in Visual Studio .NET is that I've been having a hard time tearing away file dependencies with the .NET framework, even though I don't specifically use it.

Out of the Loop....

Dang....

It's only been a week since I last worked on the VFS code and I'm already unfamiliar with it. Guess I need to take some time to sort it out again. There seems to be some memory issues with deleting a file. I'll have to take a closer look into that. For now, I think I'll let it sit a bit overnight. Been thinking about implementing a few more features.

For one thing, I need to be able to recognize the version of the VFS that was created by the VFS Generator. I may do version changes later and it would definitely cause problems if the versions weren't right, since it'll mess up the data if the format has been changed. Also, been thinking about ways to build directory structures within the VFS. Thinking about folding trees and etc, but the sticking point is how the structure is saved along with the filename. It would be nice if I could just save directory structures directly into the VFS files and not have to rely on a index file, but that has some strange issues with itself, since it effectively increases the storage overhead. Was thinking about just storing a md5 hash of the file name + path, but then retrieval would mean I'd need to undo the hash to know what's stored there, and I'd still need an index file. So....all I can say now is.......dang it......

Busy Work.....

Busy, busy, busy..........that's kind of the thing these days. Things always come one after another and divert me from programming.

E-day has been a good experience this year and has given me quite a few new ideas. For one thing, I think I'm comfortable with multi-viewport rendering now, which opens a whole new world of possibilities. About a year ago, there was a small project that got started here called IDEA (Interactive Distributed Evolutionary Algorithm). The original prototype evolved smiley faces. I kept wanting to push it a little further and make it possible to evolve 3D objects, but it was just not feasible at the time. However, it becomes very feasible with multi-viewport rendering. So, I will spend maybe a few days looking into that and build a generic framework for people to work on later.

Started playing with the Mac G4 in my office, which has OS X and XCode installed on it. Managed to crash it a few times in the past few days, but nothing serious. I really want to learn a bit about Cocoa and Carbon, since it seems that OpenGL is actually a UI component within the UI designer for Mac OS X, how cool is that. XCode does take a while to get used to though, no to mention the Mac OS X interface itself. Considering that I've been a windows user for the past 10+ years, some habits are just hard to change.

Going Bonkers!

Does anyone actually use that phrase "Going Bonkers" anymore? Think it is like a decade old or something like that, but oh well. I currently don't have the spare brain cells to think about it either.

My proposal has been driving me nuts, since I'm trying to push it out and it seems to be growing to a 90 page monstrosity rather quickly. I'll get back to programming once I'm done with it in the next 2 days.

Probably on the to-do list is to first root out the bugs for the VFS. Then I have to continue with the engine foundation. There are a few bugs in that too with the math template. Then go ahead and build the vector and matrix templates.

Bugs Galore!!!!

Yup, the VFS Manager is full of bugs.....

Just found another one today where the availability bit vector wasn't dumped to file when the file was modified....

This means that the reported free space will be reset everytime you reload the VFS Manager, and if you add new files, they'll overwrite and corrupt old ones. Oh well, seems no big deal. However, it's always the small things that kill a project.