Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (683) Games in Android Showcase (196) games submitted by our members Games in WIP (751) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Collision Avoidance  (Read 2183 times) 0 Members and 1 Guest are viewing this topic.
Gjallar

JGO Knight

Medals: 29
Projects: 1

Follower of Nurgle

 « Posted 2013-08-29 17: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

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 obstacles){            setBodyPos(x + dx, y + dy);   // Set Body(Rectangle) to where it will be if dx/dy get applied      updateBodyCenter();            SortedIntList overlappingObs = new SortedIntList();      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> iterator = overlappingObs.iterator();      while (iterator.hasNext()) {   // Loop through the sorted intersecting Obstacles         SortedIntList.Node 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;   }`
Several Kilo-Bytes

Senior Devvie

Medals: 11

 « Reply #1 - Posted 2013-08-29 17: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.
Gjallar

JGO Knight

Medals: 29
Projects: 1

Follower of Nurgle

 « Reply #2 - Posted 2013-08-29 17: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

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
Several Kilo-Bytes

Senior Devvie

Medals: 11

 « Reply #3 - Posted 2013-08-29 18: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.
Gjallar

JGO Knight

Medals: 29
Projects: 1

Follower of Nurgle

 « Reply #4 - Posted 2013-08-29 18: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
Several Kilo-Bytes

Senior Devvie

Medals: 11

 « Reply #5 - Posted 2013-08-29 20: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.
Gjallar

JGO Knight

Medals: 29
Projects: 1

Follower of Nurgle

 « Reply #6 - Posted 2013-08-30 16: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... ?
Several Kilo-Bytes

Senior Devvie

Medals: 11

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

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

JGO Knight

Medals: 29
Projects: 1

Follower of Nurgle

 « Reply #8 - Posted 2013-08-30 16: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.

 orrenravid (210 views) 2016-07-16 03:57:23 theagentd (281 views) 2016-07-11 14:28:54 Hydroque (366 views) 2016-07-06 05:56:57 Hydroque (519 views) 2016-07-03 08:52:54 GrandCastle (392 views) 2016-07-01 09:13:47 GrandCastle (385 views) 2016-07-01 09:09:45 CopyableCougar4 (437 views) 2016-06-25 16:56:52 Hydroque (413 views) 2016-06-22 02:17:53 SwampChicken (379 views) 2016-06-20 13:22:57 SwampChicken (303 views) 2016-06-20 13:22:49
 Archive 30x Brynn 23x Slyth2727 23x TritonDreyja 22x EgonOlsen 22x orangepascal 22x orange451 20x DavidBVal 19x Spasi 18x KaiHH 12x LiquidNitrogen 11x Phased 11x Opiop 11x princec 11x Longor1996 10x theagentd 10x
 Making a Dynamic Plugin Systemby Hydroque2016-06-25 00:13:25Java Data structures2016-06-13 21:22:09Java Data structures2016-06-13 21:20:42FPS Camera Tutorialby Hydroque2016-05-22 05:40:58Website offering 3D Models specifically for games for freeby vusman2016-05-18 17:23:09Website offering 3D Models specifically for games for freeby vusman2016-05-09 08:50:56Website offering 3D Models specifically for games for freeby vusman2016-05-06 11:10:21Website offering 3D Models specifically for games for freeby vusman2016-04-29 12:56:17
 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