Jump to content

  • Log In with Google      Sign In   
  • Create Account


Collision Correction


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
5 replies to this topic

#1 regenschauer   Members   -  Reputation: 104

Like
0Likes
Like

Posted 10 February 2013 - 11:48 AM

Dear Community; I have a Problem with the Correction after a Collision in a Platformer I try to create. I have tried many things and all have magically failed. Now, I turn to you, as I feel like I might need some external help with the Problem.

 

I use Java and I have a Entity class, which has a function called collide with a list of other Game Objects. If I find a Collision, I add it to an Array of colliding objects. Now, I would need to work out how to move the this object out all those collisions.

 

My coordinate System is also oriented with the y axis pointing downwards, meaning the bigger the y value, the lower the object on the screen.

 

Objects are represented like this:

 

J4DoyTo.png

And the Objects I collide are determined like this.

	public void collide(ArrayList<Entity> objectsToCollide){
		ArrayList<Entity> CorrectionEntities = new ArrayList<Entity>();
		
		for(int i = 0; i < objectsToCollide.size(); i++){
			Entity currentCollisionObject = objectsToCollide.get(i);
			if(currentCollisionObject == this)
				continue;
			if(Entity.entityBoxesIntersect(this, currentCollisionObject)){
				CorrectionEntities.add(currentCollisionObject);
			}
		}
		
		if(CorrectionEntities.size() == 0)
			return;
		
		for(int i = 0; i < CorrectionEntities.size(); i++){
			//TODO: Correct Position
			
			
		}
	}

 

Now the correction is supposed to happenn at the TODO marking, I put it there, as the other trials have failed horribly.

 

Thank you very much for your help,

 

regenschauer



Sponsor:

#2 Norman Barrows   Crossbones+   -  Reputation: 2040

Like
0Likes
Like

Posted 11 February 2013 - 09:25 AM

Sounds like your talking about collision recovery after a collision has been detected.

 

There are a number of possible collision recovery strategies:

 

1. "Bang and turn"

this is one of the most common, is very simple, and sort of works half decent depending on the type of obstacles in the world. the basic idea is you turn the unit left or right, and move for a short distance, then resume normal movement towards your target. this works ok for maneuvering around trees, rocks, people, etc, IE.anything small enough for the unit to move around during the "move for a short distance" part. It doesn't work for big objects. there, the unit collides, turns, moves some, then turns back, collides again, turns again, moves some more, etc. eventually it finds its way around a large object, but with multiple collisions. Banf and turn doesn't work well at all for concave obstacles, such as a room with a door to the south, and your target is north of the room.  When deciding hich direction to turn, you usually turn towards the target. Adding a bit of randomness can help here, as turning towards the target doesn't always work - something like turn towards the target 75% of the time and away from the target 25% of the time.

 

2. A*

A* will find a path from the unit to the target - guaranteed. but it may be slow. Tricks here include things like only doing A* out to a range of 10 squares around the unit, instead of the whole map, or spreading the calculations out over multiple frames.

 

3. Navigation meshes.

Although i don't have much experience with these, i suspect its possible to use a nav mesh where nodes blocked by obstacles are marked and not used in the path calculation.

 

4. Heuristics.  

by using collision type checks during the collision recovery movement phase, you can check for things like obstacle_to_the_left(), obstacle_to_the_right(), etc. Using this, you can have the unit continue collision recovery movement until is has a clear line-of-sight to the target. units can be programmed to detect a wall ahead, to turn before they hit it, to run along the wall until they reach the end and can resume normal movement, etc.

 

5. other methods i cant think of right now (anyone else out there have any more recovery algos?)

 

 

A* is the guaranteed solution if you have the processing power.

 

Sometimes its necessary to modify the game design a bit, make the map smaller or split it up into multiple smaller maps for A*, not allow concave obstacles, etc.


Norm Barrows

Rockland Software Productions

"Building PC games since 1988"

 

rocklandsoftware.net

 


#3 Norman Barrows   Crossbones+   -  Reputation: 2040

Like
0Likes
Like

Posted 11 February 2013 - 09:32 AM

Note:

while A* works, its not the way people do path finding in real life. In real life, humans seem to use heuristics. Or maybe we do A* in our heads, but so quickly and intuitively that we don't know it. I suspect that its possible to write a heuristic based collision avoidance / path finding algo that performs close to A* with much less overhead.


Norm Barrows

Rockland Software Productions

"Building PC games since 1988"

 

rocklandsoftware.net

 


#4 EWClay   Members   -  Reputation: 659

Like
0Likes
Like

Posted 11 February 2013 - 09:39 AM

The last reply is all about AI, but I assume you are actually talking about physics, in which case:

For each colliding pair, find the axis of minimum overlap. Move each object half the overlap distance in opposite directions along this axis. Repeat the whole collision algorithm (including building the list) until all collisions are resolved or you hit a maximum number of iterations.

There are ways to optimise this if it becomes too slow with all the searching and iterating. That's for later, get it working first.

#5 Norman Barrows   Crossbones+   -  Reputation: 2040

Like
0Likes
Like

Posted 13 February 2013 - 06:20 PM

The last reply is all about AI, but I assume you are actually talking about physics, in which case:

For each colliding pair, find the axis of minimum overlap. Move each object half the overlap distance in opposite directions along this axis. Repeat the whole collision algorithm (including building the list) until all collisions are resolved or you hit a maximum number of iterations.

There are ways to optimise this if it becomes too slow with all the searching and iterating. That's for later, get it working first.

 

OK, i see what you're saying, not the recovery AI, but how to re-position the units. Well the answer to that is they're not supposed to overlap in the first place! You're supposed to check for collision BEFORE you actually move, not after! you calculate a unit's new position, check that new position for collision, if none occur, move the unit, and so on for each unit in turn. No units overlap because they stop if moving would cause overlap. When i first started building games, i too did the normal thing and moved the unit, then checked for collision. while researching the answer to the "fixing collided unit positions" problem, i learned i was doing it in the wrong order! If you want collisions to be high resolution, you check for collision, if one occurs you then apply the same process with a smaller movement rate (whatever granularity you want), like step moving a missile and checking for collisions at each step. 


Norm Barrows

Rockland Software Productions

"Building PC games since 1988"

 

rocklandsoftware.net

 


#6 Lightness1024   Members   -  Reputation: 736

Like
0Likes
Like

Posted 14 February 2013 - 09:44 AM

I have a super simple way to do that as a mean for a platform game demo:

http://carnage-engine.git.sourceforge.net/git/gitweb.cgi?p=carnage-engine/carnage-engine;a=blob;f=carnage-engine/collisionmanager.cpp;h=856a5595993d64b9a56df4617d42fc947933ce24;hb=HEAD

function FindFreePosition.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS