My final unanswered Exile question

reminisce about bbc micro & electron games like chuckie egg, repton, elite & exileRelated forum: adventures


VectorEyes
Posts: 44
Joined: Fri Apr 13, 2018 1:48 pm
Contact:

My final unanswered Exile question

Post by VectorEyes » Wed Apr 25, 2018 11:30 pm

Hi all,

I grew up with Exile. It came out when I was in primary school. It's still, I think, the game that I remember most fondly.

I finally completed it (under emulation) 15 years later. And I'm halfway through a second playthrough that solves it the 'proper' way (no cheating by abusing the physics system!)

I think I know all the mysteries of the game -- the special fifth weapon (including two ways to get it), the way you're 'supposed' to use the coronium rocks, etc. ... except one. There's a mysterious switch over to the east of the map, near where the red frogmam is. When you press it, it makes a 'door opening' sound. But I've never been able to work out what it does.

My gut feeling is that it's something left over from a puzzle that was never completed. But I'd dearly love to know whether it has some mysterious effect that nobody has ever documented, or whether it really does nothing.

Does anyone know? Or is anyone sufficiently interested in the internals of Exile to work it out? I'm considering trying to teach myself enough 6502 assembly and knowledge of the BeebEm or B-Em debuggers to work it out on my own, but I thought before I did that I might throw open the question to the Stardot community. I'm sure there must be some Exile enthusiasts here who know the answer!

It's this one:
MysterySwitch.PNG

User avatar
trixster
Posts: 588
Joined: Wed May 06, 2015 11:45 am
Location: York
Contact:

Re: My final unanswered Exile question

Post by trixster » Thu Apr 26, 2018 12:28 pm

Have you tried watching the full play-through on Youtube by LordTriax (I think)? Maybe he makes use of the switch?
A3020 | A3000 | A420/1 | BBC B + 128K RAM/ROM + 20K Shadow + Pi0 + VideoNuLA
Master Turbo + DC + BeebSID | Atom | A4000 060 | A3000 060 | A1200 060 | A500
Atari Falcon 060 | Saturn | PS1 | SNES | CPC6128 | C64 | 3DO | MD | Jaguar

VectorEyes
Posts: 44
Joined: Fri Apr 13, 2018 1:48 pm
Contact:

Re: My final unanswered Exile question

Post by VectorEyes » Thu Apr 26, 2018 1:21 pm

Thanks trixster. I have, yes. From memory, Lord Triax's play-through skips the area with the red frogman and that switch entirely. That being said, I'll go and double-check now just to make sure!

User avatar
trixster
Posts: 588
Joined: Wed May 06, 2015 11:45 am
Location: York
Contact:

Re: My final unanswered Exile question

Post by trixster » Thu Apr 26, 2018 3:15 pm

Good work on completing Exile by the way! =D> My brother, Dad and I played it loads when it was first released but we never got much beyond the mysterious door to the west. There was much fun to be had though messing about with the robots and imps and fluffy!

I spent some time with the fantastic Amiga version too, but again never got particularly far.

Is your switch mentioned in either of these two solutions?

http://8bs.com/elecgame/exile_solution.htm
http://www.exile.plus.com/download/exile-solve.txt
A3020 | A3000 | A420/1 | BBC B + 128K RAM/ROM + 20K Shadow + Pi0 + VideoNuLA
Master Turbo + DC + BeebSID | Atom | A4000 060 | A3000 060 | A1200 060 | A500
Atari Falcon 060 | Saturn | PS1 | SNES | CPC6128 | C64 | 3DO | MD | Jaguar

VectorEyes
Posts: 44
Joined: Fri Apr 13, 2018 1:48 pm
Contact:

Re: My final unanswered Exile question

Post by VectorEyes » Thu Apr 26, 2018 4:11 pm

Thanks! I read through both those solutions years ago (indeed I think one of them was the one I used to complete the game) but neither solution mentions that switch, sadly. Both of them pretty much ignore the red frogman as well. I always wondered whether they were somehow connected.

User avatar
trixster
Posts: 588
Joined: Wed May 06, 2015 11:45 am
Location: York
Contact:

Re: My final unanswered Exile question

Post by trixster » Thu Apr 26, 2018 5:43 pm

One last thought, and it's a long shot: do you have access to the Amiga version of the game (WinUAE plus an ADF image is probably the easiest way :) )? I know that the map isn't identical but from memory it's relatively close - you could see if this switch is present here and if so maybe see what it does. Or have a look at an Amiga longplay on youtube to see if it appears?

And if it's not in the amiga version, try the C64 one!

Here's a link to the Amiga map (I can't view it at work to check!)

http://exile.acornarcade.com/amigaimg3.html

thumbnail
Image

There's a map of the C64 version here:
http://www.solutions.c64.org/

Your switch does appear to be present in the C64 version! It might be worth posting on Lemon64 forum to see if anyone knows? At least one person on there has completed that version of the game so they might have the answer.
A3020 | A3000 | A420/1 | BBC B + 128K RAM/ROM + 20K Shadow + Pi0 + VideoNuLA
Master Turbo + DC + BeebSID | Atom | A4000 060 | A3000 060 | A1200 060 | A500
Atari Falcon 060 | Saturn | PS1 | SNES | CPC6128 | C64 | 3DO | MD | Jaguar

VectorEyes
Posts: 44
Joined: Fri Apr 13, 2018 1:48 pm
Contact:

Re: My final unanswered Exile question

Post by VectorEyes » Thu Apr 26, 2018 9:51 pm

Thanks! Very useful links.

So frustrating. The published C64 solution says to press the switch ... but doesn't say why!

So now I'm left with the following options:

- Play the C64 version under emulation up to that point to try to work out what effect it had on the C64.
- Debug the BBC version, breakpoint the switch handling code, hit the switch, try to work out exactly what it's doing by looking at what memory locations the swicth handler altered.
- Register on Lemon64 and ask there.
- And, I suppsoe, hope somebody else knows the answer and reads this!

tom_seddon
Posts: 118
Joined: Mon Aug 29, 2005 11:42 pm
Contact:

Re: My final unanswered Exile question

Post by tom_seddon » Thu Apr 26, 2018 11:36 pm

Don't know if you've seen it, but there's a buildable Exile disassembly here: https://github.com/tom-seddon/exile_disassembly - the answer is presumably in there somewhere!

(also note README's link to original, which might be a bit more readable in places, but isn't buildable)

If you add any additional comments please submit a PR :) I promised myself I'd attempt to figure out more of the physics system and some of the finer points of the sprite routine, but have yet to get round to it...

--Tom

User avatar
Rich Talbot-Watkins
Posts: 1281
Joined: Thu Jan 13, 2005 5:20 pm
Location: Palma, Mallorca
Contact:

Re: My final unanswered Exile question

Post by Rich Talbot-Watkins » Fri Apr 27, 2018 10:10 am

I had a quick look at that to see if I could learn anything, as I too remember that switch and the offscreen door sound, but I didn't get anywhere. There seems to be a table that somehow defines what happens when a switch is triggered, and there's no other kind of hardcoded logic there, so I'm assuming that switches are only able to force a state change in another game object.

Anyway, the answer is there, somewhere. The magic happens in the switch_effects subroutine, which uses the mysterious switch_effects_table to do its work.

Code: Select all

.switch_effects
    STX zp_various_9c
    LSR A
    PHA
    AND #$03
    STA zp_various_9d ; switch_type_and_03
    PLA
    LSR A
    LSR A
    TAX
    LDY #$FF
.L49E9
    INY
    LDA switch_effects_table,Y                     ; find a zero slot in switch_effects_table
    BNE L49E9
    DEX
    BPL L49E9 ; find the Xth zero slot in switch_effects_table
    TAX
.L49F3
    LDA background_objects_data,X
    STA zp_various_9a
    AND zp_various_9c
    EOR zp_various_9d
    STA background_objects_data,X
    INY
    LDX switch_effects_table,Y
    BNE L49F3
    CMP zp_various_9a
    BEQ L4A10
    JSR play_sound
    equb $C7,$C3,$C1,$03; sound data
.L4A10
    RTS
A second pair of eyes could be useful here Tom! It looks like the first time it enters the L49F3 loop, X will always be 0 (is that right?) so background object 0 is always affected (why?). Then subsequent times round the loop affect the object indices from the switch_effects_table until the next &00 byte, so we can see here that a switch is able to change the state of more than one object.

The AND/EOR/STA is the classic generic way of setting/clearing/toggling bits. In this case it always toggles (AND #&FF / EOR #&00..&03), so assume these bits in the background objects data determine whether a door or a teleporter are locked. Can switches do anything else? Change teleporter destination? Each object type presumably has its own interpretation of this byte.

If we can figure out which switch this is, and where the indexed background objects are in the world, we can crack this mystery! If I'm interpreting this table correctly, it looks as if there are only 24 switches in the entire game - does that seem too few, or about right?

VectorEyes, do you have a save game at this switch which you could attach, so anyone with enough time could investigate this with an emulator and debugger?

VectorEyes
Posts: 44
Joined: Fri Apr 13, 2018 1:48 pm
Contact:

Re: My final unanswered Exile question

Post by VectorEyes » Sat Apr 28, 2018 10:24 pm

This is exactly the sort of response I was secretly hoping for when I started this thread! :)

Tom, when I sat down to try to work it out myself last week, I started out with both your buildable version and the version from level7.org.uk. I got as far as realising that the original dissassembly from level7 was based on the non-sideways-RAM version, and I was playing in BeebEm emulating a Master 128, and the 'handle switch effects' routine wasn't where I thought it would be in memory. I couldn't easily work out quickly how to determine where a function would be placed in memory in the 'sideways RAM version' from the .6502 file. I know it'll be easy but I am a complete BeebAsm novice. So then I tried to find a "search memory for this sequence of bytes" function in the BeebEm debugger. Then I gave up and thought I'd post here!

Rich, 24 sounds about right for the number of switches in the game. From memory, they can change teleporter locations (there's a puzzle that involves shooting through a teleporter beam to hit a switch and change the teleport location), they can unlock/lock doors as well as open or close them, they can disable turrets, turn on one of the spaceship thrusters, and probably a few other things as well. So definitely more than just controlling doors!

I'm attaching a game state. It's from BeebEm emulating a Master 128. Unfortunately I can't remember whether I'd already hit the switch during the playthrough or not, because it's been several years since I played. (I had to zip it up as I couldn't upload a .UEF file.)

Really curious to see where all this leads. Even if it is (as I suspect) to "Play door sound, and don't do anything else!"
Attachments
MysterySwitch.zip
(123.45 KiB) Downloaded 9 times

User avatar
scarybeasts
Posts: 19
Joined: Tue Feb 06, 2018 7:44 am
Contact:

Re: My final unanswered Exile question

Post by scarybeasts » Sun Apr 29, 2018 1:33 am

tl;dr -- I know the answer to this. The superficial one and the real one.

But first I have to say that I also claim Exile as a significant influence of my youth (and beyond) and I also carried this same question around for decades: "what does the button do?!". I spent a lot of time pressing the damn thing, especially before I had worked out how to open the rune door.

I finally answered "what does it do?" during a replay rampage a few years ago where I also went through some of the online assembly. The rampage resulted in: https://scarybeastsecurity.blogspot.com ... egant.html

It's not covered in the blog post but during that rampage, I hit the button in b-em with a breakpoint in the appropriate place. The button effects are to toggle the couple of doors near the gargoyle head / sucking bush below. This is the same effect as the button that is directly by the gargoyle head / sucking bush.

I thought this answer would bring satisfaction but of course it did not: "Whyyyyyyyy oh whyyy????". Because there is no obvious gameplay use to that button there having that effect.

I resolved this via contacting the Exile author. Interestingly enough, the button is essentially an aliasing artifact due to the way the table of hand-selected world decorations works. Most of the decorations are "clean". But in the case of this mystery button, it's -- what would you call it -- an echo of the button below. The buttons (real and echo) have the same X co-ordinate and same effect. I didn't get in to full detail but no surprises, I believe the echo is the result of an attempt to compress a lot of detail into not many bytes of RAM :-)


Cheers
Chris

User avatar
scarybeasts
Posts: 19
Joined: Tue Feb 06, 2018 7:44 am
Contact:

Re: My final unanswered Exile question

Post by scarybeasts » Sun Apr 29, 2018 6:50 am

In fact, that button... too soon...

Introducing "Fixile" (attached), a new game a bit similar to Superior Software Exile but where the mystery button now toggles open the rune door.


Cheers
Chris
Attachments
Fixile.ssd
(79.5 KiB) Downloaded 10 times

User avatar
scarybeasts
Posts: 19
Joined: Tue Feb 06, 2018 7:44 am
Contact:

