Jump to content
  • Advertisement
  • entries
    64
  • comments
    45
  • views
    81811

Pathfinding 1: Map Representation and Preprocessing

Sign in to follow this  
ericrrichards22

1436 views

This was originally intended to be a single post on pathfinding, but it got too long, and so I am splitting it up into three or four smaller pieces. Today,we're going to look at the data structures that we will use to represent the nodes of our pathfinding graph, and generating that graph from our terrain class.

When we were working on our quadtree to detect mouse clicks on the terrain, we introduced the concept of logical terrain tiles; these were the smallest sections of the terrain mesh that we wanted to hit when we did mouse picking, representing a 2x2 portion of our fully-tessellated mesh. These logical terrain tiles are a good starting point for generating what I am going to call our map: the 2D grid that we will use for pathfinding, placing units and other objects, defining areas of the terrain, AI calculations, and so forth. At the moment, there isn't really anything to these tiles, as they are simply a bounding box attached to the leaf nodes of our quad tree. That's not terribly useful by itself, so we are going to create a data structure to represent these tiles, along with an array to contain them in our Terrain class. Once we have a structure to contain our tile information, we need to extract that information from our Terrain class and heightmap, and generate the graph representing the tiles and the connections between them, so that we can use it in our pathfinding algorithm.

The pathfinding code implemented here was originally derived from Chapter 4 of Carl Granberg's Programming an RTS Game with Direct3D. I've made some heavy modifications, working from that starting point, using material from Amit Patel's blog and BlueRaja's C# PriorityQueue implementation. The full code for this example can be found on my GitHub repository, https://github.com/ericrrichards/dx11.git, under the 33-Pathfinding project.
graph_thumb4_thumb.jpg?imgmax=800


Read more "
Sign in to follow this  


0 Comments


Recommended Comments

There are no comments to display.

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!