SalarShushan: Actually you made the right connection. The game was based on the novels of Piers Anthony and his magical world of Xanth. Have you read the books? I liked the early ones but lost track of the series later.
Really? Wow...
Years ago as a teen i was building a library with most of his books in it :P How far did i read... It was pretty darn far. I don't think i got through his whole every-letter-in-the-alphabet he was going for, but i read 20 books or so? God that was a long time ago.
I figured the game wasn't connected to Piers Anthony simply because the word Xanth could have been pulled from thin air as the name of the badguy, rather than the demon Xanth... Along with Mars, Earth, and... Jupiter? Although there were video games of book series long long ago, but the graphical quality was rather low. I remember trying to play Dragons of Pern on the Atari, getting hopelessly lost and quitting...
edit: Glancing at the screenshots and wikipage on the game, it does look familiar, and of course
Demons Don't Dream i remember that book. One of the larger plot points was one of the companions was randomly selected to betray you if you selected them, but they would only betray you at the last moment...
I was so excited for most of Piers Anthony's stuff long ago... Although it got weaker over time as he didn't try as hard after a while before putting a book out.