The introduction

Several splash screens interspersed with artwork serve as the introduction to Burn 'Out. This introduction also shows off the two of the strongest points of the game - the art style and the music. Unfortunately, it's mostly downhill from there.

The game

If you've played any other faux-3D racing games like E-Type or Lotus II then you'll know what to expect from Burn 'Out in terms of gameplay. You have to steer your car to the left and right as you drive along the track, avoiding other drivers and all manner of obstacles that are in your path. However instead of driving a sports car you're driving a beach buggy, and the tracks have more in common with roller coasters than they do with public roads.

In total there are 40 tracks available, which must be completed in a fixed, linear order. In order to proceed to the next track you must finish 3rd or better, and without running out of time on the clock. Most races only take a couple of minutes to complete, and there's no save game system, so if you're planning on playing the game to completion you'll need at least a couple of hours spare.

Inbetween each race you'll be taken to the garage, where you're given the opportunity to spend your race winnings on upgrading the three core components of your buggy (engine, gearbox, tyres), or to respray the bodywork to a colour other than the default gray. Curiously the garage screen has a hidden time limit imposed on it - if you spend too long deciding which upgrade to purchase next then you'll be kicked out and into the next race without any warning.

As previously mentioned, one of the strong points of the game is the music. I'd guess that there are between 10 and 20 music tracks in the game, spread across the 40 race courses, resulting in a great deal of variety. It's rare to see a home-grown RISC OS game where so much attention has been given to the music. Unfortunately the game engine lets the music down somewhat, as whenever a sound effect plays it will cut out part of the music. I often fear collisions not because of the effect they'll have on my speed, but because of the effect they'll have on my enjoyment of the music. There is an option to disable the sound effects, but it has no effect on the music cutting out - it's as if all it does is mute the volume of the sound effects instead of stopping them altogether.

Another failing point of the game is the difficulty. The majority of the tracks are easy - assuming you've spent your money on the right upgrades there's absolutely no reason why you won't finish in first place, with the 2nd and 3rd place drivers miles behind, and with ample time left on the clock. But then there are the tracks featuring time bonus gates. The gates are barely any wider than your buggy, making them almost impossible to hit, especially considering the way the buggies bobble up and down and side to side as they drive along the track. Some of the time gate tracks are tuned so that if you miss even one or two of the gates you're almost guaranteed to run out of time before completing the race. The only other tracks that cause me some difficulty are the final few tracks of the game. Apart from being a bit more twisty and turny than the previous tracks they also feature quite harsh time limits, harsh to the point where one crash is all you need to ruin your chances.

The verdict

Burn 'Out is a fun and attractive game, but it seems like too much time was spent on the art and music and not enough on the code and gameplay. With some extra time spent to tune the difficulty the game could have been an all-time great, but as it is it's just a pale immitation of the arcade game it was inspired by.

The full version of Burn 'Out can be downloaded for free from Ian Jeffray's website. StrongARM/RISC OS 4 compatible.

2 comments in forum ]]> Sat, 01 Oct 2011 18:00:00 GMT http://www.acornarcade.co.uk/comments/rss/news1266.html http://www.acornarcade.co.uk/comments/rss/news1266.html Last month Alan Peters surprised everyone by announcing that TBA Software are back from the dead. Their back catalogue includes AXIS (which was awarded five stars by Acorn 32-Bit Gaming), Formula Two Thousand (FTT), Cyber Ape, Cobalt Seed, and BHP [Review]. Last month Alan Peters surprised everyone by announcing that TBA Software are back from the dead. Their back catalogue includes AXIS (which was awarded five stars by Acorn 32-Bit Gaming), Formula Two Thousand (FTT), Cyber Ape, Cobalt Seed, and BHP [Review].

TBA Software are sharing their progress on a new blog. Already they have released a 32-bit only version of their high performance image filing system, TBAFS.

They have started to produce a 32-bit version of their 3D graphics library and game runtime, TAG, and they are working on using extra features of modern ARMv7 CPUs to make it run even faster.

Another member of the TBA Software team, Martin Piper [Interview], has managed to render levels from BHP on Windows. Alan is hoping to get BHP running on the BeagleBoard XM in the near future.

In other news, the excellent RISC OS classic Inferno [Review] has been released for Apple iOS devices. There's no mention of support for Android devices. Paradise's website claims that Inferno is their "very first iPhone title", so perhaps we will see Overload [Review] and the long awaited Pocket Money / Toybox Dreams [Preview] make their way over to modern handheld devices too.

3 comments in forum ]]> Fri, 10 Jun 2011 12:57:00 GMT http://www.acornarcade.co.uk/comments/rss/news1253.html http://www.acornarcade.co.uk/comments/rss/news1253.html APDL, long-time distributor of Public Domain and not-so Public Domain software, have taken the next logical step from distributing their PD/freeware collection on floppy disc or CD and have begun distributing it online instead. Apart from the obvious advantage to the end-user of being able to access the software immediately, APDL have also decided to forgoe charging any nominal download fees, making the archive truly free. APDL, long-time distributor of Public Domain and not-so Public Domain software, have taken the next logical step from distributing their PD/freeware collection on floppy disc or CD and have begun distributing it online instead. Apart from the obvious advantage to the end-user of being able to access the software immediately, APDL have also decided to forgoe charging any nominal download fees, making the archive truly free.

Of course the age of much of the software is likely to make its relevance somewhat limited (especially if it's not 32bit compatible, or even StrongARM compatible) - but by making the archive available free of charge APDL have given Acorn preservation enthusiasts a big helping hand, and for that this move should be applauded.

APDL point out that not all the software from their PD/freeware catalogue has found its way online yet, so some patience may be necessary if your favourite bit of software is missing.

Links

• Newsgroup announcement
• APDL's PD library main page
• APDL's commercial software catalogue - much of which is also available for download (although not for free, obviously!)

72 comments in forum ]]> Thu, 25 Mar 2010 14:15:00 GMT http://www.acornarcade.co.uk/comments/rss/news1238.html http://www.acornarcade.co.uk/comments/rss/news1238.html The RISC OS classic 3D shoot em' up, Star Fighter 3000 has been updated to enable it to run on new ARMv7 powered machines. This lets gamers play it on the raft of new hardware platforms that RISC OS Open is pushing towards, such as the BeagleBoard, and it is hoped, the Pandora, Touch Book and other consumer friendly devices. The RISC OS classic 3D shoot em' up, Star Fighter 3000 has been updated to enable it to run on new ARMv7 powered machines. This lets gamers play it on the raft of new hardware platforms that RISC OS Open is pushing towards, such as the BeagleBoard, and it is hoped, the Pandora, Touch Book and other consumer friendly devices.

