Preventing the cliche part will be difficult, because you already have chosen a direction (map progression/type of dungeons and the use of elements (although it might help they are Chinese)) that is quite cliche on itself in respect to the fantasy setting of your game.

I hope that you're not fixed on the map progression, because some places might be better to switch if that is better for the story.

I'll have a thought about this today and see what I can come up with. Here is already one thing:

Dungeons (metal boss): One thing could be an old crashed and burried space ship (with the metal boss being a sort of powerfull robot, advantage is that tile sets from this could be reused for sci-fi related games), other idea is to have the metal boss to be some metal golem/construct in some sort of dwarven ruins (although this is going slightly into the cliche direction again, so that would have to be wrapped in the story quite carefully).

> For example, the hero of this story is not The Chosen One.

I think it could be interesting for the chosen one to exist somewhere in the world.  Perhaps he's a complete chump following in your foot steps after you've cleared the way, while taking all the credit for your accomplishments.  Maybe you're following after him, making sure he can get the job done (spoiler: he can't).  Maybe you have to find him to light a fire under his ass, and then you learn that he's worthless/unwilling so you have to save the world yourself.  Maybe it turns out that the chosen one you're looking for is actually the bad guy.  Maybe the chosen one is the real deal, but he's more messiah than fighter so you have to clear the way for him.

Going back to my previous idea about the storyline: There is a villain trying to steal the power of the gods.  He has each of the elemental gods shackled in secret places, and their power radiates out to shape the surrounding area.  The wood god's power causes the area to be a forest full of crazed hero-murdering ent monsters, etc.  Since the evil guardians gain strength from the trapped god over time, the ones in the later dungeons are stronger than the earlier ones.  The gods normally hold dominion over the elements, so the natural order is gone when they are chained.  Tornadoes, droughts, tidal waves, and earth quakes ravage the land, and the hero has to help set things right.  As the hero liberates more of the gods, the villain becomes desperate and captures the sun god to take his place.  In the final act, the hero must ascend the sky bridge to the local version of Mount Olympus to slay the villain and restore light to the world.

The above paragraph assumes that the hero is working to restore the world to order, but an alternative motivation for the hero is that he is a fallen angel, a casualty of the villain's ascension to the divine throne, who seeks to kill the villain to reclaim divinity and free the gods to whom he is still loyal (or he could turn rogue and try to take the power for himself).  The hero is stripped completely of power when cast out of the heavens, not even able to wield a simple dagger at first, but able to quickly regain staggering levels of power as he advances.  Also, he respawns when he dies because you can't kill a divine being for very long. :)

Potentially, the boss of each area would be an already-occurring denizen, warped by the power of the chained god.  Thus, the obvious choice for wood would be some ent-like creature, but I'd also be tempted to make it a bear or sasquatch, perhaps with a plant-like nature due to the divine presence.  For the metal boss, my instinct would be a minotaur chief, perhaps turned into some kind of half-metal monster armed with a spiked chain.  For the earth caves, I'd say the ant lion queen would be an obvious choice.  For water, a shark or squid could fit, or monstrous merman.  For fire... well, not many things live in volcanoes AFAIK but a scorpion or snake would go along with the desert theme.  For the final sun-defeating boss, I'm reminded of beliefs and superstitions that say that eclipses are the result of a dragon devouring the sun, and dragons have significance in Chinese myth, so the villain could easily be a dragon or somehow identify with dragons.

What if the main character (hero) pissed off the bad guy and now he has to gain the power of the elements just to be able to save his ass or perhaps he was working with the bad guys and now wants to redeem himself.

I believe that using a "shady" character would be an interesting twist since deeds of the past might haunt the main character,people will hesitate to help and you can accept and embrace that you are "evil"  or try to be "good" and hope you earn the respect and admiration of the people you are trying to save.

Perhaps a companion asks the main character about "what happened" and the story changes depending on what the main character's answer is.

Here's a scenario ...

Grasslands (feat. a pioneer village)

-Goblins have been attacking the caravans the road has been closed and you are stranded in this village (you are not a local)  a messenger is sent but you can't leave until The Order will come to help the villagers

-The folowing night disaster strikes !!! some villagers go missing, and an even sinister foe arises in desperation the village elder asks you for your help.

-You accept since you don't really have a saying in the matter and descend in to the local crypt were you fight undead

-You reach the Inner chamber doors but you have to fight the "final boss" (witch is extremely weak doe his recent resurrection) after a brief battle you naturally get you ass kicked but as you are about to get killed "The order" arrives and the final boss flees.

 -Now you find yourself "dragged" in this conflict since the "final boss" will surely come after you so you will have to confront him with or without "the order's" help.

