When I first meet John Marston he's resting in the wilderness, beneath an open sky. The day is just beginning, and there's work to be done. The former outlaw rises from his spot besides the remains of a campfire, and walks over to where his horse is diligently waiting; moments later they are racing across the plains. A coyote appears, chasing the horse's heels. Marston calmly steers his ride in a wide arc, levels his pistol, and shoots the critter dead. Welcome to Mexico. Welcome to Red Dead Redemption.

Technically, this is a sequel - or at the very least a follow-up - to 2004's Red Dead Revolver - but aside from the return of the Dead Eye aiming system (think bullet time, but with Stetsons) this could almost be an entirely different license. There's a new storyline, a new anti-hero and a brand new structure. While the first game was a comparatively restricted third-person adventure, a half-finished project that Rockstar inherited from Capcom, Redemption is quite clearly a rootin', tootin' relative of the Grand Theft Auto gang. True, there may be no cars to steal, and fewer pedestrians to "accidentally" mow down, but the open world is still arguably the star of the show: an enormous playground in which you can live out your cowboy fantasies. And as we've come to expect from Rockstar's sandbox ventures, there's a huge amount to see and do.

For a start, the aforementioned coyote is just one of the creatures that you'll encounter out on the frontier strip. There's a whole miniature eco-system at work here: If you shoot someone and leave their corpse out in the open, vultures will show up to tuck into your handiwork. Slow the pace down as you gallop from point A to B, and you might spot a few rabbits hopping about. If you want to earn yourself a bit of cash, you can hunt the poor bunnies and skin them. If you're feeling really adventurous, you can go all Cormac McCarthy and try to tame a wild horse. This will take some effort (and some form of "mechanism" that the developer has yet to reveal), but if you succeed you'll have a loyal nag that responds to your beck and call. As we'll discuss later, this can be extremely useful.

For today's adventure, however, Marston is more concerned with human beings than with animals. He begins by riding to a nearby town, where the NPCs are going about their business. Everyone here has their own routine, and if you're got a spare moment you can watch them as they go about their activities.

You can bet that things won't stay quiet for long.

During the day you'll find most people milling about the marketplace. You'll see people chopping up chickens and preparing other foodstuffs, as well as running various stalls where you can re-supply. Two items stand out during the live gameplay demo I'm watching: the bandana lets you hide your identity, which in turn allows you to commit major crimes (Marston can't just go on an undisguised rampage, presumably as this would interfere with the plot), while the advanced campsite will give you some form of bonus when you stop for a rest. It seems that you can camp and save the game wherever there's a path of flat, open ground, and doing this will helpfully spawn a horse if you've managed to lose your ride. It's hard to see what else you could need from these rests, but apparently the advanced campsite will be well worth the investment - and there'll be a visible difference to your impromptu home, too.

Retail therapy may be the key activity during the day, but in the evening the market empties as people retire to the nearby cantina. Here players can drink, get into fights over women or play poker. You can't cheat, sadly, but you can start gunfights if you're unhappy about the way a game is going. One Rockstar rep tells me that he managed to snatch back all his money after murdering his opponents - but he was also gunned down before he made it out of the cantina.

Right now, Marston isn't in the mood for shopping or poker. He heads over to the sheriff's building, where an elderly man is hammering up a Wanted poster, detailing the crimes of two notorious bandits. Our hero tears down the notice and leaves town. There are bounties to be had, and he intends to collect. Now, the GTA games usually make it fairly explicit about where you need to go for a mission, but things aren't so simple here in the Old West. The notice tells Marston where his targets were last seen, but once you reach this area you'll have to scour your surroundings until you spot the men you're looking for. Before any of this happens, you'll have to actually get to your destination - an undertaking that's fairly dangerous in its own right. While a railroad and stagecoach system will allow for a certain degree of fast travel (presumably a bit like the taxi system in GTA 4), you'll be spending plenty of time in the saddle. As you ride across the land you'll encounter random NPCs and events.

You're free to ride past these strangers, but there are certainly gains to be had if you stop and see what's going on. Still, you'll do well to be a bit cautious with these strangers; they don't call this The Wild West for nothing. At one point I saw the player encounter a traveller who was being robbed at gun point by a small gang. He could choose to help the robbers for a share of the spoils, or help the victim by gunning down the attackers. During the demo I saw Marston chose to play the nice guy and was rewarded appropriately, but on another occasion, things didn't go so smoothly: as he was riding through the scrublands, a man approached him on foot, begging for help; as soon as he slowed down, the newcomer pulled him from the saddle and attempted to steal his horse. Luckily the nag in question had developed a bond with Marston; at the touch of a button our hero issues a shrill whistle, at which point the horse threw off the would-be hijacker. This trick looks amazingly satisfying to pull off, and I can't wait to give it a go for myself.

