# Dominion Strategy Forum

• October 21, 2018, 04:58:54 pm
• Welcome, Guest

### News:

DominionStrategy Wiki

Pages: [1]

### AuthorTopic: A problem similar to alttp randomizer using graphs  (Read 423 times)

0 Members and 1 Guest are viewing this topic.

#### sudgy

• Cartographer
• Offline
• Posts: 3309
• It's pronounced "SOO-jee"
• Respect: +2540
##### A problem similar to alttp randomizer using graphs
« on: October 15, 2017, 04:42:31 pm »
+1

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).
« Last Edit: October 15, 2017, 06:43:36 pm by sudgy »
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

Quote from: sudgy on June 31, 2011, 11:47:46 pm

#### Watno

• Margrave
• Online
• Posts: 2705
• Respect: +2890
##### Re: A problem similar to alttp randomizer using graphs
« Reply #1 on: October 15, 2017, 06:36:33 pm »
0

Unless I'm misunderstanding something, even if you need object C to get back from a and object A to reach A, and object C can be reached using object A, there's no guarantee the player gets C before getting stuck in a.

What I believe you need to do is consider each component of your graph that lies behind a oneway edge separately, I.e. the object you need to get back from a, must be reachable when you are at a.

Also, I don't think your algorithm makes all legal configurations equally likely.
Logged

#### sudgy

• Cartographer
• Offline
• Posts: 3309
• It's pronounced "SOO-jee"
• Respect: +2540
##### Re: A problem similar to alttp randomizer using graphs
« Reply #2 on: October 15, 2017, 06:43:07 pm »
0

Unless I'm misunderstanding something, even if you need object C to get back from a and object A to reach A, and object C can be reached using object A, there's no guarantee the player gets C before getting stuck in a.

I meant to imply that C was after a already.  Maybe I should make that clearer.

Quote
What I believe you need to do is consider each component of your graph that lies behind a oneway edge separately, I.e. the object you need to get back from a, must be reachable when you are at a.

I know that, but the question is what do you have when you get to a?  If you have to have A before getting to a, C should be able to require A.

Quote
Also, I don't think your algorithm makes all legal configurations equally likely.

Maybe not, but I think it's close enough and is simple.
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

Quote from: sudgy on June 31, 2011, 11:47:46 pm

#### Watno

• Margrave
• Online
• Posts: 2705
• Respect: +2890
##### Re: A problem similar to alttp randomizer using graphs
« Reply #3 on: October 16, 2017, 12:40:38 pm »
0

Assuming that it is allowed for a vertex to require multiple items to reach, or for a vertex to carry no new item, your algorithm might get stuck anyway.
Logged

#### Watno

• Margrave
• Online
• Posts: 2705
• Respect: +2890
##### Re: A problem similar to alttp randomizer using graphs
« Reply #4 on: October 16, 2017, 12:44:36 pm »
0

Quote
What I believe you need to do is consider each component of your graph that lies behind a oneway edge separately, I.e. the object you need to get back from a, must be reachable when you are at a.

I know that, but the question is what do you have when you get to a?  If you have to have A before getting to a, C should be able to require A.
You can insert a proxy item and vertex: If some vertex v requires any one of the items in the set S, add a vertex v' that has the incoming edges of v, and place an item x there. Replace the set S with the singleton set {x} in all requirement sets behind v.

(This might be problematic with overlapping requirement sets)

EDIT: Of xcourse that doesn't really help you if there are multiple paths.
« Last Edit: October 16, 2017, 12:48:57 pm by Watno »
Logged

#### Tables

• Margrave
• Offline
• Posts: 2731
• Build more Bridges in the King's Court!
• Respect: +3218
##### Re: A problem similar to alttp randomizer using graphs
« Reply #5 on: October 16, 2017, 12:56:57 pm »
0

Out of interest, what game are you thinking about particularly? I'm guessing it's a Castlevania or something similar but I dunno.

A good solution would be, rather than changing the solution, change the problem. Modify the game such that whatever typically causes the PoNR to no longer exist.

If that's not possible, another option is to duplicate the required item. Maybe it can be found before the normal PoNR, but if you don't find it, then a duplicate copy can be found in that area as well to ensure you can escape it. This has upsides and downsides - it makes things more predictable as a player knows if they can access the PoNR area, they can find at least one of the items to escape it there as well. It might also require some modification to the game so that nothing weird happens by having two of the same item in the game.

A final option is to consider everything in each PoNR area to require a set of prerequesite items to leave the area. Or in other words, make the game logic assume the player must have some set of items to escape the PoNR area already before they can even access them. That way players know that, before they reach those areas, they should be able to find an item/set of items that allows them to escape it. So if they don't have such items, they should either return and search more, or know they're risking a softlock by not finding such an item.
Logged
...spin-offs are still better for all of the previously cited reasons.
But not strictly better, because the spinoff can have a different cost than the expansion.
I hereby declare myself the best dominion player in the world. Obviously.

#### sudgy

• Cartographer
• Offline
• Posts: 3309
• It's pronounced "SOO-jee"
• Respect: +2540
##### Re: A problem similar to alttp randomizer using graphs
« Reply #6 on: October 16, 2017, 03:54:11 pm »
0

Out of interest, what game are you thinking about particularly? I'm guessing it's a Castlevania or something similar but I dunno.

It's a puzzle adventure game that my brother makes for a few people to play.

Quote
A good solution would be, rather than changing the solution, change the problem. Modify the game such that whatever typically causes the PoNR to no longer exist.

If that's not possible, another option is to duplicate the required item. Maybe it can be found before the normal PoNR, but if you don't find it, then a duplicate copy can be found in that area as well to ensure you can escape it. This has upsides and downsides - it makes things more predictable as a player knows if they can access the PoNR area, they can find at least one of the items to escape it there as well. It might also require some modification to the game so that nothing weird happens by having two of the same item in the game.

A final option is to consider everything in each PoNR area to require a set of prerequesite items to leave the area. Or in other words, make the game logic assume the player must have some set of items to escape the PoNR area already before they can even access them. That way players know that, before they reach those areas, they should be able to find an item/set of items that allows them to escape it. So if they don't have such items, they should either return and search more, or know they're risking a softlock by not finding such an item.

I've thought of other modifications as well, but I'm trying to find if there's a simple solution that doesn't involve changing the game.  The best solution that changes the game that I've thought of is just removing the PoNRs.  In the original game they're so temporary that it wouldn't make much of a difference other than that you won't be searching for the object that lets you leave.

Also, I don't want to have softlocks ever possible.
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

Quote from: sudgy on June 31, 2011, 11:47:46 pm
Pages: [1]

Page created in 0.087 seconds with 20 queries.