From everyone at The Icon Bar, we would like to wish you a Merry Christmas and a happy and prosperous New Year. Thanks for reading TIB in 2008 (what there was of it to read!) and we'll see you in 2009. Oh, and don't forget to vote in Drobe Awards 2008 poll while there's still time!

Links:
Christmas (Wikipedia)

3 comments in forum ]]> Thu, 25 Dec 2008 00:00:00 GMT http://iconbar.com/comments/rss/news1217.html http://iconbar.com/comments/rss/news1217.html A while ago you may remember that I wrote an article about video conversion for RISC OS, and near the end raised the topic of video conversion on RISC OS using a port of ffmpeg. A while ago you may remember that I wrote an article about video conversion for RISC OS, and near the end raised the topic of video conversion on RISC OS using a port of ffmpeg. Although the version of ffmpeg I originally tried on RISC OS was old and broken, Christopher Martin obviously thinks there's some merit to this approach, as he has recently produced !FFmpeg, a working port of ffmpeg for RISC OS.

Once more in the interests of SCIENCE, I threw a few test videos at !FFmpeg and measured its performance against that of a similar version of ffmpeg running on my Windows PC.

Test one: DVB-T

Since my first article was largely concerned with converting recorded DVB-T (aka Freeview) TV programmes for watching on RISC OS, I figured the logical place to start would be with testing that. I copied a short clip over to my Iyonix and attempted to convert it to a suitable resolution for playback (416x312x25fps MPEG 1 @ 850kbps). The conversion rate was about as bad as I was expecting - 3fps. But at least it did work, and the resulting file was played back through !KinoAMP without any problems.

Of course since there's currently no software/hardware available to record DVB-T on RISC OS, there's little point in transferring multi-gigabyte files over to a RISC OS machine in order to encode them - you might as well use the PC that recorded the programme in the first place. In my case, my 2.6GHz PC was able to re-encode the test clip at a much more acceptable 235fps.

Test two: YouTube

For this test I saved a .flv file from YouTube and converted it for playback. Since the video resolution was only 320x240, I decided to keep things simple and just used the !FFmpeg WIMP frontend to handle the conversion for me (more on that later).

End result: My Iyonix achieved a conversion rate of 11fps. Since the !FFmpeg frontend used the -sameq option, the quality of the video did not degrade due to the transcoding, but the output file was 3 times the size of the input. Nevertheless, KinoAMP was able to play it back without any problems.

Performing the same conversion on my PC resulted in a conversion rate of 1080fps - so still about 100 times faster than what RISC OS can offer.

Test three: YouTube on a RiscPC

Since the conversion rate on the Iyonix was nearly acceptable (or at least in the double-digit range) I decided I might as well try converting the same .flv video to MPEG on my StrongARM RiscPC, with the right settings for RiscPC playback (288x216x25fps video @ 250kbps, same 64kbps mp3 audio as source). The conversion ran at a less than stellar 2-3 fps, but once more the output was watchable when played back through KinoAMP, and the video quality hadn't degraded too much.

The !FFmpeg frontend

As mentioned earlier, !FFmpeg comes with a RISC OS frontend, which can simplify the task of converting many videos. However it doesn't allow you to specify the output resolution, so if you're converting a high resolution video, or one for playback on a RiscPC, you'll have to run ffmpeg from the command line for the best results. Unfortunately that isn't as easy as it sounds, as ffmpeg seems to have trouble finding files unless you give it the full pathname or remove the filename extensions (which could make life even more difficult since you'll have to specify the output container format manually).

Conclusion

Video conversion on RISC OS - it's now possible, but the poor performance of converting even low-resolution videos like those on YouTube means that it still isn't something you'd really want to do unless you have no better alternative available. However it is worth noting that the current version seems to have been compiled against GCC 3.4.6, which means it's missing out on the soft-float support available in the GCC 4.1.1 pre-release. Soft-float support could result in a significant performance boost, even if it still doesn't result in better-than-realtime conversion.

If you really do want to watch YouTube on RISC OS, you might want to have a look at Murnong, an ffmpeg-based solution again created by Christopher Martin. The transcoding performance isn't likely to be any better, but at least it will simplify the number of steps you need to go through to get a video downloaded and converted.

1 comment in forum ]]> Sat, 20 Dec 2008 20:00:00 GMT http://iconbar.com/comments/rss/news1216.html http://iconbar.com/comments/rss/news1216.html Saturday 6 December saw the Midlands User Group's RISC OS Christmas Show in Birmingham. The show was held at Birmingham University's Guild of Students, and was attended by a steady stream of people throughout the day. What follows is a brief report and some photos from the event.

