Otherwise just do a search for 'random map generators' and you should come up with some pointers

If the map is fixed each time you play then it's just a case of using the same seed for the random number generator. However since as you say there was only 32K of memory to play with, it seems a bit unlikely that the entire map would have been in memory at once. This would suggest either rebuilding the 'mini map' each time you move to a new area (By going through the entire algorithm and ignoring the bits outside the mini map), or a different kind of algorithm where each section of the map has its own seed, cutting down the time needed to create the mini map.

What kind of function could do make this branching effect?

Looks to me like the following:
* Create a room
* Pick a random point on the edge of the room
* Create a passage from that point to somewhere
* Create a few more passages
* Choose one (or more) passages to create more rooms at the ends of

...

Personally, I'm beginning to feel it was a tree-like branching function- I'll have to look for something like it somewhere (something which expands from a single point i.e. the opening under the Perseus ship on Exile)

Please forgive me if I disagree entirely
Such map descriptions are good ways of generating random maps, if you can hold all this state at once. However, I do not believe Exile does this. There was an interesting article on Exile in EDGE magasine recently where the author described an algorithm which would calculate the map at the appropriate coordinates. It was mentioned that some rare positions allowed programmer-defined extra data.
Looking at the 'global view' of the map at the website Andreww mentioned earlier, I'd like to make several observations:
1)pathways run only horizontally, vertically or diagonally, and only at certain regular offsets. They appear to form a sort of grid. See that at some positions there are passageways that traverse the whole map, with a few short interuptions.
2)Caverns are generally rectangular
3)In strips the height of the grid, diagonal pathways alternately only run top-left to bottom-right and top-right to bottom-left.
4)The colouring (indicating different graphics sets) is generally in broad swatches, with some edges apparent as 1in2 gradients rising to the right.

There are probably more simple observations to be made (and if anyone notes any, please give them here - no prizes for saying that the top is mostly empty )
Anyway, these observations, and the statements to Edge lead me to suggest the following basic procedure:
1) Chose a 'random' seed or algorithm given some quick hash of the top bits of x and y coordinate
2) given a certain hash of x/y top & middle-range bits, the tile is empty. (Defines caverns)
3) if the bottom 'few' bits of x or y coord are zero, the tile is potentially empty (as part of a passageway) Decide if it is given some function of the top bits, and the opposite axis.
4) Likewise for diagonal passageways. If low bits of x=y give or take some value, it is empty. But if a certain mid-range bit of y (which will be the next bit up from the bottom bits of (3)) is set, invert (EOR with all ones) one of x or y first.
5) Do tidying up. This entails selecting the appropriate tile for a grid position given surrounding positions solidities etc. It may be that passageways are initially defined as a diagonal run of a special value, which creates an empty tile here, and forces bordering tiles to cause widenting. May insert some forground stuff like pillars etc.
6) if the x/y value gives some value when hashed, it is programmer definable. Look it up in a LUT. This table would be interesting, because the data is of necessity spa**e. Some hashing function would be required. Perhaps a paired list of y-values and data for each x-value?

Anyway, something like that.
I've been wondering about this for years and am finally piecing it together. The Edge article was very helpful, I reccomend it wholeheartedly.

Or am I totally wrong?
Yours,
Tony

This table would be interesting, because the data is of necessity spa**e. Some hashing function would be required. Perhaps a paired list

I missed this issue and I'd been keeping my eyes open for ages! That's a big blow :-(

Assuming, or possibly ***uming [my stars] that you are referring to Edge, I had a look for this article last night. I remembered it as being from perhaps two months ago. Actually it is p150-153 of the December 2000 issue (Edge no.91).
Do a PhD, watch the years fly by...
Anyway, you may be able to get it as a backissue, I suggest you ask by email:
backissues@futurenet.co.uk
Yours,
Tony

1) Chose a 'random' seed or algorithm given some quick hash of the top bits of x and y coordinate
2) given a certain hash of x/y top & middle-range bits, the tile is empty. (Defines caverns)
3) if the bottom 'few' bits of x or y coord are zero, the tile is potentially empty (as part of a passageway) Decide if it is given some function of the top bits, and the opposite axis.
4) Likewise for diagonal passageways. If low bits of x=y give or take some value, it is empty. But if a certain mid-range bit of y (which will be the next bit up from the bottom bits of (3)) is set, invert (EOR with all ones) one of x or y first.
5) Do tidying up. This entails selecting the appropriate tile for a grid position given surrounding positions solidities etc. It may be that passageways are initially defined as a diagonal run of a special value, which creates an empty tile here, and forces bordering tiles to cause widenting. May insert some forground stuff like pillars etc.
6) if the x/y value gives some value when hashed, it is programmer definable. Look it up in a LUT. This table would be interesting, because the data is of necessity spa**e. Some hashing function would be required. Perhaps a paired list of y-values and data for each x-value?
Anyway, something like that.
I've been wondering about this for years and am finally piecing it together. The Edge article was very helpful, I reccomend it wholeheartedly.
Or am I totally wrong?
Yours,
Tony

