In my last post i covered how to find the distance from a point to a circular arc-length, and how to computer intersection point, normal and penetration distance (assuming a circular collision shape).
This time i'm going to cover how to actually generate all the arc-lengths from a map composed of overlapping circles.
Mapping it out
So, in your favourite mapping tool, you need to generate a collision map to represent your world; something like what we have in Figure 1, to represent the top down 'island' map in Figure 2.
I used Expression Blend since my example is written in Silverlight.
Goal and process
The goal here is to generate the boundary of the map, which will consist of a bunch of circular arc-lengths (and potentially whole circles, although not in this particular illustration).
A high level overview of the process is this:
- Intersect all the land-circles, generate intersection points
- Discard any intersection points that are not on the boundary
- Generate arc lengths from these intersection points
- Discard any arc-lengths which are occluded.
The first thing i do in my algorithm is to take every land-circle and intersect it with every other land-circle in the map.
There are three cases to deal with:
- Separation - the circles are not intersecting
- Containment - one circle is contained within the other
- Intersection - the two circles are intersecting
Obviously we are only concerned with case 3, but we have to correctly detect and avoid the other two cases.
Consider Figure 3 where we have two land-circles a and b intersecting. The first thing to note is that the intersection points always lie along a line perpendicular to the vector between the circles. This leaves us with two right angled triangles, with edge lengths: ra, h, d0 and rb, h, d1.
And the distance d between the circles is d0+d1.
Long story short (ref. Paul Bourke):
d0 = (ra2 - rb2 + d2) / (2d)
h = sqrt(ra2 - d02)
So, then just compute the point at the base of h, and therefore the two intersection points, since h is symmetrical and we know its always in the direction perpendicular to the vector between the two circles.
The two conditions to watch out for are:
- Separation - if d > ra+rb
- Containment - if ra2 - d02 > 0
As the intersection points are generated, they are associated with each circle they 'belong' to (as long as they are not occluded by another land-circle), along with the angle from the centre of the circle to the intersection point in map space.
This angle will be used later to help generate the arc-lengths.
Discarding occluded intersection points
As each intersection point is generated, it is discarded if it is contained within any land-circle - i.e. not lying on the boundary of the map.
For this i just calculate the distance between each intersection point and every circle and if the distance is less than some negative tolerance (i.e. slightly inside the land-circle), consider it contained.
The red dots in Figure 4 represent discarded intersection points.
Generating the arc-lengths
Arc-lengths are defined as an association to the parent land-circle (and therefore centre point), a start angle and a sweep angle.
To actually generate the arc-legnths, i loop over each land-circle - if there are intersection points associated, i do the following:
- Sort intersection points based on the angle i stored earlier, from smallest to largest
- Generate an arc-length from one intersection point to the next
- If the arc-length just generated is occluded, discard
As in Figure 5, the green intersection points associated with land-circle A were generated in the previous step.
Discard occluded arc-lengths
The arc-lengths a0, a1 and a2 were generated by the above algorithm. a1 was discarded because it was occluded by a land-circle.
Occlusion is determined by the arc-length distance to point function described in part 1 - the point in question is the centre of land-circles.
No intersection points
Its possible to have no intersection points associated with a land-circle, this simply represents a land-circle by itself in the map, and can be stored as an arc-length with 2PI sweep angle.
Ok, so now we have everything we need, we've got a list of arc-lengths that were preprocessed for us to use at run-time, so how do we use them?
For each moving object:
- Loop over all land-circles
- Get distance to land-circle from object
- If distance < 0, resolve collision
Step 1 is obvious, step 2 was described in part 1 of this blog entry...
I assume each moving object has a velocity that we want to alter based on the collision detection.
So, once we've detected a collision, we've got the normal, which is pretty much all we need to resolve the collision.
In Figure 6, we have our moving object (the green circle), with velocity v and our normal n pointing out from the surface.
We want to compute the unwanted velocity, that is to say the velocity which we want to remove to resolve this particular collision. So, first we compute the relative normal velocity:
relNv = v . n
v.n is shown in Figure 6 as the dotted line.
We only want to remove negative relative normal velocity, that is motion not in the direction of the normal.
To resolve the collision:
vel -= min(relNv, 0) * n;
The min() ensures we don't remove positive motion in the direction of the normal - this would cause the object to 'stick' to the surface.
Figure 7 shows the velocity of the object after the resolution has taken place; the motion towards the normal has been removed.
In order to be able to correctly resolve multiple simultaneous collisions (that can occur quite readily even in this example) with no jittering we would need to start exploring a contact solver to solve for the 'global solution' to the collision problem, but this is beyond the scope of this article... although i have included such a solver in the source code.
The system described thus far will handle multiple collisions, but there may be jittering due to the fact that each collision resolution only considers itself and not all the other collisions that may be occuring - it will tend to over-correct.
Ok, so this requires some amount of cheating to solve without going for the full solver. The problem becomes most apparent when there is a strong desire (for the character) to travel past the edge of the map where there are two opposing normals. This usually happens when the user clicks outside the map (in the sea) and where there are two opposing normals.
To stop this from being a problem in the demo, what i do is this: whenever the user clicks on the map, i check to see if the click point is inside the map (on land), if not i snap it to the nearest point on the land.
This helps by reducing the size of the 'walk vector' for the character in problem situations. Its still not enough to fix the jittering completely, though.
To do this i keep track of whether the character is getting any closer to the target click point. If not, stop trying to get there.
This might be an acceptable solution in general - if not, i recommend going for the full solver. If you would like an article on how the solver works, let me know in the comments section.
In general altering the actual position of objects during the collision detection is highly discouraged - only the velocity should be altered, otherwise the position will be incorrect after you modify it for the rest of the objects, causing all kinds of nonsense.
However, there may well be instances where altering velocity of objects is not enough to stop them slowly sinking in to other objects under extreme circumstances. In these cases it is acceptable to maintain a position correction vector which gets accumulated during the collision detection and then applied once at integration time and then cleared to 0 for next frame.
For this example it is unnecessary, but i mention this here anyway because this so often gets overlooked in articles about collision resolution.
Here is a demo of the technique as described so far, clicking the left mouse will send the character on a mission towards the click-point.
As promised i've made the source-code for this demo available here BreakingOutOfTheGrip.zip its for VS2008 Web Developer Express and requires Silverlight 3 to build.
Its on a do-what-you-like-with-it licence, but with no warranties provided.
Ok, so now we've got no grid, how do we organise our world so that we can still quickly query it to find objects near a point, or objects near objects etc?
This is what i'll cover in the part 3!