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 (535)
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 Avoidance  (Read 1064 times)
0 Members and 1 Guest are viewing this topic.
Offline Gjallar

JGO Coder


Medals: 13
Projects: 1


Follower of Nurgle


« Posted 2013-08-29 19:05:47 »

Now this might be a piece of cake to most of you, but it took me several attempts to create a satisfying result regarding this.
Since I didn't find much regarding Collision Avoidance on the internet, I thought I post my function here. For two reasons!

Reason number 1, I have a feeling I am overcomplicating this and it could be done with much fewer lines of code. I know .. I shouldn't
even worry about that because my function does work perfectly fine (it seems). But yeah, I'm still very curious. I commented the code
for easier readability, please take a look!

Reason number 2, if my approach to Collision Avoidance does get your seal of approval I thought this might help others that struggle with it, since I
didn't find much resources on that topic out there.

Thank you!

EDIT: The code is intented for a topdown 2D game in which you can move in all four directions (up, down, left, right).

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  
   public void move(float dx, float dy, Array<Entity> obstacles){
     
      setBodyPos(x + dx, y + dy);   // Set Body(Rectangle) to where it will be if dx/dy get applied
     updateBodyCenter();
     
      SortedIntList<Entity> overlappingObs = new SortedIntList<Entity>();
      float distX, distY;
      int distDirect;
     
      for(Entity obs : obstacles){   // Loop through all available Obstacles
 
         if(body.overlaps(obs.body)){   // Check if intersection with the Object is true
           obs.updateBodyCenter();
            distX = (centerX) - (obs.centerX);
            distY = (centerY) - (obs.centerY);
            distDirect = (int)(Math.pow(distX, 2) + Math.pow(distY, 2));   // Calculate the distance between this
                                                                 // Entity and the Obstacle
           int index = distDirect;
            boolean tryIndex = true;
           
            do{                                 // Do-While loop to avoid double indexes (Took me hours to find that error)
              if(overlappingObs.get(index) == null){  
                  overlappingObs.insert(index, obs);   // Add the intersecting Obstacles to a List
                 tryIndex = false;               // (Sorted from closest to farthest Obstacle)
              }
               else{
                  index++;
               }
            }while(tryIndex);
         }
      }
     
      Iterator<SortedIntList.Node<Entity>> iterator = overlappingObs.iterator();

      while (iterator.hasNext()) {   // Loop through the sorted intersecting Obstacles
        SortedIntList.Node<Entity> node = iterator.next();
         Entity obs = node.value;

         if(body.overlaps(obs.body)){
            float xOffset = 0, yOffset = 0;   // Calculate how much of the Obstacle's body intersects
             
            if(centerX > obs.centerX) xOffset = body.x - (obs.body.x + obs.body.width);
            if(centerX <= obs.centerX) xOffset = (body.x + body.width) - obs.body.x;
           
            if(centerY > obs.centerY) yOffset = body.y - (obs.body.y + obs.body.height);
            if(centerY <= obs.centerY) yOffset = (body.y + body.height) - obs.body.y;
           
            if(Math.abs(yOffset) > Math.abs(xOffset)){   // Substract the calculated offsets from the dx, dy values
              dx -= xOffset;
            }
            else if(Math.abs(xOffset) > Math.abs(yOffset)){
               dy -= yOffset;
            }
           
            setBodyPos(x + dx, y + dy);   // Update the Entity's body to be on the newly calculated position
           updateBodyCenter();
         }
      }

      x += dx;
      y += dy;
     
      overlappingObs.clear();
      overlappingObs = null;
      iterator = null;
   }
Offline Several Kilo-Bytes

Senior Member


Medals: 11



« Reply #1 - Posted 2013-08-29 19:46:18 »

Check if an object intersects before sorting. Why sort a hundred objects when all you need is usually one or zero?
Your distance equation can be simplified. Do not bother with abs because a positive or negative number square is always positive.
Do not bother with square root because it doesn't change the relative order of values.
Why do you use ints? Can't a float work as well?
Why sort at all? Am I missing something?
If you want to simplify offset distances, you can use center coordinates and half-widths and half-heights.
Offline Gjallar

JGO Coder


Medals: 13
Projects: 1


Follower of Nurgle


« Reply #2 - Posted 2013-08-29 19:58:56 »

