Monday 19 November 2012

How does I draw it?

Ran into a rather interesting problem this week, it involves finding the common (outer) tangents of two circles, but more on that in a bit. First lets look at why.
You have a bunch of Nav-Circles all set up neatly on a map, but all you can see are the circles.

 Indeed drawing circles on a computer screen is only a small jump and a bit of maths from drawing a triangle so that need not be the issue, the issue is what you should see between the circles. If you look at my previous examples (and the one below) you will no doubt notice that all the walk-able areas are draw (in Inkscape's beautiful list of default colours), and that was pretty easy doing it all by hand.

I naively figured that it would be pretty simple to get the computer to do the same; all the information's there, it's just a bit of vector maths, how hard could it be? It turns out to be a non trivial task if you're on the wrong track, thankfully I have a teacher at hand to solve the problem in five minutes and make me look incompetent.
So what's the solution? Maybe I'll start with...
The problem:
Find t where t is the vector that shares a common outer tangent with two circles that have centre positions at A and B respectively and radii of R and r.
First we find the vector from A to B (we'll call this vector D for difference), so D = B - A



What we want to do is normalize D, rotate it by a certain angle, scale it by R and add A to find the point P (shown bellow), as well as scale it by r and add B to find point Q


The problem now is finding the angle to rotate by, let's denote the angle with the Greek letter Omega. By projecting a line from B onto the line AP, we can form a helpful little triangle. The triangle's sides have lengths: (R - r), |t| and hypotenuse |D|.

Using the Pythagorean theory we can at least find out the length of t



But that's not all that helpful, but what we can use is SOH CAH TOA to find omega, we know the Adjacent length (R-r) and the Hypotenuse (|D|) so
(or if you're an idiot like me you'll use arcsin( |t|/|D|) and not notice your gratuitous scheme until you're writing a web-log post on it)

Excellent, now we can find the points P and Q, you also only need to draw one line PQ (or if you want filled in square, PQAB) for each of each circle's neighbours. When the line is drawn from the blue circle it will be on top, and when coming from pink, it will be on the bottom (or vice-versa depending on exact implementation).

Monday 12 November 2012

Am I closer to that one, or that one?

In a map full of way-points, it's pretty easy to find which one you're closest to. All you need to do is look at each node one by one and keep track of which one's closest. With circles it's a bit less obvious; consider the following scenario:

Which circle is Bob closer to? As the crow flies he's closer to the centre of B, but it would make more sense to say A is the closer circle. The solution to this is rather trivial, we need to search for the smallest distance relative to each circles radius, i.e. Distance/Radius instead of just Distance.

Here's another issue that can pop up, consider the following:
Notice that Bob first goes back to the starting Circle despite having clear line of sight on the second? This can be fixed. When receiving the path simply compare the distance from Bob to the second Circle with the distance between the first and second. If Bob is closer then remove the first circle.
This also auto magically fixes another issue involving the target destination being between the same two circles as Bob.

Sunday 11 November 2012

Following the yellow blip road

Following up, how does one take advantage of the great new object that is the circle? It's pretty damn easy if you have a bit of know how, you don't even have to change anything in your path-finding system; you only need to change some things about in the AI. So lets begin.
Start with an a character that we want to follow the path, we'll call him Bob. Bob retrieves a list of circles from the full set, this list consist of the circles he should follow in order.

Middles Only
Bob moves towards the next circle in his list, when he reaches the centre of the circle he pops that circle from the front of the list.

This gives a rigid path that looks exactly like a path made from way-points, so in other words, like crap (unless Bob is a robot [or perhaps a patrolling guard]).

Closest First
Gets a shorter path than the 'Middles Only' algorithm, albeit it sounds pretty much the same.
Bob moves towards the next circle in his list, when he reaches the edge of the circle he pops that circle from the front of the list.

Doesn't that look better already? Also notice that in following this algorithm, Bob will never leave the designated areas we've set out for him.

Closest Last
Watch out! Vector maths ahead! Or at least you need to pay special attention to my words.
Bob moves towards the point on the firsts circle in his list that is closest to the second. When he reaches the point he pops the first circle from the list.
How do we find this point? Glad you asked, it's super simple. Lets say the first two circles in Bob's list are called A and B respectively. First we get the vector that goes from A to B which is of course (B - A), normalize that vector, then multiply that by A's radius.
This gives the equation:
||B.p - A.p|| * A.r

For those visual thinkers:



Closest To Closest Last
Not quite as tricky as it sounds, it's kind of a mix of the previous two.
Bob moves towards the point on the firsts circle in his list that is closest to the second. When he reaches the edge of the circle he pops the first circle from the list.
Overlaid on top of Closest Last to give you a better idea

This is about the shortest path I've been able to find, so it'd be great for something fleeing a rampaging monster, or Bob when you tell him this is how he has to get around from now on.