Randomizing Chests, people who give masks and shops in MM?

[TyranitarTime]

Is it possible for someone to make a randomizer to randomize MM Chests, people who give masks and shops?

 

[DeathBasket]

It's very much possible. However, I think it'd be quite difficult for it to be effective because most areas depend on you getting certain items to progress.

[TyranitarTime]

It's very much possible. However, I think it'd be quite difficult for it to be effective because most areas depend on you getting certain items to progress.

Not really.

You can use the bomb hover glitch to get to most places.

I'm requesting this so we at www.zeldaspeedruns.com can have a different experience racing Majora's Mask.

[DeathBasket]

I'd be happy to try and do it but the problem I'm seeing is exactly what you've pointed out - what if you don't get bombs? Even then, you need to also get a bomb bag to use them. There needs to be more thought put into this than it would immediately seem. Is there much demand for a hack like this? Anywhere we can talk about it?

[TyranitarTime]

You can come to the Zeldaspeedruns IRC, I won't be there now however because it's midnight in Europe and I need some sleep.

 

We have thought about it and for this to be beatable, Bomb Bags, Bombs, Bombchu's, Zora Mask and Deku Mask need to be excluded from the randomization.

Everything else can be randomized.

[DeathBasket]

I'll be around I guess.

I will start really thinking about this tomorrow after I have slept, it's late now.

[mzxrules]

Teach me how to hover to Inverted Stone Tower! Because that's kind of a big problem with randomized chest contents. 

 

If you have purely randomized contents, you risk making it impossible to obtain certain items. If you don't randomize the key/boss item locations in dungeons, you'll end up with a sort of 100% run with a broken flow to it. 

[TyranitarTime]

Teach me how to hover to Inverted Stone Tower! Because that's kind of a big problem with randomized chest contents. 

 

If you have purely randomized contents, you risk making it impossible to obtain certain items. If you don't randomize the key/boss item locations in dungeons, you'll end up with a sort of 100% run with a broken flow to it. 

hm.

Dungeon stuff like the dungeon items, maps and compasses won't be randomized.

Wouldn't this only be used for a bingo?

Trying to get as far as you can with what you can find.

[DeathBasket]

I was hoping it'd be possible to have randomised items while still being able to beat the game. If all the dungeon items stay the same then it's really not going to be a lot different to a normal playthrough other than masks being random. The only difference in any% would probably be finding the hookshot. I'm still thinking about how it can be randomised but beatable without having to follow a normal route through the game.

[TyranitarTime]

I was hoping it'd be possible to have randomised items while still being able to beat the game. If all the dungeon items stay the same then it's really not going to be a lot different to a normal playthrough other than masks being random. The only difference in any% would probably be finding the hookshot. I'm still thinking about how it can be randomised but beatable without having to follow a normal route through the game.

Wait a minute, all the dungeon items are the Bow, Fire, Ice and Light arrows.

We could randomize the Fire and Ice Arrows.

[DeathBasket]

Well so far I'm thinking that items can be grouped into importance or similarity. Categories like:

Transformation masks

Important items (ocarina, bow, magic arrows, hookshot)

Normal masks/unimportant items/event items?

Bottles

Songs

 

It may be possible to randomise dungeon chests too but that could be a pain. Some items will need to be fixed to ensure you can progress. Bomb bags, chus, song of healing and Fierce Deity's mask are some examples. If it's done like this, you should at least be able to get all transformation masks with isg, bomb hovering and song of healing as well as whatever masks/items you can get from around Clock Town too. I'm pretty confident that it will be possible to beat the game this way.

[TyranitarTime]

Well so far I'm thinking that items can be grouped into importance or similarity. Categories like:

Transformation masks

Important items (ocarina, bow, magic arrows, hookshot)

Normal masks/unimportant items/event items?

Bottles

Songs

 

It may be possible to randomise dungeon chests too but that could be a pain. Some items will need to be fixed to ensure you can progress. Bomb bags, chus, song of healing and Fierce Deity's mask are some examples. If it's done like this, you should at least be able to get all transformation masks with isg, bomb hovering and song of healing as well as whatever masks/items you can get from around Clock Town too. I'm pretty confident that it will be possible to beat the game this way.

This is good.

Now how would we randomize this?

[DeathBasket]

I'll probably do it by hijacking the function the game uses to give you items and have it load some code from somewhere in the ROM that will handle everything. I'll also need to make sure chests can't be opened twice too to prevent people from savewarping to get all items out of one chest over and over.

 

One thing, is the first cycle still needed or should I skip it by having you start with the song of time and changing the start position?

[wareya]