Re: My final unanswered Exile question

Post by scarybeasts » Sun Apr 29, 2018 7:34 am

Oh, one more thing. If you want to convince yourself the button really is an echo, try wasting it. You can blow the front piece off a button with the plasma gun, alien plasma weapon, cannon, etc.

Waste the mystery button and guess what: the other nearby button blows up too. These two buttons are two views on top of the same underlying state. (If you're feeling less destructive, just press the button and see that the other one toggled position too.)


Cheers
Chris

User avatar
FourthStone
Posts: 516
Joined: Thu Nov 17, 2016 2:29 am
Location: Melbourne, Australia
Contact:

Re: My final unanswered Exile question

Post by FourthStone » Sun Apr 29, 2018 7:59 am

This is a great thread!
=D>

User avatar
Elminster
Posts: 2032
Joined: Wed Jun 20, 2012 8:09 am
Location: Essex, UK
Contact:

Re: My final unanswered Exile question

Post by Elminster » Sun Apr 29, 2018 8:43 am

Yesterday I watched ready player one, today I find out the mystery of the button. It is like the world is coming into conjunction with all the planets. Better get my lottery ticket in.

triaxisaworm
Posts: 8
Joined: Tue Dec 11, 2012 10:07 pm
Contact:

Re: My final unanswered Exile question

Post by triaxisaworm » Sun Apr 29, 2018 10:35 am

Thanks for solving that. It still flags up a bit of mystery though - what was the point of the vertical sliding tiled door? The horizontal door by the switch is obviously used to shift the coronium rock and solve that puzzle, but I could never get the purpose of the other door it triggers a bit further up and to the left - near the gargoyle. (Maybe though its another part of that shadow effect.)

I have a final unanswered question too - why didn't the gamers make use of those two large underwater cavern areas near where you find the big fish and radiation pill? (I would never have known they were there if I hadn't viewed the screenshot map of the entire game.) They are blocked off by red mushrooms and are located along the tunnel just below and to the right of the nest where the big fish is found. The other route is to the left past the blue mushrooms further along the tunnel just below where the pill cavern is.

Later on in the game once you've collected the mushroom pill, its possible to swim through these and you discover these two huge caverns - but with nothing in them! (The cavern to the left is also part of the windy tunnel and has some interesting effects when you swim through it.) It was probably just a memory issue, but would have been nice to have an extra key stored away here that was needed to complete the game, or some secret stash of energy pods or coronium rocks you could return to use late on in the game!

User avatar
davidb
Posts: 2070
Joined: Sun Nov 11, 2007 10:11 pm
Contact:

Re: My final unanswered Exile question

Post by davidb » Sun Apr 29, 2018 10:56 am

triaxisaworm wrote:Later in the game once you've collected the pill, its possible to swim through this and you discover these two huge caverns - but with nothing in them! (The cavern to the left is also part of the windy tunnel and has some interesting effects when you swim through it.) It was probably just a memory issue, but would have been nice to have an extra key stored away here that was needed to complete the game, or some secret stash of energy pods or coronium rocks you could return to use late on in the game!
There are also creatures in places you can never reach. These are presumably just an artifact of the map generator which places things like nests automatically. I'm not sure if those can be nests with finite numbers of creatures or if they're infinite creature generators, like the wasp nests.

Removing the artificial structures from the start of the game, you can see how the empty cave with the wasp nest and grenade near the surface was placed specially by the authors, replacing a passage with a door that the map generator had placed. Remove even more structures and you get a feel for what the planet "naturally" looked like. ;)

I used one of the disassemblies online to find addresses in the Electron version that I could patch. I'm guessing that it would be trivial to apply similar patches to the BBC version of Exile using jsbeeb - isn't that possible by passing custom parameters in the game URL?

VectorEyes
Posts: 44
Joined: Fri Apr 13, 2018 1:48 pm
Contact:

Re: My final unanswered Exile question

Post by VectorEyes » Sun Apr 29, 2018 9:43 pm

Wow, it feels so good (if a little bit tinged with sadness) to have the question answered after all these years!

triaxisaworm, I think the vertical door near the 'actual' button (the coronium-past-the-bush-with-vertical-and-horizontal-door puzzle) is to stop the bush seeing into the corridor to the right. If it wasn't there, the bush would always push the coronium rightwards and you could never get it out of the alcove. (It depends somewhat on whether you regard the switch as turning the bush on and off, or opening and closing the doors and thus altering what the bush can see).

This is explained the scarybeast's video that demonstrates a much improved technique for getting the rock out of the alcove, that doesn't require any screen-shifting or thrust-and-throw shenanigans.


I have to say that looking at the game without all the mapped areas is, well, bizarre. I'm so used to the official map that seeing anything different feels very wrong! It's fascinating to look at how the game was put together. Given the number of systems in play, I'm amazed that it ever got finished and published!

The Electron version looks a bit painful to play, as well. I grew up on the "BBC with sideways RAM" version, so I suppose I was spoiled!

User avatar
davidb
Posts: 2070
Joined: Sun Nov 11, 2007 10:11 pm
Contact:

Re: My final unanswered Exile question

Post by davidb » Sun Apr 29, 2018 10:12 pm

VectorEyes wrote:I have to say that looking at the game without all the mapped areas is, well, bizarre. I'm so used to the official map that seeing anything different feels very wrong! It's fascinating to look at how the game was put together. Given the number of systems in play, I'm amazed that it ever got finished and published!
I think the game was developed incrementally so, while the end result looks like it would be impossible to put together in one go, I doubt it was planned that way in the beginning. The Exile tribute site has a bit more information on this.
VectorEyes wrote:The Electron version looks a bit painful to play, as well. I grew up on the "BBC with sideways RAM" version, so I suppose I was spoiled!
I found the letterbox display of the ordinary BBC version a bit restrictive after the Electron version. :)

User avatar
scarybeasts
Posts: 19
Joined: Tue Feb 06, 2018 7:44 am
Contact:

Re: My final unanswered Exile question

Post by scarybeasts » Mon Apr 30, 2018 6:23 am

Hey VectorEyes, I think triaxisaworm is referring to a different vertical door, the one that the gargoyle is firing directly towards.

I always assumed that bouncing that door makes it easier to get past the gargoyle. But replying it just now, I'm not sure.

I don't think that door bouncing is an accident. From the disassembly:

; switch_effects_table
#4978: 00 46 a9 00 6a 8b 00 e6 85 d8 00 c7 88 00 68 00

00 6a 8b 00 means that that switch was explicitly chosen to have two effects because this table encodes a variable length (and NULL terminated) list of effects per button.

Unsolved mystery or just a quirk?


Cheers
Chris

VectorEyes
Posts: 44
Joined: Fri Apr 13, 2018 1:48 pm
Contact:

Re: My final unanswered Exile question

Post by VectorEyes » Mon Apr 30, 2018 9:41 am

Ah, I see what you mean. Sorry triaxisaworm, I mis-read your post.

My recollection is that closing the vertical door opposite the gargoyle makes it easier to blow it up, because the balls of flame that it emits are more likely to bounce back and damage it. I've no idea whether that was the intended puzzle solution, or just an outcome that fell out of how the physics system interacts with the gameplay.

It looks like we know exactly what the button does now, but it's still a bit ambiguous as to whether some of the effects of the buttons in that area of the map (and indeed the layout of some of the objects) were 100% deliberate or just left over from unfinished puzzles and/or an effect of trying to pack so much into so little memory.

VectorEyes
Posts: 44
Joined: Fri Apr 13, 2018 1:48 pm
Contact:

Re: My final unanswered Exile question

Post by VectorEyes » Mon Apr 30, 2018 9:45 am

One extra thought: I wonder whether it's something to do with those switches being the only ones that control *two* doors at once? I'll have to go and look up whether there's anywhere else on the map where a switch controls more than one door at once.

User avatar
Rich Talbot-Watkins
Posts: 1281
Joined: Thu Jan 13, 2005 5:20 pm
Location: Palma, Mallorca
Contact:

Re: My final unanswered Exile question

Post by Rich Talbot-Watkins » Mon Apr 30, 2018 10:01 pm

Thanks Chris (scarybeasts) for that amazing explanation!! I may have competition here for the title of biggest Exile fan :) It's also been a huge influence on me since I first saw it as a teenager, and it just seems to impress me more and more as I learn new things about it.

So one thing I'm wondering is how it comes to be that a single object can have multiple 'views'. I'd assumed that all objects in the game were hardcoded in the 'tertiary object stack' (as the disassembly calls it), but this sounds a little more as if they are rather placed procedurally, and some quirk of the algorithm happens to generate that switch in two different places. Do you have any insights into how all this works?

