This semester, we did a research project on a game called Mario Chase. Rules can be found here. The game is basically hide-and-seek. The only change is that those who are seeking (toads) the person hiding (Mario) know how far away they are from the person. The person hiding also gets to move around throughout the game. This problem would be trivial if we knew where on the board the seekers were, however; we do not have that metric. This is also not a problem that can be found through graph traversal methods, because the goal state (where Mario is) changes frequently. Graph search also does not work because we do not know what the goal state is, only how far away we are from it.
We ran several algorithms, and found the most efficient one for finding Mario was rather simple:
for each toad: replace the previous distance to mario with current distance. recalculate the toads distance to mario. if the previous distance is smaller than the current distance: move the toad in a random direction else: move the toad in the same direction
It was great to work on this with my friends Adam Peters and Lee Hiler!
EDIT: The github repository is located here. The system was designed to model mario chase as simply as possible. We render the maps, and than we save them as JSON. We than made a quick node server to fetch these data files, and view them in browser.