Back in '99, Inogrames released Outcast, an excellent adventure game that presaged the sandbox gameplay of GTA III by two years. As a Navy Seal, your mission is to escort three scientists to a parallel dimension in order to close a black hole threatening earth. Sounds like typical action fare, but things get interesting when you begin interacting with the dimension's people. The Talans, as they are called, hail you as their messiah. Theirs is a world of servitude and social strife. As you interact with the townsfolk, the story unfolds in non-linear series of quests and chance meetings. Common today, revoutionary for the time. Perhaps a little too revolutionary, as the game received universal accolades but flopped commercially.
It was the first game with an open-ended 3D world that the player was free to explore at his leisure. Additionally, it achieved a perfect, seamless balance between intense firefights and casual exploration, perhaps even better than that found in GTA III. The game seemed to live and breathe on its own, regardless of player action. The world of Adelpha would keep on turning, whether you wanted to further the overarching plot or not. The excellent artificial intelligence rivals even today's games. All this was soundtracked by the Trans-Siberian Orchestra. This too was progressive. Unfortunately, the development studio responsible for Outcast shuttered before they were able to start work on a planned sequel.
Anyway, some dudes are now doing an unofficial sequel using the Crysis engine. Hope the self-described amateur developers are able to capture the game's unique charm and don't run into any legal trouble. They've finished one of the world's regions as of March.
See that Stargate-lookin' portal there? That, my friend, is a Daoka. You use them to bop around the planet quickly. Not too compelling, but it's the only video footage I was able to find.