The main announcements for this show were from RISCOS Ltd. who had their new RISC OS Upgrade CD available, along with a "RISC OS Virtually Free" CD, which for a few quid gives you a licensed copy of RISC OS 4 to be used with emulators, and comes with instructions for some emulators on how to get started.

RISC OS Open Ltd. had an Iyonix which was running a ROM image built from the publicly available sources, and were selling calendars, t-shirts, mouse mat and coaster packs and source CDs.

Orpheus and RISC OS Now were also present, notably with free mince pies for the punters (which were yummy!). A new issue of RISC OS Now was available, albeit in A5 size instead of the usual A4 size booklet. Paul Vigay took along an Acorn System One to show off, along with an Enigma Machine kit, which were on display on the Orpheus stand.

NetSurf were in attendance showing off the latest builds of the open source browser, including a Linux build with support for tabbed browsing. CJE had their mini-tardis at the show for all the spares you could need, and R-Comp had their usual selection of RISC OS products for punters, ranging from Games to laptops.

The Acorn through the Ages display contained working examples of Acorn kit from days gone by, from the Atom through to the Omega (although the Omega had an amusing sign on the top stating "Microdigital Omega - Non working". The BBC Model B on display sadly went up in smoke during the afternoon, leaving the unmistakable smell of burning electronics hanging around that half of the room for the afternoon.

Shortly before the show ended, the raffle was held. Each punter who entered had a number on their ticket (I was visitor number four!), and the number was picked randomly by a programme on Graham Shaw's computer, with source code available for anyone who wanted to check it was all above board. The winning number, as I recall, was 20.

Shortly after the raffle, the show drew to a close as crowds thinned out. Overall, it seemed a productive day. There were plenty of people at most of the stands throughout the day, and it looked from my viewpoint at the NetSurf stand that a fair amount of money changed hands around the room. Next year's show will be on the 5th of December. I'll leave you now to peruse the photos below from today's event. For those who missed them, the live feed and its photos are still available for the time being, here.

Show photos

Click a photo for a larger view

The show venue		The show is this-a-way
		Exhibitors getting ready	Punters start to trickle in
	Paul Vigay looks like he's up to something...	He's got an Acorn System One, and a built Enigma kit	ROL look ready for Christmas
Paul Vigay shows off his kit to Drobe's Photographer and ROOL	CJE get busy	RISC OS Now was popular with the punters (and exhibitors!)	Advantage6 had some A9 all-in-ones
	ROL check out the opposition	John Cartmell looking amused	Despite this photo, the Atom was working
This BBC B later went up in smoke, leaving the smell of toasty electronics hanging around for a while	Archimedes and A3010 on display	A5000, A7000 and RiscPC	A portable BBC Master
R-Comp had lots to sell	Orpheus special offers	NetSurf	A rather dark MW Software (sorry Martin!)
Microdigital Omega. Non working	Home-Made portable	Another look at that non working Omega	A9 Home in a briefcase, and a VA-running laptop
Kinetic RiscPC in a tower case	ROOL goodies		Meteors, anybody?
Linux port of NetSurf with tabbed browsing	Iyonix running a ROM image built from publicly available sources	General show atmosphere	Another look at PV's Acorn System One and Enigma kit
Electron		Another look at the Omega
		Paul Vigay had free mince pies!	I decided to not ask.
	The show starts to wind down		Artworks and Easi/TechWriter highlights
R-Comp find a quiet moment	Just after the raffle. The chap behind the chap in a suit won.

10 comments in forum ]]> Sat, 06 Dec 2008 20:43:00 GMT http://iconbar.com/comments/rss/news1215.html http://iconbar.com/comments/rss/news1215.html The Midlands Christmas Show kicks off tomorrow. During the day, The Icon Bar will (mobile phone signal permitting) have a live update feed from the show for those of you who can't make it to the show, which you can see at the following URL...

Further information:
Live update twitter feed
Live photos
Midlands User Group Christmas Show website

