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.

3 comments:

  1. 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).

    Keep it up! (:

    ReplyDelete
    Replies
    1. 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.

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

      Delete