# Establishing if a tile is available to move into

I'm working on a grid-based game as a hobby project. Think of an ANSI game like ZZT. The grid is represented by a two-dimensional array of objects which contain both the UI element which takes care of displaying the sprite image and also the data accompanying whatever is in that position on the grid. I'm having trouble working out the mechanics of elements on the game grid determining whether they are able to move into a neighbouring cell.

Determining whether there is something in any given grid position is straightforward, as each instance of the class representing a cell on the grid has a property representing the sprite in occupation of the cell. Checking if this property is nil works fine in establishing if something static is there, but it becomes problematic if there are many objects moving from one grid position to another. The problems I'm having are:

1. Objects in grid cells will attempt to push objects out of their destination cell; this is intended behaviour, so that the player or NPCs can move objects around. The object which is pushed will check if it is capable of moving in that direction, and if the cell into which it is being asked to move already contains another object. If it does, it will attempt to push that object, and so on and so on until an object either agrees to be pushed (into an empty spot), or refuses (because there is nowhere for it to move or because it cannot move in that direction). The return values for the attempt to push will then cascade back up to the originating object and the sprites all move (or not). This causes a problem, however, if there are several sprites moving in a straight line in the same direction. Rather than all moving forwards together (which they should), the last object in the line thinks that the next cell is occupied so tries to push the object in that cell, which is unnecessary, because that object will be moving anyway. This causes the objects to spread out with gaps between them, which is abnormal.
2. Due to this, I considered having the objects check if the destination cell is occupied, and if so, check if the object in that cell will be moving out, and if anything else will be moving in. However, I'm concerned this could result in a condition where several objects may refuse to move because of each other's presence.

I have considered looking at source code for a similar game, but I don't want to copy another implementation, rather I'm looking for guidance on how I can solve the problem. Thanks in advance!

• One possible solution I'm considering is altering how the actors are associated with the grid elements. Only one actor can occupy any given cell, which is why I added a property to the cell to contain the pointer to the actor object. But if this was an array, then actors could add themselves to the array knowing another actor will be moving out in the same tick, without overwriting the pointer to that actor. ETA - actually the cell's actor property is a weak reference anyway, so I might just need to check if the actor occupying the destination cell is moving in the same direction... – mashers Jan 31 '18 at 21:22

## 2 Answers

It looks like you can resolve this like so:

1. For each dynamic object in your grid....

2. If that dynamic object has already had its movement updated this cycle, continue to the next one

(this is important because we have some out-of-order updates coming)

3. If that dynamic object needs its movement updated, check to see if the cell it's moving into is free

• if so, move it, and mark it as having already updated its movement this cycle
4. If the cell it's moving into is not free, check if it contains a dynamic object whose movement has not yet been updated

• if so, recursively resolve its movement starting from to step 3
5. If the cell it's moving into is not free and does not contain a dynamic object that might yet move, check if it's a pushable object

• if so, recursively resolve the push starting from step 3
6. If we still haven't been able to move the object, we've exhausted our options, and the object cannot move this cycle

• mark it as having already updated its movement this cycle, and continue to the next...

So for your example of a line of objects all moving in the same direction, this scheme will lead us to recurse all the way down to the lead object, move it (if able), then move its first follower, and so on, back until we reach the object we started with in the chain. Because we skipped around the normal iteration order to move the leader first, we mark it as done for this cycle, so that we don't accidentally move it a second time when we resume our normal iteration.

If you manage to recurse all the way back to the same object again, then you have a tautology "this object can move, if the chain of objects ahead of it can move, if this object can move." So all moves in that loop can complete successfully, you'll just need to use a little caution executing them to make sure you don't overwrite anybody since the moves no longer have a "front-to-back" order but happen simultaneously.

This basic version remains sensitive to the order in which your original iteration over the dynamic objects runs: if two objects are positioned like so:

 A--->[  ]
^
|
B


Then the result depends on whether A updates first, then B pushes it, or B updates first, then is pushed by A:

A first           B first
A
[ B ]              [ A ] B


One common strategy to approach this is to split your movement resolution into two phases: in the first phase, every object tries to reserve the cell it wants to move into - propagating pushes as above, but not moving anything yet, just noting an intention to move. If any cells get reserved more than once, record a list of all the objects trying to reserve that cell. Then proceed with all uncontested moves.

Next you move on to your lists of contested moves, and check if they're still contested (an object might have gotten pushed so it no longer wants to enter a contested cell). Perform any moves that are now uncontested, then check this lists again...

Once you have only contested moves left, perform an order-independent resolution on each of those contested lists (eg. "nobody gets to move" or "a randomly selected object gets to move" or "the object with the highest speed value gets to move, with ties broken by...." are all examples of resolution rules you could use).

Now at last you can move everything. Just watch out for cyclic dependencies and make sure you don't chase an infinite loop! ;)

• Thank you @DMGregory, this is an excellent explanation! I will need to ready through a few times to make sure I fully understand everything before trying to implement changes. Just a follow-up question, would you consider it sufficient to have a boolean property on each movable object to determine whether it has updated this cycle? This would then involve iterating over them and clearing these flags at the beginning of each cycle... – mashers Feb 1 '18 at 13:14
• ... so perhaps the cycles should be numbered, and after updating each entity stores its last updated cycle number, so if the current cycle number is higher, it knows it needs to update. – mashers Feb 1 '18 at 13:14
• Both strategies will work. If using numbers, just be cautious if the value can wrap-around over very very long games. You can also store this info in a parallel array if you want to avoid cluttering your object members. One other way to do it is, if you're using reservations, the reservation field can double as the updated flag: if it's still null/default, the object hasn't had its first update pass yet; if it's non-defaultl and not equal to the object's position, it's had its first update but not the second; otherwise it's had both updates. – DMGregory Feb 1 '18 at 14:06
• Thank you @DMGregory. I will read through your post again and let it all sink in before forking and trying to implement these changes. – mashers Feb 1 '18 at 19:37