On the vital item topic, you could re-randomize until you have required items in places they're accessible. Also, are you going to do a true randomize or a shuffle? I think that a shuffle would be more appropriate, keeping the normal distribution of items. This is assuming you do a proper randomization per ROM or something. If you don't want to require people to cart multiple ROMs around, but still want a "deterministic" thing going on, you could do it in game ASM but seed it based on the second file's name.

[TyranitarTime]

I'll probably do it by hijacking the function the game uses to give you items and have it load some code from somewhere in the ROM that will handle everything. I'll also need to make sure chests can't be opened twice too to prevent people from savewarping to get all items out of one chest over and over. One thing, is the first cycle still needed or should I skip it by having you start with the song of time and changing the start position?

Skip it, but have Magic, Song of Healing, Song of Time, 101 rupees in bank and Deku Mask.

[mzxrules]

I'll probably do it by hijacking the function the game uses to give you items and have it load some code from somewhere in the ROM that will handle everything. I'll also need to make sure chests can't be opened twice too to prevent people from savewarping to get all items out of one chest over and over.

 

One thing, is the first cycle still needed or should I skip it by having you start with the song of time and changing the start position?

 

The trouble with that is that you'd have to save your randomized item list, otherwise one could constantly reload an owl statue until they obtained the item they needed.

 

On the vital item topic, you could re-randomize until you have required items in places they're accessible. 

A terrible idea. If you know what places certain items won't be accessible, write the generation algorithm so that they aren't put there. Otherwise, you risk running into a situation where randomization takes 2, 3, 1000, never attempts.

[TyranitarTime]

Any updates, DeathBasket?

Would really love to see this working

[wareya]

>Otherwise, you risk running into a situation where randomization takes 2, 3, 1000, never attempts.

You really over-estimate how much time that would take.... If it takes more than a couple seconds to work then you've gone off the deep end in bad luck etc. Average case performance for something like this is O(n × m!) where n is the number of items to place and m is the number of items that have to be in one specific single location, IIRC. If you let them each/individually be any any of a set of locations, then that lowers. Each randomization should take a small fraction of a second with a set as small as MM's.

If you're really worried about it, you can build a list of valid sets in advance and pick a random one, or take a list of every item in the game permute vital items into acceptable locations in advance of randomly placing the others.

[DeathBasket]

Any updates, DeathBasket?Would really love to see this working

 

I've got some of the basic information I'll need, just figuring out which items can go where without becoming impossible to get. I can probably start putting an actual hack together tomorrow but it might take a while to get everything working properly and actually test things.

[mzxrules]

>Otherwise, you risk running into a situation where randomization takes 2, 3, 1000, never attempts.

You really over-estimate how much time that would take.... If it takes more than a couple seconds to work then you've gone off the deep end in bad luck etc. Average case performance for something like this is O(n × m!) where n is the number of items to place and m is the number of items that have to be in one specific single location, IIRC. If you let them each/individually be any any of a set of locations, then that lowers. Each randomization should take a small fraction of a second with a set as small as MM's.

 

No, it is you who does not understand the pitfalls with the solution you proposed. 

 

you could re-randomize until you have required items in places they're accessible.

 

Or in other words, randomizing then checking to see if the game guessed correctly.

 

To start, your math is quite wrong, for a simple reason... It does not accurately model the problem, which is either

[*]The number of shuffles required to put all required items in the places they're accessible, or

[*]The number of shuffles required to place a single item such that no duplicates/exclusions occur, yet all items remain accessible.

O(n × m!) where n is the number of items to place and m is the number of items that have to be in one specific single location

 

For one, the set of items that must be in a single location does not exist in the set of items are to be randomized, and thus should not be part of the equation. 

The other, is that it is impossible to know how many randomization attempts it will take without actually having an algorithm to check the validity of the solution of each randomized attempt. 

 

To prove my point, lets say you were to implement it like this: You have a pool of potential items, and you randomly choose one out of the pool. You run some sort of check and if the check passes you get that item and it is removed from the pool; else you randomly choose another. Obviously the more complex the check algorithm becomes, the more the reroll count moves from 0, potentially to infinity if you make a mistake along the way. 

[wareya]

Since you obviously have zero respect for me I'm going to do a stupid POC of the random algorithm to show you that I'm not full of shit.

from random import shuffle# Let's say we have 1272 chests in the game (realistically, this is aggressive -- the real value is probably in the 100s)array = range(1272)def find():    # Let's shuffle our array of chest contents    shuffle(array)    # For arbitrary numbers, let's say that items #'d 142, 439, 23, 549, 283, 1, 532, and 489 all have to be in places under 100    # Realistically, this is pretty aggressive; the probability of any one sort being right in this case is roughly 0.08^8    #  Yes, that's extremely low, and yes, I am completely aware that this is how absurd bogus sorts are    # Replacing this simple "under y" function with a per value lookup is trivial.        under1h = [142, 439, 23, 549, 283, 1, 532, 489]        while(1):        condensed = array[:100]        good = True        for i in under1h:            if not i in condensed:                shuffle(array)                good = False                break        if(good):            returnprint "Let's start!"find()# Our chests are now in sorted order.