Star Fighter 3000 rates amongst the very best games ever produced for the RISC OS platform. It was originally created by Fednet and released in 1994. Since the turn of the millennium, Chris Bazley has maintained the game. Over the years he has done much to improve it. As well as releasing new versions to handle changes like RISC OS 4, 32-bit hardware and now the new compatibility with BeagleBoard class machines, he has worked on many improvements and fixes for the game itself.

One of the most significant changes has been to enable the game to run inside a desktop window. This is a very unusual feature amongst traditional RISC OS games, but it allows you to play a game while you keep an eye on your Parmesan chat window, as well as distracting you from any real work! The game's sound code has also been rewritten and now enables you to listen to MP3s in the background.

Star Fighter 3000 on Iyonix (left), and BeagleBoard (right)
This picture shows four copies of Star Fighter 3000 running simultaneously on both the Iyonix and the BeagleBoard. The Iyonix struggles to run the games at half the game's full frame rate, while the BeagleBoard, almost manages to run them all at the full 25fps.

Further changes have increased the redraw distance (reducing pop-up), overhauled the configuration system and fixed lots of bugs, amongst billions of other changes. For your astonishment, the full, vast, change log is linked to below. Other work by Chris has produced an array of utilities for editing the game's data files and from time to time he even finds time to work on creating a full desktop map and mission editor!

Upgrades are a free download for anyone who has ever purchased a commercial copy of the game, and are available from the official Star Fighter 3000 site, linked to below.

Links

• Star Fighter 3000 - Official site
  • Downloads
  • Change log
  • Utilities
  • Map / mission editor progress
• RISC OS Open - Official site

7 comments in forum ]]> Sun, 08 Nov 2009 13:17:00 GMT http://www.acornarcade.co.uk/comments/rss/news1234.html http://www.acornarcade.co.uk/comments/rss/news1234.html This was going to be a pretty dry fluff piece about the gaming events going on in my home city, something I'd pop in to between renewing my travel pass and getting some new shoelaces. Then something slightly surreal happened to me. This was going to be a pretty dry fluff piece about the gaming events going on in my home city, something I'd pop in to between renewing my travel pass and getting some new shoelaces.  Then something slightly surreal happened to me.

I've just spent around an hour in the company of one of the men partly responsible for getting me into computers in the first place.  And I didn't recognise him.

Game City, which is in its fourth year, has been described as the Sundance Festival of gaming.  It takes over the centre of Nottingham for five days, from marquees in the square to random Pac Man cabinets in shopping arcades, so it's difficult to miss.  However, although I've known about it in the past, I failed to even get photographs of UK games premieres playing on the giant screens because I didn't even have the foresight to charge my 'phone.

But this year, I'd already read that there was going to be several events to commemorate the 25^th anniversary of Elite, which is one of my all-time top 10 games.  Top 3, even.   Maybe even top 1.  So folding origami Elite ships seemed right up my proverbial street.

Entering the tent, I saw that one whole side was inundated with tiny kiddlings who were probably too young to even pronounce "origami", never mind have a clue about Elite.  This not being my sort of crowd I decided to sit on a table across the way, the only other occupant being a balding man with glasses and a beard.  Having nearly spilled his coffee sitting down, we made small talk and tried to fix the wobbly table, and then set about furiously folding spaceships: him a Mamba, me a Cobra Mk III.

After a while we were joined by two other men, a Commodore 64 fan from back in the day and an ex-student who had only just been born when Elite was released.  We laughed about how impenetrable the instructions were without the accompanying videos available on the website, that the space station they were making had seemed like the easy choice but in reality came in six parts, and chatted about what games we liked and how we'd got into Elite.  It was only when the original origami-ist left the table that the C64 fan hissed: "Wasn't that Ian Bell?"

Ian Bell, in case you don't know, was the guy that created Elite in the first place, along with David Braben.  It was seeing Elite on the BBC B that convinced me that I really, really needed a computer of my own, although my family could only afford an Electron.  It was enough – and crucially, had its own version of Elite.  I just commented that I thought Ian Bell had a bigger beard.

He came back, although we all seemed too polite to actually ask him if he was who we thought he was.   So we sat there folding and chatting, until someone walked past and said "Hi, Ian!"

(It was later reinforced by one of the organisers handing him a big VIP badge.  "If you'd have been wearing that," I pointed out, "we would have known right away!"  At which he smiled, took it from around his neck and tucked it away in a pocket.)

"We thought it was you!" said the ex-student, and we started to grill him about what he was doing now, if he was still writing games, if he played many himself, and I rather rudely took a photo of him without asking.  He said that he'd tried writing games until recently, but it was difficult for one man to get anywhere on his own.  Because he wanted to create a psychedelic world to take you somewhere that you'd never been before, instead of using an existing game engine that made most games look alike, he had tried to do everything from scratch.  That hadn't panned out, so now he had a paying job with someone else.  He didn't seem that in to talking about himself though, so we all went back to discussing games in general.

