This is one of the all time classics - an extremely challenging and fun game requiring tactical skill, planning, and not an insigificant amount of memory.
The gist of it is - each player is a Titan (2-6 players) and you start with 6 weak creatures (2 centaurs, 2 gargoyles, and 2 ogres) and move around the masterboard in a semi random fashion (you roll a die, but don't always have many choices). The masterboard is divided up into "terrain" types which are essentially biomes. Plains, swamp, jungle, tundra, mountain... (Titan also has "Brush" and "Marsh" and "Towers" and no ocean, but there is an extremely good correspondance).. This is what gave me the idea.
In Titan, your forces are in "stacks" of up to 7 creatures - you cannot have more than one stack in 1 location (terrain). There are about 20 types of creatures and they each "recruit" others - but only in certain terrain types.
A creature can recruit one of it's own OR upgrade (if you have 2 or 3 of them). Most creatures can be recruited 2 different terrain types (some only 1).
When you reach 7 creatures you can split your stack - usually the two weakest form a new stack, so you can continue to grow your armies.
The rest of the game is essentially fighting - when two players stacks meet, they have a little tacticle battle on a small hex grid (roughly 4x4) called a battle map. There is a different battle map for each terrain type, and "native" creatures have advantages and/or can ignore obstacles. Winning a battle gets you points - more points for more and more powerful creatures you kill - and every 100 points your Titan gets stronger in battle.
I think we could make a pretty fun minecraft version of this game... but it would take more than a little work.