I've been mulling over a big change. Guards need to have local knowledge of the current state of the world but use their memory of the default state of the world elsewhere. At the moment they use global knowledge of the current world state. If they are traveling somewhere and you open up a shortcut to their destination, they will veer toward it even if you opened it up out of their sight. For instance:
In this picture the guards are attempting to get to the open door next to the ghost (ignore him; he doesn't do anything yet). The window just southeast of the thief is locked from the inside so they have to take a very long route. If the thief opens the window, however, they will currently instantly change their path to this:
They shouldn't do this because they have no way of knowing that the window was opened.
I think what I will do is prepare a “field of view” for each guard on each turn. This would be an overlay created by using a version of the field of view algorithm that the thief and lamps use for projecting sight and light, respectively. When checking the world state, the guard would check the overlay first, and, if it didn't see the square, go to the world map and get the default state for that square.
This is a fairly big change, though. In the mean time I've tightened up the existing path-finding code and made a couple of improvements.
The main optimization was to reduce the number of searches the code does. The previous code was pointer-free, so there were lots of lookups based on position. Adding a closed flag to the path nodes, rather than having a separate set, was the first step. Using pointers between nodes to represent the path, and using pointers in priority-queue entries for referring to the nodes, was the next step. Finally, I stored the cost estimate for reaching the goal on each node rather than recomputing it when needed.
The enhancements I made are subtle. While messing around with secret doors I noticed that guards would sometimes take the long way to get to the secret door. This happened when I would open the door, they would see that it was open, and then I'd close it again. (Currently they don't care that it has been closed; they travel to it regardless.) The problem was because a closed secret door is currently impassable to them. (This is going to change; I need to overhaul guard movement costs to take into account the direction through doors and whether the guard has a key to that door.) When a guard tries to move to an impassable location the normal pathfinding fails. In that case he picks the closest reachable point to the goal and moves there instead. The problem came when there were multiple reachable points the same distance from the goal. The guard was just picking the first one. Now, ties are broken by considering the cost to reach each point, so the guard won't do anything crazy.
The other enhancement is something I've been meaning to add for a long time but hadn't gotten around to. Guards choose uniformly randomly from all paths that have the same cost. This breaks up their movement so they don't always take the exact same route. Each time an additional alternate path is found there is a (diminishing) chance that the algorithm will switch to that path instead. Each node keeps track of the number of paths found to it so far with the same cost. The chance of picking a new path is 1/n so that every path is equally likely even though we roll the dice every time we add a path.
No comments:
Post a Comment