Although he didn't play games himself, and didn't know the names of any space-based games of recent times (even Eve didn't seem to ring any bells), he had more to say when we got into some of the mechanics of gaming.  I mentioned how I'd started Elite on the Electron many times after losing my saved games (they had to be saved on audio cassette!), and came to like the start more because when you were striving to get all the equipment the anticipation was often more exciting than being all-powerful (rather like the tipping point in RPGs, where the scrabble to defend ends, and all that's left is rather dull (counter-)attack).  Rather than being offended that I seemed to be less excited about later parts of his game, he admitted that levelling at the start of Elite were something he thought they'd got particularly right.  He also commented on his amusement at some of the myths that came out of the user groups (Mr. C64 noted that these were often school groups set up to do maths but which inevitably ended up as Elite-playing sessions), although all the people trying to track down the Generation Ships were the fault of his use of a little artistic licence. And I probably wasn't the only one that left Elite running while I read in my room, choosing to fly through space like I was really there rather than use the interspace jump to get to planets quicker.

I noticed he'd finished his Mamba some time before, and my Cobra was also complete (if not entirely space-worthy).  So we all had a go at trying to fix the six parts of the space station together, which was pretty much impossible.  I got some sticky tape from one of the many interns hanging around, and it ended up with him making a large cube that in no way resembled a space station, and me holding out little bits of tape on the end of my fingers.  I pointed out that if anyone should know the design, it surely had to be him – but he neatly ducked it by pointing out some subtle differences in the corners.  I'm still not convinced.

Eventually the space station was complete, but by then Mr. Bell and the younger member of our team had already drifted away.  After an almost frantic amount of folding, followed by some intense fiddling to try and get it all to fit together, all that was left was to shake the hand of the remaining fellow folder and walk away.

They say you should never meet your heroes: they inevitably disappoint.  I'm not one for hero worship, to the point where I was completely clueless as to the identity of the man sitting opposite me, but I have to admit that Ian Bell had quite some effect on my formative years.  And it turns out that he's just like us – happy to sit there making paper spaceships and chat about games, not wanting to be in the limelight.  What was most telling however was the charming way in which he left us.

He put a piece of photocopied paper down on the table with a picture of a cat on it.  "Our Burmese has just had some kittens," he said quietly.  "If you're interested..."

Our combined efforts

First up: "Keita Takahashi, director of the cult Katamari games, is spending a month in the city working on designs for the play area at Woodthorpe Grange."  A few months ago, the idea that a top Japanese games designer would come to Nottingham – and then design a park – would have seemed too far-fetched.  But then Sven-Goran Eriksson, international football manager, turned up at lowly Notts County – a team who almost fell out of the football league entirely last year, and could now be one of the richest clubs in the world (owned by a consortium of billionaires, rather than a single sugar daddy).  And after staying in Nottingham for a while, had the chance to jump ship and manage his home country – but decided to stay, and bring one of his old friends in for good measure.  So now, yes, sure, whatever!

Apparently this is something Mr Takahashi's been talking about since his first appearance at Game City in 2006.  He's never designed a park before, but he's got a background in sculpting and fine arts, so along with a landscaping expert and input from local schoolkids he might be able to do something interesting.  Konami are paying for him to stay here, and the local Council are just paying for the construction.

The second thing I noticed was a rather awkward piece of advertising.  "At 2pm, Lord Puttnam of Queensgate will reflect on changes in the creative industries in A Tale of Two Industries."  It took me a while to realise that this was David Puttnam, producer of such film greats as Chariots of Fire, The Killing Fields and, um, Bugsy Malone, and that the second industry would probably be movies.  Not the greatest of adverts then!

Links:
Game City
(Twitter feed)
Video games creator Keita Takahashi is re-designing a playground at Woodthorpe Grange Park
David Puttnam
Ian Bell's Asian Kittens

2 comments in forum ]]> Wed, 28 Oct 2009 14:00:00 GMT http://www.acornarcade.co.uk/comments/rss/news1228.html http://www.acornarcade.co.uk/comments/rss/news1228.html Acorn World - now there's a name from the past. The final show was cancelled in 1998 when Acorn closed its workstations division - now it's back thanks to Dave Moore and the Retro Reunited team. The show, held over the weekend at the Cedar Court Hotel in Huddersfield, offered a range of vintage games consoles and bizarre Acorn hardware hacks. The Acorn scene was mostly 8-bit oriented although there was some RISC OS coverage too. Acorn World - now there's a name from the past. The final show was cancelled in 1998 when Acorn closed its workstations division - now it's back thanks to Dave Moore and the Retro Reunited team. The show, held over the weekend at the Cedar Court Hotel in Huddersfield, offered a range of vintage games consoles and bizarre Acorn hardware hacks. The Acorn scene was mostly 8-bit oriented although there was some RISC OS coverage too.

A Panasonic 3DO console caught my eye as there was a copy of Star Fighter available to play. This port from the Archimedes was developed by Krisalis and wasn't something I had ever seen running before. It was possible to compare this souped up version to the original running on an A3010 in the other room. Naturally I had a go - it felt remarkably similar to the Acorn version in terms of how the plane handled and I was happy that I had retained the skills to dock with the mothership despite not playing the game for about 10 years. The main changes were how weapons were selected, the isometric map and a lack of shop. Some more advanced graphical effects like mountains and rippling water were nice but didn't really add to the gameplay.

Over in Acorn World there was a mixture of old and new. In the far corner was a collection of RISC OS computers and emulators including a Risc PC rocket ship fitted with a pizza oven. Sadly this wasn't running but considering the number of BBC Micros emitting noxious fumes elsewhere in the room it seemed sensible to avoid further fire hazards!

Paul Stewart's home-brew laptop was on display again. He's made quite a few enhancements since I saw it at Wakefield last year: there's a larger 15" monitor and a CD drive. The aluminium suitcase has been replaced by a more conventional looking case - glossy black but rather battered around the edges. He mostly uses it just at home but plans to take it out more when it's complete. I asked him about his plans for his new online PDF magazine called Drag and Drop. Work is ongoing and he hopes to get the first issue out in the next month or so. He has no plans for printed copies; he wants to avoid the printing issues which have plagued other RISC OS magazines in the past and he likes to provide clickable links in the content. It will be produced almost entirely on RISC OS.

Nearby was the BBC Domesday machine, ably maintained and demonstrated by Joel Rowbottom. The Domesday system seems to never lose its magic - whenever I see it at these shows it is always surrounded by an eager queue of people wanting to look up their home town. Invariably they find some little treasure of information that would otherwise have been lost. Absolutely captivating. I was sorry to hear that the Domesday 1986 site had gone offline following the untimely death of its author and maintainer, Adrian Pearce. Plans are afoot to make it accessible again, possibly using an online BBC Micro emulator or as a Google Maps mashup. Both of these are very exciting projects - the emulator would really show how early multimedia programs operated, and the Google Maps mashup could provide a whole host of exciting new possibilities. I'm really tempted to write an iPhone app to use it - imagine being able to travel anywhere in the UK and hit a button to see how it looked 25 years ago!

