2d isometric land – breaking out of the grid update

Submit to StumbleUpon

Welcome back to my blog :)

Ok, so i’ve realised i was a fool; i totally overcomplicated what you actually need to do in order to collide with a landscape composed of overlapping circles in part 1 and part 2.

An email from Andre, the programmer on the gloriously pretty bunnibunni set me on the right track, although my revised technique is slightly different than his.

Bunni bunni

The new way

Ok, lets have another look at the problem.

Figure 1

Figure 4

What we actually want to have is a distance function; we’d like to know the distance from any given point to the exterior of the map in Figure 1 and Figure 4. Once we have this we can tell if we’re inside or outside the map and also (with the addition of closet point on exterior) the shortest direction to the exterior and therefore contact normal.

The way to achieve this is actually quite simple. All you need to do is to take your candidate point and project it on to the edge of each circle. If the projected point lies inside another circle it is discarded, if not that is the closest point to the circle.

If all projected points lie inside another circle, the distance to the exterior is the closest distance to an exterior vertex (shown in green in Figure 1).

Figure 2

In Figure 2, the projected points (shown in blue) are inside another circle and so are discarded, leaving the closest distance to be the distance to the closer of the two external vertices.

Figure 3

In Figure 3, the projected point lies does not lie within another circle and therefore is the closest.

Conclusion

With this new method you don’t need to worry about arc-lengths or even have to bother with any kind of cheating (as detailed in part 2) and indeed, you don’t need to think about having a solver in order to resolve the collision because there is only one possible closest point returned – you can just use the simple technique i outlined in part 2.

Its just a much better way of doing things :)

Thank you to Andre for pointing me in the right direction…

The code

There is no live example since it looks pretty much identical to the previous version. But, i’ve uploaded the code for you to inspect here – should be a lot easier to follow. BreakingOutOfTheGrid2.zip

Have fun,

Cheers, Paul.

Submit to StumbleUpon

About Paul Firth

A games industry veteran of ten years, seven of which spent at Sony Computer Entertainment Europe, he has had key technical roles on triple-A titles like the Bafta Award Winning Little Big Planet (PSP), 24: The Game (PS2), special effects work on Heavenly Sword (PS3), some in-show graphics on the BBCs version of Robot Wars, the TV show, as well as a few more obscure projects.   Now joint CEO of Wildbunny, he is able to give himself hiccups simply by coughing.   1NobNQ88UoYePFi5QbibuRJP3TtLhh65Jp
This entry was posted in Collision Detection, Graphics, Physics, Silverlight, Technical. Bookmark the permalink.

2 Responses to 2d isometric land – breaking out of the grid update

  1. raigan says:

    How do you identify the “exterior vertices”? If it’s true that, when the closest point is an interior vertex it must be formed from the intersection of a circle containing the query point, then this is a simple local query… otherwise aren’t you going to have to interesect every circle in the scene?

    • Paul Firth says:

      Hi Raigan,

      Yes, you are correct – in the code i actually do intersect every circle in the scene up front and just store the intersection points… In production code you would simply stick all the scene data (circles, vertices etc) into a spatial hierarchy and then do a proximity query against the character to get the result very quickly :)

      Cheers, Paul.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

WP-SpamFree by Pole Position Marketing