I must say I'd like to have a look at the magazine as I don't understand what you're describing here Tony.
Are you saying that the random seed/algrotihm works upon the coordinates?
Surely, a function using a particular number/set of numbers wuld generate the map and then you could 'zoom-in' on a section?

I must say I'd like to have a look at the magazine as I don't understand what you're describing here Tony.
Are you saying that the random seed/algrotihm works upon the coordinates?
Surely, a function using a particular number/set of numbers wuld generate the map and then you could 'zoom-in' on a section?

Well, if you are in Birmingham you can have a look at my copy. But it might be more sensible if I just type in the relevant section, it is only a sentence or two. Almost all of my previous post was my own speculation, based on those observations. Which bit was it you didn't understand? This?:

1) Chose a 'random' seed or algorithm given some quick hash of the top bits of x and y coordinate

One thing in the article I don't think I mentioned was that the author stated that there was some difficulty getting all the caverns joined up. My idea here is that they divided the map into different sections using large scale map coordinates, then could modify the algorithm for each subgroup independently, to force them to have connections. This would also allow the generation of areas with different overall structure, such as more or less winding tunnels, caverns etc.

I must confess I don't really understand your comment, about zooming in. I guess my description meshes to some extent with yours if the number used to generate the map at any point uses some function of the coordinates. If not could you be more explicit?

Yours,
Tony

I missed this issue and I'd been keeping my eyes open for ages! That's a big blow :-(

Assuming, or possibly ***uming [my stars] that you are referring to Edge, I had a look for this article last night. I remembered it as being from perhaps two months ago. Actually it is p150-153 of the December 2000 issue (Edge no.91).
Do a PhD, watch the years fly by...
Anyway, you may be able to get it as a backissue, I suggest you ask by email:
backissues@futurenet.co.uk

I missed this one, too, but fortunately found a copy in the office. It's quite an interesting article and its chillingly accurate description of the game mechanics sent shivers down my spine!

Now I just need to find a scanner...

P.S. Administrator: your commenting code doesn't work properly. I had to edit the quoted text manually...

I missed this one, too, but fortunately found a copy in the office. It's quite an interesting article and its chillingly accurate description of the game mechanics sent shivers down my spine!

Now I just need to find a scanner...

P.S. Administrator: your commenting code doesn't work properly. I had to edit the quoted text manually...

I'd be interested in knowing more about this. Edge have run out of copies of this issue.

Just bought a copy of Exile (Beeb version) - the novel actually gives a reasonable insight into the locations in the game.

Max

I must confess I don't really understand your comment, about zooming in. I guess my description meshes to some extent with yours if the number used to generate the map at any point uses some function of the coordinates. If not could you be more explicit?

Yours,
Tony

I meant enlarging the pattern to give an open space to form a passage.
This kind of map generation is something I don't think was used for any of the later versions but was nevertheless fascinating and may well come in useful in other areas.

regards

Andrew

I meant enlarging the pattern to give an open space to form a passage.

Ah, you mean this bit:

5) Do tidying up. This entails selecting the appropriate tile for a grid position given surrounding positions solidities etc. It may be that passageways are initially defined as a diagonal run of a special value, which creates an empty tile here, and forces bordering tiles to cause widenting. May insert some forground stuff like pillars etc.

Basically, it is easy to find if a tile is on a diagonal, as (for the 'low bits')x=y. However it is a little slower to find if you need x=y plus or minus one, or whatever.
If you generate the local map in sections, you can get a speed-up, by (say) setting a whole row to solid except for the one where x=y.
Now, if you are generating in sections, you can also use intermediate values. This would be advantagous where several processing options were to be considered, such as horizontal, vertical and diagonal passageways, the special-tile lookups, and other operations such as smoothing off aliasing using diagonally half-filled tiles. Remember that the 6502 only has a few registers (is it 3?) so you can't hold quite as much state as we are used to now on the ARM.
So I imagine the whole section would be set to 'solid', then the passageways cleared out.

So with a two-pass procedure you might have a range of intermediate values which then affect surrounding tiles (or vice versa). One value for example might indicate that the vertically adjacent tiles were also empty, or diagonally half-empty blocks.

This kind of map generation is something I don't think was used for any of the later versions but was nevertheless fascinating and may well come in useful in other areas.

Yours,
Tony

.constant EQUD &1D872B41

LDR R0,seed
LDR R1,constant
MOVS R0,R0,LSL #1 ; Set random carry
EORCS R0,R0,R1
STR R0,seed
xxxCC ; Do this...
yyyCS ; ...or alternatively this

The 'constant' number will apparently produce a sequence length of 4294967295, which is pretty much the maximum from a 32bit seed. You might also need some code to ensure the seed never gets changed to 0, because that would end the seqeunce. Obviously you need to repeat the bit generator as many times as needed to build up an N bit number. If you want a number between 0 and N, then the technique I'd use is to build up say 16 bits of random number, multiply by N, then divide by 2^16.