Other nutty delights included an Acorn Electron reimplemented on an FPGA (I'd love somebody to mod their Omega with this!) - apparently the most time consuming step was getting the 6502 processor working (the design was downloaded from the internet). I also saw a BBC Master hosting an ARM 7 processor.

Retro Software were there in force with a range of new titles including The Krystal Connection and Zap which you could actually buy on disk or cassette to run on your BBC! The packaging looked great and it was very reminiscent of the classic Superior Software titles. Speaking of which, you could buy large prints of the artwork for Superior games such as Ravenskull, Codename Droid and Repton 3. Retro are also developing games for the Android mobile platform, handing out free fluffy balls with goggly eyes to promote their new Mole Miner game.

Acorn World shared the room with the presentation theatre. The main presentation of interest to Acorn users on the Saturday was the Q and A session with Kenton Price, Jamie Woodhouse and Matthew Atkinson.

Kenton was infamous for writing a Repton clone called Ripton which I'd not come across until today. He wrote it when he was 16 (and some of the humour in the game shows that!) following delays with the official Repton 3 release. It was submitted to A&B Computing but they rather wisely decided not to publish it. There was great rivalry between A+B and Superior back in the day although looking back now Kenton and Matthew aren't really sure why. Kenton went on to talk about Mole Miner which - quite bizarrely - has 36 sound samples of Nicholas Parsons (who was kind enough to record them especially for the game last month in Edinburgh).

Next up, Jamie Woodhouse talked about releasing Zap - a brand new old title that has been sitting in a disk box for 25 years. He also wrote Qwak which appeared on a Play It Again Sam compilation for the BBC and Electron (I remember playing this game lots when it came out). He later released it for the Game Boy Advance. This was self published after sometimes feeling disgruntled with publishers and wanting more freedom.

Matthew Atkinson was a prolific Acorn game programmer who was responsible for Repton 3 and UIM. When Superior asked him to write Repton 3 he had no idea how successful the series would become. It's amazing that they are still being played today. He described a game based upon the Cadbury's Milk Tray adverts called 'And All Because'. Superior were keen to break into new markets and Cadbury were keen to licence it. Sadly halfway through development the marketing team decided against it as they wanted to head upmarket and not be associated with games.

I had an interesting talk with Jason Fitzpatrick from The Centre of Computing History. He'd been working on the forthcoming Micro Men documentary for BBC Four and had been tasked with finding appropriate computers and magazine advertisements to be shown onscreen. He was on set during filming to ensure that the computers behaved themselves (unfortunately during one take the power supply for BBC Micro blew up resulting in authentic but unwanted black smoke) - the Centre had even modified a Beeb to become a prototype Proton. It was all quite hectic but he hopes they've managed to keep everything looking authentic.

Sunday was quieter around the stands and the real focus was on the presentations. Unfortunately I arrived too late for the first impromptu talk from Mel Pullen, a contractor at Acorn who engineered the Teletext and Prestel adaptors. In the afternoon the second talk was by Robert Sprowson who was representing RISC OS Open Ltd. He began with a brief history of Acorn and RISC OS (not quite managing 31 years in 31 seconds but a good attempt!) leading on to the founding of ROOL and the current state of development. He compared the efforts of 30,000 Microsoft OS programmers to around 100 at Acorn to effectively just one - The Icon Bar's very own Jeffrey Lee - working on the port to the Beagle Board. He also showed us a slide of the Iyonix ROM image - literally a bitmap image made of the raw data - and pointed out the bits that he had worked on. Releasing the source code isn't just a case of uploading a CVS repository to the internet; great care has to be taken to remove commercially sensitive sections and some fruity words in the comments.

He was careful about the situation between ROOL and RISC OS Ltd, understanding that ROL are a commercial (though not for profit) organisation who need to sell products. The general aim to converge APIs is a "lofty goal". Questions were asked about the shared source licence granted by Castle and whether it would discourage developers from contributing. It was also unclear how much Castle would charge per licence if a commercial product was to be released using RISC OS. The cheapest option would be to sell the hardware (such as a Beagle based netbook) and let the end user download and install the ROM image themselves (much as happens with Linux in the desktop world today). Someone from the audience suggested that RISC OS could supplant the terrible Windows Mobile OS, but Rob said that even if RISC OS could be ported to such a device, there would still be a huge amount of work creating all the applications to run on it (such as phone diallers and text messaging).

The final presentation was by Steve Furber; now Professor of Computer Engineering at the University of Manchester, he was famous here for his work on the BBC Micro and ARM processors. His talk was about the heritage of the BBC Micro, and he joked that the audience members - still living in the past - would know or remember more about the topic than he did. Back in the day, Steve worked for the Cambridge Processor Unit who were helping fruit machines make the transition from purely mechanical devices to computerised systems. Acorn started as a trading name (quite possibly chosen because it came before Apple in the telephone directory) but eventually became the company's full name.

Steve talked in detail about some of the engineering challenges they encountered when designing the BBC Micro and the limitations of other processors when looking to build its successor. After disregarding chips like the 32016 and 68000, and encouraged by Herman Hauser's belief that silicon design was crucial to the success of the company, Acorn set about creating their own. The main problem was this: nobody in small companies designed processors because big corporations spent millions getting them wrong. So it was with some surprise that he and Sophie Wilson discovered that the Western Design Centre in California was not a grand building but a small bungalow on the edge of town filled with Apple IIs and populated by students. This gave them the confidence to design their own RISC chip and the rest is history.

Interestingly, the ARM chip was designed and tested on a BBC micro. Steve recently found the ARM reference model - coded in BBC Basic and only 808 lines long - on a disk in his garage. This was deeper than an emulator (which only has to mimic the processor at an instruction level) and it turned out to be important evidence for several ongoing patent defence cases in America. (It also means you won't find it free to download on a web site any time soon). Having no money and no people kept the ARM design simple. Even the power consumption was a happy accident: without being able to accurately measure the power consumption they managed to stay well under the target of 1 watt - by a factor of ten!

There was immense public interest in microcomputers in the early 1980s and the BBC gave Acorn a trustworthy reputation. Similarly when wanting to spin off ARM Ltd as a separate company it was Apple (who wanted the ARM chip for their Newton) who made the company credible. Now all the ARM processors produced to date have more combined computing power than all other processors put together. Steve then talked about his recent projects and plans. He is working on SpinNaker, a multiprocessor computer built using thousands of ARM 9s yet offering only around 1% of the capacity of the human brain.

Overall it was a fascinating weekend. It was sometimes hard to differentiate exhibitors from guests - but maybe that didn't matter; everyone could just get on and chat about what they were interested in. It was obvious that everyone had put a lot of effort in to organising the event (not least carrying all the heavy equipment upstairs!) There was a nice friendly atmosphere and it was great to be able to just go up to any machine and play with it. The crowd seemed quite different from the Wakefield shows - a reasonably younger crowd, perhaps including quite a few people who were probably too young to see all this when it was new. Here's to the next 25 years!

See also:
Joel Rowbottom's show report
More photos
Group photo taken at the end of the show
Retro Reunited as it happened on Twitter
Acorn World video

5 comments in forum ]]> Mon, 14 Sep 2009 11:00:00 GMT http://www.acornarcade.co.uk/comments/rss/news1226.html http://www.acornarcade.co.uk/comments/rss/news1226.html Back at the start of this month I decided to take a break from debugging some code and have a quick de-stressing blast on Team Fortress 2. As I loaded the Steam client, the "updates" window popped up what seemed to be a bargain - Fallout 3, half price just for that weekend! That'll be fun, thinks I, and cheap too! That'll be fun, thinks I, and cheap too!

It really didn't turn out that way.

I never got to see the game in action at all. I mean, I got to see the menu - loads of times - but after "Start New Game", all I'd be seeing is my own desktop. All the more galling, I'd get little messages popping up telling me "Phlamethrower is now playing Fallout 3", taunting me. I would have liked to have been playing Fallout 3, too.

There are, alas, two main problems with buying games from Valve via their Steam client:

1. They don't support games they don't write
2. They don't do refunds

What I got was a stock response telling me to go to their support page and follow a link to the developer's website. Which didn't work. So via Google I got to the Bethesda forums, which gave a link to a Microsoft download to fix the Live software. That link didn't work. After thrashing around on my own I went back to Valve, who finally gave me a link that did work, to Bethesda's generic support contact form. Guess what? It didn't work. The email server seemed to be rejecting mail from the web server.

