Grid-based entity collision issues

Hi all
I’m attempting to implement collisions between multiple entities in a 2D top-down game and I’ve decided to use a grid for this purpose. The grid itself works correctly. The collision detection, well, it sort of works, and it’s something I’ve been scratching my head over. Here’s the code (I’m aware it’s probably quite a mess):

http://pastebin.java-gaming.org/4a0672552301d

What I’m not really understanding is that I’ll end up with results like this:

Yeah. They sorta… go into each other.
My understanding of detecting collisions is that all i’d have to do is find suitable entities, figure out the distances from their edges and if it is zero or less than their respective velocities then I’d either stop them from moving, OR slow them down in order to touch in the next tick. Is there a better way to do this? Or is there a better way to handle collisions in this manner?

Thanks.

For debug purposes, try adding a collision check after you have done all your movement code. If the unit doesn’t collide before moving, but collides after moving, throw an exception or something and you will know that you made an invalid move.

Sorry, I probably should’ve said: they go into each other like that and then stop. It’s like they’re sorta one step behind on collisions, if that makes sense.

Are you testing collision based on thier current position or thier position incremented by the thier velocity?
This usually happens when you are not accounting for the velocity.

It would be easier to show you guys the code… it can probably explain the issue better than I can because I don’t fully get it myself. I’m relatively new to anything except tile-based collisions.


public void doCollisionsForEntity(BaseEntity b) {
        calcIndexSet(b.x, b.y, b.width, b.height);
        testedWith.clear();

        for (int x = iSet.eOX; x <= iSet.eEX; x++) {
            if (x < 0) {
                continue;
            }

            for (int y = iSet.eOY; y <= iSet.eEY; y++) {
                if (y < 0) {
                    continue;
                }

                //System.out.println("x: " + x + ", y: " + y);
                if (grid[x][y].inUse) {
                    for (BaseEntity bEnt : grid[x][y].entlist) {
                        if (bEnt != b && !testedWith.contains(bEnt)) {
                            if (bEnt.x + bEnt.width <= b.x || b.x + b.width + b._xvel<= bEnt.x) {
                                continue;
                            }

                            if (bEnt.y + bEnt.height <= b.y || b.y + b.height + b._yvel <= bEnt.y) {
                                continue;
                            }

                            testedWith.add(bEnt);

                            //System.out.println("Testing " + b.targetName + " with: " + bEnt.targetName);
                            int _dR = (bEnt.x + bEnt._xvel - (b.x + b.width + b._xvel));
                            int _dL = (b.x + b._xvel - (bEnt.x + bEnt.width + bEnt._xvel));
                            int _dB = (bEnt.y - (b.y + b.height));
                            int _dT = (b.y - (bEnt.y + bEnt.height));

                            System.out.println(b.targetName + "&" + bEnt.targetName + " - l dist: " + _dL + ", r dist: " + _dR + ", t dist: " + _dT + ", b dist: " + _dB);

                            boolean _cR = ((_dR <= 0) && bEnt.x > b.x);
                            boolean _cL = ((_dL <= 0) && bEnt.x < b.x);
                            boolean _cB = (b._yvel > 0 && _dB <= b._yvel);
                            boolean _cT = (b._yvel < 0 && _dT >= b._yvel);

                            System.out.println(b.targetName + "&" + bEnt.targetName + " - cl: " + _cL + ", cR: " + _cR + ", cB: " + _cB + ", cT: " + _cT);

                            if (_cR) {
                                if (_dR < 0) {
                                    //b.x -= _dR;
                                    b._xvel = 0;
                                }
                            }

                            if (_cL) {
                                if (_dL < 0) {
                                    //b.x -= _dR;
                                    b._xvel = 0;
                                }
                            }
                            
                            if (_dR < b._xvel && b._xvel > 0 && _cR){
                                b._xvel = _dR;
                                System.out.println("new xvel (r): " + b._xvel);
                            }
                            
                            System.out.println((_dL > b._xvel) + ", " + (b._xvel < 0) + ", " + _cL);
                            
                            if (_dL > b._xvel && b._xvel < 0 && _cL){
                                System.out.println("gggg");
                                b._xvel = _dL;
                                System.out.println("new xvel (l): " + b._xvel);
                            }

                        }
                    }
                }
            }
        }
    }

You shouldn’t be assigning a velocity to reach the next entity, you should be snapping to the next entity when you’ve collided. So if you’re going to collide on the next collision pass, let yourself collide, then rebound so that entity1.x = entity2.x - entity1.width if you’re moving right or vice versa if you’re travelling left. This will make sure you’re not adjusting one entity’s velocity and then the other, only to be giving them twice as much velocity total and forcing themselves into each other. I’d say you should change velocity in as few places as possible, from friction (so you’ll be doing this ALWAYS), and then from acceleration (when a key is pressed). If you’re going to collide, make the entities not inside of each other and set v = 0. It’ll save you a lot of headaches, as it’ll mean adding explosion movements and things like that won’t suddenly be based on your collisions in the same frame and things of the sort.

