# An Endeavor in Resolving Simultaneous Grid Movement

Synth Spelunkers is a rhythm-puzzle game in which players place small ‘Spelunkers’ onto a grid, which then move one tile every beat of song. When these Spelunkers move, they move based on a predetermined set of logic, which for a single Spelunker is pretty simple to implement. However, we’re not dealing with just a single Spelunker, but a whole group of Spelunkers, all of which must move simultaneously. And what’s more, when Spelunkers move to certain tiles, that may change the states of other tile which can affect where other Spelunkers are able to move, which in turn can have considerable run-on effects.

To put it simply, it’s a bit of a mess to try and work around. Our initially solution didn’t quite hit the mark and had a few issues with the order in which things happened, so I was tasked with reworking the system from the ground up to try and fix it. And goddamnit I did.

This one is going to be massive. Brace yourself.

To begin addressing this system, let’s first look at the rules for a single Spelunker.
NOTE: A ‘Clear’ tile is one a Spelunker can move to, whilst a ‘Blocked’ tile a spelunker cannot move to. Things like switches and spikes are still counted as Clear.

1. Determine where the Spelunker can  move.
1. If the tile in front of the Spelunker is Clear, it will move there.
2. Else, if the tile to the left of the Spelunker is Clear, it will move there.
3. Else, if the tile to the right of the Spelunker is Clear, it will move there.
2. Once the Spelunker knows where it’s moving, activate the tile effects (if it has any).
1. If it’s a switch, change its state and activate the linked objects.
2. If it’s spikes, kill the Spelunker if they’re active.
3. If it’s an exit, remove the Spelunker and increase the exit counter.

That’s more or less the basic idea behind how Spelunkers would move if they were completely alone, because they wouldn’t need to worry about any other Spelunkers changing the state of the map. But they do.

This means that a Spelunker may be standing in front of a door, that is going to be opened by another Spelunker this beat. If we resolve the Spelunkers in order this way, then if the door Spelunker is first in the list, it will turn because it thinks the door if closed. But if the switch Spelunker is first, it will enter the door instead. So, how do we deal with this?

Essentially, the core of the system is a series of loops. Each loop steps through every Spelunker, until it finds one that’s capable of moving with certainty (ie. not in front of a door that might open). At this point, something has changed and the map may have changed also, so the loop begins again, ignoring the one Spelunker that we’ve already confirmed has moved.

```do //Cycle through all checks until everything is resolved
{
//Reset anything that's not been set yet to Unset State.
ResetSpelunkers();

//Reset Direction
currentDirection = Direction.Forward;

//Prep WaitCount
//Used to determine if the loop is working.
previousWait = waitCount;

//Loop through all 3 directions
for (int i = 0; i < (int)(Direction.Right + 1); i++)
{
//Move any spelunkers you can, and check for changes.
hasChanged = CheckDirection(currentDirection);

if (hasChanged)
{
break;
}
else
{
currentDirection = currentDirection + 1;
}
}
//Determine the number of Spelunkers set to Waiting
waitCount = CalculateWaiting();

//State has changed, reset loop.
if (hasChanged)
{
continue;
}
else
{
//If anything is still waiting, see if we need to force a resolution.
if (waitCount > 0)
{
//If nothing has changed, force a resolution.
if(waitCount == previousWait)
{
ForceResolve();
}
}
else
{
isResolved = true;
}
}
}
while(!isResolved);
```

Now, this system works using a form of Finite State Machine. Each Spelunker possess a state variable, and it can only be in one of four states at any given time.

• Unset – The default state at the start of each beat. Must be included in all checks.
• NextCheck – This Spelunker needs to be accounted for until the next low level loop.
• Waiting – This Spelunker can be ignored until the next high level loop.
• Set – This Spelunker has found a space. Is now ignored for all checks.

To clarify, the high level loop is the loop that is getting reset every time something moves. The low level loops are the individual checks for the forward tiles, left tiles, etc.

To get into the specifics, for each Spelunker, first the loop checks where it can move and what kind of tiles are around it. Or more specifically, it check if it’s going to try and move through a door. If it is, it then checks if any other Spelunkers have any chance of moving onto a switch that will change the state of that door. If not, it will treat the door as a Blocked or Clear tile depending on its state and respond according. If it might change, it will wait for later loops before deciding what to do.

This process then repeats until one of two things happens. Either A. All spelunkers have found a valid place to move to, or B. the number of Spelunkers set to Waiting has not changed since the last loop. You may have noticed it at the end of the code above, but this means that we need to force a resolution, as a situation has arisen where there is no simple loop logic that can determine the outcome.

For example, if two Spelunkers are both in front of their own doors, and they both have a button to their left that activates the other’s door, they’ll both be waiting on each other eternally. So we need to implement a form of tie-breaker, that simply forces one of them to move as if the door can’t be opened, then we return to the standard loop to see if everything works out.

```void ForceResolve()
{
bool hasChanged = false;
bool enterDoors = false;

do
{
for (int i = 0; i < spelunkerCount; i++)
{
hasChanged = spelunkers[i].ForceResolveTile(Direction.Forward, enterDoors);

if (!hasChanged && spelunkers[i].state == SpelunkerState.NextCheck)
{
hasChanged = spelunkers[i].ForceResolveTile(Direction.Left, enterDoors);
}

if (!hasChanged && spelunkers[i].state == SpelunkerState.NextCheck)
{
hasChanged = spelunkers[i].ForceResolveTile(Direction.Right, enterDoors);
}

if (hasChanged)
{
break;
}
}

if (!hasChanged)
{
enterDoors = true;
}
}
while(!hasChanged);
}
```

To do this, we step through the waiting Spelunkers based on the order they were spawned. This is our tie-breaking factor. Then for that one Spelunker, we look at the first clear space they can move to. If it’s a switch, and that switch is linked to a door that another Spelunker is waiting on, then that move is made and the loop is reset.

If the Spelunker cannot move to a Clear space that will actually change the outcome of the next loop (eg. opening the other door), the loop proceeds to check the next waiting Spelunker, to see if they can break the stalemate. However, if a Spelunker is waiting on an open door, it is automatically skipped.

But what happens if all of the Spelunkers are waiting on open doors? This then means that none of the Spelunkers actually have to change paths, as the doors can’t be closed (because every remaining Spelunker is entering a door tile). In this situation, entire Force Resolve loop is run again, but with an extra condition that forces the first able Spelunker to enter the door tile its waiting on. You’ll notice this condition being set at the end of the loop above. Then it returns to the main loop, where things should then resolve as normal (or perhaps return to this force resolve loop another one or two times before being completely done).

I’m not going to get into all of the finer points of how the lower level tile resolution works – in terms of determining what effects to activate when entering different types of tiles and the exact logic for determining how their state changes in there. I say this because it’s a really, really big web of functions that is not going to be pleasant for you to dig through.

I will however, leave you with this flow diagram of how the whole system works as one, so you can try to better get your head around it.

NOTE: This diagram is a bit old, so the Force Resolve doesn’t account for all doors being open. (You also may need to open the image using a form of hover-zoom because it’s pretty big and WordPress is being weird about it (opening the image in a new tab isn’t helping)).

Overall, the system manages to effectively resolve beats in a manner that doesn’t require ridiculous amounts of loops, so long as there’s not a ridiculous amount of Spelunkers. As it stands, the loop will always manage to find a resolution to any configuration (with the one exception of if two Spelunkers want to move to the same space, which is something I will expand the system to account for). All in due time, however. All in due time…