First, assume that the AI has some kind of overall goal. E.g,, "Find the boss" in your example. Yea you want to beat it, but really it's about finding it. Assume it has no idea how to get to the goal, just that onceit exists. And it will know it when it finds it. Once the goal is met, the AI can stop working to solve the problem.
Also, I'm going to use the generic term "lock" and "key" here, even if it might be a chasm and a feather. I.e., feather "unlocks" the chasm "lock".
Solution Approach
It seems like you'd start first with just an AI that was basically a maze explorer (if you think of your map as a maze). Exploring and mapping out all the places it can go would be the primarily focus of the AI. It could be based purely on something simple like, "Always go to the closest path I have seen but not yet visited."
However, a few rules would kick in while exploring that might change the priority...
- It would take any key it found, unless it already had the same key
- If it found a lock it had never seen before, it would try every key it had found on that lock
- If a key worked on a new type of lock, it would remember the key type and the lock type
- If it found a lock it had seen before and had the key, it would use the remembered key type (e.g, second red lock found, red key worked before on red lock, so just use red key)
- It would remember the location of any lock it could not unlock
- It would not need to remember the location of locks it had unlocked
- Any time it found a key and knew of any previously unlockable locks, it would immediately visit each of those locked locks, and try to unlock them with the new found key
- When ever it unlocked a path, it would simply revert back to the exploration and mapping goal, prioritizing stepping into the new area
A note on that last point. If it has to choose between going to check out an unexplored area it's seen before (but not visited) versus an unexplored area behind a newly unlocked path, it should make the newly unlocked path the priority. That's probably where there are new keys (or locks) that will be useful. This assumes a locked path probably won't be a pointless dead end.
Expanding the Idea with "Lockable" Keys
You could potentially have keys that can't be taken without another key. Or locked keys as it were. If you know your old Colossal Caves, you need to have the bird cage to catch the bird - which you need later for a snake. So you "unlock" the bird with the cage (which doesn't block path but can't be picked up without the cage), and then "unlock" the snake (which blocks your path) with the bird.
So adding some rules...
- If a key can't be taken (it's locked), try every key you already have on it
- If you find a key you can't unlock, remember it for later
- If you find a new key, go try it on every known locked key as well as locked path
I won't even get into the whole thing about how carrying a certain key might negate the effect of another key (Colossal Caves, rod scares bird and must be dropped before bird can be picked up, but is needed later to create magical bridge).
