Strategies for Using Tile & Object Collision Together

Discussion in 'Programming' started by atmobeat, Aug 19, 2019.

  1. atmobeat

    atmobeat Member

    Joined:
    Feb 24, 2017
    Posts:
    45
    Greetings GameMakers! One problem I am starting to run into is that tutorials often only focus on one mechanic or system, and as soon as those systems interact new challenges get introduced. That's fine but I also don't want to reinvent any wheels so I'm coming here to see if any of the more experienced programmers out there have a strategy that works well for my problem. My game is a top-down zelda-like.

    I've got tile collision working on its own and object collision working on its own, but I need them working well together. The problem I have is that both collision scripts have some code for sliding/relocating the instance that can potentially move the calling instance to a slightly different location than it is trying to go. So it seems that the following situation could easily come up: (1) the player tries to move the character into a wall (call it location L1), (2) the object collision script says it's fine to move to L1 as there is no object there, (3) but the tile collision script does not and rather finds a nearby location (call it L2) to move the player to so that the instance slides along the wall for better feeling controls, (4) unfortunately, L2 is a location now overlapping an object so the object collision script now needs to find a new location L3. I think you can see that there is potential to get stuck in a loop here if the tile collision script keeps trying to slide/relocate the instance into another object and the object collision script keeps trying to move the instance back into the tile wall.

    Obviously, just feeding slide locations into the other script won't work perfectly. So is it better to combine the scripts into one script? Still, how would the checks work to avoid infinite loops with sliding whether in one script or two? Does including object collision checks within a tile collision script undermine the performance gains?

    Thanks for all help!
     
  2. the_dude_abides

    the_dude_abides Member

    Joined:
    Jun 23, 2016
    Posts:
    626
    Most people seem to do collision checks before allowing characters to move. From your description it sounds like you have instances overlapping obstacles already, as you talk of sliding / relocating etc. Is that a game play feature (for whatever reason) and you feel you must have it this way? because at first glance it seems like you've approached the collisions in the wrong way, and are being reactive rather than preventing them to begin with.

    Even if you had something like an enemy being knocked backwards, or some other action where you think you can't control the response, you ought to still be checking for collision before allowing any movement at all. And if collision is found you temper the response accordingly.

    The other thing I'm curious about, is that you have static obstacles like walls mentioned. Are all the objects static? because you could do that with an mp grid. It could be used for pathfinding, and for collision checks, and the latter wouldn't need any combination of results from tile / object checking. Instead you could see if the direction an instance is being moved in would put it in an occupied cell, and then respond to the situation from there. Treat it the same as the generally accepted way of doing collision checking, whilst keeping it more straightforward than having to combine two different results.

    Tiles are a graphical benefit, but not physical - so you may be thinking "I can't fill an mp grid with them". That isn't true: you could loop through the tiles and use mp_grid_add_rectangle to add them in. In my experience using grids for checking collisions isn't costly at all - even when the grid is huge. I currently use one that is 250,000 cells, and I'd imagine you wouldn't need anywhere near that many cells. It's the pathfinding that is the most expensive aspect of them. Filling in the grid can be relatively costly too, but if all your objects are static then that is a one time only cost.

    I could be wrong, but I'm fairly certain that, put to the test, looking up if a grid cell is occupied is cheaper than alternative collision checks, and tile collision checking. That's just compared to doing one of them, let alone having to do both types. Though this is based on the assumption that everything you want to check for collision is static.
     
  3. curato

    curato Member

    Joined:
    Jun 30, 2016
    Posts:
    415
    I personally like tiles you can set up different indexes that do different things like a wall that blocks everything or a pit where it blocks the player but bullets don't care or you can set one for damage like lava or something. I think the main issue is don't overlap and check before moving. Both types can work well at the same time. Basic check both and if either is no then don't move to that spot.
     
    atmobeat likes this.
  4. Ido-f

    Ido-f Member

    Joined:
    Feb 19, 2018
    Posts:
    125
    Good point.
    I think what I would do is, for the object collision script, only move the object if it won't collide with a tile in the new designated location. Maybe check several bounding-box-edge locations.
    That way, worse case scenario, the objects would overlap as long as there isn't a tile free zone to snap into.
    Not physically accurate, but I think that it would feel alright and not buggy.
     
    atmobeat likes this.
  5. atmobeat

    atmobeat Member

    Joined:
    Feb 24, 2017
    Posts:
    45
    I do collision checks before allowing characters to move, but nearly all collision tutorials move the character some amount even when a collision is found. The reason why is that you don't want to just stop the moving object when a collision is found. That won't result in pixel perfect movement. So you move the object as close as possible to the originally targeted location. That's what I'm talking about when I mention sliding/relocating. You aren't moving the object to the original location it was trying to go to, but you are finding a new location for it to go to. That is pretty standard in tutorials even though people don't call it relocation (that was probably a bad label on my part). Sliding is a more common phrase for collisions against wall objects or tiles.

    But you can't just use tiles in a real game. Enemies can't be tiles and many games don't let you just move through an enemy. So you need both tile collision and object collision. I agree that both types can work well at the same time but getting them to work correctly together is something nobody talks about in tutorials and it isn't trivial at all. "Check both and if either is no then don't move to that spot" will absolutely not work. For one, just because a collision is found doesn't mean I don't want my player object to just stand there. I'd like it to move as close as possible before stopping.

    No, my zelda-like has enemies that move around and cannot be moved through, so I need object collision as well. The grid idea isn't bad but for my game I'm looking for pixel-perfect and don't want to force the player and enemies to line up with a grid-like structure. I think a grid collision and movement system is great for certain kinds of games. I'd even like to use it someday on a turn-based game like Stoneshard and similar games.

    I think this is hinting at what I'm thinking I will have to do. For my object collision script, when the calling object finds that some collider object is already at its target location, it attempts to move one pixel closer on the x and y axis until it no longer can. What I could do here is just check each time I try to "inch" closer whether that location will collide with a tile.

    I could also do it the other way instead. So start with my tile collision script and just put some place_meeting collision checks before the calling instance is moved anywhere.

    This all sounds like a "merged strategy" where you have one script that does both tile and object collision checks. Is this the best way? Are there other ways? Again no tutorial I've seen includes both kinds. I remember @Ariak mentioning in his "On Slopes and Grids" tutorial (https://forum.yoyogames.com/index.p...lision-line-without-objects.4073/#post-290746) that he should update it with grid+object combined collisions (his grid collision is basically GMS1.4's version of GMS2's tile collisions). Here's the quote:

    Did he or anyone else ever do this? My search of the forum didn't return anything.

    I decided to upload a picture to show the problem. Suppose my game has slopes (this can happen with non-sloped walls too). Suppose my player object (the blue square) receives input from the player to move directly to the right to the target location marked by the green square with a 'T' in it. My tile collision script will see that there is a tile there and slide the player up the slope to the location with the purple square with an 'S' in it. But this new location collides with a bat enemy. Now I can do an object collision check here, but doing so will more than likely relocate my player to the nearest place not colliding with any of my "par_impassable" objects. From the picture, that will evidently be below the bat or below and to the right of the bat. That will put my player object back into a collision with the sloped tile. And on and on it will go, my object collision script fighting with my tile collision script.

    Now, obviously this problem is solvable. I'm just looking for some options and would love some particularly elegant solutions. When I see really good code, I see the beauty of it. Show me the beauty of object+tile collisions people!

    EDIT: my bad, I forgot some descriptive parts of the pic.

    MOD EDIT: FIVE posts merged. Please do NOT multi-post just to reply to multiple people. Use the multi-quote tool and reply to them all at once. ;)
     

    Attached Files:

    Last edited by a moderator: Aug 20, 2019
  6. the_dude_abides

    the_dude_abides Member

    Joined:
    Jun 23, 2016
    Posts:
    626
    I didn't consider curato' point that you may want objects to be "solid" for one thing and not another, but I would think whichever way you do it, it will have to be a hybrid of systems with many conditions depending on the object and it's response.

    - get point to consider move to
    - test for tile collision
    - test for static object collision (assuming those are not tiles anyway)
    - test for moving object collision
    - if the three tests above are clear: can move
    - if can't move: repeat tests on a pixel by pixel basis to see how far you can move (if at all) which requires all three again.....sounds costly

    I don't know if you can do slopes with tiles? Which, as this is top down, I assume you mean to be edges that are not straight horizontally, or vertically?

    Examples of tile collision I have seen generally seem to be along these lines:
    if moving down
    {
    if (y + height + down distance) > (tile.y - tile_height)
    {
    can't move
    }
    else
    {
    can move
    }
    etc
    So how would that deal with a sloped tile? It seems like it couldn't. That might require precise collision checking with an object.

    Another alternative would be to use physics objects, and build the world out of chunks. By doing it that way you could have shapes that don't conform to square / rectangular etc, and use an approximation of the standard way of collision checking - just with physics functions instead. Or actually just use physics full stop? If you're going to be building a world that has odd shapes in it, then that would seem to be a way that gets around checking all sorts of disparate elements like slopes / tile collisions / object collisions etc

    physics.png
    If the green areas were physics fixtures, then how many things would it cut out having to test manoeuvring around, and doing further collisions as well? enough to perhaps make physics the "cheaper" option?

    No tile collision, no object collision, no slope collision.....
     
    atmobeat likes this.
  7. atmobeat

    atmobeat Member

    Joined:
    Feb 24, 2017
    Posts:
    45
    Yep, this is basically what I'm trying to do. See the above link for Ariak's tutorial on doing nearly any kind of slope. It's for GSM1 and uses grids but once you understand it, you can convert it to GMS2 tiles. Testing for both kinds of collisions is almost working. For some reason, my player-character is sticking a bit to objects but sliding perfectly along tiles. Not sure why, since both kinds of collisions are handled nearly identically. I may post my code in here once I get things ironed out.

    EDIT: actually, I'm not sure why you would need different checks for static and moving objects. Objects are objects and when checking for any object it is at exactly one location when doing the check.
     
  8. the_dude_abides

    the_dude_abides Member

    Joined:
    Jun 23, 2016
    Posts:
    626
    You probably don't need a separate check. I'll admit I'm just theorising here, and could well be talking out of my derriere :)
     
    atmobeat likes this.
  9. curato

    curato Member

    Joined:
    Jun 30, 2016
    Posts:
    415
    A lot of the tutorials out there use !=0 to look for collisions assuming you only have the empty tile and one tile for collisions in it. They tend not to point out with any clarity that you can have more than one tile in your collision tile set and you can return that number and do anything you want with it.
     
    atmobeat likes this.
  10. the_dude_abides

    the_dude_abides Member

    Joined:
    Jun 23, 2016
    Posts:
    626
    I only briefly experimented with using tiles for collisions, but I found two problems with them. Baring in mind that my implementation / understanding is most likely flawed.....

    1) They have to be a factor of 2 in size (?) and I wanted pixel perfect accuracy
    2) Despite the functions for finding tiles / grid cells seeming to be the same (using keys like a ds map...?) the performance was better for grids. Though that may be because I'm still using GMS 1, but it could also be evidence of my bad programming :)

    As I'm only using the grid for collisions I haven't considered the effects of anything else. At this point I have little to offer to the topic, so will leave more experienced minds to it, but it's an interesting area to look at and experiment in.
     
  11. curato

    curato Member

    Joined:
    Jun 30, 2016
    Posts:
    415
    yeah GMS2 is where you want to be for tile collisions. If you get into them they don't have to be powers of two
     
  12. atmobeat

    atmobeat Member

    Joined:
    Feb 24, 2017
    Posts:
    45
    I completely agree. I use the different index values for a variety of things. Lava and water like you mention, but I also use them for different height levels of terrain. I use a single tile set with a bunch of tiles numbered to match their index value from 1 to whatever my max height level is. I'll have a layer for each height level and only put collision tile 1 with index 1 on height level 1. Then you can have the tile collision check relative to the height level the player is on. I've got my code working. It wasn't too difficult actually. I'll post it after I make sure it's the way I want it. I'll put my tile collision code up as well.
     
  13. atmobeat

    atmobeat Member

    Joined:
    Feb 24, 2017
    Posts:
    45
    Alright, here's the code. The found_tile_collision_at script functions like place_meeting except for tiles. I used Brenan Wayland's method here (see https://medium.com/@brenan.wayland/tile-collision-in-gamemaker-studio-2-2e761b795c3d). I like my move_and_collide script to take speed and direction so that it isn't tied to controls and is a bit more flexible. It isn't a common way of doing things so feel free to ask questions. It doesn't expend all of one axis's move and then go to the next axis. It will get around corners and it kind of has some push friction built-in. Let me know what you think.

    Code:
    /// @func    found_tile_collision_at(x, y)
    /// @param    {real}    x        Required: the x position to move the calling instance to
    /// @param    {real}    y        Required: the y position to move the calling instance to
    /// @return    {bool}            Returns true if a collision with a tile is found, false if not
    /// @desc    This function moves the calling instance to the given x/y location and checks
    /// @desc    for a collision with a tile from the given collision layer
    var _xTarget, _yTarget, _xStart, _yStart, _collisionFound;
    _xTarget = argument0;
    _yTarget = argument1;
    _collisionFound = false;
    // Save current position and temporarily move to the position we want to check just like place_meeting
    _xStart = x;
    _yStart = y;
    x = _xTarget;
    y = _yTarget;
    
    // Retrieve the correct collision tilemap layer and tilemap (this is relative to calling instance's z-value)
    // You can replace this stuff with whatever your collision layer is
    var _collisionLvl, _collisionLayer, _collisionTilemap;
    _collisionLvl = (z div CELL_SIZE) + 1;
    _collisionLayer = "lay_collision_lvl_" + string(_collisionLvl);
    _collisionTilemap = layer_tilemap_get_id(_collisionLayer);
    
    var _xPoints, _yPoints, _xPointsLength, _yPointsLength, i, j;
    // Initialize arrays containing all of the points along each axis that you want to check
    // I use an array here because it makes it easier to add additional points later if needed
    // One could even automate how many points are selected using a data structure that uses collision 
    // mask/sprite size to determine _xpoints and _ypoints
    _xPoints = [x,bbox_right,bbox_left];
    _yPoints = [y,bbox_top,bbox_bottom];
    _xPointsLength = array_length_1d(_xPoints);
    _yPointsLength = array_length_1d(_yPoints);
    //Iterate through points of possible contact, check if there's a tile there, double-break out if so
    for (i = 0; i < _xPointsLength; i++)
        {
            for (j = 0; j < _yPointsLength; j++)
                {
                    _collisionFound = (tilemap_get_at_pixel(_collisionTilemap,_xPoints[i],_yPoints[j]) == _collisionLvl);
                    if (_collisionFound) then break;
                }
            if (_collisionFound) then break;
        }
    
    //Return to the original position
    x = _xStart;
    y = _yStart;
    return _collisionFound;
    

    Code:
    /// @func    move_and_collide(speed, direction, colliderType)
    /// @param    {real} speed           Required: the distance the calling instance is going to move this frame
    /// @param    {real} direction       Required: the direction the calling instance is going to move this frame
    /// @param    {real} colliderType  Required: used for the object collision checks and will usually just be par_impassable
    /// @return   Nothing
    /// @desc    Handles all tile & object collision checks and movement for any object 
    
    var _moveSpeed, _moveDirection, _colliderType, _xComponent, _yComponent, _xSpeed, _ySpeed, _xTarget, _yTarget;
    _moveSpeed = argument0;
    _moveDirection = argument1;        // Could round to nearest 45 or 22.5 or whatever degrees if you wanted
    _colliderType = argument2;
    _xComponent = lengthdir_x(_moveSpeed, _moveDirection);
    _yComponent = lengthdir_y(_moveSpeed, _moveDirection);
    
    // Manage fractional movement so only integers enter into collision/movement
    unusedX += _xComponent;        // Add current step's movement to any previously saved decimal value
    unusedY += _yComponent;        // unusedX/Y need to be instance variables already created in calling instance
    _xSpeed = unusedX div 1;         // Get rid of the decimal part for integer-only movement/collision
    _ySpeed = unusedY div 1;
    unusedX -= _xSpeed;            // Unused variables now just store the remaining unused decimal move value
    unusedY -= _ySpeed;            // Declare unusedX/Y in whatever objects/parents will use this script
    
    // Where the calling instance is trying to move to
    _xTarget = x + _xSpeed;
    _yTarget = y + _ySpeed;
    
    // The following won't always work for high-speed collisions (HSC), so HSC check will eventually be needed
    if (!found_tile_collision_at(_xTarget, _yTarget) and !place_meeting(_xTarget, _yTarget, _colliderType))
        { 
            // No tile/object collision, so no need for all the stuff below, just move.
            x = _xTarget;
            y = _yTarget;
            exit; 
        }
        else
            {   // Tile or object collided with, so try to move as close as possible pixel by pixel
                var _remainingX, _remainingY, _incrementX, _incrementY, _skipX, _skipY;
                _remainingX = _xSpeed; 
                _remainingY = _ySpeed;
                _incrementX = sign(_xSpeed);
                _incrementY = sign(_ySpeed);
                _skipX = false;
                _skipY = false;
                do
                    {   // Increment x/y positions until no longer possible
                        // Try to "inch" forward along both axes
                        // Find the axes that cannot be inched-forward along
                        // Skip that axis for a loop iteration because abutting a tile or impassable object
                        // Skip for only one loop iteration because movement along one axis may free movement along other axis
                        _skipX = (found_tile_collision_at(x + _incrementX, y) or place_meeting(x + _incrementX, y, _colliderType));
                        _skipY = (found_tile_collision_at(x, y + _incrementY) or place_meeting(x, y + _incrementY, _colliderType));
                        if (_skipX and _skipY) then break; //Abutting something along both axes, can't move at all in direction
                        if (!_skipX and !_skipY)
                            {    // Collider is    diagonal, check if immediately diagonal. If so prefer movement in direction of most movement
                                if (found_tile_collision_at(x + _incrementX, y + _incrementY) or place_meeting(x + _incrementX, y + _incrementY, _colliderType))
                                    then if (abs(_remainingX) >= abs(_remainingY)) then _skipY = true;
                                        else _skipX = true;
                            }
    
                        // Inch closer to tile or object unless skipping that axis this loop-iteration
                        // Also, skipping x-axis while unable to move anymore along y-axis (remaininY = 0)
                        // means there's no prospect for moving on x-axis anymore either. Same for y-axis.
                        if (!_skipX) 
                               {
                                    x += _incrementX;
                                    if (_remainingX != 0) then _remainingX -= _incrementX;
                               }
                                else if (_remainingY == 0) then _incrementX = 0;
                        if (!_skipY)
                               {
                                  y += _incrementY;
                                    if (_remainingY != 0) then _remainingY -= _incrementY;
                               }
                                else if (_remainingX == 0) then _incrementY = 0;
                        // If no more unused movement, stop trying to inch along that axis (increment = 0)
                        if (_remainingX == 0) then _incrementX = 0;
                        if (_remainingY == 0) then _incrementY = 0;
                       
                        _skipX = false;
                        _skipY = false;
                    }    until (_incrementX = 0 and _incrementY = 0);        // Break loop when not inching anywhere
            }
    
     
    the_dude_abides likes this.

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice