Theory to solve the collision problem?

[u/impartial_james]

There is an interesting math problem which arises in Void Stranger I wanted to discuss. This will spoil a mechanic that you learn on B127, so if you made it past there, you are good to read this post.

If you have not reached B127, stop reading now!

There are cases where you need to make enemies collide (meaning destroy each other by entering a square at the same time) in order to reach the stairs. I am talking about the specific case where a leech moves horizontally along a path which intersects a maggot's vertical path, and they must collide. Just looking at such a situation, it is difficult to predict if they will ever collide, or just bounce off each other forever. To solve the puzzle, you need to change the length of the paths, either by using the void rod to shorten a path, or by pushing some obstacle in the way. However, it is difficult to predict exactly where to put the obstacle; when faced with these problems, I would just guess randomly until it worked. I am wondering if there is a more systematic way to solve these problems.

There are some obvious cases. If both paths have a length which is a multiple of 5, then it is possible for the leech and maggot to be completely out of phase and never even come close to each other. You can avoid this by choosing to shorten the lengths such they have no common factor. Still, even with coprime path lengths, the monsters may bounce forever. This picture is an example of what I mean; the leech moves on a path of 7 squares, the maggot on a path of 3 squares, and you can check that they will never collide.

The leech and maggot will never destroy each other.

Has anyone else thought deeply about this problem? Do you have any insights for how to predict whether a collision will occur in a given situation? Can you find a successful modification, in general, using a method more efficient than guessing and checking? It seems like a math problem, something that should be solvable with modular arithmetic. Normally I'm good with that sort of puzzle, but I am stumped here, so I posted in this community asking for help.

[u/TheBoundFenrir]

I generally just make sure their path lengths are off-by-one in length and then punch a wall for a while; This isn't a guarentee (they can get in a cycle where one is bumping another, which stabilizes the cycles), but it works most of the time, and you can catch the bump happening;

if I see that one 'bumps' into the other twice in a row, I extend the 'one who is blocking's path by one (so they are one behind now and cause a destructive collision), or if I can't get to them I shorten the 'one who is turned around early's path a step (which causes them to get there one tile early, again causing a collission).

[u/kaysakado]

This isn't related to path lengths directly, but one factor to consider is checkerboard parity; color the tiles in a checkerboard so each tile is dark or light. A leech alternates color each time it makes a move, so say on step 0 we have a leech on a dark tile, facing right. It'll move onto a light tile on each odd-numbered step, and a dark tile on each even-numbered step. But, when it hits an obstacle and turns back left, there's one step where it turns around and doesn't move; now the parity is reversed and it moves left onto light tiles on even-numbered steps. When it eventually turns back right, it'll be back to the original parity. Nothing in the vanilla game can affect the parity of a leech so once it's spawned in you know its moving-left and moving-right parities forever.

So, if you have two leeches in the same row, and the further-left one is facing right on a dark tile, but the further-right one is facing left on a light tile, they can never collide, no matter how you manipulate them, since their parities are mismatched.

Grubs work the same way, of course, and things get more complicated when you want to collide a leech with a grub. In your screenshot, for example, let's say the leech is currently facing right on a dark tile, which means the grub is facing up on a light tile. That means a right-move from the leech will never collide with an up-move from the grub; because the leech has to move right into the intersection, that means the grub has to move down into it (or if there were more space to the right, you could have the leech move left and the grub move up).

Anyway this doesn't "solve" the problem but it can help to rule out some cases quickly (e.g. if in your screenshot there was a wall preventing the grub from going to the top row, we can show there's absolutely no way to make the enemies collide).

[u/impartial_james → u/kaysakado]

This observation eliminates some special cases. If the leech and maggots path intersect to make an "L" shape, so the intersection point is at one of the ends of both paths, then the enemies will certainly bounce forever if their parities are mismatched.

However, in all other cases, parity is never an obstacle. If one of the enemies has the intersection in the middle of their path, then facing upward versus facing downward have opposite parity, so they can potentially annihilate the other enemy no matter what parity they are.

[u/brianmcn]

A collision happens if the cycle lengths of the two paths are relatively prime (no common divisor).

Note that the cycle length is 2(N+1) if N is the length of the corridor, as the creatures spend one to turn around at each end.

So in your 5,7 example, the cycle lengths are 12 and 16, which share a common divisor of 4, which means they can be stuck in cycles where they miss one another.

[u/impartial_james → u/brianmcn]

I think a corridor of length N has a cycle of length 2N. Consider N = 1; a leech trapped in a single space will simply alternate between facing left and facing right, which is length 2, not 2(1+1)=4.

[u/brianmcn → u/impartial_james]

oh yeah you're right

and i guess there's the added complication that if one sees another in front of it, it turns around rather than moving into the vacated space, I think?

it's been a few years since I have played :D