I tiried a quick drawing program to generate random tunnerls and rooms in a tiny form but I had a problem stopping excessive crossover.
I would assume the next step would be to scale up a particular area, however I'd first need to get a psedo-random number generator that produced a repeatable set of nos. for a particular map to use these as the 'seeds'.
The quick prog. I mentioned just use BASIC RND.

For what it's worth, I've nearly tried this myself following this discussion. But other programming projects eat up any free time.

IIRC, you can seed BASIC RND somehow. So you can always get the same sequence of numbers. But I don't remember how you do this exactly.
HTH.

Perhaps we could have some sort of competition?

I propose the following ground-rules:

0) The program should run on an Arc or RiscPC, not necessarily a BBC ;-)

1) The program being capable of displaying the map in scaled form, such that 1 tile=1 pixel.
The full map may not be completely displayable, if larger than the screen resolution. If this is the case the user must be able to scroll around.
Other displays are not required, however they may aid understanding and are not prohibited.

2) The map size must be at least 256*256, however larger maps are prefered. Any wrapping or non-wrapping method is permitted, and the form the map uses must be stated.

3) The map calculation algorithm should be 'small', as should the amount of memory required for calculation. (I propose, say 8k total work area for map generation. A zoomed in dispay should be able to use sprites etc from outside this space.)

4) The algorithm should be able to calculate any given map coordinate 'in isolation'. While values from the surrounding area may be used, these must first be generated locally.
This means you can't generate the whole map (say 256*256) in one pass and be unable to specify the state of a specified coordinate without generating the whole map. Generating small sections of the map at once is permitted. Performing multiple passes of such a section is permitted.

5) Every entrant must vote for the map-generater they think is best, and fits these rules (excluding their own entry)

6) The competition is 'for honour' (unless I or anyone else decide to offer a prize).
As such collaboration and friendly advice is positively encouraged.

7) Source code must be released.

This is the *challenge*. Any suggestions / modifications / takers?

Only one addition:

The map must be similar to that in Exile - i.e. a vertical series of connected caverns and passages cut through the ground. Features such as water, objects, etc. are optional.

Hmmm... 8k workspace... yes... I think I can do that... I know the technique I need to use, but can it be made to create the right kind of map...

However this would practically rule out using C (For the finished version, at least). Keeping track of how much memory each variable uses would be practically impossible considering how many temp vars and things C uses.

Of course if I take up the challenge then you'll have to too, Tony

If this is a success perhaps we can use our competitiveness to make the RISC OS world a better place? Just think how many man-hours you could get if you could employ the playpenners...

Pseudo random bit generator, straight from the PRM's (well, almost ):

.constant EQUD &1D872B41

LDR R0,seed
LDR R1,constant
MOVS R0,R0,LSL #1 ; Set random carry
EORCS R0,R0,R1
STR R0,seed
xxxCC ; Do this...
yyyCS ; ...or alternatively this

The 'constant' number will apparently produce a sequence length of 4294967295, which is pretty much the maximum from a 32bit seed. You might also need some code to ensure the seed never gets changed to 0, because that would end the seqeunce. Obviously you need to repeat the bit generator as many times as needed to build up an N bit number. If you want a number between 0 and N, then the technique I'd use is to build up say 16 bits of random number, multiply by N, then divide by 2^16.

What if the carry isn't set though, the seed will be unchanged?

<blockquote><font color="#667799">I tiried a quick drawing program to generate random tunnerls and rooms in a tiny form but I had a problem stopping excessive crossover.
I would assume the next step would be to scale up a particular area, however I'd first need to get a psedo-random number generator that produced a repeatable set of nos. for a particular map to use these as the 'seeds'.
The quick prog. I mentioned just use BASIC RND.</blockquote></font>
I'd be interested in seeing your program.
Is there anywhere on here we could exchange such programs? I don't think there is, but would it be a good idea?

F

I'll send you the program Toby, It's very simple but perhaps you could make a couple of suggestions?

I'd prefer to have some idea about doing it and learn

I don't want to launch into some competition.

What if the carry isn't set though, the seed will be unchanged?

That's right. If the seed is changed to 0, then the carry will never get set again, and so the seed will stay as 0. The sequence itself won't cause it to turn to 0, but you might need a safeguard in whatever routine generates the seed in the first place.

WRT to the competition thing, I can't be bothered doing anything for it now

Fine Tony, don't reply then

Erm, arn't I allowed to go home before 9pm?
Didn't get chance to webpotter on Fri, was at home on Sat (fiddling with my own Exile map prog) and my parents visited on Sun. Work on Mon, this is the first chance I've got.
So is anyone game? I don't think anyone need feel embarassed about their program or programming skills - any entry should be better than nothing.

8 ) The map must be similar to that in Exile - i.e. a vertical series of connected caverns and passages cut through the ground. Features such as water, objects, etc. are optional.

WRT to the competition thing, I can't be bothered doing anything for it now

<repeat *10^6>Ah, go[ooo] on[...|,]</repeat>

My email address is in my profile.