Hello and welcome to Wildbunny blog!
In this first instalment i'm going to talk about bringing some simple technology to isometric 2d games to help them break out of the regular grid look which afflicts so many 2d games today, on Facebook or otherwise.
I've picked on Farmville here, but in fact even our own game, PuzzleShare is guilty of the same crime.
Why the grid?
You might ask why so many games choose the regular grid. The principle reason is that its very easy to work with - you just render everything top to bottom in screen-space to depth sort it, all the tiles are the same size so making new art isn't a problem and it makes mouse picking easy for users because everything is regular. The only real problem is how to deal with height, but very few games on Facebook even bother to tackle this problem.
So, why change?
The principle reason to stop using a regular grid is differentiation. If you can make your game look fresh and different by brining a new design ethic it will stand out from the crowd and if you do it right, it can look a whole lot better than it would have.
This is a nice example of what you can achieve if you do a little extra work, taken from the excellent LostGarden.
Of course, the real question is how do you approach this? Looking at the above image, its clear to see that the landscape could be composed of lots of overlapping circles (with a slight vertical squish applied). Seems simple enough, right?
The real problem, though is how to deal with collision against the interior of the set of overlapping circles. You can't just use a simple circle vs circle routine in reverse because you run into all sorts of nasty problems where the circles overlap.
Consider the case in Figure 1, where the character (represented by the green circle) is intersecting the land (defined by the union of circles A and B). In this case the character will be compelled to remain within B (as its closest to the character), but as the character travels up the map, there will be a point where the character is closer to A, and it will snap inside of A in a discontinuous and jarring manor.
What you actually want in this case is a smooth transition as the character is repelled from the left apex of the union of A and B - appearing to pivot around the apex.
Looking at Figure 2 you can see what i was getting at - the left apex of the union of the two circles appears smooth and rounded when seen from the POV of collision with the character. You may have noticed the character is now a tiny green point (it should be zero radius, actually but for the purposes of illustration its just small), and that the walls of the union of circles have expanded by exactly the radius of the character. Whats going on?
The Minkowski difference
Ok, so what happened in Figure 2 was we started to look at the problem a little differently. We've discarded the interior of the union of the circles completely, we shrank the character down to a point with zero radius and at the same time enlarged the boundary of the circles by the radius of the character.
This enables us to see the problem for what it really is using something known as the Minkowski Difference. In reality the problem boils down to being able to compute the distance between the character and the circular arc lengths which comprise the exterior of the union of circles.
Once you can compute the distance, you can tell if the character is intersecting the circles and also compute the Penetration Distance and resolution vector which allows you resolve the collision.
Figure 3 shows the nearest distance from the character to the circle interior d and the radius of the character r. If d is less than r there is a collision, and furthermore, the penetration distance is r-d, and the normal to use is simply the normalised vector from the closest point on the boundary to the character centre.
Distance to circular arc-length
So, how do i compute the distance from a point to a circular arc-length, you ask? Well, its actually quite easy. There are only two cases to deal with:
Case a, where the point lies inside 'pie' which is defined by the centre of the circular arc-length and the arc start and end. This is simple enough to compute; just project the point a onto the arc length by computing the vector from the centre of the 'pie' (which is actually the circle's centre before it turned into an arc-length), to the candidate point a, normalise and multiply by the radius. Once you have the point on the arc, just subtract from a and compute the length.
Case b, where the point lies outside. This is even easier; its always the distance to the closer of the two end-points of the arc!
Ok, so you now know how to find the distance to an arc-length, calculate the normal and penetration distance, and resolve the collision!
Next time i will talk about how to actually generate the set of arc-lengths from a bunch of overlapping circles, and will provide full source code!
In the mean-time, please check our new game, PuzzleShare...