itch.io

The AI was fun to build (and honestly, took up most of this project's dev time). 

The first component was a scoring function: every tile gets a desirability score (where lower is better). To calculate it, a maze-solving algo figures out how many spaces away that tile is from the player following the walls of the maze (simple bucket fill spreading outwards from player worked well enough at our maze size). However, most tiles on the board are not connected to the player, and we assigned those a value of 100 by the maze algorithm. We then also calculate the Manhattan distance between the player and the considered tile. This number was divided by 10 and added to the maze-solver distance. E.g., a score of 3.3 meant that a tile was 3 steps away from the player by direct connection and also has a Manhattan distance 3 (straight line); a score of 100.4 means that a tile is unconnected to the player by the maze directly but is only 4 cells away by Manhattan distance. 

Then, we have the AI check every single permutation of 3 moves it could make. For each of those sets, it simulates where the player would end up, where it would end up, and scores its final position vs. the player. It chooses whichever trio of moves results in it ending at the lowest score. (There was additional layers of logic for optimizing shorter paths etc., but those would take even longer to explain through.)

The first couple iterations had some bugs to quash with the AI getting stuck at local minima, but once we had it "planning" 3 steps ahead, it went from dumb to incredibly competent... always such a joy to see your algorithm suddenly (and seemingly magically) beat you at your own game