No comments in forum ]]> Fri, 05 Dec 2008 14:46:00 GMT http://iconbar.com/comments/rss/news1214.html http://iconbar.com/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://iconbar.com/comments/rss/news1213.html http://iconbar.com/comments/rss/news1213.html Anyone reading this will have seen it by now, but just in case you gave up hope (but, erm, kept coming back to us for updates), Drobe has - after a few sparks of life recently - now relaunched. Anyone reading this will have seen it by now, but just in case you gave up hope (but, erm, kept coming back to us for updates), Drobe has - after a few sparks of life recently - now relaunched.

There has been some criticism of the new design; visually, I think it looks great, but then I've always enjoyed websites that are clean and simple and uncluttered. My biggest complaints with the old design were that the masthead looked too busy, and there wasn't enough white space; both of these issues have now been addressed. (Although can we have the logo back in colour? Pretty please?)

The biggest advantage to the new site is with the outside links to other articles. Previously stuck in a sidebar to the right, they are now fully integrated into the main article listing - making them easier to see immediately, and also allowing comments. This clearly makes the site easier to run, and Chris Williams has made no bones about the fact that if the site was to return, it needed to take up less of his time. (Co-running a couple of websites myself, I fully sympathise.) This redesign solves that issue - now an interesting link can spark off a decent discussion rather than a full article, and the fact that a lively commenting community can fill in the gaps and make people come back to the site is vital when a site-runner is short on time. Moreover, there's also still room for full Drobe articles when time allows. A win all-round for everyone - or, at the very least, the best everyone was going to get in the current climate, as a return to numerous full-length updates from Drobe seems unlikely at this point.

I also personally like the disappearance of the comment and user ratings - I never found them especially helpful, and at times they almost felt like they were inviting trouble, rather than alleviating it. Maybe they'll come back in a future update - the launch article says some missing features are due back soon - but I really hope they don't.

Any bad things? Well, I can't say I like the linking of the headline of the launch article to an email address - I don't want my email client appearing unless I specifically want it to, and I don't really feel like having to check the browser status bar before clicking on every link. (I generally solve that issue on my websites by only linking email addresses to actual visible email addresses - but then I am a bit of a boring bastard.) Still, I don't expect this to be a major issue - most headlines will link to external articles or actual Drobe content, rather than email addresses.

A bigger disadvantage is the addition of threaded discussion. I've never liked it on websites, as I find it easier to follow all new comments on a discussion at the bottom of the page, rather than having to glance right through the list of comments. This is a personal dislike, though - many people love threaded discussion, and it does have its benefits too. It's certainly not something that would be easy to allow users to switch on and off - threaded discussion discourages the quoting of the previous comment, and so allowing users to switch it off would quickly render some comments unintelligable.

Still, overall, it's a great redesign. It would have been easy to give up on the site completely, or have unrealistic expectations of how much time you would actually be able to spend on the site to keep it running properly. The new look allows the site to be quickly updated, for commenters to keep the site interesting with new discussion - and also allows full articles to be posted as and when time allows. It's just great to have Drobe back again - hell, I haven't used RISC OS in ages, but I still drop in, because there's usually stuff worth reading there, external link or not.

And that bloody awful creased paper background has gone as well. Result.

On a TIB note, the irony is not lost on me that this is only the sixth article we've actually published on here this year. The idea of us being qualified to comment on how another site does is slightly laughable, admittedly. So feel free to laugh away - although we should have a fourth installment of our Building the Dream articles up soon.

9 comments in forum ]]> Tue, 11 Nov 2008 04:21:00 GMT http://iconbar.com/comments/rss/news1212.html http://iconbar.com/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://iconbar.com/comments/rss/news1211.html http://iconbar.com/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 http://iconbar.com/comments/rss/news1210.html http://iconbar.com/comments/rss/news1210.html Gareth Moore wrote in to let us know that, as foretold in the forums, the "Brits Who Made the Modern World" series is a big rip-off of the book "The Backroom Boys". No, wait, that wasn't it. The Backroom Boys". No, wait, that wasn't it.

The final episode airs on August 22nd at 7:30pm on Five. Go on, guess what it's about.

