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.

I think we want to be as inclusive as possible.
And we want things to be as productive as possible.
However I don't know C, so the code would be indicipherable to me at least. Can't you explicitly type things in C? I'd be inclined to trust peoples estimates of the assembler-equivalent size. Just add a word for every operation in the line etc. Regarding the data, will you really need lots of different sorts of variables at random?
If the problem is all the extra junk they dump in your program, can't you pursuade the compiler to generate Assembler for just the section you want? (I've seen code snippets which were stated to be from the C compiler.)

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

Um... yeh.. :looks furtive

However I don't know C, so the code would be indicipherable to me at least.

It doesn't have to be - it can be very easy to read if properly written and commented. The only minor sticking points will probably be differences in pointer and array syntax compared to BASIC, but again these could be commented.

Can't you explicitly type things in C?

Every variable in C has a type. The typing is relatively weak in that it can be overridden if necessary but that doens't change the fundamental type of the variable in use, just how it's interpreted by the compiler at that point.

I'd be inclined to trust peoples estimates of the assembler-equivalent size. Just add a word for every operation in the line etc. Regarding the data, will you really need lots of different sorts of variables at random?

If the only concern is workspace then that workspace could be explicitly allocated and then all variables created in it. To prevent variables being created on the stack they could be declared as global.

However, TBH, if you're really worried about this then you probably shouldn't be writing the code in any high-level language - that's not what they're for.

If the problem is all the extra junk they dump in your program, can't you pursuade the compiler to generate Assembler for just the section you want? (I've seen code snippets which were stated to be from the C compiler.)

The Acorn compiler can definitely generate an assembler file - it helps when tracking down bugs in the compiler or to see if you could gain worthwhile performance increases by rewriting a section in ARM yourself.

<blockquote><font color="#667799">What if the carry isn't set though, the seed will be unchanged?</blockquote></font>

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.

So it's just shifted once if the carry isn't set?

It doesn't have to be - it can be very easy to read if properly written and commented. The only minor sticking points will probably be differences in pointer and array syntax compared to BASIC, but again these could be commented.

<snip>

If the only concern is workspace then that workspace could be explicitly allocated and then all variables created in it. To prevent variables being created on the stack they could be declared as global.

I hadn't thought of the stack..
The rule should be something like:
code size (of map algorithm) + workspace <=8k.

However, TBH, if you're really worried about this then you probably shouldn't be writing the code in any high-level language - that's not what they're for.

So it's just shifted once if the carry isn't set?

It only gets shifted once anyway - If the carry is set, then it gets EORed with the magic constant. If the carry isn't set, then nothing will happen (Apart from the mandatory shift to set/clear the carry in the first place)

Tony:

I might try the challenge, I might not. If you don't hear from me then assume I'm not doing it

regards

Andrew

Tony - did you get the message in which I sent you the quick map program or are you not bothered?
Either way, let me know please if it's not too much trouble.

Yes I did thanks - it worked the second time.
I meant to email you and tell you I'd tried it but was a little busy - I had a cocktail party on Sat.
Anyway, I had just a quick look at it.
It seems to make some interesting mazes, although I haven't looked at the internals.
I guess it is choosing random positions for the 'rooms' then randomly choosing other rooms to make passageways to.
This makes a nice connected maze (As you have said, a bit too connected.)
If this is correct, it does mean it would be a little tricky to determine the state of an individual tile - one would have to consider all rooms and connections.
Anyway, I'm thinking about it. (May take some time, I'm a bit slow.)

Well I was thinking with a maze generated from a fixed random no. generator such as the one on this thread, you could somehow scale up at a particular point of the maze/map.
The first problem though would be to try to stop it crossing over so frequently as I mentioned a while ago.

Yes, you certainly could do this.
My concern is that it might be a bit slow to do.
Imagine you suddenly want to draw somewhere in the middle of the maze.
To find out the information about the appropriate area, one must first consider all the rooms. Then one must consider all the corridors, to see if any pass through the region of interest.
As the map gets larger the process gets longer.
This is why I favour some kind of more direct algorithm based on the x & y coordinates directly.

Nevertheless, I have a couple of suggestions regarding your connectedness problem.
You are drawing all your corridors room-to-room. I think this is unnecessary. You could try drawing your corridors either room-to-random distance away, or just between two random points.

By changing the average length, or the number of corridors, you can also modify the connectedness.

In the original Exile map, I don't think absolutely everything was connected. Some areas were reachable only by teleporter, and some were unreachable.

Yes that sounds better but I'm no clearer as to how the original map was constructed. I don't think it's something that can be said to be generated simply by 'an algorithm' as I've been told the code to generate it was over 1K in length.

I just don't see how you can get from having a function to draw a pattern to a representation of parts of that pattern be scrolled through step by step.

Here is a simple example to illustrate one method. Please note I'm not suggesting that it is exactly how it was done - indeed I think not. It may be part of the full story however:

Suppose we have 32 'rooms', each of which is the same size and can be in any one of 16 rows and 16 columns (ie in a grid).
One way of describing them would be to store the position of each one as a byte; 16*16=256.
This method would thus take 32 bytes.
However, to find out if any particular position was in a room or not; one would potentially have to scan the entire list. There are ways to avoid doing 32 tests, but still this would take several tests.
Another alternative is to describe whether each position is a room or not (like a bitmap or sprite). This would take 1 bit for each position; 16*16=256 bits; 32 bytes. This is the same amount of space (I chose the numbers so that they would be, and we wouldn't be distracted by space concerns). However, to find out if a particular position is filled or empty, we just have to load the appropriate byte and test the right bit. No cycling is required because all the information is 'local' and easily generated from the coordinates.
Now, that was a very small map, and obviously we couldn't do the same for the whole exile map. But there is a whole world of possibilities.
* use larger meta-tiles to define large-scale features
* use several small interacting maps with different dimensions and which repeat over different distances

I'm not sure if that explains anything because I didn't fully comprehend your last para. If not, could you be a little more explicit, maybe give an example?

That still doesn't explain how you draw a section of the map and then the next part as you move along it stpe by step. You can't store infromation in an algorithm only generate it on the fly.

To get a screen-worth of map, one would loop through screen positions i,j to i+w,j+h

screen position (top left)=f(i,j)
top left-but-one=f(i+1,j)
...
bottom right=f(i+w,j+h)

OK?

so to display the next bit (say, moving right) you first scroll the screen, then just draw the column (increment i, then draw f(i+w,j) to f(i+w,j+h) on the right.

does that make sense?
I might write a quick demo if I get round to it.

Yes it makes sense but you'd still need a function whic generates a pattern which would need to draw in steps according to the smallest degree of movement the player would make on screen.
I think I'm beginning to see it - maybe for a demo. the best thing would to be a really simple function say a couple of lines which changed in their y according to the x value and then work on that.
The simpler the better as long as it illustrates this.

I'm pleased to say I've managed to make a demo - Andrew, it should be in your mailbox now.
If anyone else would like a copy, just let me know.
I am quite delighted with it; it came very easily.
It is not quite in the Exile map style, but I think it a good proof of concept.
The idea which finally let me make a map without too much obvious repetition is that of 'alternative patterns'.
The idea is that you have several different patterns, and use another, larger-scale pattern to choose which one to use at each point.

Andrew, just thought I should check with you the concept of 'tiles'. I'm sure you're aware of this (although you might not call them tiles) but I think it needs mentioning.
The idea is that rather than worrying about every individual pixel of map, it is described as a grid of tiles (usually rectangular or square). Each tile is defined by one of a limited number of different images. In some cases tiles may themselves be grouped together into larger 'meta-tiles'.
In my demo there is no complicating extra fluff, the tiles are solid rectangles either filled or empty. I intend to develop it - partly filled (eg diagonal) tiles can be generated by taking in to account the state of the surrounding tiles.
For the area on the screen (and probably a small distance beyond) the tiles can be stored in memory, to avoid having to recalculate them all the time.

Hope you like the demo.
Yours,
Tony

I'm dying to know...

So what did you think?
I'm dying to know...

You'll have to re-send as a ZIP Tony I'm afraid.

After a quick look at the program running I'd say it looks pretty promising Tony.
I'd like to see the tiles scrolled pixel by pixel though and then we could look about designing proper games tiles. i'll have a closer look at the listing asap.

I was interested to see your update of your Exile Tribute page with interesting info from James Bonfield. What particularly interested me was the judicious use of small amounts of programmer specified map.

I have a cunning plan for converting solid/empty blocks into slightly more aesthetic straight and diagonal sections.. I'll report on my progress.
pixel scrolling will be implemented once I get that done and move to ARM code.
Pixel scrolling is slightly more tricky in ARM code - you must draw exactly to the screen, and I tend to worry about efficiency issues.

The original Exile had large 'swaths' of different types of ground. I'm planning to do similar. This can be done using an algorithm manipulating the top bits of x&y to choose the type.
My intention is to combine the 'tile shape mask' generated above with a texture (and edging) to get the final tile.
'Special tile' generation is already underway.
At the moment I've got the positions chosen. Firstly, only a subset of positions can contain a special. Secondly, the the position must be empty and either the position above or below must be filled. I think this will be OK, with some hashing algorithm to map special positions onto descriptions.

I liiked your pseudo random number generator Tony and would like to see what is possible by experimenting and refining that. It may become highly complex but if it gets a good result then it may be worth it. There are some nice patterns in your existing map however - I wonder if the Exile author's map was similar originally?

If anyone else is reading this, I should point out that my map generates a lot more wiggley passages than the Exile map. These came about almost by chance and I liked them.
I also got some nice large caverns - again by chance.

To get nice straight passages like in Exile I suppose a slightly different technique would have to be applied.

Something which doesn't seem to be commented on much about the Exile map is the presence of one-in-two gradients. Indeed, many people seem to have completely ignored them. This is a shame because I think they made the map much better - however I'm not sure how they were done.

Yes I don't know how you came up with the functions that generated the pattern but it's fascinating how it generates the passages.
IS this what you mean by adjacent postions being related?

Yes - I meant that if they were not then one would tend to get a lot of little enclosed areas.
Although on reflection this may not be such a problem with only two values and equal probabilities. Although it would if you wanted more solid area than empty.
My thought was basically that if you have an empty position, you will want more, connected empty positions next to it.

On a somewhat unrelated note, I like the map you have in the background on your site. Did you generate it from a clearer map and if so how could I get hold of a copy?