Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
And I'm not done yet! I found out how to enter the skeleton throne trap door without having to use either the scepter or the ring (the hole will be open as soon as I enter this room). This should save 10 seconds or so. I also have another idea that could save 5-10 seconds. Stay tuned!
EDIT: Argh, I can't get the new route to work at all. RAM address 0506 makes me overwrite previous items that I pick up, so I'm not sure it will work. I'll look into this some more, but unless I find something new, I think the previously posted run might be submitted soon.
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Here's a weird death I found using HHS' script extraction. By using Big Coin on this left torch here, the game initiates a dialogue with the troll, who throws you to your death.
Link to video
Apologies in advance for a bit of a long post here.
Quite a long time ago I was playing around with the glasses glitch with the intent of doing a speedrun -- I thought that I could jump to the end of the game using the inventory overflow. Much to my surprise, I succeeded! It was really a stroke of pure luck that I found this by pure experimentation, without tools, and before I gave up. However, the lack of tools made me unable to reproduce it, so I abandoned it for a while.
SGDQ pushed me to get into TASing for the first time, and after a week and a half or so of work, I'm happy to present a working example of this skip. I've uploaded the movie here, and I made an encode here.
Forgive the disgustingly unoptimized menus/everything throughout.
Essentially what I do is set address 04E5 (page 2, slot 3 of EI) to value $D2, by taking the horseshoe and nothing else from the lab. By USE-ing $D2 from the wraith room, it jumps straight to the end event where you defeat the behemoth. Just as Randil predicted, it's an improvement about understanding the unknown codes in EI better and how the game handles them.
I haven't taken a lot of time to really understand why this works, but my suspicion is that it works like so:
- USE routine does a calculation that directly involves the item and room values to figure out what address to jump to for the resulting actions (by "directly involved" I mean that the value is explicitly used, such as in a jump table, rather than an explicit case-by-case check).
- By giving the routine calculating the address a value different than any expected item, the resulting address jumps into random memory. (As noted by Randil before, jumping to random memory is pretty unstable and usually useless. For most values, this ends in graphical glitchs, hangs/freezes, opening text repeatedly, infinite chains of events that don't end, etc. I assume this is because it jumps into data display routines without commands to check/end/return.)
- In this case, $D2 from the wraith room is the exact (or near-exact) value needed
to successfully jump to the ending trigger in memory.
After looking through HHS' dumps (which are extremely helpful, thank you for those), it seems like the address that triggers the ending is A90E, though skipping to A909, A90B, or somewhere in that range may result in the ending event as well.
This movie is meant to just be a proof of concept -- after taking the time to read this thread and watch the current submission, I see that my menus are incredibly lacking! I was completely unaware you could do default actions with no action selected, move the cursor diagonally, or wrap the cursor to the top from the bottom. I also had no idea some rooms didn't decrease the torch counters -- I had those values watched but didn't pay much attention to them. The book room in particular is important! Many thanks to everyone who helped in this thread and Randil for his previous TASes. Had no idea this game was getting so much love!
I hope to re-do and submit this movie using the previously found optimizations/tricks and potentially input, but I think there's the possibility of an even faster setup here -- some value to use to jump from the library area would be ideal. After redoing the movie, next step for me would probably be looking at the action subroutines in depth. All comments and any possible improvements are very welcome!
I made an encode here.
Essentially what I do is set address 04E5 (page 2, slot 3 of EI) to value $D2, by taking the horseshoe and nothing else from the lab. By USE-ing $D2 from the wraith room, it jumps straight to the end event where you defeat the behemoth. Just as Randil predicted, it's an improvement about understanding the unknown codes in EI better and how the game handles them.
So, you literally require enough items so that when you go into the Lab, the Horseshoe will drop into Page 2, Slot 3.... and then you keep "TAKEing" Glasses in the Wraith room until it shows the screen with Globe, then push it to the next page, use option 3 and BOOM, game complete?
I wonder what other rooms will be able to trigger this, in case going forward a bit more may unveil a slightly faster room. I'd hate to think a few more options and a few rooms forward may yield a slightly faster result than all that backtracking.
But regardless, this is an absolutely PHENOMENAL find and makes me wonder if this will be possible in Deja Vu and Uninvited?
Mr. Kelly R. Flewin
Mr. Kelly R. Flewin
Just another random gamer
----
<OmnipotentEntity> How do you people get bored in the span of 10 seconds? Worst ADD ever.
I made an encode here.
Essentially what I do is set address 04E5 (page 2, slot 3 of EI) to value $D2, by taking the horseshoe and nothing else from the lab. By USE-ing $D2 from the wraith room, it jumps straight to the end event where you defeat the behemoth. Just as Randil predicted, it's an improvement about understanding the unknown codes in EI better and how the game handles them.
So, you literally require enough items so that when you go into the Lab, the Horseshoe will drop into Page 2, Slot 3.... and then you keep "TAKEing" Glasses in the Wraith room until it shows the screen with Globe, then push it to the next page, use option 3 and BOOM, game complete?
I worded it a bit badly there -- by page 2, slot 3, I meant page 2 slot 3 PAST the end of the actual inventory. Basically, the slot I use at the very end is the same data that the game uses to determine what items are present in the lab, so by taking the horseshoe I change it to the value I need.
But you've got the gist -- put the magic value in the right place, use it, and boom, game complete ^^
Mr. Kelly R. Flewin wrote:
I wonder what other rooms will be able to trigger this, in case going forward a bit more may unveil a slightly faster room. I'd hate to think a few more options and a few rooms forward may yield a slightly faster result than all that backtracking.
That's part of what I'm looking to test before submitting this -- right now the $D2 value is specific to the wraith room, but I do think it should be possible to use other values from other rooms. The question is if we can get those values into memory where the inventory overflow can reach.
Mr. Kelly R. Flewin wrote:
But regardless, this is an absolutely PHENOMENAL find and makes me wonder if this will be possible in Deja Vu and Uninvited?
Thanks! I haven't really looked at either Deja Vu or Uninvited, but I know that there's the bullet overflow glitch in Deja Vu, and I think Uninvited has something similar? It may be possible!
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Amazing! Please keep us posted on your future progress! I will take a closer look at your movie file in the near future and post any relevant thoughts I have about it.
Thanks! I haven't really looked at either Deja Vu or Uninvited, but I know that there's the bullet overflow glitch in Deja Vu, and I think Uninvited has something similar? It may be possible!
Yeah, Deja Vu has (as you say) this bullet overflow trick. I haven't been able to use it in the same way as the glasses trick in Deja Vu, but maybe you will have more luck. There is (as far as I know) no similiar trick for Uninvited (if there is, let me know :) )
Amazing! Please keep us posted on your future progress! I will take a closer look at your movie file in the near future and post any relevant thoughts I have about it.
Thank you! I definitely will.
Yeah, Deja Vu has (as you say) this bullet overflow trick. I haven't been able to use it in the same way as the glasses trick in Deja Vu, but maybe you will have more luck. There is (as far as I know) no similiar trick for Uninvited (if there is, let me know :) )
Ah, well, it may look grim then. I remember seeing the bullet trick a few years back and thinking it wasn't as interesting/powerful as the glasses, but when I said I haven't looked at them I really mean it haha.
Some thoughts on where I'm going with this for now: I want to do some work around trying to find a faster setup than backtracking to the wraith room.
I remember that while messing around with invalid item values, I got to the exact same chain of events by using different values with USE and LOOK. I believe the values I used were USE with $D4 and LOOK with $73, but that could be wrong -- need to double check my notes. (In particular, I think $73 is the globe, but I've also seen codes that had the display name of an item, but jumped to random memory when used, so it's unclear whether that's an issue.)
What getting the same events suggest to me is -- using these two different values jumped to the same location in memory. If the different actions use static offsets (amount it jumps doesn't change by room or other variables) then it's possible that we could LOOK at a $71 from the wraith room and also jump to the end event. Overall I think it means we're not constrained by what action we're using, we can still jump to the same location. Actions meant to be used directly on scenery (in particular, OPEN and CLOSE) seem to be a bit harder to use, because they'll return "It won't open!" or similar for some out-of-range values, but it's possible to sometimes use them.
There's a couple constraints that may apply, I think:
- if the start of where the action looks is too far away from the ending event, we may not be able to produce a large enough value to complete the jump.
- if a particular action in a particular room starts looking in a location past where the end event is triggered, we won't be able to go backwards to hit it.
Judging by HHS' dumps, it seems like there are quite a few rooms where actions start past the address that the ending triggers at, but I'm not really sure yet. Overall I think there's enough options that there's no real choice but to analyze the actual routines for calling actions.
Later tonight I'll probably start on debugging these calls. If anyone has any memory/RAM values that have to do with the current selected action, those would be really helpful!
I worded it a bit badly there -- by page 2, slot 3, I meant page 2 slot 3 PAST the end of the actual inventory. Basically, the slot I use at the very end is the same data that the game uses to determine what items are present in the lab, so by taking the horseshoe I change it to the value I need.
But you've got the gist -- put the magic value in the right place, use it, and boom, game complete ^^
That makes sense. Also watching someone doing this real time has assisted me in grasping the concept a bit better.
That's part of what I'm looking to test before submitting this -- right now the $D2 value is specific to the wraith room, but I do think it should be possible to use other values from other rooms. The question is if we can get those values into memory where the inventory overflow can reach.
Jiseed [www.twitch.tv/jiseed], is at time of this post, currently doing End of Game glitch attempts and he actually proved my curiousity accurate. Literally does the Glasses glitch in the hallway and then moves forward one room, "USE" and poof! Game end! AND!!! It went wayyyyyy faster than the super slowdown of your version.
With this, he's currently sitting at a PB of 5m52s.
Thanks! I haven't really looked at either Deja Vu or Uninvited, but I know that there's the bullet overflow glitch in Deja Vu, and I think Uninvited has something similar? It may be possible!
Deja Vu does have the bullet overflow glitch... but I mean if you managed to surf the code to this execution, I would not be surprised if you'd figure another pathway via the glitch to execute the End Game scenario via proper flagging.
Uninvited, no one has discovered anything... well that's been publicly known or documented somewhere that we are aware of... so who knows, your magic fingers may find the element required.
Mr. Kelly R. Flewin
Mr. Kelly R. Flewin
Just another random gamer
----
<OmnipotentEntity> How do you people get bored in the span of 10 seconds? Worst ADD ever.
Jiseed [www.twitch.tv/jiseed], is at time of this post, currently doing End of Game glitch attempts and he actually proved my curiousity accurate. Literally does the Glasses glitch in the hallway and then moves forward one room, "USE" and poof! Game end! AND!!! It went wayyyyyy faster than the super slowdown of your version.
With this, he's currently sitting at a PB of 5m52s.
Wow, just wow. Extremely timely too! Thanks so much for posting this and to Jiseed for finding the better setup. I was just in the middle of debugging, but that's going pretty slowly, so I think I'm just going to finish up the movie with the setup Jiseed is using. 2 rooms off library is almost as fast as possible -- the fastest possible being in the hallway itself (unless the hallway itself also has the massive lag, but...).
I think I should have the movie finished up end of this week at the latest! Thank you again for the heads up.
I've completed an attempt that I think is fairly solid -- movie is here: http://dehacked.2y.net/microstorage.php/info/212494539/zekna_randil_shadowgate_v2.fm2.
Total frame count is 15812, time around 4 minutes 24 seconds.
I re-used Randil's input as much as possible, and used it in whole up until the waterfall room. I also use Jiseed's glitch setup.
The only routing choice I make is to pick up an extra stone in the waterfall room -- this saves 2 page turns in either the mirror room or the drake room/bridge (depending on whether you use the stone on the sling in the sphere room or not), and also saves about 40 frames at the glasses section. There's one less pair of glasses to take, and having the torch be at the very bottom of the menu saved some movements as well.
I did a full playthrough without taking the stone -- taking the stone turned out to be 50 frames faster.
This is my first full, official TAS attempt, so any and all feedback is very appreciated!
Joined: 4/20/2005
Posts: 2161
Location: Norrköping, Sweden
Nice job! The spear suicide was hilarious. :) The menu movement seemed very good as well (I watched parts of the new content in frame advance). I'm afraid I don't have much to contribute other than my awe of the fact this game can be broken this much!
Thanks! I'm hoping that part can serve as some entertainment ^^ I remember that you said previously in this thread that using it was the fastest way to do that -- pretty sure I facepalmed when I read it since I hadn't thought of it at all.
Randil wrote:
The menu movement seemed very good as well (I watched parts of the new content in frame advance). I'm afraid I don't have much to contribute other than my awe of the fact this game can be broken this much!
Thank you so much for taking the time to look at it. I'm glad to hear it looks good! And really, I think everyone (myself included) is in awe at how broken this is now.
d-feather wrote:
You actually surprised me there with an improvement that large. The ending had me scream "WHAT?!" as well.
Thank you! I'm glad to hear it was entertaining, even after skipping all the interesting item creation/memory manipulation the previous run did. And of course, thanks for taking the time to watch it!
Yes! Apologies for the lack of updates.
I decided I wasn't really going to be satisfied until I've tested all possible blank EI values that are faster to hit than the current one, to be sure none of them result in an end skip. It's unlikely that one will result in a faster skip, but I want to be sure. Basically I plan to figure out all possible values for the first and second pages of EI that are manipulable on the route -- some of the second page requires going too far to be worth it, and some of the first page is related to the wraith/rope/wizard rooms. Then test all first page values in every room one off from the hallway, and second page values in the hallway. Basically, test anything that would be faster than the current setup.
There isn't a lot of manipulation possible for these values -- some of the rooms have to end in a certain state, and some you must take something (stone room) or can't take more than one extra item (dragon room). I'm hoping to get through the rest of these this weekend.
As for smaller improvements, I saved 4 frames because I didn't realize you could skip the text after defeating the behemoth on the first possible input frame. Normally this is only true of "continuing" text, which this didn't strike me as.
I'm also fairly sure that I can save about 60 frames by taking the sword in the closet. This will take at worst 32 more frames, and will also:
- not have a natural page turn in the dragon room, potentially saving lag frames, saving ~1-3 frames
- remove the need to page turn in the lake room, saving ~65 frames
- require taking one fewer pair of glasses, saving ~30 frames
This will move the torch during the glasses overflow to a less desirable spot in the inventory list, but I'm fairly certain I can keep it where it is if I just take and light the torch one action early.
Hoping to finish all this up this weekend.
Here are some details on how scripts work in this game: There is a main table at the beginning of bank 3, pointing to tables for all types of objects: Scenery, Fixed Containers, Trash, Items, Containers, Doors and Magic, respectively. These tables in turn contain pointers to verb tables for every object of that kind, which list the script address for every verb that the object supports. Usually, objects support the following verbs depending on their type:
Scenery: LOOK, USE, HIT, SPEAK
Fixed containres: LOOK, OPEN, USE, CLOSE
Trash: LOOK, OPEN, USE, CLOSE
Items: LOOK, USE, LEAVE, TAKE
Containers: LOOK, OPEN, USE, LEAVE, TAKE, CLOSE
Doors: LOOK, OPEN, CLOSE, MOVE
Magic: LOOK, USE, SPEAK
There are exceptions, listed in a table at 6:$ab36 (3 bytes per entry: type, id, command set, terminated by $ff). Command set 7 includes all verbs.
Inventory entries are classified as follows:
$00-$7f: Items
$80-$9f: Containers
$a0-$bf: Fixed containers
$c0-$df: Trash
$e0-$ff: Magic
Thus, an inventory code of $d2, for example, corresponds to an invalid trashcan $12 which has its verb table at $dfc7 with entries LOOK=$3e00, OPEN=$8ff, USE=$309, CLOSE=$e003. So, you can easily run random junk from RAM by performing actions on invalid objects. Command $55 will invoke the ending.
HHS, thank you so much! This is exactly the type of information I was looking for. With this I can be sure about the existence of faster setups, and it opens up the possibilty of writing a script to check setup values instead of manual testing.
I'd love some more detail on this, if you have it. Let me go through the example to see if I understand the process:
- player does USE on #$D2
- determine type and id: item type is Trash, id is #$12 (#$D2 - #$C0, #$C0 being the first possible Trash-type id)
- get Trash table address from main type table
- reading offset #$12 from Trash table as an address gives $dfc7 (not a valid verb table address? -- I assume it breaks here because this is the invalid code)
- address $dfc7, when interpreted as a list of addresses for commands, gives $3e00, $08ff, $0309, $e003. This is random memory interpreted as a table of addresses.
- address $0309 corresponds to the address for USE offset, so we load an offset/address
- address $0309 houses command $55, the ending event.
I assume the exception table is checked at some point, but I'm also assuming that invalid item values aren't listed in the exception table.
HHS wrote:
Command $55 will invoke the ending.
A bit confused here; I'm assuming $55 is an offset into a scripting command table. Does the verb table's end address contain a value to be used as an offset into this table? Or does it simply contain an address to jump to, and $55 is an offset/designation seperate from the actual call?
To write a script to calculate the resulting command value from an item code, I assume I would do the following:
- determine type/ id, where id is equal to the difference between the current value and the first value of the same type.
- use the type as an offset into the main table and read the base address for the type table
- use the item id as an offset into the type table and read the base address for the verb table there
- use the current action as an offset into the verb table, and read value for the command to execute
- compare value to $55
questions:
- actual values for action offsets? My guess is that entries in tables of addresses are 2 bytes, and that they'd be sequential
for some order ([LOOK=0, OPEN=2, USE=4, LEAVE=6, TAKE=8, CLOSE=10, HIT=12, SPEAK=14, MOVE=16]?)
Doing all for each type seems like a waste though -- perhaps they order based on only the specific type list only?
- to be sure, no table is jumped to until the command value is loaded? It just loads values from the tables?
Yes. It is not necessarily trivial to figure out whether a given script is going to result in the ending, though. If you're executing from RAM, some commands might result in a change to the very RAM addresses that you are executing from. One might also need to take jumps into account.
The verb table entries are ordered according to the scheme given above. So, a trashcan would contain script pointers for LOOK, OPEN, USE, CLOSE, in that order. It looks up all this as soon as you have selected the object that you want to act on, and then it starts executing commands until it reaches $ff.
However, it turns out that $0300-$037F holds the tile attribute table. So $0309-$30b holds attributes for the tiles at the top of the room. There are many rooms that have a $55 in one of these locations. For example, the room that is north of the rug room (7), with the ancient tome in it, has $45 $55, so it will show the riddle and then go to the ending. Here is the full list of such rooms: 6, 7, 8, 9, 21, 34, 35, 36, 37, 72, 73, 74, 75, 84, 85, 86, 87, 88, 89, 90, 91, 92, 105, 122, 123, 124, 125.
Also, rooms with $55 in $0311-$0313 (second row): 2, 3, 4, 5, 19, 20, 21, 27, 32, 33, 35, 37, 46, 47, 48, 49, 50, 52, 53, 54, 67, 68, 76, 77, 82, 83, 84, 112, 126
Rooms with $55 in $0319-$031b (third row): 2, 3, 4, 5, 19, 20, 27, 38, 39, 40, 41, 63, 64, 69, 70, 71, 93, 94, 112, 113, 119
For the record, bank 0 has data for rooms 0-75 and bank 1 has data for rooms 76-131. They both have a pointer table at the beginning pointing to the rooms. At offset $c4 within each room is the tile attribute data (16 bytes).
If you're executing from RAM, some commands might result in a change to the very RAM addresses that you are executing from. One might also need to take jumps into account.
Ah, you're completely right. If it's a string of commands that finishes with the ending it gets much more complicated. Probably a lot easier to make a script that just finds invalid values that we can create that are faster (there aren't many) and test each manually.
It looks up all this as soon as you have selected the object that you want to act on, and then it starts executing commands until it reaches $ff.
So, the script pointers for each action point to a null-terminated list? That would explain the very prevalent "infinite" event loops when doing actions on invalid values.
it turns out that $0300-$037F holds the tile attribute table. So $0309-$30b holds attributes for the tiles at the top of the room.
This is incredibly illuminating, thank you. The fact that the end skip is room-specific is nicely explained, and why we get different events in different rooms for other invalid values.
Here is the full list of such rooms:
A bit confused by the numbering here. I thought rooms north of the tome room were 10 and 4, while it itself was 2. I also don't see 26 in the list (the grand hall), which is where we're currently doing the skip from. I'm going by the value in RAM at $500 and the room dump you did earlier.
A list of rooms like this really is helpful though. I don't think it rules out rooms entirely, as there's the possibility of reading from a different location in RAM still (I think), but this lets us rule out rooms that the current skip and similar values can be used in.
I'm struck by the fact that most of the invalid values I took actions on varied in their effect by room, with the exception of a few. Ones that didn't vary mostly didn't result in actual events, but rather crashes, cursor resets, and other things. Might mean jumping from RAM other than the attribute table or nearby isn't likely. The attribute table is certainly convenient, since it contains a decent number of values that are valid script commands!
For the record, bank 0 has data for rooms 0-75 and bank 1 has data for rooms 76-131. They both have a pointer table at the beginning pointing to the rooms. At offset $c4 within each room is the tile attribute data (16 bytes).
Thank you very much! ^^ I think it may be time for me to get my hands dirty and dive into some of the ROM.
After testing, I found that taking another stone from the waterfall room is 7 frames faster than taking the sword. I also overestimated how much time could be saved by taking the extra item. Fastest movie I have to date can be found here: http://dehacked.2y.net/microstorage.php/info/412721207/zekna_randil_shadowgate_v3.fm2.
It's 40 frames faster than the previous, due to the extra stone and some other small time savers (fixed missing some frames in menus here and there).
I was actually able to reproduce an end skip using a different value than $D2. I found that value $8D ended up executing commands from some values that changed over time, so hitting the action on different frames produced different results. In the laboratory I was able to skip to the end event by using $8D on a particular frame.
While skipping the horseshoe and going to the lab after the overflow is definitely a faster setup, the actual skip had worse slowdown than my original wraith room skip, making it slower by far. It also seems like the frame I need to wait for may not come very quickly -- after entering the laboratory, I couldn't get the skip within several hundred frames, making the setup about the same speed anyways. USE-ing $8D gives consistent values most of the time, which vary between a couple different values. I think it may be sprite or audio data from RAM that's being executed as a command, but I haven't double checked.
I'm still looking at testing other values that could potentially produce an end skip. If nothing else is found, then the above movie feels pretty close to the end product to me. Please, everyone feel free to give any suggestions you may have to improve it!
Yeah, sorry, I meant the screen number ($0501), not the room number. This can be found from the table at 6:$af95 which contains pointers to a list of screens for each room, one for each combination of opened doors, terminated with $ff.