12 comments in forum ]]> Thu, 14 Aug 2008 21:30:00 GMT http://iconbar.com/comments/rss/news1209.html http://iconbar.com/comments/rss/news1209.html A bit later than I was hoping, but nevertheless it's now time for Building the Dream 2. This time I'll be looking at the RISC OS sound system - everything from the terminology used, to what makes a sound, how the RISC OS sound system works, and how you can write your own sample player. A bit later than I was hoping, but nevertheless it's now time for Building the Dream 2. This time I'll be looking at the RISC OS sound system - everything from the terminology used, to what makes a sound, how the RISC OS sound system works, and how you can write your own sample player.

Terminology (and how sound works)

First, let's start with the basics. A sample can, confusingly, have two meanings. It can either be used to describe a sound clip (e.g. a .WAV file), or one of the individual units of sound that make up a part of the clip. For the latter, a sound sample is typically stored as a 16 bit signed integer. After some processing by the sound software/hardware to provide volume scaling or mixing with other sounds, the sample is sent to an analogue-to-digital converter that translates it into a voltage. This controls the position of the diaphragm in the speaker. In order to generate an audible sound, the position of the diaphragm must be changed many hundreds or thousands of times a second, resulting in it oscillating back and forth. These oscillations set up the required pressure waves in the air, which travel outwards from the speaker and eventually stimulate the receptors inside your ear.

Most sound hardware operates by processing a certain number of samples per second - this is known as the frequency of the sound system, and is measured in Hertz (Hz). Most hardware supports several different frequency settings, e.g. 11kHz, 22kHz and 44kHz. Although at first glance it may appear that the computer is only able to generate sounds at 11kHz, 22kHz, or 44kHz frequencies, in reality many different frequencies of sound can be generated by sending the correct sequence of samples. For example, if the sound system is set to 22kHz, and the sequence of samples 32767, -32768, 32767, -32768, 32767, ... etc. is sent to the hardware, then a constant 11kHz tone will be emitted by the speaker. The tone will be at 11kHz instead of the expected 22kHz because the period (duration) of the wave is 2 samples. I.e. every 2 samples the in-out motion of the speaker diaphragm will repeat (and it is in the in-out motion that results in a sound being produced). If the sequnce of samples had instead been 32767, 0, -32768, 0, 32767, 0 -32768, 0, 32767, ... then the tone would be at 5.5kHz, because the period of the wave is 4 samples. Many other patterns are possible, each providing approximations to different frequencies of sound. The higher the sample rate of the hardware, and the higher the resolution of the samples (e.g. 24 bit instead of 16 bit), the closer these patterns come to representing the real shape of a specific frequency sound wave. One thing to remember though is that the maximum frequency sound you can output will be half the frequency of the sound system, because a period of at least two samples is required in order to represent the essential in-out motion.

Although I've mentioned the period as being the duration of one cycle of a sound wave, it is also used to describe the duration of one sample. For example, at 22kHz, the period of each sample is 1/22050s = 0.000045351 seconds (Note that 22kHz rarely equals 22000Hz. A 22kHz sound system would typically run at 22050Hz, and it is only written as 22kHz as a matter of convenience. Similarly 11kHz is 11025Hz and 44kHz is 44100Hz). This means that, every 0.00045351 seconds, the sound hardware reads a sample from the sound buffer, converts it to a voltage, and sends it to the speaker.

The buffer is another important aspect of the sound system. Rather than constantly pester the CPU with requests for individual samples, the sound hardware typically requests several hundred samples at a time, which the CPU will put into a memory buffer ready for reading by the sound hardware. This provides more efficient operation, as it reduces the number of context switches that the CPU must perform (A context switch - e.g. switching from running an application to running the sound buffer fill routine - will take a finite amount of time. So the more context switches there are, the more CPU time will be lost to performing the switching) Bigger buffers will require less context switches, and so will incurr a lower CPU overhead. However care has to be taken, as the buffer introduces a delay in the sound system - if the buffer is too large the user will notice that a sound is only heard a considerable amount of time after it was meant to start playing. This is more of importance to games than regular desktop use, as games rely upon many sounds starting and stopping at specific times. It is also important for movie playback, to ensure the sound is in sync with the pictures - although if the buffer size remains constant, the delay can be taken into account by the movie player code.

The RISC OS sound system

There are actually two RISC OS sound systems - the older, practically obsolete 8bit sound system, and the newer 16bit sound system. Although I'll be discussing both in this section, the code samples in the next section will focus on the use of the 16bit sound system, as it is the easiest to write for, produces higher-quality sound output, and has better support for mutliple users (via the SharedSound module).

