Collisions in grid-based movement

mmmestari

Member
Hi!

I'm working on a grid-based game, in which certain objects in the game (such as the player and the enemies) move at the same time from one square to another. This is very much like it is in games like Crypt of the NecroDancer.

I have problems with how I should code collisions.

I first tried something like this. In this code, I tell the player to move one square right, if there is not an object already there that causes a collision.

GML:
if (key_right and CanMove = true)
{

rightspeed = 32;

var _instL = instance_place(x + 32, y, o_ColCheck);
if (instance_exists(_instR))
{
if (_instR.vCollision = true)
{rightspeed = 0};
}
}
Where o_ColCheck is the parent for every object that has a value for vCollision, and CanMove is the variable which checks whether sufficient time has elapsed since the last executed movement.

However, there are apparent problems with this approach. For instance, if two objects are trying to move to the same square, I would like to tell them both to stay where they are, even though there is not anything in the square they are trying to move to at that moment. Also, if I have an enemy following e.g. the player, the enemy does not move to the square the player is in, even if the player is leaving the square at the same time.

If someone could give me some direction, or link me some examples of how something like this has been done in prior projects, I'd be most grateful.
 

GMWolf

aka fel666
However, there are apparent problems with this approach. For instance, if two objects are trying to move to the same square, I would like to tell them both to stay where they are,
This is a slightly tricky one.

I would split the problem into three phases.
First every instance decides where they are going to move to next.
Then, every instance checks if another instance wants to move to the same grid square as them.
Finally, move, but only if no one else shared the same destination.


For step two, you could either have a double for loop (every instance loops over every other instance to check their destination), or use a grid that stores who wants to move to each cell, etc.
 

Yal

🍋 *lemon noises*
GMC Elder
One option that would help communicate this to the player (which is important!) would be to only check for CURRENT blockades, then "reserve" the target cell with a special target object. Halfway through the movement step, all moving objects check if there's more than one reservation in their target cell, and if so, they cancel their movement (bouncing back the way they came), potentially with additional effects like particles to indicate the collision, the player taking damage if they tried moving into an enemy, etc.
(To aid in these special check, you need to give the reservations a reference to the id of the thing that tries to move, then you can access object_index and so on)

This approach only really works if all movement happens at once at discrete steps, but that's how it works in Crypt of the Necrodancer, right?
 

mmmestari

Member
Thank you for your answers.

I think that some kind of a loop is needed. I thought about the "reservation method", but I struggled with the fact that whether a square is reserved for, say, the player, is potentially relevant for all objects. And how it is relevant for all objects is itself also potentially relevant for all objects etc...
 

Yal

🍋 *lemon noises*
GMC Elder
If you want to know where the player is heading, you could always have the player store that coordinate in global variables whenever they create a reservation?
 

mmmestari

Member
I'm still struggling to make sense of how I could deal with situations like this one. I want that in situation like this nobody moves, because the enemies collide, do not move, and therefore the lower enemy blocks the player. However, without the upper enemy, I would like for both the lower enemy and the player to move.

illustration.png
 

GMWolf

aka fel666
I'm still struggling to make sense of how I could deal with situations like this one. I want that in situation like this nobody moves, because the enemies collide, do not move, and therefore the lower enemy blocks the player. However, without the upper enemy, I would like for both the lower enemy and the player to move.

View attachment 37299
A simple method is to do what I outlined above, but repeat step 2 in a loop until no more changes need to be made.
 

mmmestari

Member
Okay, I've tried to learn "for" loops and some other stuff. I've just started with GameMaker, so I'm still a little bit confused about everything.

At the moment I'm trying something like this. It doesn't exactly work yet, but could you perhaps tell me whether I'm at the right track?

xTo and yTo are the destinations of each instance that are set prior to this code.

I'm especially uncertain about the way I use instance_id here.

GML:
var i = 0;
var _i = 0;
for (i = 0; i < instance_count; i += 1;)
   {
for (_i = 0; _i < instance_count; _i += 1;)
   {
   if ((instance_id[i].xTo = instance_id[_i].xTo) and (instance_id[i].yTo = instance_id[_i].yTo))
 
   {instance_id[i].xTo = instance_id[i].x;
    instance_id[i].yTo = instance_id[i].y;
    instance_id[_i].xTo =  instance_id[_i].x;
    instance_id[_i].yTo =  instance_id[_i].y;}
   }
   }
 

Nidoking

Member
You definitely want to use a with loop for that, not a for loop, at least for iterating over all of the instances.

Thinking about how I'd do this, I'd probably set up some kind of destination grid where each instance can place itself where it wants to move without affecting the actual room. You'd check that grid when each one tries to move, and if something is on the destination space, you'll have the stored id of that instance so you can see whether it, too will move. It seems like you'd also need some way to prevent infinite loops, but that's as much thought as I really plan to put into it right now.
 

