Posted by at 1:10 am  XNA DotA
Apr 222011


During compile-time, the Ground object is searched for a mesh called “NavPath”. This path is made up of quads and triangles and represents a navigation mesh of the Ground model.


After the “NavPath” mesh is found all the triangles (all the quads are converted into triangles as well) that make up the mesh are stored into another object, keeping track of the index of the vertices that make up the 3 corners of each triangles, as these objects are being created triangles that are neighbors are marked as such.

After all triangles are stored, the Floyd–Warshall Algorithm is used to calculate the all pairs shortest path between all triangles. The weight between shared edges are calculates as a cost of 1. The Floyd-Warshall Algorithm is one of those algorithms that in order to recreate the path a second matrix has to be created so it can be referred to while recreated the shortest path between 2 triangles. What makes this interesting is I don’t have to save the simple path matrix, just the path reconstruction “next” matrix.

At run-time when the Ground model is loaded information about the triangles is added with the midpoint of all edges as well as the barycenter (here, the arithmetic mean of the three vertexes) of each triangle. When a navigation path is requested with a start point and end point, the barycenters are used to calculate which triangles is closest to the start and end points, and a path, using the stored Floyd-Warshall “next” matrix, is calculated between those two triangles. The path returned is then the shared edge midpoints between those two, with the end point added on.

Using a self written style, based off the The AI Systems of Left 4 Dead, the minion cast a ray from its current position to the reversed edge point list. I reverse this list because what the minion is looking for is the farthest point they can straightly “see”, so once the farthest point is found we can short circuit and stop looking. These rays also are only checked against inside path walls of the Ground Model, otherwise a ray would always make contact with an outside wall.