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.
Tile Map Structures
Previously, when we implemented terrain picking, we developed the concept of logical terrain tiles. These tiles are represented by a 2x2 quad on our terrain mesh, and at present are only represented by a bounding box that encompasses the logical tile. To implement pathfinding, we need to expand on our definition of our logical terrain tile, and create a structure to contain additional information about each tile. We also need to add a 2D grid of this new tile structure to our terrain class. Our MapTile class looks like this:
public class MapTile : PriorityQueueNode {
/// <summary>
/// World-space height (y) of the tile center
/// </summary>
public float Height { get { return WorldPos.Y; } }
/// <summary>
/// World-space position of the tile center
/// </summary>
public Vector3 WorldPos { get; set; }
/// <summary>
/// 2D position of the tile in the terrain grid
/// </summary>
public Point MapPosition { get; set; }
/// <summary>
/// Type of the terrain tile - grass, hill, mountain, snow, etc
/// </summary>
public int Type { get; set; }
/// <summary>
/// Flag that determines if the tile is walkable
/// </summary>
public bool Walkable { get; set; }
/// <summary>
/// Tile set that the tile belongs to. Paths can only be created between tiles in the same set
/// </summary>
public int Set { get; set; }
/// <summary>
/// Estimate of the cost to the goal tile, using A* pathfinding heuristic
/// </summary>
public float F { get; set; }
/// <summary>
/// Actual cost of reaching this tile from the start tile in the path
/// </summary>
public float G { get; set; }
/// <summary>
/// Previous tile in the computed path
/// </summary>
public MapTile Parent { get; set; }
/// <summary>
/// Connections to the neighboring tiles - square grid provides 8 directions of movement, up/down, left/right and diagonals
/// </summary>
public readonly MapEdge[] Edges = new MapEdge[8];
}
The members of our MapTile class are:
- Height – The world-space Y height of the tile center point.
- WorldPos - The world-space position of the tile center point.
- MapPosition – The map-space coordinates of this tile, in our 2D grid of MapTiles, maintained by the Terrain class.
- Type – An integer indicating the type of the map tile. Currently, we have grass = 0, hill = 1, mountain = 2, and snow = 3. This is not fully implemented at present, but eventually I plan on using this field to modify the edge connection costs, so that the cost of transitioning from one terrain type to another can be more or less expensive, for instance, moving into a swamp from grass should cost more than moving from grass to grass. This will also come in handy when I start implementing combat algorithms, so that different terrain types give different defensive bonuses.
- Walkable – This flag indicates whether a tile is valid for a unit to stand upon. At present, this is solely dependent on the slope of the tile relative to its neighbors, so that steep slopes and cliffs are invalid positions.
- Set – We will be dividing up our terrain into sets of connected tiles, so that we can quickly determine if a path exists between any two tiles by comparing their Set values.
- F – This member will only be used by our pathfinding routine. This represents the projected cost of reaching the goal tile from this tile, according to the A* heuristic.
- G – This is another pathfinding member, representing the actual cost of reaching this tile from the start tile.
- Parent – Yet another pathfinding value. This stores the previous tile on the currently calculated path, to allow us to reconstruct the path as a list of nodes, once we have found the optimal path from the start tile to the goal.
- Edges – This array contains the connections between this tile and its neighboring tiles. This array is laid out like so: [NW, N, NE, W, E, SW, S, SE]. Null entries in this list indicate that there are no passable connections in this direction.
You can ignore the fact that this class derives from the PriorityQueueNode base class; later on, when we look at implementing our A* pathfinding algorithm, we’ll come back to this, since it is tied to the particular implementation of a priority queue that we will use for our open set.
We will use an edge data structure to store the connections and traversal costs between two adjacent tiles in our map. These edges are unidirectional, although according to our move cost function, there will always be paired connections between the two tiles; however, we could use this structure to model one-way connections if we chose a different cost function. Our MapEdge class looks like this:
/// <summary>
/// A connection between two adjacent terrain tiles
/// </summary>
public class MapEdge {
/// <summary>
/// Start tile
/// </summary>
public MapTile Node1 { get; private set; }
/// <summary>
/// End tile
/// </summary>
public MapTile Node2 { get; private set; }
/// <summary>
/// Cost of traversing this edge
/// </summary>
public float Cost { get; private set; }
}
We’ll also provide a factory method to create edges between tiles, and a helper function to calculate the cost of traversing the edge, based upon the slope between the heights of the two tile centers. We will only be considering tiles that have a slope of less than about 30 degrees to be connected (the game that I have in mind is going to have units that are based on Ancient/Medieval soldiers, carrying 30-70 pounds of armor and weapons, so this seemed fairly reasonable). If the slope is too great, we will return a null MapEdge, indicating that there is no connection between the two tiles.
/// <summary>
/// Calculate the cost to traverse this edge based on the slope between the two tile centers
/// </summary>
/// <param name="n1"></param>
/// <param name="n2"></param>
/// <returns></returns>
private static float CalculateCost(MapTile n1, MapTile n2) {
var dx = Math.Abs(n1.WorldPos.X - n2.WorldPos.X);
var dz = Math.Abs(n1.WorldPos.Z - n2.WorldPos.Z);
var dy = Math.Abs(n1.WorldPos.Y - n2.WorldPos.Y);
var dxz = MathF.Sqrt(dx * dx + dz * dz);
var slope = dy / dxz;
return slope;
}
/// <summary>
/// Factory method to create an edge between two terrain tiles
/// If the slope between two tiles is too great, return null, indicating that there is no connection between tiles
/// </summary>
/// <param name="tile"></param>
/// <param name="neighbor"></param>
/// <returns></returns>
public static MapEdge Create(MapTile tile, MapTile neighbor) {
var cost = CalculateCost(tile, neighbor);
if (cost < 0.6f) {
return new MapEdge(tile, neighbor, cost);
}
return null;
}
private MapEdge(MapTile n1, MapTile n2, float cost) {
Node1 = n1;
Node2 = n2;
Cost = cost;
}
Finally, we need to add an array of MapTile objects to our Terrain class, to store our map. We will also store the dimensions of the map in tiles, to simplify some of the lookups that we need to make into this array:
// Terrain.cs
private MapTile[] _tiles;
private int _widthInTiles;
private int _heightInTiles;
private const int TileSize = 2;
Creating the Tile Map
Now, we have an array of MapTiles defined, but to get any use out of that array, we need to generate the tilemap during our Terrain class’s Init() function. We want to perform this initialization after creating our terrain heightmap, but before generating our picking quadtree and initializing our rendering resources. This is accomplished by our InitTileMap() function and its helpers:
private void InitTileMap() {
ResetTileMap();
SetTilePositionsAndTypes();
CalculateWalkability();
ConnectNeighboringTiles();
CreateTileSets();
}
The first step of this process is to clear any existing map and reset the MapTile array to defaults, which is the purpose of the ResetTileMap() function. First, we calculate the dimensions of the map, by dividing the heightmap dimensions by the number of terrain mesh triangles that make up a map tile. Then, we allocate a new MapTile array, and initialize each element to a blank MapTile.
private void ResetTileMap() {
_widthInTiles = Info.HeightMapWidth / TileSize;
_heightInTiles = Info.HeightMapHeight / TileSize;
_tiles = new MapTile[_widthInTiles*_heightInTiles];
for (var i = 0; i < _tiles.Length; i++) {
_tiles[i] = new MapTile();
}
}
Next, we need to initialize each tile in the map with its location, both in world-space and in map-space. Calculating the world position of the tile is a little gnarly: we first calculate the world-space edges of the tile, using the vertex spacing and tile size, then offset to the center of the tile, and then offset again, since our terrain mesh is centered on (0,0). Then, we use our Height() function to determine the y-axis height of the tile center. We also set the type of the tile, which corresponds to the blend map texture that is used for rendering.
public MapTile GetTile(int x, int y) {
return _tiles == null ? null : _tiles[x + y * _heightInTiles];
}
private void SetTilePositionsAndTypes() {
for (var y = 0; y < _heightInTiles; y++) {
for (var x = 0; x < _widthInTiles; x++) {
var tile = GetTile(x, y);
tile.MapPosition = new Point(x, y);
// Calculate world position of tile center
var worldX = (x * Info.CellSpacing * TileSize) + (Info.CellSpacing * TileSize/2) - (Width / 2);
var worldZ = (-y * Info.CellSpacing * TileSize) - (Info.CellSpacing * TileSize / 2) + (Depth / 2);
var height = Height(worldX, worldZ);
tile.WorldPos = new Vector3(worldX, height, worldZ);
// Set tile type
if (tile.Height < HeightMap.MaxHeight*(0.05f)) {
tile.Type = 0;
} else if (tile.Height < HeightMap.MaxHeight*(0.4f)) {
tile.Type = 1;
} else if (tile.Height < HeightMap.MaxHeight*(0.75f)) {
tile.Type = 2;
} else {
tile.Type = 3;
}
}
}
}
Once we have calculated the world-space positions of the map tiles, we can determine whether the tile as a whole is walkable. Depending on your needs, you could determine this based upon buildings, trees, rocks or other obstacles, or certain terrain types that you wish to consider impassible. Currently, I am only determining this based upon the average slope between the given tile and its neighbors; the idea behind this is to prevent creating map edges that allow movement along a contour line on steep slopes or cliffs.
private bool Within(Point p) {
return p.X >= 0 && p.X < _widthInTiles && p.Y >= 0 && p.Y < _heightInTiles;
}
private void CalculateWalkability() {
for (var y = 0; y < _heightInTiles; y++) {
for (var x = 0; x < _widthInTiles; x++) {
var tile = GetTile(x, y);
if (tile == null) {
continue;
}
var p = new[] {
new Point(x - 1, y - 1), new Point(x, y - 1), new Point(x + 1, y - 1),
new Point(x - 1, y), new Point(x + 1, y),
new Point(x - 1, y + 1), new Point(x, y + 1), new Point(x + 1, y + 1)
};
var variance = 0.0f;
var nr = 0;
foreach (var point in p) {
if (!Within(point)) {
continue;
}
var neighbor = GetTile(point);
if (neighbor == null) {
continue;
}
var v = neighbor.Height - tile.Height;
// ignore neighbors on the same plane as this tile
if (v <= 0.01f) {
continue;
}
variance += v*v;
nr++;
}
// prevent divide by 0
if (nr == 0) nr = 1;
variance /= nr;
tile.Walkable = variance < MapTile.MaxSlope;
}
}
}
Once we have calculated the per-tile walkability, our next step is to connect the tiles with MapEdges. This is very similar to the previous function: we loop over each tile in the map, and then over its neighboring tiles, using our MapEdge.Create() factory method to build an edge between the tile and each valid neighbor.
private void ConnectNeighboringTiles() {
for (var y = 0; y < _heightInTiles; y++) {
for (var x = 0; x < _widthInTiles; x++) {
var tile = GetTile(x, y);
if (tile != null && tile.Walkable) {
for (var i = 0; i < 8; i++) {
tile.Edges[i] = null;
}
var p = new[] {
new Point(x - 1, y - 1), new Point(x, y - 1), new Point(x + 1, y - 1),
new Point(x - 1, y), new Point(x + 1, y),
new Point(x - 1, y + 1), new Point(x, y + 1), new Point(x + 1, y + 1)
};
for (var i = 0; i < 8; i++) {
if (!Within(p[i])) {
continue;
}
var neighbor = GetTile(p[i]);
if (neighbor != null && neighbor.Walkable) {
tile.Edges[i] = MapEdge.Create(tile, neighbor);
}
}
}
}
}
}
Our last step is to create sets of connected tiles. This is a necessary optimization step for our pathfinding algorithm, which allows us to easily check if it is possible for a path to exist between two points. Without this preprocessing, our algorithm would need to expand every tile in the map before deciding that no path existed.
First, we assign each tile in the map to its own set. Then, we loop over the tiles again, checking each tile against its neighbors. If one of the neighboring tiles belongs to a tile set that is less than this tile’s set, we add the tile to the tile set of its neighbor, and set a flag that indicates that the tile sets have changed. We repeat this process until there are no more changes, at which point, we have calculated all the sets of connected tiles.
private void CreateTileSets() {
var setNo = 0;
for (var y = 0; y < _heightInTiles; y++) {
for (var x = 0; x < _widthInTiles; x++) {
var tile = GetTile(x, y);
tile.Set = setNo++;
}
}
var changed = true;
while (changed) {
changed = false;
for (var y = 0; y < _heightInTiles; y++) {
for (var x = 0; x < _widthInTiles; x++) {
var tile = GetTile(x, y);
if (tile == null ) {
continue;
}
foreach (var edge in tile.Edges) {
if (edge == null ) {
continue;
}
if (edge.Node2.Set >= tile.Set) {
continue;
}
changed = true;
tile.Set = edge.Node2.Set;
}
}
}
}
}
At this point, we have fully generated and preprocessed our terrain map, and we can move on to implementing the actual pathfinding algorithm to determine the optimum path between two tiles in our map.
Stay tuned for part two.
No comments :
Post a Comment