Pathfinding and Binary Search

.........
.........
....W....
.@..W..O.
..xxWxx..
....x....
.........


*************
Pathfinding
*************

I'm in the process of coding the main pathfinding code of Adventurer. You may be interested to know that it isn't as simple as "go here", or "move towards here". No, pathfinding is a problem that has plagued and intrigued coders for years. It handles the problem of figuring out how to get from point A to point B. I've looked at the Bresenham Line Algorithm before, and I use it for my line of sight calculations. But if I used a pure line for deciding where to go, creatures would endlessly bump into walls if it was the most direct route in a wall-less environment. That's unrealistic and not very fun.

So I'm looking into what is known as the A* pathfinding algorithm. What is this, you might ask? Put simply, it looks at all adjacent tiles, guesses which one brings it closer to the target, and looks at all adjacent tiles to that one. It keeps looking at the shortest paths it's found, combined with its guess at which is next. This bit of code is very efficient, and only rarely wrong, and only by a little even then. It's perfect for what promises to be the processing-heavy Adventurer.

Now, one crucial part of this is finding the lowest number in a list of numbers. I've found it's easiest for my purposes to keep the list in order, and just pluck from the bottom. The only problem comes when it comes time to put a new number into the list, i.e. the best path estimate of a tile. I have to find where it goes. Now, I could look each and every spot, and figure out where the number I'm putting in is greater than the number to the left of it, and less than the number to the right of it. This is known as a sequential search, and it's fine if you just have a few numbers in your list.

But this list is tracking all tiles adjacent to the ones it's looked at. this could be hundreds of tiles. But there's a nifty trick that works perfectly. It's known as a binary search. It works like this: Look at the number in the middle. If yours is higher, look only in the numbers to the right and look halfway there. Same if it is lower, but for the left side. Eventually, you'll find the spot where your number is right between two. Suddenly, 2 million items takes at most 20 cycles of this pattern.

So that's what I'm implementing in my code: an A* pathfinding algorithm, saving its values in a list with binary search. It might not be the absolute most efficient thing out there, nor the easiest, but it combines the two worlds in the best way I can think of. I can expand and fine tune it later if I need to.

I expect to have this implemented within a couple days in Adventurer, and have a new download up. Then that test critter can hunt you down much more intelligently. >:D

The game can be found at code.google.com/p/adventurerroguelike