This is a cruddy python implementation, which is likely an order of magnitude or two slower than the C equivalent.

 

>No, it is you who does not understand the pitfalls with the solution you proposed.

 

I obviously do since I covered them in my second response. Yes, the speed slows down worse than exponentially as the dataset grows. I'm pretty sure that's what the big O thing I posted means.

 

>For one, the set of items that must be in a single location does not exist in the set of items are to be randomized, and thus should not be part of the equation.

 

Thank you for so rudely pointing out my obvious Freudian slip. I don't have the stress to figure out

 

>The other, is that it is impossible to know how many randomization attempts it will take without actually having an algorithm to check the validity of the solution of each randomized attempt.

 

Excuse me, but I'm pretty sure the fact that random sorts are capable of lasting forever is extremely CS 101 (the worst case performance is literally unbounded). Thankfully, PRNGs are total crap, and either will eventually give the right answer or never would in the first place -- though there's no telling how long that would take. If you don't have access to a cruddy, looping RNG, or you're afraid of unbounded performance in the paranoid case, you can simply drop in an iterative function in place of the random one. Not that it's any good either. It's pretty obvious that the re-randomization suggestion was pretty tacky in the first place, and there's no reason at all for you to be so insistent on proving it wrong when I've literally already admitted that it's terrible (O(n × m!) is worse than linear performance, and regardless of whether that specific notation is correct or not this algorithm will always have worse than linear performance) and given rational alternatives.

[mzxrules]

It's pretty obvious that the re-randomization suggestion was pretty tacky in the first place, and there's no reason at all for you to be so insistent on proving it wrong when I've literally already admitted that it's terrible

You really over-estimate how much time that would take.... If it takes more than a couple seconds to work then you've gone off the deep end in bad luck etc.Average case performance for something like this is O(n × m!) where n is the number of items to place and m is the number of items that have to be in one specific single location, IIRC. If you let them each/individually be any any of a set of locations, then that lowers. Each randomization should take a small fraction of a second with a set as small as MM's.

I don't get how you can say you admitted that it was a terrible idea, when it's obvious that you tried to defend your position. 

O(n × m!) is worse than linear performance, and regardless of whether that specific notation is correct or not this algorithm will always have worse than linear performance

Thank you for so rudely pointing out my obvious Freudian slip. I don't have the stress to figure out

Yes, the speed slows down worse than exponentially as the dataset grows. I'm pretty sure that's what the big O thing I posted means.

There is no standard algorithm for randomizing the items in MM, and in the post I responded to you did not describe any sort of algorithm, so regardless of your "Freudian slip" your notation was completely nonsensical. 

Since you obviously have zero respect for me I'm going to do a stupid POC of the random algorithm to show you that I'm not full of shit.

I'm not sure how your POC accomplishes that. As written, your POC program will have to reshuffle the array more than a million times on average, which doesn't support your earlier claim that "Each randomization should take a small fraction of a second with a set as small as MM's"

O(n × m!) is worse than linear performance, and regardless of whether that specific notation is correct or not this algorithm will always have worse than linear performance

Actually, that's not entirely true. There are three variable elements to the algorithm: The elements that can be randomized without restriction, the elements that must exist within the first part of the array, and the cut-off point (the under 100 value). As the cut-off value gets closer to the total number of items to randomize, the average number of rerolls becomes less until you hit O(n).

[DeathBasket]

Update: the hack is pretty much done, or at least it's there and works as intended. However, some items aren't being given to you the way most are so I need to either work around that or drop those items from the hack. I'll get to actual testing and fixing it up tomorrow, I suppose.

[mzxrules]

How does it work?

[TyranitarTime]

What items aren't given to you?

And will it randomize everytime a new file is made?

Can i help testing

[DeathBasket]

Randomisation is based on your filename so it should be the same for every file that uses the same name, making it usable for races and stuff so everyone gets the same items. The item list itself is generated right after you load a file from the file select screen and it's in an area of RAM that won't get overwritten - since the results depend on your filename and you can't change the filename after creating a file, this never needs to be stored in the game save.

 

About not getting the right items, it can easily be fixed... in a way. The solution is probably that you will see the object and text for one item but the pause menu will show that you got another item. I'll try and find all the instances where this happens so I can work out how best to deal with it and whether or not it can be fully fixed.