1

**General Discussion / A problem similar to alttp randomizer using graphs**

« **on:**October 15, 2017, 04:42:31 pm »

So, I was thinking about how a randomizer for another game could be possible, and I ran into problems, so I'm going to try to see if anybody here can help figure it out. I'll go back a bit though to explain the problem.

So, alttp randomizer is a game where someone took alttp and shuffled all of the items around, while making all items still accessible. The problem is to design an algorithm that can give all possible configurations that allow all items to still be accessible. To think of this in more precise terms, I decided to think of the problem with a graph. You have a graph where each vertex (item locations in alttp) holds an object (an item in alttp). A vertex requires some other objects to have been reached before reaching that vertex. The problem then becomes finding an algorithm that could, hopefully without any bias, construct any graph such that all vertices are reachable.

The solution in this case is pretty simple. Split the objects into "progression objects", which are the objects that unlock more vertices, and "nonprogression objects", which are the objects that do not unlock more vertices. Then the algorithm just picks a progression object that will unlock at least one vertex, and places it into an available vertex. This process is repeated until all vertices are reachable. All other objects are then placed randomly.

Alright, so far so good. This works for alttp, and I suspect the actual algorithm is similar to this one. However, the game I was thinking of has something that alttp doesn't: temporary no returns. There are some points in the game where you cannot return to earlier areas without acquiring another object first. In the graph, this would mean that there are some objects that have to be accessible through every possible path up to a certain vertex.

To show why this breaks the earlier solution, let there be a vertex a that requires either object A or object B, and once this vertex is reached, object C must be acquired before going back (assume C is after a in every case). Using our algorithm, we could put object A in some accessible vertex, and could then travel to vertex a. Now, since A was required to get to a, we can put object C in a vertex that requires object A as well. However, if we later put object B in at the beginning as well, we could get to vertex a without ever getting object A and we would then be stuck not being able to get object C. Well, what about always putting object C in an always accessible vertex from vertex a? This is also a problem, because the vertex object B is in could require object A or object C, and then it would never be possible to get stuck having object C require object A. The algorithm needs to somehow be able to account for both of these problems.

I've thought of a couple solutions that use some bias, which I would rather not have, but came up to a bigger problem: one of these no returns is only active when you have another object. So, if you have that object, you can't leave until you get another object, but you could also never be able to get the first object when you go there and then the algorithm needs to let you leave the place.

Anyway, I know there has to be some solution to this problem because there is a horrible algorithm that does solve it (try random configurations until one works, making sure you never repeat a configuration).

So, alttp randomizer is a game where someone took alttp and shuffled all of the items around, while making all items still accessible. The problem is to design an algorithm that can give all possible configurations that allow all items to still be accessible. To think of this in more precise terms, I decided to think of the problem with a graph. You have a graph where each vertex (item locations in alttp) holds an object (an item in alttp). A vertex requires some other objects to have been reached before reaching that vertex. The problem then becomes finding an algorithm that could, hopefully without any bias, construct any graph such that all vertices are reachable.

The solution in this case is pretty simple. Split the objects into "progression objects", which are the objects that unlock more vertices, and "nonprogression objects", which are the objects that do not unlock more vertices. Then the algorithm just picks a progression object that will unlock at least one vertex, and places it into an available vertex. This process is repeated until all vertices are reachable. All other objects are then placed randomly.

Alright, so far so good. This works for alttp, and I suspect the actual algorithm is similar to this one. However, the game I was thinking of has something that alttp doesn't: temporary no returns. There are some points in the game where you cannot return to earlier areas without acquiring another object first. In the graph, this would mean that there are some objects that have to be accessible through every possible path up to a certain vertex.

To show why this breaks the earlier solution, let there be a vertex a that requires either object A or object B, and once this vertex is reached, object C must be acquired before going back (assume C is after a in every case). Using our algorithm, we could put object A in some accessible vertex, and could then travel to vertex a. Now, since A was required to get to a, we can put object C in a vertex that requires object A as well. However, if we later put object B in at the beginning as well, we could get to vertex a without ever getting object A and we would then be stuck not being able to get object C. Well, what about always putting object C in an always accessible vertex from vertex a? This is also a problem, because the vertex object B is in could require object A or object C, and then it would never be possible to get stuck having object C require object A. The algorithm needs to somehow be able to account for both of these problems.

I've thought of a couple solutions that use some bias, which I would rather not have, but came up to a bigger problem: one of these no returns is only active when you have another object. So, if you have that object, you can't leave until you get another object, but you could also never be able to get the first object when you go there and then the algorithm needs to let you leave the place.

Anyway, I know there has to be some solution to this problem because there is a horrible algorithm that does solve it (try random configurations until one works, making sure you never repeat a configuration).