In the mean time I'd been reading the Valve forums, and it appeared the game has problems on a certain operating system - there was a long line of "me too!" posts from Vista users. I followed a number of suggestions - updating .Net, my video drivers, Live; disabling software such as ffdshow; even installing a hack to disable the game's Live component completely - all to no avail. Needless to say, the game didn't exactly take my mind off that debugging quite as much as I'd hoped.

The only option seemed to be to take the game back to where I'd bought it, and ask for a refund. Only, Valve don't do refunds.

Actually, I didn't know that at this point of the proceedings, mainly because Valve didn't bother to answer when I informed them I couldn't get through to Bethesda. After ten days, I sent yet another request, pointing out that this level of service didn't bode well for future Steam purchases. It was only then that I found out about their refund policy:

Please note [...]
that Steam purchases, per the Steam Subscriber Agreement, are not refundable

Whatever the legal technicalities, you would expect if a game doesn't run at all, you can just go back to the shop you got it from and ask for a refund. True, some people might abuse this by playing the game and then taking it back afterwards, but here Valve is in a somewhat unique position - they know exactly when I purchased the game, exactly when I first started saying I had problems, and in all probablility when I connected to their service to actually play the game. None of that really matters however, because in retail most stores would probably just give the money back anyway, just to keep the customer sweet. But I had a game that didn't work - never got past the title screen, likely it never would - and I was expected to just write the money off.

I should come clean and say that, for dramatic effect, I snipped the ends from my previous quoting. The line that informed me of the refund policy reads in full:

Please note in the future that Steam purchases, per the Steam Subscriber Agreement, are not refundable -
this refund was issued as a one-time customer service gesture.

17 comments in forum ]]> Tue, 28 Jul 2009 13:07:00 GMT http://www.acornarcade.co.uk/comments/rss/news1214.html http://www.acornarcade.co.uk/comments/rss/news1214.html As stated in the last article, this time I'll be looking at what went into the MK I map generator for my eternally work-in-progress game, DeathDawn. As stated in the last article, this time I'll be looking at what went into the MK I map generator for my eternally work-in-progress game, DeathDawn.

Specifically, I'll be looking at the implementation and evolution of the following components of the generator:

• City block placement. This is arguably the most important stage as it defines the overall layout of the city.
• Edge and node linking. A housekeeping stage that prepares the data structures for the road weighting stage.
• Road weighting. A city with roads which all have the same number of lanes isn't very realistic, so this stage uses an algorithm to determine the number of lanes each road should have.
• Road and building painting. With the city structure generated, all that's left is to translate it into the format used by the engine during actual gameplay.

City block placement

Choice of algorithm

If I wanted the city to look like a city, the choice of algorithm for laying out the city blocks is undoubtedly one of the most important choices to be made. At the time, I had several options available:

1. The previously-described algorithm used in maze game GAIO, where one large room is recursively split into smaller rooms along either the horizontal or vertical axis. Except in the case of DeathDawn the rooms would be buildings and the walls would be roads.
2. A solution borrowed from elsewhere, for example that used by Team Black Sheep's Robocup Rescue city generator. In the above-named example roads are placed onto the lines of an irregularly-spaced grid, then some roads are removed at random to enlarge the size of some city blocks, and then random offsets are applied to the node coordinates in order to add more bends and hide the fact that the roads are based around a rigid grid structure. All except the last step would be applicable for DeathDawn, due to the near impossibility of representing roads that don't run along the 4 cardinal directions.
3. An entirely new algorithm developed with DeathDawn in mind

Other useful food for thought during this development process included Nikos A. Salingaros's keynote speech "Connecting the Fractal City", presented at the 5th Biennial of towns and town planners in Europe.

Implementation

Figure 1
Output of the first city block generator (Click for larger)

Figure 2
Output of the tweaked city block generator (Click for larger)

Although I could try building a complex fractal-based generator, I decided to go with the simplest approach possible and build from there. Starting in the top-left corner of the map, the confusingly-named magic_road_algorithm() function would fill the map with city blocks (cblocks), laying them down one at a time next to each other. Each block would be rectangular in shape (for now, at least), and would be a random size (within certain limits). With a little tweaking, this algorithm worked surprisingly well.

Initial problems

Although the first version worked, it did suffer from problems. Mainly that everything had a habit of shrinking and shifting to the left as it went further down the map, and there were many instances of city blocks which are either too small or non-existent (i.e. two roads placed directly next to each other). When you take into account the fact that roads shown in figures 1 and 2 are single-lane roads, you can see how this could cause problems when the roads are widened by later stages of the generator.

Tweak #1 - cblock size selection

The first tweak was to the cblock size selection. In the initial code, the algorithm would scan the map to work out the largest cblock that could be placed, and then select a block that fits within that area (and also obeys the min/max block size). However this fails to take into account the requirements of the next block to be placed, and frequently results in situations where the next block is forced to be smaller than the minimum size. Due to the top-to-bottom, left-to-right scanning and filling of the map this results in the large number of thin yet tall blocks seen in figure 1, particularly along the right hand edge of the map.

By altering the algorithm to take into account the minimum size constraint of the next block (both in the X and Y axes), avoiding a split if the next block would be too small, the number of too-small blocks was reduced significantly.

Tweak #2 - Generate longer straight roads

Figure 3
A diagram showing city block creation. The numbers indicate the order in which the blocks are created.

The problem with the original generator was that because the widths and heights of the blocks are both random, the chances of a situation like 7 and 4 occuring are relatively slim - only 1 in N, where N is the maximum block height.

A simple solution to this problem was discovered; a uniformity parameter was added to the function. This parameter gives the random chance of the new cblock having its bottom edge in line with the bottom edge of the block to the left. If the uniformity says not to place the two in line, then a random height will be chosen as usual. By tweaking this value (current generators use the value of 30%) a satisfactory result was produced, where the city appears to have an equal number/length of long horizontal and vertical roads.

Edge and node linking

Although the magic_road_algorithm() function creates a list of cblocks, and those cblocks are linked into the cbmap, the blocks don't have any direct way of enumerating their neighbours. And more importantly for the road weighting code, there are no edge or corner structures for the road code to manipulate.

The build_edges_and_nodes() function fixes this by using the cbmap to scan the area surrounding each cblock, creating edge structures between each pair of neighbouring blocks. The edge list is then used along with the cbmap again to work out what cblocks are at the end of each edge, to create and link the corner structures.

The end result is a fully interlinked network of cblocks, edges and corners, as seen in figures 5 and 6 from the preceding article. Remember to have a quick look back at that article if none of this is making any sense!

Road weighting