Back to the mission. When Marston eventually finds the men he's looking for, a choice arises. Should he try to take them dead, or alive? The former is naturally the easy route, but the latter results in better rewards. In addition to hard cash, your behaviour in Red Dead Redemption can earn you two further assets: Fame and Honour. The first stat can only ever increase, and is representative of how well-known you are within the game world, while the latter is essentially a kind of karma system. Your honour level will affect the way people perceive you, so if you go around acting like a mean ol' varmint, you can expect to get challenged to the occasional street duel. This preview is largely concerned with the "extra curricular" activities in the game, but naturally there's a massive set of story-driven core missions too - and it's not yet clear how the honour level will affect the course of this narrative.

In any case, today Marston opts for the quick-profit route. After spotting the Wanted men and their entourage of surrounding goons, our hero opens up with a long-range rifle. Shooting is handled via a free-aim system, with a cover mechanic that automatically makes use of nearby scenery (including dead horses, if you're a really Desperate Dan), while an extra layer of grim realism is added by the in-game physics. Redemption uses a mixture of Rockstar's own tech and the Euphoria engine, and it looks great. Slain enemies slump to the floor when they take a hit to the belly; shoot a man as he rides a horse, and he may keel over in the saddle, his horse bolting off with a newly-dead rider on his back. There's more detail to the violence here than in GTA 4: target people's arms and they'll clutch the injured limb in pain; put a bullet in their leg, and they'll limp about or even crawl on the ground like the pathetic worms they are.

My appointment only allows for a short glimpse at the game, but the demo has gone smoothly, so we have some extra time to kill. My hosts decide to play through the Wanted mission for a second time, deciding to do the job in a different way - and this leads to a cool alternative outcome.

It's Rockstar doing an open-world Western. Excitement is practically guarenteed.

As I mentioned, during the first attempt Marston went in guns blazing - using a rifle to cripple one of the men, and the Dead Eye system to take out several other threats (here the action shifts into slow-motion while the player paints targets on the foes you want to hit; when reality resumes, you'll unload your pistols as directed). Once everyone was dead the player loaded the valuable corpses onto the back of his horse, then headed off in the direction of the nearest prison wagon - a sort of mobile prison stationed out in the wilderness. Now, on the second run-through, the demonstrator decides to capture his targets using a lasso - a special item that lets you take prisoners alive. This is certainly the trickier way to handle the mission, since even wounding your quarry results in a lower reward, but naturally Rockstar's agent is well-versed in the game's controls. Before long he's hog-tied the two men, and slung them onto his stallion.

During the first demo, Marston was rewarded with money and a small increase to his Fame score. That's all very well and good, but it is the second trip that proves to be really interesting. As the player hands over the two prisoners to the lawman, he receives a larger cash reward, and a stonking great bonus to his Honour. Then, as he begins to walk away, the lawman speaks, his words steeped in a thick Mexican accent. "Thank you Senor!" he says "These men will never see the light of day again!" And with that, he shoots the two men in the head.

For me, this unpredictability is one of the most exciting aspects of Red Dead Redemption. I've only spent a short while with the game, but already it feels as if Rockstar is really running with the chaotic, anything-can-happen nature of Liberty City. The game world is going to be absolutely massive, and the Mexican area will be just one of three separate geographical regions, but it's not just this that lends the game an epic quality. There are loads of things I saw during the showcase that I've not had time to detail here: the group of soldiers who were executing someone just outside a town, and the officer who threatened Marston when he sauntered over to watch; the hand-drawn treasure maps that require you to decipher simple sketches of notable in-game landmarks; the way that each horse has different characteristics, and the sickening feeling you get when one of these creatures gets shot and slips to the ground.

And on top of all this, we've got Marston himself, and the narrative that's wrapped around him. True to form, Rockstar is keeping tight-lipped about this, but from what we know so far it sounds promising - the tale of a former outlaw who is forced into hunting down an old comrade, thanks to pressure from a sinister government agency. The story is set towards the end of the Old West, at the start of the Twentieth Century, and considering the Mexican influence - and the presence of a gatling gun in one of the released trailers - it looks like Sam Peckinpah's The Wild Bunch has been a major influence. Let's hope so, because that's easily one of the best Westerns ever made. While we've had a few decent cowboy games over the past decade, it's fair to say that we're still waiting for the definitive article. Can Rockstar deliver the game we've all been waiting for? We'll have to see, but for now I'm filing this one under "Most Wanted".

Red Dead Redemption will be released on PS3 and Xbox 360 on April 30 2010.