Hey Several Kilo-Bytes, thanks for the reply!

Check if an object intersects before sorting. Why sort a hundred objects when all you need is usually one or zero?
Why sort at all? Am I missing something?

You are indeed missing something! I am checking for collision first, and only then add the Obstacle to the list. Line #12

1  
 if(body.overlaps(obs.body)){   // Check if intersection with the Obstacle is true


Your distance equation can be simplified. Do not bother with abs because a positive or negative number square is always positive.
Do not bother with square root because it doesn't change the relative order of values.

That does simplify my code, thank you!

Why do you use ints? Can't a float work as well?

I use Integer for the distance because the SortedIntList only takes Integer as a parameter for it's index  Tongue

If you want to simplify offset distances, you can use center coordinates and half-widths and half-heights.

Not entirely sure what you mean by that. I do use center-coordinates to check where the Entity is in relation to the obstacle.

Thanks again  Smiley
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Several Kilo-Bytes

Senior Member


Medals: 11



« Reply #3 - Posted 2013-08-29 20:29:12 »

But why sort at all?
You could use a SortedFloatList, although I am not sure why the order would be essential if the fractional part of a number can be discarded.
I just saw body.x + body.width, so I thought you were working with corners.
Offline Gjallar

JGO Coder


Medals: 13
Projects: 1


Follower of Nurgle


« Reply #4 - Posted 2013-08-29 20:57:15 »

But why sort at all?

Good question. Because I'm running into an issue if I dont! I guess there's again, a much simpler way to solve that, but that's my solution so far.

Take a look at followig example:


If I dont adjust the dx, dy values with the nearest obstacles first the Entity will get stuck at corners.
In the example the Entity is moving down left (hence dx and dy have the same negative value. Now if it slides
along the blue Obstacle it comes to the point (illustrated in the picture) where it's right at the edge of the red obstacle.
If I dont adjust dy with the nearsest obstacle first (the blue one) it could pick the red obstacle first. And if that happens
the code would set both dx and dy to 0, because the Entity intersects right at the edge and hence the Entity would get stuck.

By checking the nearest Obstacle first I prevent that because the blue Obstacle would have already set dy to 0 and the Entity
would have never intersected with the red Entity.

I really hope that wasn't too confusing... sorry  Cheesy
Offline Several Kilo-Bytes

Senior Member


Medals: 11



« Reply #5 - Posted 2013-08-29 22:43:48 »

That won't work if your obstacles are different sizes. The center of a small object may be father away than the corner or edge of a really big object.

You should to this: Don't update your coordinates until the end. Find all objects which may collide in one turn. (0 <= t <= 1) Check each potential collision and save the one with the smallest t value.

Then at the end to x += vx * minT; y += vy * minT;

This uses a one pass method, is faster, and more robust.
Offline Gjallar

JGO Coder


Medals: 13
Projects: 1


Follower of Nurgle


« Reply #6 - Posted 2013-08-30 18:22:40 »

That won't work if your obstacles are different sizes. The center of a small object may be father away than the corner or edge of a really big object.

Oh crap you're right.. didn't even think of that.

t-value... ?
Offline Several Kilo-Bytes

Senior Member


Medals: 11



« Reply #7 - Posted 2013-08-30 18:29:26 »

Oops. t as in time. vx and vy form the velocity vector.
Offline Gjallar

JGO Coder


Medals: 13
Projects: 1


Follower of Nurgle


« Reply #8 - Posted 2013-08-30 18:38:45 »

Oops. t as in time. vx and vy form the velocity vector.

I'm sorry I'm afraid I still dont understand, but thanks for helping me.

Maybe a picture of what I have so far will help.

EDIT: The dark-red square is the player and is moved around in realtime with WASD.

It's realtime and checks for collisions every frame so I dont understand how using 'time' will help me. If the Player interesects with
two obstacles at the same time, how will that help me to decide which obstacle to adjust the Player's values to?
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.

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

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

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

Riven (28 views)
2014-07-23 20:56:16

ctomni231 (59 views)
2014-07-18 06:55:21

Zero Volt (50 views)
2014-07-17 23:47:54

danieldean (42 views)
2014-07-17 23:41:23

MustardPeter (44 views)
2014-07-16 23:30:00

Cero (60 views)
2014-07-16 00:42:17

Riven (57 views)
2014-07-14 18:02:53
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!