How to handle two player-programmed robots attempting to enter the same discrete grid cell in one game tick

Question

I am making a game with discrete block positions (something like minecraft) where you can program robots with instructions to move around, the robots are the size of one block, and they can execute one instruction per game "tick".

There is a problem when two robots want to move to the same cell in the next game tick (the green squares are robots):

I can see three possible solutions, but all of them are not satisfying:

• The robots have an order in which their instructions are executed, so one robot will always have priority to move over the other -> difficult to tell which robot has the priority, unless each robot have a number displayed on it
• The instructions are run in a random (or seeded pseudo-random) order, forcing the player to avoid these interlocked states -> not consistent or not clear enough for the player
• Only one robot can move at a time -> not interesting gameplay wise

As this is a programming game, the behavior of the programmed robots should be deterministic and predictable by the player. What would be the best way to handle this?

Some games don't handle this at all, in minecraft for example red stone behavior is non-deterministic and depends on factors the player cannot reason about.

Answer 1

Some ways I've seen this solved:

Treat a collision as a failure state

Zachtronics games like SpaceChem and Opus Magnum commonly go this route. The player is challenged to create a program that does not lead to a conflict or collision, and causing one immediately halts execution. The player can then observe the problem, modify the program/machine to avoid it, and re-run the execution from scratch.

An alternative version of this is to self-destruct robots that are in conflict, or turn them into permanent obstacles, but then allow the rest of the execution to continue if it can, rather than treating it as automatic failure. So there may be times when it makes sense to "sacrifice" robots this way, ending their execution while the rest of the distributed program marches on.

Assign "right of way"

You can introduce a simple rule that if two (or more) robots' instructions for a given tick conflict, then one is deterministically given priority to execute, in a way that the player can easily work out which one that is without identifying characteristics on the robot.

One such rule is "The robot furthest to the east has priority. If two robots in the same east-most north-south column are in conflict, then the one furthest to the south has priority".

For any cluster of interacting robots, one column of them will always be furthest in the "east" direction of your map, and one robot in that column will always be furthest "south".

The rest of the robots in the conflicting cluster wait, effectively executing a no-op. You can decide whether they continue trying to execute the same instruction on the next tick, effectively delaying their program, or if the wait causes the instruction to be skipped and they resume at the next instruction after the conflict.

Other robots not in that conflicting cluster still execute their actions simultaneously, so you're not limited to only one robot moving at a time, which you'd raised as an issue with one of the potential solutions you identified.

Sub-step in a predictable order

You could also allow all robots to act, but have them execute their actions consecutively within the tick rather than simultaneously when there's a conflict.

You'd use a rule similar to the right of way rule to assign an order of execution, like proceeding west to east, north to south. So the west-most robot on the north-most row of the conflict acts first, then the next one acts (possibly pushing the earlier one out of the way or destroying it) etc.