In the beginning though, there was just the 8bit sound system. This is the system that was shipped with the first ARM-powered machines running Arthur. It could be configured to support between 1 and 8 channels of 8bit audio, which would then be mixed together in hardware to produce the two stereo channels output to the speakers. To do this, each channel could be assigned a stereo 'position', which controlled how much of it was mixed into the left and right output channels. Although the sample rate and buffer size of the sound system could be changed, these settings could not be changed on a channel-by-channel basis - they had to be a global change.

The 8bit sound system was based largely around the notion of voice generators - pieces of code (normally contained in a module) which either played back samples from a stored audio clip or generated the data on-the-fly. Each channel would be assigned a specific voice generator, meaning that each channel can only play one sound at once. Sound playback is controlled via the channel interface - so rather than request for a specific sound to be played, you instead issue a standard call to the channel controller to play whatever sound (voice) is currently attached to the given channel. The pitch, volume, and duration of the sound can be specified with the command, although it is up to the voice generator whether it pays attention to those values or not. Although each channel can only have one generator attached at once, there is nothing to stop the same generator from being attached to multiple channels.

Although adequate when first introduced, it's obvious that the old sound system contained several flaws. Only 8 channels existed, and so only 8 sounds could be played at once (unless software mixing was used). It was also a single-user system, as no framework existed for allocating specific channels to specific programs. Furthermore, the reliance upon voice generators made it difficult to implement continuous sound sources (such as music players). Although it is possible to implement a music player as a voice generator, the solution several music players took was to bypass the channel allocation system entirely and instead claim the entire sound system for itself, preventing any other sounds from being played at all (even if the music player only uses a few of the available hardware channels).

The other point to note about the 8bit sound system is that it used logarithmic samples, not linear; although this makes the data more difficult to process, it results in a marked increase in sound quality, as it essentially gives the computer a 12bit sound system.

16bit sound and SharedSound

With the introduction of the RiscPC came a standardised 16bit sound specification, and the hardware to go with it. The main aspect of the specification was the new SWI, Sound_LinearHandler, which allows programs to register their own 16bit sound handler function. This function has the role of filling both the left and right channels of the 16bit sound buffer with data; thus it is limited to stereo sound hardware only. The main drawback of the 16bit sound system is that only one handler can be registered at once - however this was soon resolved with the release of the SharedSound module, which is now the standard interface to the 16bit sound system under RISC OS.

The SharedSound module operates by registering its own handler (via Sound_LinearHandler); it then allows clients to register as many sound handlers as they want, via the SharedSound_InstallHandler SWI. Each time a buffer fill request is received from the Sound module, SharedSound will iterate through the list of client handlers and call each handler, allowing them to write whatever data they want to the sound buffer. Because the same buffer is shared between all clients, each client must correctly obey the mixing flags that SharedSound passes to it, to ensure data from other clients doesn't get overwritten. However the use of linear 16bit sound samples makes the mixing process trivial to perform.

Apart from providing shared access to the 16bit sound buffer, SharedSound also provides useful information about the sample rate of the buffer, in particular fractional step values to convert from the client's sample rate to the buffer rate. It also allows the volume of each handler to be changed individually (although it is up to the fill code to perform the required volume scaling). It also allows several different types of handler to be used - standard handlers that can be run from an interrupt handler, callback handlers that perform processing in a callback (which means they can take longer, as interrupts will be enabled), and process handlers (which are called in a callback after all other handlers, to allow for any effects to be applied to the final sound buffer data). In my experience, even with relatively simple buffer fill code like the one in the example below, if you're playing more than a handful of sounds at once you will get better performance by switching from an interrupt-based fill routine to a callback-based fill routine.

The only downside to the SharedSound module is that the latest version is only available if you own RISC OS 6. If you don't have RISC OS 6 (Or any earlier version of the module shipped with RISC OS Select/Adjust), then it looks like the most recent version available on the Internet is version 1.04, available from here on Castle's website. For documentation, the best source would appear to be the 'OS' StrongHelp manual, available here on the StrongHelp site.

A sample simple SharedSound sample player