The edge structures are treated by the map generator as being individual segments of road. But a city that contains roads that are all the same width isn't very realistic, so a 'weighting' algorithm is used to decide how popular (and therefore how wide) each road should be. This algorithm (in the weight_road_algorithm() function) uses an idea borrowed from The Black Sheep's Robocup entry, whereby a number of simulated journeys through the city are made and statistics gathered for what the most popular roads are. These journeys are simulated using an A* algorithm to find the 'best' route between two random points in the city (i.e. two corner structs). By performing several thousand journeys and counting how many times each road is used, the most popular roads can be identified, and they can be upgraded to the widest width possible (for DeathDawn, this is 6 lanes). Other, lesser popular roads are given 4 lanes, while the majority are left with 2 lanes. Finally the least popular roads are downgraded to footpaths, to add some more variety to the city.

Implementation details

Like all A* implementations, the one used by the road weighting algorithm relies on a priority queue data structure to store all the partial paths and decide which to process next. In the case of the road weighting algorithm, the priority queue contains pointers to road_path structures:

typedef struct _road_path {
int l;
struct _road_path *next;
corner *c;
struct _road_path *lnext;
} road_path;

• The l member contains the current total length of the path. This is used as part of the priority queue sorting function to decide which road_path to expand next.
• The next member points to the road_path's predecessor along the travel route. A more logical name would probably be prev, but next is the name that's stuck.
• The c member points to the corner which this path stops at.
• The lnext member is used to manage a linked list of all the road_paths, to allow them all to be deleted at the end of each journey simulation. It has no bearing upon the A* algorithm itself.

But how does this help us find the quickest route?

Simple: The next pointer of each new road_path is made to point towards the parent road_path. This means that, for the road_path which lies ontop of the 'end' corner, if you followed the next pointers you would travel along the quickest route back to the 'start' corner. With a little bit of extra logic to translate corner pairs into edges, you can therefore work out which edges are used in the journey and increase their use counts.

One important optimisation applied to the basic algorithm is that each corner is only processed once. This is implemented by the use of the visited flag of the corner structure. The flag is set the first time a road_path is generated for that corner, and any subsequent attempts to generate a path for that corner will fail. This optimisation is permissible because although there may be multiple paths towards each corner, we are only interested in the best (i.e. shortest) path to each corner - and due to the nature of A* the best path will always¹ be the first one generated. Without this optimisation the number of generated partial paths has the potential to increase exponentially, increasing both memory costs and execution time of the algorithm (and when you've got to perform several thousand route simulations to generate the road widths, execution time becomes very important). With the optimisation in place, you can be guaranteed to generate no more road_paths than there are corners. Care is taken to make sure the visited flag is cleared after each journey simulation - this is done in the loop that runs through the lnext pointer chain and deletes each path element.

One important thing to remember if you're implementing your own A* algorithm is that unless you implement a similar system to avoid generating redundant or looping paths, the algorithm may not terminate if there is no possible path between the two points. Well, it'll terminate when it runs out of memory, but that could easily take an unacceptably long time, or result in other bits of code failing.

Once the ten thousand or so simulated journeys have been made and the road use counts tallied, an array is produced containing pointers to each road edge. This array is then sorted in order of road popularity, from most popular to least. The first 10% of the array entries are upgraded to 6-lane roads; the next 20% to 4-lane, the next 60% to 2-lane, and the remaining 10% are downgraded to 1-lane footpaths.

¹ Actually this is probably false - particularly once the following algorithm tweaks are taken into account - but at the very least the first path generated for each corner is good enough as far as the road weighting algorithm is concerned.

Tweaking and improvements

Figure 4
Sample output of the current road weighting algorithm (Click for larger)

Fixing these problems required some quite simple tweaks to the code: When adding a new section to the route path, the path length is increased by 1 if it runs through the center of the map. The path length is also increased by 1 if it involves turning a corner. Since the A* algorithm aims to find the route with the lowest distance travelled, these changes successfully discouraged the code from generating wide roads in the city center, and significantly reduced the number of twists and turns in wide roads (although there are still various problems left to fix with wide roads).

Later on, beyond the MK 1 city generator, a problem was also identified where wide roads were being placed next to small city blocks - in fact, the roads were so wide that they were taking over the entire surface of the block (or more). Despite choosing a minimum cblock size that should avoid this, this situation is still possible due to the city block placement code being unable to guarantee that overly-small blocks won't be generated. To counter this, the edge creation function identifies when the edge is next to a too-small cblock and sets a flag in the edge (actually just changing its type it to SURFTYPE_PATH). Then the road weighting algorithm detects when a SURFTYPE_PATH edge is being inserted as part of the route, and adds a penalty of 2 to the route length, to discourage use of such paths and thus reduce the chances of wide roads being placed there.

Another post-MK 1 addition was a post-processing stage. Once the road widths have been calculated, any roads which overlap the map edge are forcibly reduced to paths, and any roads which are too wide for the cblock they are next to will be reduced in width until they no longer overlap the center of the cblock (This is in addition to the much gentler tweak where 2 is added to path lengths). Also it was observed that maps frequently contained unrealistically short sections of wide road (often only one edge long), so to combat this another processing step was added where any wide roads that are one edge long will be reduced in width.

Road and building painting

Figure 5
Ugly road/building painting from the MK 1 generator (Click for larger)

The only noteworthy feature of the MK 1 road and building painting was the use of the canvas system - although I've deliberately glossed over the structure of the final map representation, it's based around a simple compression system that doesn't lend itself well to modification. As a work around the canvas system was introduced, which allows sections of the map to be extracted in an uncompressed form, manipulated by the road/building painting code (including functions for rotating the canvas in 90 degree increments), and then inserted back into the map in its original position. Although the current implementation results in some redundant data being left behind in the compressed map, the canvas system has greatly simplified the task of generating the world.

Next time...

Next time I'll be taking a look at the stages added in the MK 2 generator, and any improvements made to existing stages which haven't been discussed above. In particular I'll go into detail about the method used to paint the road navigation flags, and into more detail about how the road and building painting works using its system of surface and building definitions.

No comments in forum ]]> Fri, 28 Nov 2008 12:00:00 GMT http://www.acornarcade.co.uk/comments/rss/news1212.html http://www.acornarcade.co.uk/comments/rss/news1212.html You may have spotted in the forums that Dan Wilson has released the soundtrack from hit game Phaethon in MP3 format. Well, we now have the whole lot archived in downloads section! You may have spotted in the forums that Dan Wilson has released the soundtrack from hit game Phaethon in MP3 format. Well, we now have the whole lot archived in downloads section!

Download file Phaethon_Sound_Track.zip (59803K)

No comments in forum ]]> Sun, 28 Sep 2008 07:35:00 GMT http://www.acornarcade.co.uk/comments/rss/news1211.html http://www.acornarcade.co.uk/comments/rss/news1211.html After writing my first article about random map generators, I said I was going to write a city generator. Well now I have, and I'm here to tell you about it over the course of the next few Building the Dream articles.Blow your own trumpet much? After writing my first article about random map generators, I said I was going to write a city generator. Well now I have, and I'm here to tell you about it over the course of the next few Building the Dream articles.

Blow your own trumpet much?