I think there's a chance here to do something really interesting with the character.

I agree that he shouldn't be a standard 'chosen one' and that making him either somewhat shady, or incompetent, or arrogant, at least initially would add a lot to the player's interest in the character and add entertainment value to the game, especially if we begin to see a change in him/her. Also love the idea that he's haunted by his past...

Ok, have been thinking about this today.

Game starts with a group of thieves doing a great heist and the player is one of the thieves (the rookie). During the break in the leader finds a nice dagger and decides to keep it. The thieves do their heist and escape from the place (the user is introduced into how things work, inventory, fighting, etc.) The thieves walk back to their lair (in a forest), but the leader decides that one person less is more profit for the others and stabs you with the dagger he found. The thieves leave you in pain and the player looses his conciousness.

A monk finds you and decides to take you to his temple. The other monks take care for you, but when you wake up your body hurts (feeling of burning). You soon find out that the dagger was magical and you are "cursed" by it. The dagger was made magical by exposing it to an element source (in this case the fire element). First part of the story will be finding the water element source to undo the curse and other elements will come in the story, but not in a lineair way as "find all the elements and defeat the bosses". The state of the sources can also have an influence on the game world, for example if the wood source is corrupted/damaged, all trees in the game look dead or ill. The elements could be blended into the magic system and could even be used to create magical weapons.

Also, a possible side quest is to take revenge on the group of thieves.

How about provide a basic level and let people submit stuff to be included, as long as it fits somewhat in what is already there and see where it goes?

I am still fond of the idea of "The Chosen One" (preferably a noble or prince or something cliched) playing a significant role in the first act or two of the game (he's really saving the world at that point), but something in the player's actions causes his death, either indirectly or directly. The blame is tacked onto the player, though it wasn't intentional, and he is sentenced to death. The player must escape those he once called friends who now wish to kill him and either carry on the Chosen One's quest (because it will bring redemption or something) or he travels the world attempting to escape the vengeance of "the good guys." Perhaps he never really regains the trust he once had, but in the end he should find his place in the world.

Alternately: Maybe the hero is a soldier in the military of his nation. The army's campaign marches them all over the world, but the hero is often assigned tasks that ease victory for the army (eg. assassinate the enemy leader in his sleep, or scout out the cave system to find a safe passage through, or rally a group of tribal natives to join our cause.) This would give the campaign a linear direction (you can't question where your army takes you) and an end goal (defeat the other side's forces) and provides many large quest goals.

Maybe I'll take that second idea a step further. Perhaps the two (or more! some of which get destroyed throughout the game...) armies are racing to capture a powerful magical artifact. The Fire Chapter would end in the enemy general acquiring the artifact and ascending to great and terrible power. Then, the player (and that handful of powerful NPC's) have to go up to the sky bridge / villain fortress to defeat him.

# motivation for defeating all elemental bosses:

Every elemental has it's energy, but 99.99... of this energy is distributed and dispersed in the world. 

But some shatters of energy sources still exists, in concrete form in form of crystals, and every boss possesses such crystal (fire shard, air shard, ...).

These crystal are very powerful and are the sources of bosses power.

# Hero & Saver

People live in closed world protected with elemental energy from aggressive outside chaos. Thus, the elemental energy is vital for live. 

But evil bosses (actually old people kings/barons mutated with energy into something new evil things) possess energy crystals and using it to keep itself live and control his own army of undead / monsters. 

And because the energy is limited it causes the border of world is shrinking and consequently there's death and cataclysm in borderlands.

Hero - some unknown knight with his castle located near border, with current speed of border shrinking soon there will be no castle anymore. So, he has to free crystals from bosses and use it's energy as supposed - to support borders against chaos.

# Adventurer & Wanderer

Everyone knows that there's legendary crystals of power, some are possessed and guarded by mighty bosses, others are lost centuries ago.

Even if someone has only one such crystal - he will became super human entity - but if someone will possess it all - he'll be a godlike. Who would not want this?

Hero - unknown wanderer / mage / warrior obsessed with his dream about crystals and his power. Seeking everywhere (catacombs, lost temples, abandoned places in forest) for it's trace.

> Hero - unknown wanderer / mage / warrior obsessed with his dream about crystals and his power. Seeking everywhere (catacombs, lost temples, abandoned places in forest) for it's trace.

Hmm... maybe we have a medieval Indiana Jones / Lara Croft on our hands?

It belongs in a museum! ;)

Why not make the hero the reluctant anti-hero?, things would start like this:

Your girlfriends runs with her lover and dumps a huge debt on you, the local lord whom you are indebted says either you bring him a relic from XXX(insert location name here) or you get an axe to the neck. When you arrive to the place and are figthing with the boss, that jackass of a chosen one sneaks in and steal the relic. You return home empty handed, noone believing the great hero would do that (steal from you), but since the lord´s brother, lord of another village is short on cannonfodder you get send there with a small troop. You are ambushed in the nigth (maybe while camping on Zombie infested Ruins?) and gotta run for the caves. And so on...

All while your debt get bigger and bigger (since all the local lords are family and know of you and take advantage of you to get their shitty jobs done) and the overly stupid and unbearing Chosen one gets in your way stealing your glory and relics.

In the end the final boss is your girlfriend, and her lover is the chosen one, who is so stupid he got tricked to give to her all the relics he stole from you. Making her a powerful deviless and the final boss to beat (with lots of pleasure).

Think of "Bards tale" or "Deathspank"if you want inspiration for this kind of story, and you can make the hero as cheeky and badmouthed as you want (cmon we all now we are tired of chilvarious knigths on their quest to save the world). Along the way the hero even may be named the lord of a goblin village by accident and to his horror, and had no other option but to accept. And even end up being remembered as the most evil warrior ever existed (just for slaying the stupid chosen one.)

Long post.... hope you use one of this ideas.

Do you have to stick to having solely one character,

One idea I had would be to have two separate characters and at each level you switch to the other, the first character you play as fights for good and the second character fights for evil.

character 1 uses earth and water elements in magic

character 2 uses fire and air to aid their magic

The two characters lives are intwined and their fates collide in the final level where you can choose whether to fight for good or evil and you fight against the other character

depending on who wins there are different outcomes, you become hero or overlord

the reason they fight for different things is because of there backgrounds, they could have both been wronged by the world but their different outlooks meant that one fought to defeat the evil that had tortured him so that it would no longer harm anyone whereas the other character is fighting so that he can be the torturer and is driven by the want to rule the world to stop harm coming to him

In the final level both characters are so driven by there wants but once you kill the other you realize that your foe was your twin/brother/sister that you just killed, and you had shared your childhood with them and had been hurt by the same evil... parents were both killed by some evil (doesn't need to be said what)...

the ending could vary from the surviving sibling killing themselves because of the guilt or whatever

hope that idea interests you :)

Scribe

Hrm, I really like a lot of the points Danimal suggested. Also, it would be hilarious if the person accidentally ended up as the lord of a goblin village. Reminds me of the time one of my players killed the orc chieftan in a D&D game I was DM'ing and immediately declared himself chief. After a long series of epic roleplaying (he relinquished his dwarven race to become an orc in heart by publicly chopping off his own finger with a hatchet! :-o ) and rediculously high persuade/intimidate rolls, I finally permitted a small portion (~10%) of the warcamp to become loyal to the dwarf.

What about the "live story" via scripting? 

How many people did really read text screens during a game? it's boring and most of people just keep clicking the "next". But remember WarCraft 3, there are amazing stories told with actual heroes using game engine.

Look at this "story" (select 720, don't watch it in low res) - http://www.youtube.com/watch?v=dFuqLpI7ujc&feature=related - it's just unbelievable! And then imagine to read all this in half-screen text page, and compare the result.

What do You think?

> Well my game engine is 2D

I didn't mean to create 3d scene, W3 is just a sample, to illustrate the concept. I mean 2D scenes + maybe sound.

For example to illustrate this story element:

> And because the energy is limited it causes the border of world is shrinking and consequently there's death and cataclysm in borderlands.

Let's suppose that we already have 2 actual playable levels/maps in game:

- a village, and the Player must save an Alchemist who called him for help.

- evil boss level.

Here's how we can reuse it to create "live story":

- show part of willage map with purple light covering one side of map. There's people walking between their houses and trees. Hero (the knight) comes to the house of alchemist and asks "Why do You call for me?", the Alchemist says "I must tell You something - there's an evil boss under the ground".

- show part of boss map, the boss is walking around the crystal guarding it and commanding his undead minions.

- back to village, part of map with alchemist house, alchemist continues "because of lack of energy borders are shrinking"

- the same village map but another part of it, near the border - the light starts moving, covering more and more territory, people near border are running terrifying between their houses, when the moving light touches house or tree it dissapear, when it touches people they are falling dead. There's also "border-beasts" jumping out of light and killing people.

- back to alchemist house - alchemist says - "it's already began, we must leav right now, this place is not safe!"

- control returned to the Player, he must escape the moving wall of light, protect the alchemist from border-beast and come with him to the exit point of map.

The big advantage of this "live story" - we don't need to create new art, maps or monsters, just add some scenario-scripts to the existing maps.