I'll now go into detail about how to write your own sample player, using SharedSound. The player will load one or more WAV files from disc and play them back all at the same time - demonstrating how to read (simple) WAV files, how to interface with SharedSound, and how to perform relatively simple activities such as playing multiple sounds at the same time, at their correct sample rates. The code could be easily expanded to support other features, e.g. looping, staggered playback, individual pitch/volume controls for each sound, etc. - basically everything you need for a simple music player or computer game.

Download the code

To run the sample you will need RISC OS 3.5 or above, a copy of the SharedSound module, and some WAV files. The included makefile is suitable for compiling the code with GCC.

The code is split into four sections, which will be explained below. It is a mixture of C and assembler; C for file reading and general control, assembler for buffer filling and some error handling. The code could have been written as a mix of BASIC and assembler (or in pure assembler), but processing the WAV files in C is much easier than in BASIC or assembler. If you really wanted you could use C for the buffer filling code instead of assembler - but that would require extra wrapper code to get the CPU/stack in the correct state for the running APCS code, as well as extra care when writing the code to ensure certain instructions (e.g. floating point) aren't used. For a simple player like this, it's a lot easier and safer just to write the buffer fill code in assembler.

1. WAV reading

Each WAV file is read into a sound struct by the load_wav() function. This function will take the filename and sound pointer as input, and attempt to convert the WAV file into a sequence of stereo 16bit samples (stored in the correct format for placing in one of SharedSound's buffers). Although the code is by no means perfect, it should be able to understand almost any uncompressed 1 or 2 channel WAV file you throw at it. If you're interested in writing your own WAV reader, then you're out of luck, because I've lost the link to the original page I used when writing the code. All I can do is point you to Wikipedia and let you struggle by yourself if one of the sites they link to gets it wrong!

2. SharedSound initialisation

This is performed by the init_sharedsound() function. After the buffer fill code has been registered with SharedSound, init_sharedsound() performs two other important tasks - it registers a couple of error handlers (more on that later) and reads the current sample rate. It uses the sample rate returned by SharedSound to calculate the playback rate of each WAV file. This is necessary because the WAV loader doesn't do any sample rate conversion. Instead, each sound is given its own playback rate.

3. Playback

On the C side, not much occurs during playback. The code merely waits in a while() loop until it detects that all samples have reached their end. This means that playback is entirely under the control of SharedSound - and our buffer_fill() code.

Each time the buffer_fill() code gets called, it processes the sound list, adding each sound to the buffer one at a time. I've deliberately left the buffer fill code quite simple, so that you can see how it works. For one, it ignores most of the information SharedSound supplies it with, such as sample rates and volume levels - because it should already know the sample rate to use, and no volume scaling is performed. Secondly, no math overflow checks are performed on the samples as they are added into the sound buffer - this will result in clicks and other noise if you play too many loud sounds at once. Extending the code to support volume scaling and/or overflow protection is fairly trivial.

Note that because of the way sound works, in order to play two sounds at the same time we merely have to add the two samples to each other. This will only work with linear sound samples however - if this code were for the 8-bit sound system then it would be much more complicated (which is one of the many advantages of using the 16bit sound system instead).

It's also worth pointing out the use of R7, R12, and R8 in tracking the playback position. R7 and R12 contain the playback position of the sound; R7 is the whole part (i.e. number of samples played) and R12 the fractional part. R8 is the sample rate. This is calculated (in init_sharedsound()) as the ratio of the WAV sample rate to the SharedSound playback rate. So if you were playing an 11kHz WAV file into a 22kHz SharedSound buffer, the ratio would be 1:2, or 0.5. This ratio is stored in R8 as an 8.24 format fixed-point number (8 bit whole number, 24 bit fraction). So the 0.5 of the example would become 8388608 (Or 0x100000 in hex). R12 is also stored in 8.24 format; this means that, each time the playback position is updated, the upper 8 bits of R12 are added to the lower 8 bits of R7, and then cleared from R12. R12's sole purpose is to track the fractional part of the sample position.

Note that R7 is saved in the sound state, but R12 is not. This does mean that if any value is left in R12 after each buffer fill, it will have the effect of stretching the sample slightly. For example if there are 100 buffer fills per second, then at most the sample will be stretched by 100 samples per second, making it 1% longer and 1% lower in pitch. If I were writing a music player then I might store the value of R12 between buffer fills; but for a simple sample player there is little point, as the effect is minor and not guaranteed to occur anyway.

4. Shutdown

Shutdown is handled by the aptly-named shutdown_sharedsound() function. This function unregisters the SharedSound handler (if it is still installed, as an error may have forced it to be removed), and disables the ErrorV handler that was installed by init_sharedsound(). The ErrorV handler is used for error handling, which is discussed below.

Error handling

Error handling is a very important part of audio playback under RISC OS, especially if your buffer fill code runs from application space or relies on data stored in application space. If your program exits in an unexpected way then there's a chance that the buffer fill code will be left active - at which point anything could happen from random data beginning to play or the machine locking up entirely. After struggling with error handling for some time, I've come across a solution that appears to work under all circumstances.

Firstly, a C atexit() handler is used to catch all cases of the C program terminating under the control of the C library. This handler will get called if the program exits via exit(), abort(), or by returning from main(). In our case, shutdown_sharedsound() is registed as an atexit funciton.

Secondly, an assembler function is attached to ErrorV, the vector that will be executed whenever the OS is made aware of an error. This is necessary to trap the cases which atexit() does not - for example more serious errors such as data aborts or undefined instructions. The assembler function that gets registered (error_handler()) disables the SharedSound handler, but, importantly, does not disable the ErrorV handler. This is because after testing it on my Iyonix I found that the machine would lock up completely on error, most likely because it does not support an error handler removing itself. Manually removing the error handler isn't deathly important anyway, as the OS is capable of removing it itself when the application exits.

Multitasking

A couple of extra considerations are needed for multitasking programs. Firstly - don't expect to be able to play sounds in the WIMP using a player in application space. This is because of how RISC OS mainpulates the memory map to allow each program to run from the same &8000 base address. Secondly - don't expect to be able to do it from a TaskWindow either (hence the check near the start of main() in the example), again for the same reason as above. If you want to play sounds from within the WIMP then you'll have to rely on buffer fill code stored in the module area (ideally inside a module rather than as a random piece of floating code), and store your sample data in a dynamic area or in the module area.

Interrupts

One important thing to remember if you're doing more complex work with sounds is that all buffer fills occur in interrupts. This means that your program doesn't know when they will occur; if you have some C code that adds and removes sound effects from a list of effects to play, then there's a chance the buffer fill code will get called in the middle of your code updating the list. You should design your code with this in mind. For example, if you are swapping a long sample with a short sample, and you update the data pointer before updating the playback position or sample length, then there's a chance random data will be played instead of sound data. The best course of action in this case is likely to be to temporarily set a 'paused' flag for that sound, or set the data pointer to 0 (and have the buffer fill code interpret that case as there being no data to play). If your sample playback list is constantly changing then you might want to keep two lists - one which is in a safe state and is read by the buffer fill code, the other which is in a volatile state as it is constructed or updated. After a list has been constructed the 'active list' pointer will be swapped to point at the other list. If you take this approach, remember that you will have to store the playback position for each sound somewhere sensible (i.e. not in either of the two lists)

For example, the game I'm currently working on, DeathDawn, uses three structures to manage sounds: Each sample is stored in a sample structure. This contains the raw sample data, length, and sample rate of that data. Each object in the game has a fixed number of sound slots; each slot can reference a sample, and contains the playback position, volume and pitch modifiers, as well as pause and repeat flags. Although there may be 30 objects in the game world with 4 sound slots each, there may only be 4 slots which are both in use and in earshot of the player. For this reason, two lists of active sounds are kept. These lists only contain pointers to the sounds that should be played. As well as the sound pointer itself, each entry also contains the final volumes of the left and right stereo channels, and the fully-adjusted 8.24 fractional step to use for playback. At the end of each frame, the active list that is used by the buffer fill code is swapped with the list that has just been assembled by the C code. Although this solution solves many problems with handling sounds it is still not perfect, for special code must be used to delete sound structures (to ensure they are not referenced in either the of the active lists), and if a sample is swapped for one of a different sample rate then there's a chance it will be played at the wrong rate for the duration of one buffer fill (although this can be fixed by moving the sample rate calculation into the buffer fill code). The reliance on active sound lists also introduces a delay of a few centiseconds between a sound being scheduled for playing and playback to begin.

Next time...

The next article, due sometime before judgement day, will deal once again with the topic of random map generators, as well as provide numerous examples of uses for the different container data structures that were discussed last time.

3 comments in forum ]]> Mon, 17 Mar 2008 12:00:00 GMT