I want to thank @DMGregory again for the great explanation in his answer above. I'm leaving his answer as the accepted answer, but wanted to also post a snippet of code which I wrote using his explanation as a guide.

This is in Objective-C, and quite a specific situation. Each Actor object can have idle Responses added to it which are carried out one at a time per tick. They can also emit Stimulus objects which are detected by other Actors and elicit further Responses from them. In this way, the various Actors can be configured to interact with each other (and the player) in ways which do not need to be pre-programmed.

The example below interacts with this system when checking if the Actor which is blocking the way will move. Its idleActions are checked to see if its Response for the current tick will result in it moving, and if so, whether it is able to do so. I'm using Objective-C block-based coding for this, and it's so deeply embedded in my (now very large) project that there was no way I was changing it all to get a return value from the block back to the main function. So I cheated by putting in the infinite loop, which is broken by the completion block when the return value is ready.

I hope this helps others who might be trying to solve the same problem, as long as it's not too specific a case to apply to others.

EDIT I've added code to the sample below to handle a deadlock situation where two Actors want to move to each other's positions on the grid (which is impossible in my case). In this situation, the one with the lowest UUID (and thus created first) will take priority and try to find a route around the other. This whole solution is possibly overkill for my needs, but it's been fascinating to see this puzzle through from start to finish. And here's gif showing the result of the below code in context. The two characters have not had their movements programmed beyond their start and end points. The path they have chosen, the re-routing, waiting for the other actor to wait, continuing the path and evaluating arrival is all handled dynamically.

- (BOOL)canMoveToGridElement:(GridElement*)gridElement direction:(GridDirection)direction {
self.moveTestGridElement = gridElement;

//Only move once per tick (reset by the GameController each tick)
if (self.hasMovedThisTick) {
return [self finishCanMoveToGridElementCanMove:NO];
}

//Prevent moving out of bounds (should never happen, but just in case)
if (!gridElement) {
return [self finishCanMoveToGridElementCanMove:NO];
}

//If the destination is emppty, move there
if (!gridElement.object) {
return [self finishCanMoveToGridElementCanMove:YES];
}

//If there's something in the destination which isn't an Actor, don't move there
if (![gridElement.object isKindOfClass:[Actor class]]) {
return [self finishCanMoveToGridElementCanMove:NO];
}

//Get the Actor which is blocking the way
Actor *blockingActor = (Actor*)gridElement.object;

//We're in a deadlock situation, where two Actors are adjacent and want to move to each other's position
if (blockingActor.moveTestGridElement == self.gridElement || self.moveTestGridElement == blockingActor.gridElement) {
//The Actor with the highest UUID (created most recently) takes priority and will try to re-route
if (self.UUID.integerValue < blockingActor.UUID.integerValue) {
GridDirection alternativeDirection = GridDirectionNone;

if (direction == GridDirectionUp || direction == GridDirectionDown) {
if ([self canMoveInDirection:GridDirectionLeft]) {
alternativeDirection = GridDirectionLeft;
}
else if ([self canMoveInDirection:GridDirectionRight]) {
alternativeDirection = GridDirectionRight;
}
}
else if (direction == GridDirectionLeft || direction == GridDirectionRight) {
if ([self canMoveInDirection:GridDirectionUp]) {
alternativeDirection = GridDirectionUp;
}
else if ([self canMoveInDirection:GridDirectionDown]) {
alternativeDirection = GridDirectionDown;
}
}

if (alternativeDirection != GridDirectionNone) {
blockingActor.waitForBlockingActorToMove = YES;
[self moveInDirection:alternativeDirection];
}

return [self finishCanMoveToGridElementCanMove:NO];
}

return [self finishCanMoveToGridElementCanMove:NO];
}

//If the blocking actor has idle actions pending
if (blockingActor.idleActions.count > 0) {
//Get the first Response in the blocking Actor's idle array
Response *firstResponse = blockingActor.idleActions.firstObject;

//If the first Response is of movement type
if ([firstResponse isKindOfClass:[ResponseMovement class]]) {
//Set by the blocking Actor's movement Response completion block
BOOL __block blockingActorDidMove;
//Keep the current thread in an infinite loop until the blocking Actor's movement completion block has finished
BOOL __block waitForBlockingActor = YES;

//Perform the blocking actor's movement Response
[firstResponse performWithCompletion:^(ResponseReturnCode returnCode) {
if (returnCode == ResponseReturnCodeFailure && firstResponse.breakResponse) {
Response *breakResponse = firstResponse.breakResponse;

[blockingActor clearIdleActions];

[breakResponse performWithCompletion:^(ResponseReturnCode returnCode) {
//Set flags for the main function
blockingActorDidMove = (returnCode == ResponseReturnCodeSuccess);
waitForBlockingActor = NO;
}];
}
else {
//Set flags for the main function
blockingActorDidMove = (returnCode == ResponseReturnCodeSuccess);// success;
waitForBlockingActor = NO;
}
}];

//Wait for the blocking Actor's completion block to finish
while (waitForBlockingActor) {

}

//If the blocking actor moved, we'll take its place
if (blockingActorDidMove) {
return [self finishCanMoveToGridElementCanMove:YES];
}
}
}

//If we've reached this point, the blocking actor either had no pending move-type idle action this tick, or was unable to move itself. Try to push it out of the way
if ([blockingActor pushInDirection:direction]) {
return [self finishCanMoveToGridElementCanMove:YES];
}

//Give up
return [self finishCanMoveToGridElementCanMove:NO];
}