Also, you should really use more descriptive variable names. I know that they’re collidedDirection and DistanceDirection, but it’s not very intuitive to everyone.

[quote]you should really use more descriptive variable names.
[/quote]
I absolutely agree. They were never going to make it into the final product, they were just there while I was slapping it together.

[quote]I’d say you should change velocity in as few places as possible, from friction (so you’ll be doing this ALWAYS), and then from acceleration (when a key is pressed). If you’re going to collide, make the entities not inside of each other and set v = 0
[/quote]
This makes a lot of sense. It’s great to get someone else’s input on this because as I said I’m not experienced in this. I’ll have a go at implementing your suggestions then I’ll share my code once it’s done.

Thank you for your help.

So, as per your suggestions, I’ve made some changes to the collision detection code. Largely it works much better, so thank you all for your help in that aspect - but I’ve got one more question. The action of an entity snapping to the respective edges of the entity that it’s colliding with, it shows a visible snapping effect, as if the entity still goes too far before being pushed ‘back’. Does anyone have any suggestions on how to prevent this? It’s what I was trying to achieve with my old solution.

Updated code:


public void doCollisionsForEntity(BaseEntity b) {
        calcIndexSet(b.x, b.y, b.width, b.height);
        testedWith.clear();

        for (int x = iSet.eOX; x <= iSet.eEX; x++) {
            if (x < 0) {
                continue;
            }

            for (int y = iSet.eOY; y <= iSet.eEY; y++) {
                if (y < 0) {
                    continue;
                }

                //System.out.println("x: " + x + ", y: " + y);
                if (grid[x][y].inUse) {
                    for (BaseEntity bEnt : grid[x][y].entlist) {
                        if (bEnt != b && !testedWith.contains(bEnt)) {
                            if (bEnt.x + bEnt.width <= b.x || b.x + b.width + b._xvel<= bEnt.x) {
                                continue;
                            }

                            if (bEnt.y + bEnt.height <= b.y || b.y + b.height + b._yvel <= bEnt.y) {
                                continue;
                            }

                            testedWith.add(bEnt);

                            //System.out.println("Testing " + b.targetName + " with: " + bEnt.targetName);
                            int distanceR = (bEnt.x - (b.x + b.width));
                            int distanceL = (b.x - (bEnt.x + bEnt.width));
                            int distanceB = (bEnt.y - (b.y + b.height));
                            int distanceT = (b.y - (bEnt.y + bEnt.height));

                            //System.out.println(b.targetName + "&" + bEnt.targetName + " - l dist: " + distanceL + ", r dist: " + distanceR + ", t dist: " + distanceT + ", b dist: " + distanceB);

                            boolean collidingR = ((distanceR <= 0) && bEnt.x > b.x);
                            boolean collidingL = ((distanceL <= 0) && bEnt.x < b.x);
                            boolean collidingB = ((distanceB <= 0) && bEnt.y > b.y);
                            boolean collidingT = ((distanceT <= 0) && bEnt.y < b.y);

                            //System.out.println(b.targetName + "&" + bEnt.targetName + " - cl: " + _cL + ", cR: " + _cR + ", cB: " + _cB + ", cT: " + _cT);
                                                        
                            if (collidingR && b._xvel > 0) {
                                b.x = bEnt.x - b.width;
                                b._xvel = 0;
                            }
                                                        
                            if (collidingL && b._xvel < 0) {
                                b.x = bEnt.x + bEnt.width;
                                b._xvel = 0;
                            }
                            
                            if (collidingT && b._yvel < 0) {
                                b.y = bEnt.y + bEnt.height;
                                b._yvel = 0;
                            }
                            
                            if (collidingB && b._yvel > 0) {
                                b.y = bEnt.y - b.height;
                                b._yvel = 0;
                            }
                        }
                    }
                }
            }
        }
    }

This is the code in my EntityManager class that actually handles the updating of positions, and the order in which the chain of logic is executed is as follows:


public void updateEntities() {
        if (entGrid == null) {
            return;
        }

        for (BaseEntity b : entityTree) {
            if (!b.dormant) {
                if (MapManager.onScreen(b.x, b.y, b.width, b.health) || b.neverIgnore) {
                    if (b.doesCollide) {
                        entGrid.doCollisionsForEntity(b);

                        //save TIME updating positions and grid indices!
                        if (b._xvel != 0 || b._yvel != 0) {
                            entGrid.removeEntity(b);
                            
                            b.x += b._xvel;
                            b.y += b._yvel;

                            entGrid.addEntity(b);
                        }
                    }
                }
            }
        }
    }

So my question is: is there a way to prevent the visible snapping effects that this code produces?

Thank you for your help.

Make sure you do all of your rendering last so that your render matches what the game state is, otherwise you’ll be 1 frame behind.
Beyond this, make sure you’re checking that the object has ACTUALLY collided, not if it’s GOING to collide, otherwise that’ll be 1 more frame.