Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (107)
games submitted by our members
Games in WIP (536)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Collision detection in several directions (2D game)  (Read 2203 times)
0 Members and 1 Guest are viewing this topic.
Offline johanbrook

Junior Newbie





« Posted 2012-04-18 23:32:18 »

Hi! I've got some issues with collision detection in a game me and a couple of other guys are working on.

It's a 2D game where you move a player around in a world filled with other collidable objects (enemies, walls, etc.). The entities (subclasses of CollidableObject) should collide with each other. I'm using the Java class Rectangle for the objects' collision boxes.

Rectangle has two handy methods I'm using below: intersects and outcode. I'm using outcode when checking in which direction another given collidable object is, in order to block that direction.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
/**
 * Check whether this object is colliding with another CollidableObject.
 *
 * The objects are colliding if their collision boxes intersect.
 *
 * @param obj The specified CollidableObject
 * @return True if the objects are colliding, false otherwise
 */

public boolean isColliding(CollidableObject obj){
   
   return this.collisionBox.intersects(obj.getCollisionBox());
}

public Direction getCollisionDirection(CollidableObject obj) {      
   int code = this.collisionBox.outcode(obj.getCollisionBox().getLocation());      
       Direction d = Direction.ORIGIN;
     
       boolean top = false, bottom = false, right = false, left = false;
     
       if((code & Rectangle.OUT_TOP) == Rectangle.OUT_TOP)
           top = true;
       if((code & Rectangle.OUT_RIGHT) == Rectangle.OUT_RIGHT)
           right = true;
       if((code & Rectangle.OUT_LEFT) == Rectangle.OUT_LEFT)
           left = true;
       if((code & Rectangle.OUT_BOTTOM) == Rectangle.OUT_BOTTOM)
           bottom = true;
     
       if(top && left)
          d = Direction.NORTH_WEST;
       else if(top && right)
          d = Direction.NORTH_EAST;
       else if(top)
          d = Direction.NORTH;
       else if(left && bottom)
          d = Direction.SOUTH_WEST;
       else if(right && bottom)
          d = Direction.SOUTH_EAST;
       else if(left)
          d = Direction.WEST;
       else if(right)
          d = Direction.EAST;
       else if(bottom)
          d = Direction.SOUTH;
     
   return d;
}


Below is the relevant code in the main game loop. entities is a List<Entity> with all the entities in the game.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
/**
* Updates the game model.
* @param dt The time since the last update.
*/

public void update(double dt) {

   moveEntities(dt);
}

private void moveEntities(double dt) {
   for(Entity t : this.entities) {
         
      checkCollisions(t);
      t.move(dt);
   }
}


private void checkCollisions(Entity t) {
   
   for(Entity w : this.entities) {
     
      // This baby is in need of a grave refactor :)
     
      boolean stop = false;
     
      if(t != w && t.isColliding(w)) {
         
         Direction currentDirection = t.getDirection();            
         Direction blockedDirection = t.getCollisionDirection(w);

         if(t != w && t instanceof Player){
            System.out.println("-----\nPlayer direction: "+currentDirection);
            System.out.println("Collision direction: "+blockedDirection);
           
            int c = t.getCode(w);
           
            System.out.println("CODE: "+c);
            System.out.println("Top: "+ ((c & Rectangle.OUT_TOP) == Rectangle.OUT_TOP));
            System.out.println("Bottom: "+ ((c & Rectangle.OUT_BOTTOM) == Rectangle.OUT_BOTTOM));
            System.out.println("Left: "+ ((c & Rectangle.OUT_LEFT) == Rectangle.OUT_LEFT));
            System.out.println("Right: "+ ((c & Rectangle.OUT_RIGHT) == Rectangle.OUT_RIGHT));
         }
         
         System.out.println("----------\n"+t);
         System.out.println(w+"\n------------");
                       
         if( (blockedDirection == Direction.NORTH_WEST ||
             blockedDirection == Direction.WEST)
               && (currentDirection == Direction.WEST ||
                  currentDirection == Direction.NORTH_WEST ||
                  currentDirection == Direction.NORTH)) {
           
            stop = true;
         }
         
         if( (blockedDirection == Direction.NORTH_EAST ||
             blockedDirection == Direction.EAST)
               && (currentDirection == Direction.EAST ||
                  currentDirection == Direction.NORTH_EAST ||
                  currentDirection == Direction.NORTH) ){
                 
            stop = true;
         }
         
         if( (blockedDirection == Direction.SOUTH_WEST ||
                blockedDirection == Direction.WEST)
                  && (currentDirection == Direction.WEST ||
                     currentDirection == Direction.SOUTH_WEST ||
                     currentDirection == Direction.SOUTH) ){
           
           
            stop = true;
         }
         
         if( (blockedDirection == Direction.SOUTH_EAST ||
                blockedDirection == Direction.EAST)
                  && (currentDirection == Direction.EAST ||
                     currentDirection == Direction.SOUTH_EAST ||
                     currentDirection == Direction.SOUTH)){
                     
            stop = true;
         }
         
         if(blockedDirection == currentDirection){
            stop = true;
         }
           
         
         if(stop)
            t.stop();
      }
   }
}


