As I wrote earlier, it will be a GP Improvement indeed. I'm not sure if I can use the Civ4 mechanism, even if it works, because the discovered resources should depend on local terrain and features, and also the improvement should be removed after discovering a resource.
In that case, just use the Deep Mine method from my own mod. It's in the Base mod, file "Terraform.lua", plus related bits in the Builds, Improvements, and Units XML files. If you're changing it from an every turn to a semi-random thing, then as long as the randomness is checked BEFORE the map is scanned, it shouldn't be a problem.
That is, let's say you want a 5% chance per turn per Improvement. So, what you do is check the Player:GetImprovementCount() function for each player, then add the total up. That'll tell you that you have N of them on the map. So do a random draw of 20 (which means 0-19); let's call the result M. If M >= N, don't scan the map. If M < N, then start the map loop. As soon as you reach the (M+1)th instance of the improvement, write down the location and break() the loop. That saved location will be the hex that gets an improvement; do whatever randomization of resources you need, place the deposit, and then remove the improvement.
There. You only need one map scan, you can abort it halfway through on average, and the only headaches are:
> Only one hex on the map can ever get a resource on a turn. It'll still average out to the same amount of time as randomizing individually, so this might be an improvement.
> The math breaks if you have more than 20 (that's 1/(5%)) of them on the map at the same time. That's easy enough to fix; just drop the break(), roll 0-19 for M instead of 0-(N-1), roll 0-(N-20) (let's call that one L), and upgrade the 20+Lth as well as the Mth. Repeat as necessary.
Hmm, I also plan the features to grow for some civs (Forest for Elves, Jungle for Lemuria, Marsh for Vodniks, with a higher probability next to existing features of the same type, but also possible elsewhere), this will probably require scanning the map as well so perhaps I'll just use my original idea
If you want the features to grow naturally, then yes, you'd probably need a full-map scan each turn, although you could get around that by populating a "candidate" array every 10 turns. Record the positions of all hexes that might be grown into, do random draws on that list, and on every 10th turn do a full-map scan to update the list. There'd really be no need to scan every single turn; sure, there might be a few quirks (like a forest growing adjacent to a hex where you just chopped a forest, or a recently-conquered Elven city might spawn forests even though it's now owned by Lemuria), but it shouldn't be too bad.
If you want forests and such to be planted by workers, see my terraforming code again. It makes things quite a bit easier.
--------
In fact, combine the two ideas. Make a new improvement; let's call it a "Tree Farm". All three of those races have a unique worker unit that can place them, using slightly different Build actions (to lock out different terrain types) and every 10 turns the game does a map scan and decides which hexes can also grow them naturally (unimproved hexes adjacent to existing Forests, Jungles, and Marshes); the game also records which type of adjacent foliage was the source for "natural" spread, and records the type favored by the planting unit's civ in the case of artificial spread. Use the graphics from Spices, or Incense or something for this improvement. The game randomly decides if a Tree Farm will upgrade itself this turn, using the kind of random draw I described earlier for your prospector; each might have a 10% chance of upgrading each turn.
Then, when it DOES decide to upgrade one, check the CURRENT owner of the hex. If it's the Elves, the Tree Farm is replaced with a Forest, even if the initial Tree Farm had been planted by a Lemurian unit or if the hex had naturally spread from a Marsh or Jungle. If it's the Lemurians, then it's replaced with a Jungle. If it's the Vodniks, then Marsh. Anyone else, or unclaimed land, and it goes with whichever type of vegetation the game recorded when it added element that to the candidate array.
Now yes, this means a Jungle can spawn because of an adjacent Forest or vice versa, within those races' territory but if these civs have regional start biases, that generally won't be an issue. You can also get around that by just going with the type when the hex was originally picked as a candidate for natural spread, regardless of who owns it, and just put the racial biases directly into the candidate logic (so only forest hexes in Elf-owned areas will be added to the list).
There. That's a mechanism that'd let you keep those racial biases, even adding the ability to plant those forests with workers, without requiring more than one map scan per 10 turns.
I hope it doesn't take so much time to make playing at reasonable speed impossible.
To someone on a reasonably up-to-date computer using anything other than the largest map sizes, it shouldn't be too much of a problem, although it'll depend a bit on how much you do in that loop. Now, there ARE those folks who love epic games on huge Earth maps... they'll have problems with this.