By: Aaron Woods and Micah Neumark
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.
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.
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.