(This is equivalent to Ryan1729's suggestion in the comments)

Conflict = wait

You could also choose to treat a conflict as "no move". The robots detect that they cannot all execute their action this turn, and the conflicting robots wait a tick instead to see if they can continue executing next frame.

(This is equivalent to Zibelas's proposal to execute the conflicting moves, then rebound and undo them, politely saying "after you")

Here you're hoping that another robot not in conflict, or some other change in the map like a moving conveyor/cycling door, results in a new state next tick that can resolve the conflict for at least one of the robots, giving them a chance to recover and continue. If the player has not arranged things so that the conflict is recoverable in this way, then this becomes a deadlock, similar to the "obstacle" variant of the failure state approach described above.

As with the "right of way" approach, you can decide if the stalled robots re-try the same instruction on the next tick, or skip it and advance to the next instruction instead.

Fast forward

When there is a conflict, all conflicting robots immediately skip the conflicting instruction and try the next one. This might produce a new conflict, causing a subset of those robots to skip forward again.

You'd want to introduce a maximum skip depth, or detect when you've looped back around to the original conflict to prevent an infinite loop when trying to advance a single tick. If you exceed such a limit or discover such a loop, then you can fall back on any of the approaches above.

Stacking robots

When two or more robots enter the same space, they stack! You can use a rule like the "sub-step" approach to decide the order in which they stack and which robot ends up on the bottom/on top.

Just what a stack means, you can determine:

• Robots that get driven over are destroyed, and only the robot at the top of the stack remains to continue executing its program next tick.

• Stacked robots continue executing their programs, and can be carried along with robots under them if they stay still, or can drive off the stack to un-stack themselves if they move.

• Stacked robots' programs are paused until an outside force un-stacks them (like the robot at the base of the stack driving under a bridge or past a magnet)

• Stacked robots merge, making the robot at the bottom of the stack more powerful (eg. able to push heavier objects or resist being pushed because it's heavier)

  (The mobile puzzle game Trainyard implements a clever version of this that I'll avoid spoiling completely here. 😉)

Answer 2

I think you can solve such a problem by introducing simple priority rules or additional gameplay elements. You may see these as instances of suggestions by DMGregory, so I'm just building up additional ideas on top of his answer.

Collision as a failure, by design

Who goes first? Nobody.

When two robots attempt to move into the same cell, a race condition occurs, and this can lead to a collision. Games such as RGB Express integrate collisions in their mechanics: puzzles must be solved by entangling actor paths without causing car accidents. This aspect prevails when trying to solve puzzles with a perfect solution (i.e. minimum distance possible).

If your game implements this mechanic, the player will always know what happens when crossing paths and will be required to avoid these scenarios. As a consequence, you must design puzzles accordingly.

Edge cases: None (I can think of), since this can also be considered a safe fallback case.

Collision as a failure, with a loophole

Who goes first? Nobody, unless...

Before thinking about priority rules, we let players solve possible collisions on their own. Since robots are programmed by players, they could get access to a TryMove command (as opposed to the base Move):

• Move: moves robots towards a direction, without further checks
• TryMove: IF the next cell is going to be free next step THEN move there ELSE perform actions

Example: the same scenario described in your question, the top robot (T) moves with Move and the left one (L) with TryMove. T is going to move from (1,2) to (2,2) no matter what; L is smarter: it knows that it can't move to (2,2) right away, then it does something else.

Possible something elses:

• Pause execution for the current step, then continue from the current TryMove instruction (wait until the cell is free/untargeted next step)
• Pause and wait, but TryMove switches to Move (only one chance to avoid collisions)
• Pause and wait up to n steps, then:
  • Switch TryMove to Move as above
  • Declare failure and halt execution

Edge cases: Two or more robots with a TryMove command meet each other: they could all halt or crash into each other.

Crossroad priority

You could assume that robots perform commands provided by players, but have a certain degree of freedom when it comes to decision-making and conflict resolution. Their "firmware" may contain instructions to solve order execution when meeting other fellow robots along the path. These are similar to common driving rules that apply to drivers.

Who goes first? Major path first, minor path last.

If paths aren't totally arbitrary, and your levels feature well-defined pathways, robots moving along main routes are entitled to go first. Then, robots crossing roads or merging to the main routes shall give priority to others before moving or turning.

Edge cases: Robots may attempt to move against the flow. Two robots try to perform the same action one opposite to another.

Who goes first? Oncoming traffic first, emerging traffic last.

Similar to above, but priority goes to robots that didn't turn recently. Working with your example: if robot T turned around 5 cells from North before meeting robot L, which previously turned and moved for 10 more cells, then L goes first. This is because L was already travelling when it bumped into T.

Edge cases: If two robots previously moved for the same distance, this may cause a conflict (collision) or require a different fallback criterion.

Who goes first? Relative left/right first.

In such a case, priority must be given to robots coming from one's left or right side. In your example, T goes first if priority is given to left-coming traffic; L goes first otherwise.

Edge cases: Four robots simultaneously approach the same cell from the four directions.

Who goes first? Heavy first/last, light last/first.

If there're different types of robots, you can define priority based on their weight, size, role or any trait of choice. Heavy-duty machines may need to move first, or lightweight drones may have priority since they move faster and can disengage the crossroad first.

Edge cases: Two vehicles of the same type bump into each other: their priority can be determined by the next trait in the hierarchy, but for identical machines, priority may not be well-determined.

Priority flags

Who goes first? Y'all don't, I DO.

Players can mark certain units with a control flag which guarantees priority over any other robot. While priority flags are an added mechanic and a limited resource, they become useful when it comes to resolving conflicts amongst multiple robots:

• Three robots bump into each other from North, East and West
• Unit N is flagged for priority, while others aren't: N goes first
• Units E and W wait for N to move over, then resolve their mutual conflict by applying a different criterion

This is a variation of "Collision as a failure, with a loophole", but the game mechanic involved is a property rather than a different command for the robots.

Edge cases: A priority-flagged robot goes first, but its movement is effectively obstructed by the mere presence of another robot. Multiple priority-flagged robots are involved in the conflict.

---

Depending on your design needs, you may consider using one or more of the above solutions. They don't conflict with each other and can be also arranged in a hierarchy of criteria, where an always-safe fallback solution is reached when other measures have failed.