My Absolute Solver

[MaxAstro]

I'm pretty proud of this, considering I've never written a maze solver before or even researched how to write one; I basically came up with this entirely myself.

This solver handles mazes of any size and seems to be reasonably fast (although I'm sure there are much better ways to do this that people who actually study maze problems know). I haven't tested it on recursive mazes but I suspect it will usually solve them (and Randy will solve them eventually for sure - for potentially very large values of "eventually").

It works by building a weight table, where tiles closer to the treasure are more highly weighted; as the drone moves, it pushes down the weight of tiles it has visited, and it tries to avoid returning to a tile it just left. If it reaches a dead end and has to backtrack, it marks all of the tiles it backtracks through as impassible until it reaches a split.

This always eventually works for mazes with no loops, but to speed things up the drone can spawn up to seven additional drones with different "personalities": Four have a favorite cardinal direction they will always try to prioritize when making choices, two prefer to turn either left or right when able, and Randy does whatever he feels like. He still has a slight preference for tiles closer to the treasure (and will grab the treasure if it's right next to him) but mostly makes choices randomly.

All of the "personality" drones will still prefer unvisited tiles over already-visited tiles, even if the visited tile is their favorite choice.

With all eight drones in play, most of the time one of the drones will happen to pick the shortest route to the treasure.

One improvement I've considered but not implemented yet is having the drones all spread out across the farm before creating the maze; as it is, I kinda like watching them race each other.

Code here: https://pastebin.com/1NhpKZFW

[umop-apisdn]

Blinky, Pinky, Inky, and Clyde send their regards.
Thanks for the inadvertent trip down memory lane!