Enable adventurers to discover existing beasts

[loothero]

When a beast is discovered, it is minted/saved to the blockchain. If the beast kills an adventurer, it receives XP the same as adventurers. Currently however there is no way to encounter these on-chain beasts which limits the fun.

We should update our Adventurer explore() function to have a small chance to find an existing beast. The chance should increase with the number of beasts on-chain (ones that have slain adventurers) but should never exceed 20% chance.

[starknetdev]

I believe we still have an issue on this in regards to computational complexity or storage, something I don't think Cairo 1 will be able to solve either.

Two of the only approaches I can see will be costly in gas. Both of these come after the chance to discover an existing beast has been calculated:

First approach is to store an array of the beast IDs that have defeated an adventurer, then use rng to pick one between the size of the list. The problem is that the storage costs could be large and theoretically infinite, even if the beats are removed from this array when killed.

Second approach would be to generate a random number between the total number of beasts and check whether it's alive (slain an adventurer). If the outcome is negative, we would increment this number in a loop, until a beast which is alive is found. Although there is no added storage costs, the computation required to loop through the beats is large, and if none are alive, then it's large computation for a pointless outcome.

Interested to see if anyone has another potential solution?