During the last few days I’ve been working on a simple pathfinding technique that could be applied to the Dungeon demo in order to prevent our hero (or his enemies) to walk through walls. In the next paragraphs I’m going to describe how I did this, but if you want more details you can always take a look at the code (it’s a bit messy right now, but I’m working on it).

So, let’s make a dungeon:

The first step was simple: identifying which sections of the dungeon are available for our hero to walk in. Then, a waypoint is placed on each empty square:

Let’s remove all walls to see things more easily:

As the image suggests, the logic behind this is very simple. Characters are moved from one waypoint to the next following a path. But in order to do that, we need to identify neighbors for each waypoint in the scene:

Simply put, if there is a line between any two waypoints, then there is a path and a character can use it to traverse the scene.

We can set any number of neighbors per waypoint. Increasing the number of connections allow characters to move more natural. For example, since I want my characters to move diagonally, we need to define additional links:

OK, now comes the hard path: Pathfinding. I spent some time reading about different pathfinding techniques and how to implement them, but since I didn’t have enough time (GearBox’s Borderlands has a lot of guilt about that) I ended up implementing my own algorithm.

It’s actually extremely simple. If I want to move from waypoint A to waypoint B, I’m going to move to whatever neighbor of A is closest to B. As I said, a very simple algorithm:

The image above shows the pathfinding algorithm in action. Green waypoints indicate the path that the character must follow to reach his destination. Yellow is used for those waypoints that were evaluated while computing the path but finally discarded.

I must note here that I wasn’t sure about the accuracy of the resulting path using an algorithm as simple as this, but in the end it turned out to be very accurate. It’s far from perfect, but it gets the job done:

Actually, my implementation can be considered as a simplified A* algorithm, where all nodes are equidistant. A* assumes that all nodes are positioned at variable distances between each other. That’s why it requires all nodes to be weighted and that weight is taken into account while doing the calculations to obtain the next node in the path. Heuristics are used to calculate the shortest path.
Since in my approach all nodes are separated by a constant distance (let’s say 1m), there is no need for weights to be used, and then all calculations are simplified. The next node in the path is calculated by just computing the distance between each neighbor of the current node and the destination node. The next node is the one closest to the final node. No heuristics are used so far.
As a side note, my implementation requires more nodes to be specified. For A*, a straight path can be represented with only two nodes regardless of the distance between them.

I think you were not actually explaining how you choose next step. Are you selecting the next possible node that is nearer the final destination?

I always thought the best path-planning in cell-like worlds was A* algorithm.

Actually, my implementation can be considered as a simplified A* algorithm, where all nodes are equidistant. A* assumes that all nodes are positioned at variable distances between each other. That’s why it requires all nodes to be weighted and that weight is taken into account while doing the calculations to obtain the next node in the path. Heuristics are used to calculate the shortest path.

Since in my approach all nodes are separated by a constant distance (let’s say 1m), there is no need for weights to be used, and then all calculations are simplified. The next node in the path is calculated by just computing the distance between each neighbor of the current node and the destination node. The next node is the one closest to the final node. No heuristics are used so far.

As a side note, my implementation requires more nodes to be specified. For A*, a straight path can be represented with only two nodes regardless of the distance between them.

On a second read, you said just that. A couple of days ago I read an analysis of PacMan ghosts. Coincidence?

I haven’t read that. Do you still have the link?