Jump to content
  • Advertisement
  • entries
  • comments
  • views

Pathfinding III: Putting it All Together

Sign in to follow this  


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.

Read more "
Sign in to follow this  


Recommended Comments

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.

Share this comment

Link to comment

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.

Share this comment

Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!