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.

Hello Lachlan! New post today I see; great seeing vector maths utilised in shortest path kinds of scenarios in AI within games. (If that's what you're getting at).

ReplyDeleteKeep it up! (:

Not just the shortest path, it also has to be easy to modify in a level editor. I'm hoping to get another two-three post this week.

DeleteAh, okay; I stand corrected. Well you've got more time to get more done now. (:

Delete