VectorEyes, it seems as if switches are designed to be able to influence any number of objects when toggled - the switch_effects_table encodes a list of objects whose state needs to be toggled, delimited with zeroes. Looking at the table, there are a few entries which affect 3 or even 4 objects! Talking of that table, there's also some mysterious unused code here which references it and does something odd with it, like the upper bits were designed to mean something else.

Can anyone explain why switches always perform some state change on background object 0 (the first time round the loop)? Anyone know what background object 0 is? In fact, I'm not really all that clear on what all these background_object tables are. Why are the background_objects_data and background_objects_type tables not the same size? No one knows.

User avatar
scarybeasts
Posts: 19
Joined: Tue Feb 06, 2018 7:44 am
Contact:

Re: My final unanswered Exile question

Post by scarybeasts » Tue May 01, 2018 7:26 am

Hi Rich,

Ok, I was supposed to be doing work this evening but your question nerd-sniped me: "how it comes to be that a single object can have multiple 'views'".

Turns out it's actually pretty simple. With reference to the online assembly, http://www.level7.org.uk/miscellany/exi ... sembly.txt.

Looking at the function determine_background, &1715, we can breakpoint there, say in b-em and then force lookups of the content of any game tile by setting &95 = square_x, &97 = square_y.

The useful button is at x=e3,y=bc. This location returns a game tile value of 3. 3 happens to be a special value that makes the engine look up a background object in a hash table of sorts, with the x co-ordinate mixed in. For game tile value 3 at x=e3, this leads to a data pointer value of 6e, (stored in &bd) and a type pointer value of 4c (stored in &be).

Let's look up data pointer value 6e in the background objects table. Data values start at &986. &986 + 6e == &9f4:

# &74 : &0663 = &e3 &0762 = &08 &09f4 = &e4 &0abd = &37 (&e3, &9c) &08: switch

Ok, let's look up the echo of the button, at x=e3,y=9c. Ah, this also returns a game tile value of 3, again a special value causing a background object lookup. Since the value is the same, _and_ the x co-ord is the same, we'll get the same data and type pointers that we got earlier, because the result is essentially f(tile value, x). So two map tiles reference the exact same memory locations for a single button.

My mental model of this is that it's essentially a compression artifact.

Your other question: "Can anyone explain why switches always perform some state change on background object 0".

I'm not 100% sure but I think it might be an optimization to save a few bytes here and there. This trick would enable eliminating checks for "was the result the NULL object"? Who cares -- just write the object slot, even if it's 0, and slot 0 can just be a dummy slot that can be trashed arbitrarily.


Cheers
Chris

User avatar
Rich Talbot-Watkins
Posts: 1281
Joined: Thu Jan 13, 2005 5:20 pm
Location: Palma, Mallorca
Contact:

Re: My final unanswered Exile question

Post by Rich Talbot-Watkins » Wed May 02, 2018 10:24 am

Gotcha. I hadn't realised Exile effectively 'maps' permanent objects like that - I'd assumed they just existed in the tertiary pool and were activated on proximity, but of course, having them generated as a map tile means that activation comes for free, rather than having to perform proximity checks over the entire pool every so often. It's almost surprising that there are no other such instances of object 'echoes' like this, given how they're generated.

The map generation code really is remarkably clever. I was interested to see how the pieces of 'mapped' data fit into the map as a whole, so I wrote a little program in BASIC to perform the algorithm and plot different coloured pixels accordingly, and was surprised to see the following result:
exilemap.png
Blue is forced empty, white is mapped, red is generated.

That is incredibly intricate for what, at this point, is still a reasonably simple algorithm which just categorises (x,y) as "definitely empty", "mapped", or "generated". The "generated" part then performs even more complex manipulations on the (x,y) to give the fine detail of the map. Already though you can see various landmarks: the spaceship and first caves, the area with the survivors, the maggot machine, the water areas at the bottom of the windy shaft, and the rune portal cave.

User avatar
jms2
Posts: 1969
Joined: Mon Jan 08, 2007 6:38 am
Location: Derby, UK
Contact:

Re: My final unanswered Exile question

Post by jms2 » Wed May 02, 2018 3:03 pm

That's great! =D>

Can we see the BASIC algorithm?

