In Which Nicholas Learns About Pathfinding

I’ve always been pretty aware of pathfinding. A*, that’s a thing, right? And there’s some Russian dude with an unpronounceable name that starts with D? I’ve never really needed true pathfinding; if I made an AI who needed to get from point A to B, he’d use some sort of “randomly pick left or right” or just “follow the player” sort of method. I have a textbook called AI Game Programming Wisdom, which has never really offered up much wisdom as it has inspiration for ideas. It has multiple chapters on pathfinding, and every single one of them has to do with A*. I recognize A* as being the “best in the field,” but I’ve never really known for sure how it works. I’ve never needed to, really.
But a few days ago, I started working on code that would allow the player to click on a location in the isometric map, and the character would walk there. You know, like all the other old isometric games. Or any point-and-click adventure game. It obviously wasn’t that hard; people had been doing it literally for decades. Except it was. What made it worse was the fact that I’d “homebrewed” my own isometric engine; it didn’t really recognize that you could travel straight north and not deviate east or west- as far as it was concerned, you only went up, down, left, and right. And if you were traveling straight north, you were going up and over to the left, which confused the bejeebus out any sort of click-to-walk code I attempted. I realized after a while that I was going to HAVE to use some sort of pathfinding algorithm.
The textbook I have doesn’t do a very good job explaining A*; it assumes you already know what it is. All the forums for GarageGames (the makers of Torque) kept touting a resource that had been released 6 years ago that added A* functionality, but it didn’t apply to what I’m using right now. The more and more I read, the more I realized that A* was just too complicated for what I wanted to do. Dijkstra’s Algorithm was the precursor to A*, published in 1959 –1959!– and seemed far more suitable to my needs (and isn’t Russian, it turns out). I spent another couple days trying to find a good explanation of it in pseudocode, and it was finally the wikipedia page (of all places) that clicked with me. In not more than a couple of hours, I had a fully-functional click-to-walk code. The only problems is has is if the path it needs to take wanders too far off the screen; the algorithm essentially can’t “see” where he needs to go, and it calls it a null path (that is, a little red click-y target). So far, I can only find one place where that even applies, and you really have to go out of your way to click in the right spot to make it happen. Plus, I feel like that’s a pretty intuitive problem- just get closer to where you want to go first.

The isometric engine aside, I commissioned some artwork for the final boss in the Japan Dream level, so it’s a lot easier to see what’s happening throughout the boss fight now. It looks pretty good, especially just for prototyping graphics, and it’s courtesy of Lucas Onky of Puffergames. I found his portfolio in the TIGForums and he was an absolute pleasure to work with.
I also made it so the mouse can select menu options, since I saw so many playtesters trying to do that. I still need to update the “View Controls” thing to show the spacebar as jump, but aside from that (and graphics, of course) the level is pretty much finished.
The isometric level takes a while to load, but that’s because it’s generating all its geometry information at runtime instead of loading it from a file. Once I have the level design completed, I can save it and then load it whenever I like, cutting the level-loading time down by a huge chunk, but it needs to be done in-game for now. Just bear with me; it’ll get better.