nkzw-tech / athena-crisis

Athena Crisis is an Advance Wars inspired modern-retro turn-based tactical strategy game. Athena Crisis is open core technology.
https://athenacrisis.com/open-source
Other
1.37k stars 105 forks source link

Skip already-visited tiles during radius calculation (approx. 5% fewer tiles) #25

Closed ide closed 1 month ago

ide commented 1 month ago

We have found the shortest path to a given tile when it is dequeued from the priority queue for the first time. There is no shorter path because all other tiles in the priority queue have the same or greater cost from the starting tile (Djikstra).

To keep the implementation simple, this commit uses the existing closed array to mark tiles that have been visited. We can also remove the check for currentVector.equals(start) because the tile for start will already have been put into closed.

The tests pass. The number of visited tiles is slightly lower in one of the Radius test cases (added logging to measure this).

The random MapGenerator test perhaps shows a more representative impact. I ran it one time before and after this commit, and looked at the average number of tiles visited in calculateRadius during each run: before = 395, after = 372. Of course, there is randomness and it shows we can expect about 5% savings in tiles visited.

cpojer commented 1 month ago

Amazing, thanks for the PR and the improvement! Radius calculation is finicky, especially with Trenches that take movement points on traversal in/out but the tests should catch all of the edge cases these days. I believe in a past version there was an issue where a shorter path was discovered later on, but that was before I made use of the priority queue.