• entries
64
45
• views
82219

# Pathfinding III: Putting it All Together

2924 views

Watch the intrepid red blob wind its way through the mountain slopes!

Last time, we discussed the implementation of our A* pathfinding algorithm, as well as some commonly used heuristics for A*. Now we're going to put all of the pieces together and get a working example to showcase this pathfinding work.

We'll need to slightly rework our mouse picking code to return the tile in our map that was hit, rather than just the bounding box center. To do this, we're going to need to modify our QuadTree, so that the leaf nodes are tagged with the MapTile that their bounding boxes enclose.

We'll also revisit the function that calculates which portions of the map are connected, as the original method in Part 1 was horribly inefficient on some maps. Instead, we'll use a different method, which uses a series of depth-first searches to calculate the connected sets of MapTiles in the map. This method is much faster, particularly on maps that have more disconnected sets of tiles.

We'll also need to develop a simple class to represent our unit, which will allow it to update and render itself, as well as maintain pathfinding information. The unit class implementation used here is based in part on material presented in Chapter 9 of Carl Granberg's Programming an RTS Game with Direct3D.

Finally, we'll add an additional texture map to our rendering shader, which will draw impassible terrain using a special texture, so that we can easily see the obstacles that our unit will be navigating around. You can see this in the video above; the impassible areas are shown with a slightly darker texture, with dark rifts.

The full code for this example can be found on my GitHub repository, https://github.com/ericrrichards/dx11.git, under the 33-Pathfinding project.

Videos are always a treat!

You need to teach people about using binary heaps for A*. That would actually be useful. And why don't you use a line-drawing algorithm optimization for getting the ray intersection with the heightmap? I think octree is slower.

I'll take it under advisement; it is a topic worth a quality explanation.  I didn't really want to get bogged down comparing the performance of different data structures for the priority queue, and there are quite a few to pick from, apparently.

On your second point, I'd love to have a pointer to explain what you're referring to.  It wouldn't surprise me if there's a smarter way to do intersections on the terrain than I'm doing; I just picked the simplest thing that I thought would work, and ran with it when I did some profiling and realized it performed well enough for what I was using it for.

## Create an account

Register a new account