Several things I need answered.
>1. How did they end up there?
2. Who are they fighting?
3. Main boss(es): why do they want the staff?
1 ... this 2 characters... where some random prison cell mates, that got there randomly... from various "charges?" or ... they where long life friends, who had a common dream, to become the best sheepherders in the whole realm, but they could only achieve it if they managed to take a hold on the most mythical and powerful herding item there was ever created by the Celestials that created all beings... and left this artifact on earth so that those who posses can bring peace and prosperity to the world... that is if they want to do good. they ended up in the cell, by entering the wrong village, and doing some "scams" so they can sustain themselves, in their quest in finding that "mythical staff", but as they where running their "scams" they got caught by the village guards, and sentence to hang or something odious ... as it happens, their despair is their luck also, as it happens and will be shown that the room they where kept in had a "hidden passage" to a secret treasure room under the kings palace. paba baaaaam!! they found the secret room, by trying to escape, while one of them noticed some brics could be taken out of the wall. paba baam baaaaaam!!!
2. the evil shepherds alliance or better known as (ESA) they where some sort of evil group that wanted to get the staff so they can exploit the world, and make money or fortune on the backs of all creatures and subdue everyone.... TADADAAAAAA!
3. i think point 2 explains it.
on point 3 u can have different difficulty bosses, from the lowest rank (foot soldiers, leutenends etc...) in the ESA hierarchy to the highest (aka the leader or the boss of the bosses etc) bidibup bop!
(this is basically all plots and story lines in all scifi/adventure movies/games/stories in all times...even the bible and the Round Table Knights... and so on and so forth..."holy grail story" etc, santa claws, grinch same plot.)