Oh boy, does he need maps.
I started by having Antidote remember where Red had already gone, which immediately improved his ability to figure out his surroundings. These maps persist between level transitions (i.e. if he goes downstairs, then back upstairs, he'll remember what upstairs looks like). Our hero is unfortunately blind, though, and can only "feel" his way around an area. The "X" marks in the screenshot above indicate areas he has tried to walk, but crashed into some solid object. The "?"s are places where he hasn't been yet, and are VERY enticing to the algorithm. Blanks are open, previously walkable areas that are appealing, but not as much as the unknowns.
This produces hilarious results in towns where NPCs sometimes wander about. Our hero will remember where he last crashed into people, and generally try to avoid those areas. But sometimes he'll check them again, and will overwrite his previous understanding of the collidability of a tile.
This method got him to crash into the tiles of grass above Pallet that trigger the Oak sequence much more efficiently than my previous algorithms, and I consider that a success. Unfortunately he hasn't been taught how to talk yet so he gets stuck once Oak warns him about tall grass.
I made a modification to this algorithm that uses heuristics. The number on a tile indicates how appealing that tile is to be on, factoring in the tiles around it. This produces much faster pathing successes, but with its own set of challenges. For example, it's currently possible for him to get stuck going between two tiles where the most interesting tile is the other one. The next step will be increasing the interest of places that aren't in his 10-tile walking history.
But that is a task for another day.