Although this article could just be dismissed as me blowing my own trumpet, I'm hoping that it will serve a somewhat more useful purpose. Before, during, and after working on the map generator I've searched the Internet for examples of similar generators and failed to find any. Sure, there are odd bits and pieces - descriptions of simpler generators that have given me ideas on some techniques to use, or screenshots of sexy work-in-progress realtime generators, but no actual algorithms or code samples from generators that come close to the required complexity of my generator.

So hopefully this article will become a useful reference point for anyone else wanting to undertake the task of writing a city generator, whether they're targeting a grid-based world representation like mine or a vector-based one.

Apart from discussing the algorithms used in the generator (and why they're used) I'll also talk about the data structures that are used - so even if you're not interested in random map generators you should be able to find plenty of examples of uses for the data structures covered in the first Building the Dream article, as requested quite some time ago.

Why random?

This is the first question I asked myself - and the first question you should ask yourself if you're planning a random map generator (or any other kind of procedural content, really).

Figure 1
The Vice City map from GTA 1 - would you want to create a map as large and detailed as that? (Click for larger)

Although writing a map editor would probably take less time and effort than writing a map generator, I decided to go down the generator route. This is because I've tried creating a city by hand before, for GTA 1, and know that it's a lot of hard work. I'd be constantly scrutinising the map, wondering if two adjacent buildings are too similar to each other, or whether the road layout of the map feels right, or whether there's too much or too little detail in a certain area. And every time I need a new unique building for a mission I'd have to go back and rip an existing generic building out - potentially changing the layout of large areas of the map in order to make it fit correctly. So although writing an editor would be quick and easy, creating the maps would likely be not.

However a map generator, although it would take a certain amount of time and effort to get working right, could potentially spawn millions of detailed maps just at the click of a button, with minimal effort on my part to feed the generator with input parameters. This would be particularly useful since at the time I started I also had no idea exactly how many maps I wanted the game to have.

As an added bonus, writing a random map generator would also be a hell of a lot more interesting than a boring old level editor.

The goal

Figure 2
Liberty City from GTA 1, rendered in full 3D with the Junction 25 editor. (Click for larger)

In the interests of keeping things simple and not reinventing the wheel, the DeathDawn map structure is based around that of GTA 1. GTA 1 was capable of providing large cities (about 1km square) to the player, using under 500K of storage for the map itself. Each city consisted of a set of cubes arranged in a 256x256x6 grid. In real-world terms the length of the side of each cube is around 4m (or at least that's the length I've based DeathDawn around). The cubes were fairly limited in what they could do - you could specify the textures of the 5 visible sides, and the slope of the top surface - but that's about it as far as architectural details go. In addition to the visible features of the map there were also certain invisible features - such as the content type of the block (solid, air, or water), and how the AI should behave (whether it's pavement and should have pedestrians walking on it, or whether it's road and should have cars drive along it - and in which direction). Uncompressed this data could easily be 6 or more megabytes in size, but by relying on the fact that most blocks are identical, and many vertical stacks of blocks are identical, the size can easily be reduced to under 500K, leaving much more space for textures and sound effects.

Although DeathDawn's map format is slightly more advanced than that of GTA 1, the goals are pretty much the same - for the map generator to produce a map typically 256x256 block-stacks in size, with as much building detail as possible, and with the right AI flags to allow for pedestrians and cars to spawn and find their way around the map. The generator should also be capable of producing any secondary data needed - such as the locations of traffic lights, train tracks, and the territories of the different facitons. It should also be able to add specific buildings to the map at the demand of the mission script, so that missions can use unique buildings if they want.

Evolutionary development

Figure 3
Sample output of the MK 1 generator (Click for larger)

The MK 2 generator was designed as a partial restructuring, partial rewrite of the MK 1 generator, in order to solve all of the major bugs as well as provide scope for the addition of new features - such as hills, bridges, train tracks, and the mission buildings. Although the MK 2 generator managed to fulfil most of these goals, several design flaws became apparent during its implementation, the most important of which was that there was no way of guaranteeing that the mission buildings that were requested actually made it into the map.

And so the MK 3 generator was devised - a reordering of the stages the MK 2 generator goes through, in order to ensure as best as possible that the mission buildings will actually be placed. Plans are also being made to improve the MK 3 generator further, in particular to improve the level of detail and placement of regular buildings.

Note that the DeathDawn source code currently available on my site contains the source for the MK 2 version of the generator; however by the time this set of map generator articles is complete I'm planning on having the latest version available for your viewing (dis)pleasure.

Overview

Figure 4
Sample output of the current MK 3 generator (Click for larger)

1. Zoning #1. This stage splits the empty map into zones, and assigns each zone a style, dependent upon which factions have been chosen to inhabit the map. The size of each zone is determined based upon how many mission buildings must be spawned there (and how large they are), in an attempt to ensure that enough space is available when it comes to placing them.
2. City block placement. This fills the map with a series of rectangles, in a grid-like pattern. Each rectangle will later contain a building, and the edges of the rectangles will become roads. The zone location data that was generated in the first stage is used to apply different road and building styles to each city block.
3. Edge and node linking. This doesn't add any new features to the map; it's just a housekeeping stage to correctly link together all the structures created by the city block stage.
4. Road weighting. This stage decides how wide each road should be, by simulating a large number of trips through the city using an algorithm similar to the one a real-world computer route planner would use. After the trips have been simulated, the most-used roads will be chosen to be the widest roads (i.e. motorways), and the least-used will be downgraded to footpaths.
5. Zoning #2. This stage examines the map to find the true size and shape of each zone (the earlier zoning stage just gives estimated bounds). It also assigns names to each zone, which will be seen by the player as he drives around the city.
6. Mission building placement. Using the city block and zone information generated in the previous stages, this stage searches for suitable locations to place the mission script buildings that have been demanded by the mission script.
7. Layer splitting. Added in the MK 2 generator, layers allow the generator to support hills, by storing the data for different altitudes in different structures. The current layer splitting code merely splits the map from one layer into two, by randomly placing hills throughout the map and moving all the buildings that lie inside a hill up onto the second layer. Eventually the layering code may be expanded to allow for more complex structures (notably bridges), or it may be discarded altogether in favour of a more streamlined approach.
8. Road prepainting. The final map structure, as used by the game, is wholly incompatible with the data structures used by the generator. The map painting (and pre-painting) stages are therefore concerned with translating the map generator data into the final map data structure. In the case of road pre-painting, this involves marking into a temporary 2D array the location of each road.
9. Road and building painting. This is a fairly complex stage. Not only does it paint each building into the main 3D map structure, but it also paints the surrounding road and ground blocks. In particular it contains code for placing the correct road textures on the surface of each block, as well as the navigation flags used by the AI.
10. Hill side painting. A more correct name for this stage may be 'cliff face painting'; it involves a brute-force examination of the map to look for gaps in the joins between the upper and lower layers of the map, and places wall textures at the appropriate places to ensure that the player can't see through to the void underneath the map.
11. Traffic light placement. Now that all the roads and buildings have been painted, each road intersection is examined to see if it is suitable for hosting a set of traffic lights. Although this stage could probably be performed before the road and building painting, it's easier to do it after, as it provides a much more robust method of verifying that the traffic lights won't be placed incorrectly.
12. Train track placement. The map generator is capable of generating elevated train tracks for inner-city and inter-city rail travel. Similar to the hill side and traffic light placement code, a brute-force approach is used to examine the finished map, to ensure that the train track weaves around buildings instead of ploughing straight through them.

In detail

For this first article about the map generator, I'm going to be talking solely about the data structures that are used. Understanding the data structures is vital to understanding the flow of the generator as a whole. Later articles will go into more detail about each stage of the map generation.

If you're put off by all these wordy descriptions, don't worry, because there's a few diagrams at the end showing how everything fits together.

The layer structure

First off there is the layer structure. This was introduced in the MK 2 generator as a way of tieing together various variables and structures that the generator uses.

• The r member of the structure, a 'rect', contains the minimum and maximum X and Y bounds of the layer, measured in blocks. Currently this is just set to the bounds of the map, but in the future it may be used to limit development to certain areas (e.g. if there is water at the edge of the map the layer would be restricted to just the island of land in the middle).
• The z member gives the layer its height above ground, measured in blocks.
• The cblocks member is a pointer to a gdll - a linked list structure that I often use in my code to make handling linked lists slightly easier. The linked list will contain a list of all the city blocks that are contained in the layer.
• The cbmap member points to a 2D array of pointers to cblocks, allowing rapid lookup of which city block falls on which map block. The cblocks pointed to by the cbmap are the same cblocks that are contained in the gdll list.
• The corners member is another of my linked list structures, but a different type - a frame-based linked list, which is basically just a linked list of arrays. A frame-based linked list allows you to quickly and easily look up the Nth element of the list, at the cost of much slower insertion/removal of items in the middle of the list. In the case of the map generator, this speed trade off was deemed worthwhile to ensure the speedy operation of the road weighting algorithm. As the name suggests, the data contained in the corners linked list is a list of all the corners of the city blocks; or more correctly, a list of all the end points of the edges which join city blocks. More about this later.
• The surfmap member is similar to the cbmap, in that it points to a 2D array. But instead of indicating which city block each location belongs to, it instead indicates which surface type (road, pavement, grass, water, etc.) each location is. This is mainly used by the road painting code to ensure that roads aren't painted where they shouldn't be. Although the final map structure contains similar data, it works out easier for the map generator to store it in a temporary array as well.

The cblock structure

Each cblock represents a city block; i.e. a plot of land with one or more buildings inside it, and surrounded by pavements and roads. Currently only one building is placed in each cblock, but this will likely change with the MK 3+ generator - take a look at figure 4 and you'll see how much empty space there currently is inside each city block.

typedef struct _cblock {
rect r;
rect br;
gdll *neighbours;
gdll_item *i;
zonedef *z;
struct _layer *l;
builddef *b;
int msi;
} cblock;

• The r member provides the bounding box of the block. This box stretches from the middle lane of the road one one side to the middle lane of the road on the other side. This represents the maximal area that the painting stages will paint grass or pavement into, to fill in the gaps between the building and the road.
• The br is another bounding box, but this time provides the bounding box of the building that sits inside the block. This is computed by looking at the widths of the roads that surround the block.
• neighbours is a linked list of edges that surround the block. edge structures are created whenever two cblocks touch, and are used to generate the roads and paths that run through the city.
• z points to a zonedef - a structure that dictates which building, pavement and road styles to use when painting the cblock. The z field is also used by the 'Zoning #2' stage to calculate the true bounds of each of the named map zones and faction territories.
• l points to the layer that the city block belongs to. During map generation certain information (most notably the Z coordinate) of the city block is needed, so a reference back to the parent layer is the easiest way of providing that information.
• b points to a builddef, i.e. a building definition. It indicates the type of building that's been selected to spawn at the location. Currently this field is only used for the mission buildings; for all other city blocks a random building is selected at painting time, using the list given in the zonedef.
• If a mission building is being used, the msi field will be set to the index in the master mission building list. If no mission building is being placed in this block then the index will be -1. The msi field is crucial to allow the building location to be fed back to the mission script.

Edges

The edge structure is used to link neighbouring cblocks together, and dictates the locations of the roads and paths that run through the city.

typedef struct _edge {
gdll_item *a,*b;
corner *c,*d;
int type;
int weight;
short clip,dlip;
} edge;

• a and b are two gdll_item pointers; gdll_items are used to reference individual entries in gdll lists. There are two of them because the edge is shared between two cblocks, each of which has a different list of neighbouring edges.
• c and d are two corner pointers, dictating the two end points of the edge.
• type is the type of edge - road, pavement, cliff, etc.
• weight has a dual meaning. During the road weighting stage it's a counter of how many times the edge has been used, and after the stage it's the number of lanes in the road (assuming it is a road).
• clip and dlip are the distances from c and d at which the straight part of the road exists; i.e. it's how large any crossroads or T-junctions are. This information is mostly redundant with information stored in the corners themselves, but for the moment it stays where it is. shorts are used to try and keep memory usage down, although in reality there are still many other memory optimisations I could apply if I wanted.

Corners

As their names suggest, corners are the places where edges meet.

typedef struct {
struct _edge *edges[4];
short x,y;
int visited;
short w,h;
struct _layer *l;
int type;
} corner;

• edges is a small array listing the edges that the corner is connected to. Since edges only run horizontally or vertically, there's no chance of there being more than 4 edges connected to a specific corner.
• x and y are the coordinates of the corner within the layer.
• visited is a flag used by the road weighting algorithm.
• w and h are the dimensions of the corner, in terms of the total number of lanes (map blocks).
• l is a reference to the layer that this corner belongs to.
• surftype is the surface type of the corner (road, pavement, etc.) This could be calculated just by looking at the surface types of the connected edges, but storing it locally helps keep things simple.

What?

If all those data structures are confusing you, then perhaps these diagrams will help. Figure 5 shows how the different data structures fit together to represent different parts of the city. Figure 6 shows the actual relationships between the different structures, from the datas point of view (i.e. what pointers point to what).

Figure 5
How the data structures represent the city

Figure 6
How the data structures are related in code

Next time...

The next article, due shortly after judgement day, will take a look at what constituted the MK 1 map generator - i.e. the city block placement, edge and node linking, and road weighting stages of the generator. If there's space I may also describe the algorithm used to paint the road navigation flags for the intersections.

1 comment in forum ]]> Sat, 23 Aug 2008 11:00:00 GMT