Ripped out all the old AI and tried some new stuff. I had a method that worked well, but it did all its work on a single turn, when the ghost reached an intersection. On slow machines this resulted in a pause once you reached the more complex mazes, which was rather disconcerting, and not a desirable trait for a video game.
I then tried a way of doing a little bit of the work each frame. Initially this was recursive and worked well. I thought it might be more efficient to do it iteratively and spent a lot of time working the bugs out. I still have to make this a little more efficient. It could probably do much less work per turn. In any case the ghost now makes great decisions when it is far off and makes decisions that are good but not great when it is near to the player. I think that this is a good balance, though it might appear counterintuitive. The ghost shouldn't be too smart, or else it when there are only a few pellets left it would just find one and sit on it, which wouldn't be much fun. In any case, it should not get caught in the loop behavior that plagued it before. Also the first move the ghost makes is going to be random and the first smart move that it will make is at the second intersection that it hits.
I could add virtual intersections to allow the ghost to turn around, but I like the predictability of only allowing decisions at intersections.
Oddly, the hardest thing to debug was the behavior in very small mazes. For example, it is possible to get a maze with no intersections, just one continual loop. Or a maze with just two intersections. I forced small mazes to test these conditions.
There were some more bug fixes as well.
Again, as a reminder, I have started to use Eclipse (well, ok WSAD, same thing) as my development environment instead of VisualAge for Java. Both Eclipse and VAJ are excellent tools. Note that the applet no longer runs if your Java is old. You can easily update it by downloading a new JRE at http://java.sun.com/.
