jeroenroosen/jpacman-framework — pull request #1 by michaeldejong (2013-11-13 20:42:47+00:00)
Title: Fixed navigation bug in pathfinding algorithm

This pull request fixes a bug in the pathfinding algorithm in the `Navigation` class. To find the problem I first benchmarked normal gameplay using jvisualvm. I found that the `findNearest()` method in the `Navigation` class took up 85% of all CPU time whilst playing. To further pin-point the problem I created a test which loads the `board.txt` file, and attempts to locate the closest `Ghost` on the board from the square at `(1, 1)` using the `findNearest()` method. The original `findNearest()` method took 53 seconds to solve this.

I found out that the same `Square` objects were added multiple times to the target list. This meant that every `Square` was visited multiple times, in turn causing more adjacent `Square` objects to be added to the target list again, until all `Square` objects were eventually visited. I've modified the `findNearest()` method to check that an adjacent `Square` object has not yet been visited and is not yet scheduled to be visited. This means that every `Square` is visited exactly one time. Additionally I modified the visited `ArrayList` to a `HashSet` since this has a better lookup time: O(1) vs. O(n).

Where the original solution took 53 seconds to solve the new test, this solution takes 15-20 milliseconds.