Direction is an enum with the eight directions (N, S, E, W, NE, NW, SE, SW).

The problem: it's only working in some directions. If the player moves to another object from north or west, collisions aren't working. I've debugged the code, and it indeed does run through the code above. The printouts are showing legit results, but still the if blocks aren't catching the correct direction.

I can't for my life figure out why it's only north and west. My unit tests are (supposedly) testing this (green).

I'd deeply appreciate any assistance. The project code is located in a repo at GitHub: https://github.com/johanbrook/medioqre/

Thanks!
Offline philfrei
« Reply #1 - Posted 2012-04-19 00:11:46 »

Looks like a fun debugging project.  Smiley

Just a nutty idea, but North and West kind of suggest it might have something to do with the iteration order, if it proceeds in a direction like reading a book. Does checking against something that has already been collision-tested different in any way different from something yet to be tested?

For example, this might be the case if you only touch each possible combination of two objects once instead of twice, or if the second collision test between two objects somehow overwrites what happened in the first test, or doesn't register because of something that happened during the first test.

I'm assuming the direction constants are all correct. That would be an embarrassing place for a typo (something I've certainly done before).

Wish I had time to download the code. This is kind of neat. (I'm working on some code with many colliding objects, but am using a representation of the screen as the place where I update and test locations rather than testing each object against every other object.)

"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
Offline 65K
« Reply #2 - Posted 2012-04-19 07:02:31 »

Just from a quick glance: you never check for blockedDirections NORTH and SOUTH, if that does mean anything.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline johanbrook

Junior Newbie





« Reply #3 - Posted 2012-04-19 09:37:57 »

Quote
Just from a quick glance: you never check for blockedDirections NORTH and SOUTH, if that does mean anything.

You're correct, I am not, those checks are done with the block

1  
2  
3  
if(blockedDirection == currentDirection){
   stop = true;
}



Quote
Just a nutty idea, but North and West kind of suggest it might have something to do with the iteration order, if it proceeds in a direction like reading a book. Does checking against something that has already been collision-tested different in any way different from something yet to be tested?

For example, this might be the case if you only touch each possible combination of two objects once instead of twice, or if the second collision test between two objects somehow overwrites what happened in the first test, or doesn't register because of something that happened during the first test.

I'm suspecting something like this, but can't isolate the cases (except for the main problem that collisions don't work when the enemy is south or east of the player). I'd appreciate some advice on this.

Here's the printouts of the two objects (t and w) from line 45-46 in the code posted:

1  
2  
3  
4  
5  
6  
[x:-9:y:1] [w:20:h:20] [speed:30] [moving:false] [dir:EAST] [hp:100]
[x:0:y:0] [w:20:h:20] [speed:0] [moving:true] [dir:SOUTH_WEST] [hp:100]
------------
----------
[x:0:y:0] [w:20:h:20] [speed:0] [moving:true] [dir:SOUTH_WEST] [hp:100]
[x:-9:y:1] [w:20:h:20] [speed:30] [moving:false] [dir:EAST] [hp:100]


As you can see, the order och t and w is switched. Haven't analyzed this yet.

Below is a screenshot of what's happening.



(Larger: http://f.cl.ly/items/3g0A0U3T0B0p2Z0Z0L16/Sk%C3%A4rmavbild%202012-04-19%20kl.%2009.29.27.png)

The player is the leftmost guy (haven't made sprites for enemies yet). Check the console: the player's direction is EAST and the enemy is situated NORTH EAST of the player. The top: true, right: true printouts also verify this.

So why aren't they colliding? It's something with my if blocks that aren't correct. I've worked with this for so long now I'm going crazy: seems I can't think straight any longer Smiley

Quote
That would be an embarrassing place for a typo (something I've certainly done before).

It would indeed, but I certainly hope people here can help me find it Smiley
Offline johanbrook

Junior Newbie





« Reply #4 - Posted 2012-04-19 09:48:04 »

Worth noting is that switching order of the if blocks isn't changing anything (I thought stuff were overwriting other stuff).
Offline philfrei
« Reply #5 - Posted 2012-04-19 10:10:00 »

Just trying to think this through a bit:

In the code which checks for collisions, you iterate through each object, and test it against every other object, yes?

So, you check T, and find it is colliding with W, and T is set "stop = true". Anything else changed for the state of T at this time? Do you do anything to compensate the motion so that the collision state no longer occurs?

Later in the same collision iteration, you get to object W, and test it against every object, including T. However, T is now "stopped" or has had some other state changes, meaning the results could potentially be different this time the collision is tested. Does that "stop=true" value affect the result of this second test, from W's perspective?

I am assuming that the order of the tests is such that the first test will always be (or will tend to be) from the point of view of the object that is higher and to the left. (Y value is lower, X value is lower) And the second test (when the enemy POV was tested first) is the problem.

Only other thing I can think of is to limit the screen to two objects and set them no more than a turn or two away from collision and set a breakpoint at the top of the if blocks. Stepping through and examining state of both objects should reveal something!

"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
Offline philfrei
« Reply #6 - Posted 2012-04-19 10:23:45 »

1  
2  
3  
4  
5  
6  
7  
private void moveEntities(double dt) {
   for(Entity t : this.entities) {
         
      checkCollisions(t);
      t.move(dt);
   }
}


So, if the enemy is (t) and a collision is detected with the player, I notice that you move t in the very next line, before you have a chance to check the collision from the POV of the player. Does this move() method change the state of (t) such that it causes the collision check to fail when the player becomes (t) and the enemy becomes (w)?

(I'm also wondering about t.stop() at the end of the collision check. Will this affect the second test?

When I did a brute force collision test like this in the past, I used two passes. In the first I marked every object in collision, and in the second iteration I resolved the collisions for all the marked objects. That kind of change to the logic might help.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
private void moveEntities(double dt) {
   for(Entity t : this.entities) {        
      checkCollisions(t);
   }

   for(Entity t : this.entities) {
      t.move(dt);
   }

}


"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
Offline johanbrook

Junior Newbie





« Reply #7 - Posted 2012-04-19 11:41:18 »

Thanks for the great replies.

Some more info: in the class Entity (inherits from CollidableObject) I have these instance variables below. In conjunction with them, here are relevant methods:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
private int movementSpeed;
private boolean isMoving;
private Direction direction;

/**
 * Move in a the set direction.
 *
 * @param dt Delta time
 * @pre isMoving() == true
 * @see setDirection()
 */

public void move(double dt) {
   // Upper left corner is origin
 
   if(this.isMoving){
      Point currPos = getPosition();
     
      int x = (int) (this.direction.getXRatio() * (double) this.movementSpeed * dt);      
      int y = (int) (this.direction.getYRatio() * (double) this.movementSpeed * dt);
               
      this.setPosition(currPos.x + x, currPos.y + y);
      EventBus.INSTANCE.publish(new Event(Property.DID_MOVE, this));
   }
}

/**
 * Let the entity stop.
 *
 */

public void stop() {
   this.isMoving = false;
   
   EventBus.INSTANCE.publish(new Event(Property.DID_STOP, this));
}


/**
 * Let the entity start moving.
 *
 */

public void start() {
   this.isMoving = true;      
}

/**
 * Set a direction of the entity.
 *
 * Note: Will only set a new direction if <code>dir</code>
 * differs from the current direction.
 *
 * @param dir The new direction
 * @pre getDirection() != dir
 */

public void setDirection(Direction dir) {
   
   if (this.direction != dir) {
      this.direction = dir;
      EventBus.INSTANCE.publish(new Event(Property.CHANGED_DIRECTION, this));
   }
}


As you can see, move() ONLY actually moves an object IF the isMoving boolean is true, which is handled with start() and stop(). Apart from that, no other methods actually change the state of the object.

I get your reasoning about the iterations, and it's indeed something in there. It wouldn't surprise me if I've got some of the iteration logic wrong. Your suggestion regarding separating the collision checks and the actual movement method is clever, will investigate.

In my head, I've seen the t variable as the player, and w as the opponent. But even if we think the other way around (= t is enemy, w is player) issues shouldn't arise, since I'm not changing anything related to the OTHER object in each iteration. I.e., I'm only manipulating t in each iteration, and not its opponent (may it be a player or an enemy).

I've reduced the test case to only check for collisions with the isColliding() method, and that indeed works as intended.

What bugs me is the special cases: why no collisions when the player is approaching an enemy from west and north?

Have a look at this scenario:


(Large: http://f.cl.ly/items/0P182k3W3n2e1g1z1F3w/Sk%C3%A4rmavbild%202012-04-19%20kl.%2011.37.06.png).

The player is REALLY close to the (only) enemy, and the "Collision direction" is set to NORTH, which would cause all my direction checks to fail, and stop would be set to false.
Offline philfrei
« Reply #8 - Posted 2012-04-19 22:34:10 »

I see your point about the result of a collision being a "stop", and thus the two checks (player as t, enemy as t) should match state. But, just to double check, does the collision test use the current position or the "next" position of the entities? Entity state includes location, speed, direction, not just the boolean isMoving. If "next" positions are used for the check, and one of the entities is stopped (and the future move not made) then the second test will be using different state info from the first.

How well do the rectangles and the graphics for the object line up? For example, if the graphic is printed evenly around a center point, and the rectangle extends east and south from the center point? Or, if the player is centered and the enemies are drawn from the corner position? (Just a double check for a common overlook.)

Another ideas for troubleshooting:
 - reverse the order of occurrence in the entities array, and see if this changes anything.

But I still think setting a breakpoint for the start of the collision testing would be best, and step debugging. For a breakpoint, you can sometimes write a conditional that will only execute when conditions are optimal, and break on that. I think you want to verify that the results of intersects() and outcode() are what you think they are.

Duh! You can do this (and easily step debug): make a unit test of checkCollisions(), and feed it isolated cases that test various locations.

e.g.,

1  
2  
3  
4  
5  
6  
7  
8  
9  
    Entity enemy = new Entity(); // then set the location
   Entity[] entities = { enemy };  // or whatever is needed to load entities with the single enemy object
   Player p = new Player(); //  then set the location
   checkCollisions(p);

    p.setLocation(); // or whatever is needed to put in a new location
   checkCollisions(p);

    // and repeat for all the test cases



"Greetings my friends! We are all interested in the future, for that is where you and I are going to spend the rest of our lives!" -- The Amazing Criswell
Offline johanbrook

Junior Newbie





« Reply #9 - Posted 2012-04-21 21:20:21 »

Hi again, my sincerest thanks for your suggestions. I've actually solved the problem now!

It was Rectangle's outcode which used "incorrect" comparisons in order to return an integer constant for the position. I wrote an almost exact implementation in my super object class, which corrected the issues described. "Never trust other's code", eh?

It took days of debugging Smiley Thanks!

The code:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
public int getLocationOfPoint(int x, int y) {
   int out = 0;
   if (this.collisionBox.width <= 0) {
       out = LEFT | RIGHT;
   } else if (x < this.collisionBox.x) {
       out |= LEFT;
   } else if (x > this.collisionBox.x) {
       out |= RIGHT;
   }
   if (this.collisionBox.height <= 0) {
       out |= TOP | BOTTOM;
   } else if (y < this.collisionBox.y) {
       out |= TOP;
   } else if (y > this.collisionBox.y) {
       out |= BOTTOM;
   }
   return out;
}
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

CogWheelz (15 views)
2014-07-30 21:08:39

Riven (21 views)
2014-07-29 18:09:19

Riven (14 views)
2014-07-29 18:08:52

Dwinin (12 views)
2014-07-29 10:59:34

E.R. Fleming (32 views)
2014-07-29 03:07:13

E.R. Fleming (12 views)
2014-07-29 03:06:25

pw (42 views)
2014-07-24 01:59:36

Riven (42 views)
2014-07-23 21:16:32

Riven (30 views)
2014-07-23 21:07:15

Riven (31 views)
2014-07-23 20:56:16
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!