Collision Avoidance

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).

	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;
	}

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.

Hey Several Kilo-Bytes, thanks for the reply!

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

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

[quote=“Several_Kilo-Bytes,post:2,topic:43892”]
That does simplify my code, thank you!

[quote=“Several_Kilo-Bytes,post:2,topic:43892”]
I use Integer for the distance because the SortedIntList only takes Integer as a parameter for it’s index :stuck_out_tongue:

[quote=“Several_Kilo-Bytes,post:2,topic:43892”]
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 :slight_smile:

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.

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:

http://i.imagebanana.com/img/kc78eekp/Issue.png

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 :smiley:

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.

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

t-value… ?

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.

http://i.imagebanana.com/img/mg46exl6/visualisation.png

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?