Now that there's a protagonist and a rough gameplay idea, the storyline needs to be developed so as to mesh with the gameplay.
The Barrier Realm has been closed off from the rest of the world for some time, let's say about three or four generations, so still within living memory, but only for the oldest people living there. The rest of the country left them to it, since there wasn't much of value in that small area. The people inside the wall built a peaceful little community, largely self-sufficient and only open to visitors and tradespeople with specific papers.
Lena, young woman living in a village in the Barrier Realm called Havenook, is training to be a teacher. She is well-read and practical, less artistically inclined and more logical than most people in her community.
Out of the blue, the village is attacked by gangs from outside the wall, who have apparently discovered that the closed off community with no security measures is an easy target. The Gang's leader boasts that the seal mark on his hand makes him invincible, and using this ability he scaled the great wall, jumped inside and unlocked the door from within to let his gang through. A distraught Lena, cornered when trying to get the other villagers to make a break for it, pushes the gang leader and unexpectedly absorbs the seal from him!
This leads to something of a stand-off, since Lena can't fight at all, but the Gang have no means to hurt her, but fortunately at that moment, another outsider appears and dispatches the Gang single handedly, sending them running for the gate. The stranger also bears a seal on her hand, which seems to give her a power that multiplies the force with which she impacts her surroundings, hence she was able to send the gangsters flying with even very light looking punches! She explains that her name is Grace and she works for the government. She's around her late twenties, early thirties and extremely straightforward and no-nonsense.
Grace explains that people in the outer world about ten years ago, created a machine that allows non-magically inclined people to find Lay-Crosses (Layline crossing points) and absorb seals from them, an ability previously only open to very lucky people, most of whom never discover their ability because they'd only realise they had it on getting close enough to a Lay-Cross to detect it. It didn't take long for people to find and end up constantly fighting over Seals, and it was only a matter of time before people turned their eyes toward the Barrier Realm, which it turns out sits on about six!
Time is of the essence. The only thing preventing all kinds of unpleasant people getting to the Lay-Crosses is the rugged landscape of the realm. Some have already been taken. The Seals must all be either nulled so that only natural Mages can use them, or have the power passed onto a worthy bearer. In order to do this, Grace needs Lena, a natural Mage with knowledge of the area.
Lena, feeling she's not up to this, explains that there's a Natural Mage in the main hub city of Aldcastre. An old Sage with the power to absorb and communicate great amounts of information, who is in charge of the Great Library. They rush across the moors to the City, only to discover that the Sage passed on just two days previously, and passed on his power to his apprentice, a man called Aldan. Aldan is a natural Mage of about thirty years, which for a Sage and head Librarian is extremely young, his Seal gives him an amazing memory for facts and concepts, and telepathy, and he explains that, knowing the area, there is no way he can get through the dangerous terrain surrounding the Crosses. He can, however, give Lena advice, as he knows the location, at least roughly for most of the Crosses.
So Lena sets off on her quest to close off all the Crosses. She must get through difficult terrain in order to reach them. Later in the game, she must sneak through enemy fortifications and cities to take back Seals and return them to their proper places. There are also logistical problems whereby having got herself to a place, she needs to work out how to get Grace there too, since her super-impact power can be used to clear obstacles. As she moves around, Aldan and Grace (speaking through Aldan's mental connection) can give advice, or more often, natter away and take the mickey.