In game, I have received several complaints about the fuzzy path walking option that is enabled by default in the client. This option was added to make the paths that actors take from one point to another less predictable (without it, everyone walks the same path when using the same coordinates). The most common complaint I have heard, was that the generated path was longer then needed, with too many turns, making the actor appear like it was drunk. A second problem, that I found while looking into this problem, is that the path fuzzing as it is currently implemented absolutely fails at its intended goal.
As an illustration of the second point, here is a heat map of the current pathfinder, on a simple walk, 10 steps in the x direction, and 5 in the y direction, averaged over 1000 tries. (apologies for the awful looking plots, but I decided I had spent enough time on this).
Note that the scale is logarithmic: the blue squares are actually 50-100 times less likely to be reached than the yellow ones. So, over 98% of the time, the actor is still following the same path. As an example of the first problem, here's the same sort of plot, but for a larger walk:
Note how in ~10% of the time, the actor walks down some distance in the y direction, only to find out there's a house in the way, and walks back up again before starting the final stretch. The same thing also happens in smaller walks, though on a lesser scale.
The current path fuzzer works by applying a random penalty on each step. In itself, this penalty is not large enough to affect the path in a single step, but in several steps the penalty can build up to make a path less desirable (this is also why the path fuzzer has almost no effect in short walks). However, the neighbour nodes are still evaluated in the same order as without the fuzzing enables, so the generated paths are still mostly the same. In addition to that, a heuristic is used that can (probably will), overshoot the actual cost of the path, which can lead to paths that are too long.
In an effort to make the path fuzzer better, I have done away with the random penalty, and instead evaluate the neighbour nodes in a random order. For the first test case above, this gives the following heat map:
i.e. much more random. In addition, I used an accurate heuristic, so the generated paths are all optimal in terms of the number of steps taken (assuming no cost for making a turn). To illustrate that, here's the second test case[1][2]
Of course, with no penalty for turning, it's entirely possible to generate a path that makes a turn on every step, which can visually be very distracting. However, if we apply a constant cost on every turn, only the paths with the lowest number of turns will remain, defeating the purpose of randomising[3]:
To avoid this, a penalty is added on a turn with a random chance, depending on the length of the straight stretch before the turn. Immediately after a turn the chance of adding the penalty is 1 when making a new turn, and this chance is decreased linearly to zero over a maximum straight segment length. In the examples above a segment length of 5 was used, this can be increased if it is found that the actor turns too often. Or the penalty chance can be decreased more slowly in the beginning.
While I am pleased with the results, it does come at a bit of a cost. For small maps, like IP, the difference is negligible. The time cost of the worst case scenario I could think of, a walk across the entirety of WS, goes from 7ms to 45ms on my laptop. This is mainly due to the fact that the accurate heuristic leads us to evaluate many more nodes. If I use the overshooting heuristic, the time taken drops back down to ~9ms, but then all randomization is gone as well (this heuristic is bad, it basically boils down to: go diagonally whenever you can). Of course 45ms is negligible in comparison to the minutes you then spent walking (heck, even a reply from the server for a single step takes longer to reach me), but the increase is there.
Anyway, I am willing to see if I can speed this up, but do we think it is worthwhile?
[1]; I realize this does no necessarily show that the paths are optimal, since one cannot see individual path, but they are, and the figure strongly suggests they are.
[2]: Note that the house is nicely avoided
[3]: This also illustrates a weakness in the proposed algorithm: although the two paths are equal in cost, the fact that the route that starts diagonally incurs the cost of the turn later makes that path evaluate its neighbour nodes earlier, making the occupation of the two paths asymmetrical.
(Apologies for the long post)
In game, I have received several complaints about the fuzzy path walking option that is enabled by default in the client. This option was added to make the paths that actors take from one point to another less predictable (without it, everyone walks the same path when using the same coordinates). The most common complaint I have heard, was that the generated path was longer then needed, with too many turns, making the actor appear like it was drunk. A second problem, that I found while looking into this problem, is that the path fuzzing as it is currently implemented absolutely fails at its intended goal.
As an illustration of the second point, here is a heat map of the current pathfinder, on a simple walk, 10 steps in the x direction, and 5 in the y direction, averaged over 1000 tries. (apologies for the awful looking plots, but I decided I had spent enough time on this).
Note that the scale is logarithmic: the blue squares are actually 50-100 times less likely to be reached than the yellow ones. So, over 98% of the time, the actor is still following the same path. As an example of the first problem, here's the same sort of plot, but for a larger walk:
Note how in ~10% of the time, the actor walks down some distance in the y direction, only to find out there's a house in the way, and walks back up again before starting the final stretch. The same thing also happens in smaller walks, though on a lesser scale.
The current path fuzzer works by applying a random penalty on each step. In itself, this penalty is not large enough to affect the path in a single step, but in several steps the penalty can build up to make a path less desirable (this is also why the path fuzzer has almost no effect in short walks). However, the neighbour nodes are still evaluated in the same order as without the fuzzing enables, so the generated paths are still mostly the same. In addition to that, a heuristic is used that can (probably will), overshoot the actual cost of the path, which can lead to paths that are too long.
In an effort to make the path fuzzer better, I have done away with the random penalty, and instead evaluate the neighbour nodes in a random order. For the first test case above, this gives the following heat map:
i.e. much more random. In addition, I used an accurate heuristic, so the generated paths are all optimal in terms of the number of steps taken (assuming no cost for making a turn). To illustrate that, here's the second test case[1][2]
Of course, with no penalty for turning, it's entirely possible to generate a path that makes a turn on every step, which can visually be very distracting. However, if we apply a constant cost on every turn, only the paths with the lowest number of turns will remain, defeating the purpose of randomising[3]:
To avoid this, a penalty is added on a turn with a random chance, depending on the length of the straight stretch before the turn. Immediately after a turn the chance of adding the penalty is 1 when making a new turn, and this chance is decreased linearly to zero over a maximum straight segment length. In the examples above a segment length of 5 was used, this can be increased if it is found that the actor turns too often. Or the penalty chance can be decreased more slowly in the beginning.
While I am pleased with the results, it does come at a bit of a cost. For small maps, like IP, the difference is negligible. The time cost of the worst case scenario I could think of, a walk across the entirety of WS, goes from 7ms to 45ms on my laptop. This is mainly due to the fact that the accurate heuristic leads us to evaluate many more nodes. If I use the overshooting heuristic, the time taken drops back down to ~9ms, but then all randomization is gone as well (this heuristic is bad, it basically boils down to: go diagonally whenever you can). Of course 45ms is negligible in comparison to the minutes you then spent walking (heck, even a reply from the server for a single step takes longer to reach me), but the increase is there.
Anyway, I am willing to see if I can speed this up, but do we think it is worthwhile?
[1]; I realize this does no necessarily show that the paths are optimal, since one cannot see individual path, but they are, and the figure strongly suggests they are. [2]: Note that the house is nicely avoided [3]: This also illustrates a weakness in the proposed algorithm: although the two paths are equal in cost, the fact that the route that starts diagonally incurs the cost of the turn later makes that path evaluate its neighbour nodes earlier, making the occupation of the two paths asymmetrical.