User avatar
Rich Talbot-Watkins
Posts: 1281
Joined: Thu Jan 13, 2005 5:20 pm
Location: Palma, Mallorca
Contact:

Re: My final unanswered Exile question

Post by Rich Talbot-Watkins » Wed May 02, 2018 3:56 pm

Sorry, I wasn't clear there - the algorithm was directly ripped from Exile and left in 6502; the BASIC bit was just calling it for every X and Y to get a result.

This initial part of the algorithm is fairly easy to explain however!

First thing to note is that there are two artifically created gaps in the mapped data: the first between the Pericles and the upper caves, and the second between the upper and lower caves. On its own, the algorithm would generate these values in a block, so they 'cook' the Y value so that it's split into three strips (you can even see how the upper and lower caves are split; imagine pushing them together - they fit perfectly!).

So with an X and a cooked Y value, it then does:

Code: Select all

f3_xy = ((((cooked_y AND &A8) EOR &6F) DIV 2 + x) EOR &60) + &28
f2_xy = ((f3_xy AND &38) EOR &A4) + cooked_y
hash = (f2_xy EOR &2C) + f3_xy
* Actually, this is slightly simplified: in reality the 6502 C flag is occasionally adding extra carry into these additions, which makes a subtle difference to the result.

if f2_xy < &20 and hash < &20, then the position corresponds to mapped data. That gives 1024 possible values, which would map nicely to the 1k block of mapped data - but it's not doing this in an obvious way; instead it's doing something dreadfully cunning to get a unique map address from f2_xy and hash, and I still haven't figured out how it works (anyone? code at 17D6...17EB). It seems like it wouldn't be a 1:1 mapping but it needs some thought.

Finding "definitely empty" works on a similar principle. If cooked_y < &4E, it's above the surface, so it's definitely blank if it wasn't mapped. Otherwise, if 'hash' was less than &3D, it's empty rather than mapped. You can make the caves around the mapped regions bigger by increasing this value.

Otherwise if it's below the surface (cooked_y > &4E), it gets really complicated, but I didn't explore this any further yet. There are quite a few hardcoded cases (where particular ranges or values of x,y give specific values), and the whole thing seems very much like a big hack that got them the results they needed, rather than anything with any particular plan behind it!

User avatar
Rich Talbot-Watkins
Posts: 1281
Joined: Thu Jan 13, 2005 5:20 pm
Location: Palma, Mallorca
Contact:

Re: My final unanswered Exile question

Post by Rich Talbot-Watkins » Wed May 02, 2018 4:34 pm

Rich Talbot-Watkins wrote:if f2_xy < &20 and hash < &20, then the position corresponds to mapped data. That gives 1024 possible values, which would map nicely to the 1k block of mapped data - but it's not doing this in an obvious way; instead it's doing something dreadfully cunning to get a unique map address from f2_xy and hash, and I still haven't figured out how it works (anyone? code at 17D6...17EB). It seems like it wouldn't be a 1:1 mapping but it needs some thought.
I just got it to increment every map data address it accesses, and they all map uniquely, and each is hit exactly once. Still no idea how. That's black magic!

Edit: for anyone who cares, here's a faster version of the program, all in 6502, which produces the above picture!
exilemap.zip
(1.12 KiB) Downloaded 17 times

User avatar
BigEd
Posts: 1826
Joined: Sun Jan 24, 2010 10:24 am
Location: West
Contact:

Re: My final unanswered Exile question

Post by BigEd » Wed May 02, 2018 4:47 pm

Maybe a perfect hash function, as first seen in 1984?

User avatar
Rich Talbot-Watkins
Posts: 1281
Joined: Thu Jan 13, 2005 5:20 pm
Location: Palma, Mallorca
Contact:

Re: My final unanswered Exile question

Post by Rich Talbot-Watkins » Wed May 02, 2018 4:56 pm

Ah, I've got it. Essentially it's combining them as:

bits 0-2 = bits 0-2 of f2xy
bits 3-4 = (bits 3-4 of f2xy) EOR (bits 0-1 of hash)
bits 5-7 = bits 2-4 of hash
bits 8-9 = bits 0-1 of hash

So every bit is represented uniquely in the mapping. The last remaining clever bit is that it doesn't appear to generate duplicate mapped sections across the entire x,y domain.

And then there's the actual map generation to consider...

Post Reply