WayPoints Project


By: Aaron Woods and Micah Neumark

Our Goal
 Our goal was to create a system of waypoints, allowing the character to simply follow waypoints to the goal.
This works by generating weights for each edge, relative to what terrain the waypoints reside in, and how close the waypoints are to the goal point.
The gradient that this creates allows the character to traverse easily along a short path to the goal, without knowing where the goal actually is.

Downloads
 The source code is available as a zip file here.
The base source code is available here.
The Mac OS X Binary (PPC, built in 10.4.6 on a Powerbook G4) is available here.
The presentation is available as a pdf file here.

Screenshots

Implementation Details
 The first challenge was to create the system of waypoints and to organize them into a grid. This was accomplished by creating both an edge structure and a waypoint structure. The Edge has the weight and pointers to two waypoints in it, while the waypoint has a pointer to an edge for north, south, east, and west. In addition, it also has a position vector. With this information, we can deduce the apporiate location to go to.


The next challenge was to implement an algorithm to appropriately weight the edges so that the character properly traverses the grid to the appropriate location. This ended up being a challenging proposition. Originally, we decided to use Dijkstra's algorithm. Unfortunately there were several problems with this. First of all, Dijkstra's Alogorithm does not involve a goal point. This was problematic. Secondly, regardless of which shortest path algorithm we used, we found that it could just as easily find a path going along the wall than down the middle since the distance is technically the same, even though, in practice, that would not be true.

The path down the middle yields a distance of 10. The path down the side also yields a distance of 10.

In the end, we ended up using a slightly simpler heuristic for edge weights. The terrain weights are taken into account, and then the Manhattan distance from the goal. We divide the Manhattan distance from the goal by the maximum distance possible (which, since the sides are equal and the play area can be divided into two isosceles triangles, can be found by sqrt(2) * side length) and multiply this number by the current weight set by the terrain.

Originally, we set the terrain weights to number such as 2, 3, and 5. Later, we realized that setting these numbers this high put too much emphasis on terrain, and not enough on Manhattan distance. After reducing these numbers, to along the lines of 0.2, 0.3, and 0.5, the character reacted much better.

Finally, allowing the character to follow the waypoints started out very simple, but began to get a bit more complex later on as we tweaked the performance of the character. First of all, in order to make the character stop once it has reached the goal, we needed to set a condition that checked whether the character had reached the goal node or not. If so, just home in on the goal node. If it has not, we need to decide where to go next. This is quite complex.

The basic idea is that we initially go to the closest waypoint, and from there, decide which waypoint to go to next based on the weight of the four edges (go to the waypoint with the lowest weight on the connecting edge). There are a couple of things to think about in this area.

First of all, how close should can we be when we say we have reached a waypoint? This took a bit of tweaking but we realized that the number we used should somehow be related to the distance between waypoints. Eventually we settled on a 2:1 ratio. This gave us better behavior.

We began running tests at this point to watch the behavior of the character. There were times when the character would seem not to move at all. This was fixed by not allowing the character to go back. There should not really be a time when the character needs to backtrack, because if it does, it will only end up going back and forth between those two waypoints.

There were times when the character would start zig-zagging toward the goal. This was more complicated to improve. Due to a weight calculation error, the debug output showed that the zig-zag motion seemed to appear because the distance from two adjacent waypoints seemed to be equal even though there was an obviously correct choice. In order to solve this, we checked to see if any of the adjacent weights were equal, and if so, check the other two weights to see which was lower. We subtract a small amount from the closer of the two equal weights to the lower weight.

If c < d, then the East Weight will have .001 subtracted from it.
If d < c, then the West Weight will have .001 subtracted from it.