How have the creative team behind 'Grand Theft Auto' followed the most controversial videogame ever? By capturing the 'grandeur of the open landscape' and blazing a trail across the Wild West...

New Austin is a vast, varied and ruggedly scenic area north of the US-Mexico border, where dusty plains are intersected by imposing mountain ridges and scattered with one-horse towns and trading posts. It is 1910, the US is well on the way to achieving its manifest destiny, and railway lines and wooden oil rigs attest to the coming of modernity – but New Austin is still frontier country: wild, dangerous and rich in opportunity.

This intricately designed virtual land-scape is where Rockstar Games – maker of the landmark, controversy-generating, 70 million-selling Grand Theft Auto (GTA) series of crime-themed videogames – is inviting players of its latest magnum opus, Red Dead Redemption, to spend their leisure hours over the coming months. Later, as the game's overarching plot unfolds, players will also get to venture into Nuevo Paraiso, south of the border, to pick sides during the Mexican civil war; and then back north, to spend as long again in the more verdant and developed plains of West Elizabeth.

Rockstar has been a pioneer of the non-linear, "open-world" style of gameplay in which players are free to navigate virtual environments at their own pace. And with each successive title, the illusion that players are immersed in a complex, three-dimensional, fully populated and independently existing world grows stronger.

In Rockstar's offices in Chelsea (welcoming, but less flash than you might expect), I get to mosey around New Austin. I'm involved in several shoot-outs, a rescue mission and a mine-cart chase, but still manage to drink in the spectacular scenery from atop my horse. The horizon seems very distant, and the Rockstar employee who leads me through the demo tells me that the game's world is as expansive as that of the largest GTA title, San Andreas. Given how long it seemed to take to traverse San Andreas, even by helicopter, Red Dead Redemption promises to take the player on a very epic journey indeed. That the player is free to explore its every last nook and cranny means the building of this game world represented a massive design challenge, which has taken a team drawn from Rockstar's multiple studios five years to get right.

"As we were exploring Westerns, one of the main themes to emerge was the idea of movement, of journeying across the land," says Dan Houser, the thirtysomething English co-founder of Rockstar and the game's lead writer. "At the same time, we asked, 'What does the West mean?' Is it outlaws and gunfights in one-horse towns, or the conflict between America and Mexico, or the coming of modernity to the great plains? We couldn't really decide, and so for this to be the complete Western, we needed all three of those environments in there."

The game's scale was less of a problem for the programmers than its rural setting, however. "It's so much harder to make a natural landscape look good than it is to make buildings or space stations look good," explains Houser, "for the simple reason that computers naturally draw straight lines. Buildings and space stations are made of straight lines; but fields of grass or the cragged side of a mountain, these are geometrically enormously complicated and have far more nuances of colour, texture and lighting than a man-made environment. To get a computer to draw them is an enormous challenge."

Red Dead Redemption is the spiritual successor to a more linear shooting game that Rockstar acquired half-built, then completed and released in 2004 as Red Dead Revolver. "That was very much an attempt to do a videogame spaghetti Western," says Houser, "in which the focus was purely on the Mexican stand-offs and duels. This game, we wanted to feel like more of a gritty, revisionist Western, taking our cues from films such as Unforgiven or The Wild Bunch."

Houser is celebrated for his games' cine-literacy, and a certain amount of the research for Red Dead Redemption consisted of watching films. But much did not. "We took our inspiration from the real world," he says. So, Rockstar New York's full-time research team was despatched to the photographic archives of the Library of Congress in Washington DC to study the era's clothing and architectural styles. They mined old copies of the mail-order Sears catalogue (first published in 1888) for inspiration for the 90-odd fake brand names that appear in the game. Meanwhile, for the artists based at the company's studio in suburban San Diego, the very landscape they were attempting to digitally recreate was only a short drive away.

"I grew up in the foothills of gold-rush country in California and spent my summers camping in the mountains and deserts of the West," the game's art director, Daren Bader, tells me from San Diego. "So these locations are very personal to me."

Even if the landscape hadn't been nearby, the Redemption team could afford to go the extra mile while developing the game's visual design: Take-Two, the US games developing and publishing company of which Rockstar is a subsidiary, posted revenues just shy of $1bn for last year. And Houser explains that it was never going to be feasible to research the look of the game from the comfort of a sofa with a pile of Sam Peckinpah DVDs. "Films are a two-hour experience, in which the director has had control over the position of the camera at all times, whereas we're trying to make an 80-hour experience in which the player has control of the camera. We need to build a world. You can certainly use films as mood boards, but to figure out how it looks around the back of the street, or what the other side of the mountain looks like, you need to go out and look."

Bader, who worked in traditional, two-dimensional animation before joining the games industry 20 years ago, expands on the process: "We created concept paintings and character designs based on our research, and began to flesh out the world from there. This is very similar to the pre-production of an animated film but, after this point, the similarities stop. Unlike in a film, we have to make it look as good as possible from every angle at virtually any time of day during any type of weather in any given location of the game. That's a lot of ground to cover once you start adding it all together.

"Visually, we wanted to push the theme of the dying of the Old West by showing the harshness of the environment: everything is sun-bleached and scorched, dirt and dust float in the air continually, grit and grime are in every corner of every room. Life back then was difficult, so we made it that even the buildings look as though they've lived a hard life. Along with layering dirt and grime everywhere, one of the things we did was keep the colour saturation of the world low. Happy, bright colours tend to make for a light-hearted or fantasy experience, which was the polar-opposite of what I wanted to achieve. That isn't to say the game is black and white, but it does allow for the colourful moments to mean much more. For example, the sunsets in our game are the moments where we bring focus to the vastness and grandeur of the open landscape."

The declining popularity of the Hollywood Western, suggests Houser, coincided with the advent of digital technology, as it is a genre that cannot be substantially improved with the application of special effects. Indeed, in the great post-war Westerns of, say, John Ford, the landscape itself – for which CinemaScope might have been invented – is the special effect.

"The landscape is how America defined itself, and Westerns – from the name onwards – are about geography. And the thing about videogames, the one thing they do very well, is represent geography. They give you an environment, let you explore it and really feel like you are in it, in a way that is beyond any other medium."

Designing a convincing open-world game with a rural environment the size of Red Dead Redemption's might have been technologically impossible only a few years ago, and it is yet to be seen whether gamers will take to life during the death throes of the Old West in the numbers that they took to a life of crime in Grand Theft Auto. Still, Houser is sure that Rockstar has discovered a perfect marriage between content and form. "The game is hopefully well-written, cleverly designed and everything else, but the technical achievement is unquestionably brilliant," he says. "And I can say so because that part was nothing to do with me."

'Red Dead Redemption' (Rockstar Games) for Xbox 360 and PlayStation 3 is out on 21 May