Pathfinding III: Putting it All Together

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.

Adding Shadow-mapping and SSAO to the Terrain

Now that I’m finished up with everything that I wanted to cover from Frank Luna’s Introduction to 3D Game Programming with Direct3D 11.0, I want to spend some time improving the Terrain class that we introduced earlier.  My ultimate goal is to create a two tiered strategy game, with a turn-based strategic level and either a turn-based or real-time tactical level.  My favorite games have always been these kinds of strategic/tactical hybrids, such as (in roughly chronological order) Centurion: Defender of Rome, Lords of the Realm, Close Combat and the Total War series.  In all of these games, the tactical combat is one of the main highlights of gameplay, and so the terrain that that combat occurs upon is very important, both aesthetically and for gameplay.

Or first step will be to incorporate some of the graphical improvements that we have recently implemented into our terrain rendering.  We will be adding shadow-mapping and SSAO support to the terrain in this installment.  In the screenshots below, we have our light source (the sun) low on the horizon behind the mountain range.  The first shot shows our current Terrain rendering result, with no shadows or ambient occlusion.  In the second, shadows have been added, which in addition to just showing shadows, has dulled down a lot of the odd-looking highlights in the first shot.  The final shot shows both shadow-mapping and ambient occlusion applied to the terrain.  The ambient occlusion adds a little more detail to the scene; regardless of it’s accuracy, I kind of like the effect, just to noise up the textures applied to the terrain, although I may tweak it a bit to lighten the darker spots up a bit.

We are going to need to add another set of effect techniques to our shader effect, to support shadow mapping, as well as a technique to draw to the shadow map, and another technique to draw the normal/depth map for SSAO.  For the latter two techniques, we will need to implement a new hull shader, since I would like to have the shadow maps and normal-depth maps match the fully-tessellated geometry; using the normal hull shader that dynamically tessellates may result in shadows that change shape as you move around the map.  For the normal/depth technique, we will also need to implement a new pixel shader.  Our domain shader is also going to need to be updated, so that it create the texture coordinates for sampling both the shadow map and the ssao map, and our pixel shader will need to be updated to do the shadow and ambient occlusion calculations.

This sounds like a lot of work, but really, it is mostly a matter of adapting what we have already done.  As always, you can download my full code for this example from GitHub at https://github.com/ericrrichards/dx11.git.  This example doesn’t really have a stand-alone project, as it came about as I was on my way to implementing a minimap, and thus these techniques are showcased as part of the Minimap project.

Basic Terrain Rendering

Shadowmapping Added

Shadowmapping and SSAO

Generating Random Terrains using Perlin Noise

Previously, we have used our Terrain class solely with heightmaps that we have loaded from a file.  Now, we are going to extend our Terrain class to generate random heightmaps as well, which will add variety to our examples.  We will be using Perlin Noise, which is a method of generating naturalistic pseudo-random textures developed by Ken Perlin.  One of the advantages of using Perlin noise is that its output is deterministic; for a given set of control parameters, we will always generate the same noise texture.  This is desirable for our terrain generation algorithm because it allows us to recreate the same heightmap given the same initial seed value and control parameters.

Because we will be generating random heightmaps for our terrain, we will also need to generate an appropriate blendmap to texture the resulting terrain.  We will be using a simple method that assigns the different terrain textures based on the heightmap values; a more complex simulation might model the effects of weather, temperature and moisture to assign diffuse textures, but simply using the elevation works quite well with the texture set that we are using.

The code for this example is heavily influenced by Chapter 4 of Carl Granberg’s Programming an RTS Game with Direct3D, adapted into C# and taking advantage of some performance improvements that multi-core CPUs on modern computers offer us.  The full code for this example can be found on my GitHub repository, at https://github.com/ericrrichards/dx11.git, under the RandomTerrainDemo project.  In addition to the random terrain generation code, we will also look at how we can add Windows Forms controls to our application, which we will use to specify the parameters to use to create the random terrain.