Welcome back!

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.

## Intersection

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: r_{a}, h, d_{0} and r_{b}, h, d_{1}.

And the distance *d* between the circles is d_{0}+d_{1.}

Long story short (ref. Paul Bourke):

d_{0} = (r_{a}^{2} – r_{b}^{2} + d^{2}) / (2d)

and

h = sqrt(r_{a}^{2} – d_{0}^{2})

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 > r
_{a}+r_{b} - Containment – if r
_{a}^{2}– d_{0}^{2}> 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 a_{0}, a_{1} and a_{2} were generated by the above algorithm. a_{1} 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.

# Run-time

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?

## Collision detection

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…

## Collision resolution

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.

## Multiple Collisions

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.

## Cheating

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.

## Penetration

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.

## The Demo

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.

## The Source

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.

## Next time

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!

Have fun,

Cheers, Paul.

Where is the facebook like button ?

Good point I need to find the wordpress plug in for that….

Done I love wordpress, so easy to use….

Pingback: 2d Isometric land – breaking out of the grid part 2 « RaminMjj

Awesome! Can’t wait for part 3, it’s suspenseful: what sort of spatial partition could possibly fit circular arcs well?!

Sorry for the OT-ness of this question, but on gamedev.net you mentioned “If you do things right (and this takes a *lot* of tweaking/improvement), you will be able to get your stack to be stable in just 5 iterations (which is all we could afford on LBP PSP)”.

My question is: does this mean that LBP PSP was using an impulse-based simulator? Alex’s presentations said they were using a “position-based dynamics” type sim; I’m wondering how you would apply e.g warm-starting in such a system. Please feel free to email me off-blog… thanks!

Great article. Need more

Pingback: 2d Isometric land – breaking out of the grid | www.nalli.net

Æ!!

You added a facebook button, so, add a Google +1 too

Nice article btw