The Iconbar
Maybe you should read drobe.co.uk, instead?
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.
Maybe you should read drobe.co.uk, instead?
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.
Phaethon Soundtrack
Phaethon Soundtrack
Building the Dream 3 - Random map generators, redux
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)
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
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.Aside: Why use a linked list and an array at the same time?
Throughout the code there are two basic ways in which the collection of cblocks are accessed:
- Group access - an identical operation needs to be performed on all cblocks.
- Spatial queries - given a certain point in the map, the cblock that contains that point needs to be discovered.
typedef struct _layer {
rect r;
int z;
gdll *cblocks;
cblock **cbmap;
fbll *corners;
int *surfmap;
} layer;
- 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.
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.
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.
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.
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
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.
Right On Commander!
The final episode airs on August 22nd at 7:30pm on Five. Go on, guess what it's about.
Right On Commander!
The final episode airs on August 22nd at 7:30pm on Five. Go on, guess what it's about.