GMWolf

aka fel666
Okay, I've tried to learn "for" loops and some other stuff. I've just started with GameMaker, so I'm still a little bit confused about everything.

At the moment I'm trying something like this. It doesn't exactly work yet, but could you perhaps tell me whether I'm at the right track?

xTo and yTo are the destinations of each instance that are set prior to this code.

I'm especially uncertain about the way I use instance_id here.

GML:
var i = 0;
var _i = 0;
for (i = 0; i < instance_count; i += 1;)
   {
for (_i = 0; _i < instance_count; _i += 1;)
   {
   if ((instance_id[i].xTo = instance_id[_i].xTo) and (instance_id[i].yTo = instance_id[_i].yTo))

   {instance_id[i].xTo = instance_id[i].x;
    instance_id[i].yTo = instance_id[i].y;
    instance_id[_i].xTo =  instance_id[_i].x;
    instance_id[_i].yTo =  instance_id[_i].y;}
   }
   }
It looks quite close to me.
Notice that i and _i could be the same, but you dont want to check an instance against itself. The fix here is to use an if statement to skip over any case where i == _i using 'continue'.
(You can also change the loops so _i starts counting from i + 1. You will iterate over every pair only once that way)

Currently Your loop will loop over every instance, even if they dont have the right type (not every instance is a piece on the board that can move and has variables xTo yTo).
Look into using instance_number and instance_find to loop only over instances of a certain object.
Alternatively you can use the 'with' statement, although it gets a little messy when nesting with statements because of how 'other' works.

Another modification Would be to not immediately change the xto and yto Variables. Maybe use a temporary "isBlocked" variable during the loop before going in and resetting xTo and yTo for every instance with 'isBlocked' true.
The reason is that otherwise you will not be able to detect when three objects are moving into the same spot.


You are doing great for someone just staring with GM! And it sounds to me like you are already making use of the manual (probably the most important skill). Keep at it!
 

jerob1995

Member
I wonder if, rather than looping through different scenarios - just move each instance in the step event as normal, but if it collides with another instance then move both it and the conflicting instance to their last position. If the conflicting instance hadn't yet moved it would stay where it is (since that is its last position). Otherwise both would return to their previous positions. This is untested but the logic sounds like it might work.
 

mmmestari

Member
It looks quite close to me.
Notice that i and _i could be the same, but you dont want to check an instance against itself. The fix here is to use an if statement to skip over any case where i == _i using 'continue'.
(You can also change the loops so _i starts counting from i + 1. You will iterate over every pair only once that way)

Currently Your loop will loop over every instance, even if they dont have the right type (not every instance is a piece on the board that can move and has variables xTo yTo).
Look into using instance_number and instance_find to loop only over instances of a certain object.
Alternatively you can use the 'with' statement, although it gets a little messy when nesting with statements because of how 'other' works.

Another modification Would be to not immediately change the xto and yto Variables. Maybe use a temporary "isBlocked" variable during the loop before going in and resetting xTo and yTo for every instance with 'isBlocked' true.
The reason is that otherwise you will not be able to detect when three objects are moving into the same spot.


You are doing great for someone just staring with GM! And it sounds to me like you are already making use of the manual (probably the most important skill). Keep at it!
Thank you very much for both the advice and the encouraging words :)

I'll get back on the grind later today.
 
Last edited:

Nidoking

Member
I wonder if, rather than looping through different scenarios - just move each instance in the step event as normal, but if it collides with another instance then move both it and the conflicting instance to their last position. If the conflicting instance hadn't yet moved it would stay where it is (since that is its last position). Otherwise both would return to their previous positions. This is untested but the logic sounds like it might work.
What if another instance has moved into the place where one of those instances started by the time it moves back? There has to be some amount of iteration, because there are interdependencies between instances. The question I'd be asking is whether it's easier to determine that by moving everything first, or by having each instance search around itself to determine what other instances might affect it and independently working out all of that logic. You might use two different events for that, just to simplify things. Begin Step, every instance works out where it should go, if anywhere, and then Step, it goes there.
 

Umaro

Member
I think you're going about it the wrong way. This is basically a turn-based roguelike system, and even if it looks like everything's moving at once, it is not. The way I'd do it is to make an array or a list with all the enemies, order them by distance to the player, then move them one by one from closest to farthest (so they won't stop if the enemy in front of them has just moved). Make their movement instant so each enemy knows where the previous enemy has moved, and add checks to see if they're going to walk into another enemy, then prevent their movement or make them move somewhere else.

Edit: Something like this should be the result (obviously pathfinding can be tweaked until it's as good as you want it to be).

 
Last edited:
Top