Alright! Congratulations on surviving what might be the longest post on this blog, up to this point! If you’ve come this far, maybe you’re willing to come a little further…

That look of disappointment is going to stick with me...

So, lets return to the land of Programma Arte. What do we have, now? We have all our Waypoints contained inside a container we’re calling KMStar, and that container has a script on it called… KMStar. That’s it for setup, really. If you run it, you’ll see KMStar’s waypoints member fill with all the Waypoints underneath it. Perfect! But lets actually make this, ya know, do something. And, for that, we need some controllers.

But, before we do that, we have to do something a little painful…

Waypointpain

So, not gonna lie, this part sucked for me because of how tedious it is. Lucky for you, I’ve done it all for you in my example, but you can go do it yourself, too. All our Waypoints represent a tile in Programma Arte, and each tile is of different types. We need to specify the type of tile the controllers will be navigating across, and so we’re making a script called WaypointType.

Here’s the code for it.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class WaypointType : MonoBehaviour {
    [System.Serializable]
    public enum WPType
    {
        Null = 0,
        Grass,
        Water,
        Sand,
        Snow,
        Mountain,
        Bridge,
        Town
    }

    [SerializeField]
    private WPType value = WPType.Null;

    public WPType Value
    {
        get { return value; }
    }
}

Real terrible, right? I feel this doesn’t need explanation, so I’ll save my breath (save my… type? Text? Finger taps?). But what you have to do it put this component on every Waypoint, and set each individual type. It’s about as fun as initially setting up the Waypoints, and I should’ve done this initially, too.

OK. That’s done. Lets move on.

It’s About Putting A Line In The Sand…

First thing we’re putting together, though, is a line drawer. We have a path, it connects dots, so lets actually see it connect the dots! Now, I’m going to be a bit heavy on the Unity lingo here, and, again, if you’re not using Unity, try your best to translate this into something you can fathom – Unreal, GameMaker, raw OpenGL, etc.

So, in Unity, we’ll add a simple GameObject to our scene, and attach a LineRenderer to it.

Next, lets create our KMStarPathDraw component. This component will be relatively simple. All we need to do is give it a LineRenderer, a link to the KMStar object, the HeuristicAlgorithm to run, a start Waypoint, and an end Waypoint. That’s all. Then, our callback function, DrawPath, will go and do all the work!

Here it is, in all it’s glory:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class KMStarPathDraw : MonoBehaviour {
    public LineRenderer line;

    [SerializeField]
    KMStar algorithm;
    [SerializeField]
    KMStar.HeuristicAlgorithm algorithmType = KMStar.HeuristicAlgorithm.Vector3Distance;
    [SerializeField]
    Waypoint start;
    [SerializeField]
    Waypoint end;

    private void Start()
    {
        if(algorithm != null && start != null && end != null)
        {
            StartCoroutine(algorithm.FindPath(start, end, (path) => DrawPath(path), algorithmType));
        }
    }

    public void DrawPath(List path)
    {
        line.positionCount = path.Count;
        Vector3[] pos = new Vector3[path.Count];
        for(int i = 0; i < path.Count; ++i)
        {
            pos[i] = path[i].transform.position;
        }
        line.SetPositions(pos);
    }

}

Simple, right? And, look! We actually get to use our brand new KMStar in a simple one-liner! So, that Start function is a Unity-specific function. Every Monobehavior has it, and it gets called at the Start of the object’s life. So, once we hit Play, the line goes out and generates a path.
Now, our callback parameter here might look a little funky to those unfamiliar with C#’s Lambda Expressions. The link I just provided should have all you need to get rolling with them, so I won’t dwell on it too long. Once the path is generated, we get into our callback, which passes in the new path, gets the Waypoint positions, and adds them to our LineRenderer, and, BAM! We have a line! We can see the path we made! Hurray!

lineRender

This little block of code is good for testing out the results to any new “algorithm” you come up with. That’s why I wanted to get on it first before we move into the fun stuff…

Take Control

Drawing a line along a path is cool, sure, but you know what’s cooler? Having something travel along the path! Yeah! (OK, I’ll tone it down).

So, we create a base class here, because we’ll want a few different behaviors in the future, probably. Introducing the KMStarController! In here, we’re knocking out a bulk of the work so we don’t have to later!

Members Only

So, lets look at the members to this class:

public KMStar pathfinding;
public KMStar.HeuristicAlgorithm pathFindType = KMStar.HeuristicAlgorithm.Vector3Distance;
public bool ignoreWaypointHeuristic = false;
public float recalculateDelay = 5.0f;
public float moveSpeed = 10.0f;
public Waypoint currentWaypoint;
public Waypoint previousWaypoint;
public Waypoint targetWaypoint;
private float currentDelay = 0.0f;
private bool isMoving = false;
private bool isCalculating = true;

private List currentPath;

Alright! Now we’re talking! Lets go and define these guys:

  • KMStar pathfinding – If you’re not sure what this is by now, please go back to Implementation.
  • HeuristicAlgorithm pathFindType – The algorithm this controller will be using to navigate around.
  • bool ignoreWaypointHeuristic – Oh, jeez, it’s back!?
  • float recalculateDelay – So, lets say our AI is tracking a moving target. KMStar is set up to lead you to one stationary end point. So we need to stop every so often to recalculate the new path to the moving target. This delay tells us how often to recalculate the path.
  • float moveSpeed – Base speed of the AI Agent’s movements. Keep an eye on this field, because we’re going to play around a bit with this one…
  • Waypoint currentWaypoint – This is the Waypoint we’re currently moving towards. It’s not the Target, it’s just the next step in the path.
  • Waypoint previousWaypoint – This is where we came from. Pretty self-explanatory.
  • Waypoint targetWaypoint – This is our destination! This is the actual goal.
  • private float currentDelay – A counter to go with recalculateDelay.
  • private bool isMoving – When we’re in-between Waypoints, we don’t want to get interrupted, or else we’ll get some really funky movement behavior.
  • private bool isCalculating – If we’re currently calculating out a new path, we don’t want to interrupt that either, or else we’ll get really funky.
  • private List currentPath – The current path returned to us from KMStar.

Alright! Excellent! Here it all is. We’re ready to make this Agent move! This is done a lot in the same fashion as KMStar; we have a few “helper” functions to set up the big enchilada, the Update function.

The Setup

OK, lets define some of our virtual functions. These will ultimately be empty for now, but will be called in this class. We’re setting up for the future children classes.

mmv8hpl2clxjdm9ilguffjf5nei

Right. We have 4 virtual functions to define. All of them have an empty body except for…

  • protected virtual float MoveSpeedModifier()
    • In the member definitions for this class, we have moveSpeed, and that acts as our base movement speed. When we traverse over certain Waypoints, we want to change the speed based on the “terrain” we’re crossing. In this base class, however, we’ll just return 1f so nothing changes.
  • protected virtual void OnGetPath(List path)
    • This is not our callback to KMStar.FindPath. This is just an overridable function that gets called inside of the callback, so that if our object wanted to check/modify the path before it gets used, we have the opportunity to do so.
  • protected virtual void OnNextWaypoint()
    • This gets called when our KMStarController reaches a Waypoint, and is about to start heading to the next.
  • protected virtual void PreFindPath()
    • Called before the object begins looking for a new path to the target.

That concludes the interface functions! Pretty easy for now, but just wait until we make them do stuff.

Next, we get to work on the actual callback to FindPath, GetPath! GetPath doesn’t do anything too crazy; once we get the path back from FindPath, we set our currentPath to that, check to make sure that it has more than 1 Waypoint in it, and, if it does, set our currentWaypoint to the first element in the path. Then, we switch our isCalculating flag to false. Easy-peasy.

void GetPath(List path)
{
    OnGetPath(path);
    currentPath = path;
    if (currentPath.Count > 1)
    {
        currentWaypoint = currentPath[0];
    }
    isCalculating = false;
}

Next up, is the RecalculatePath function. This function is pretty simple as well. It only gets called when we have reached our targetWaypoint, or if our recalculateDelay timer runs out. Then we set our isCalculating flag to true, set our currentDelay back to 0, and then we call our interface function PreFindPath. After that is our call out to KMStar.FindPath, passing along GetPath as the callback. Ta-frickin’-da.

public void RecalculatePath()
{
    isCalculating = true;
    currentDelay = 0.0f;
    PreFindPath();
    StartCoroutine(pathfinding.FindPath(currentWaypoint, 
    targetWaypoint, 
    (path) => GetPath(path), 
    pathFindType, 
    ignoreWaypointHeuristic));
}

Lastly, to get everything started off, we call RecalculatePath inside of our Start function (that’s been provided by the Monobehaviour).

Whew! Everything is set up! Lets define that Update function!

Give me an Update

Our Update function is a bit more involved than anything else in this class. Again, the point is to do it once here and then pretty much forget about it. This is also going to be Unity heavy, but the design is all there for what we’re doing and how to do it, so I’m leaving it up to you to go look up what functions and objects are in the Unity API by yourself. Sorry, baby birds, but, at this point, you gotta fly!

So, lets talk about the logic here. Here’s what we want to do:

  1. If our currentPath is null, return immediately. There’s nothing to do here.
  2. Next, if isCalculating is true, that means we’re currently building a new path. We don’t want to just exit outright, but we would skip everything down to Step 7. If it’s false, we keep soldiering on.
  3. Now, we update our position. We are going to move towards our currentWaypoint at a speed of (moveSpeed * ModeSpeedModifier() * Δt (delta time between frames)).
  4. Next up, we check to see if our distance between, well, us (we’re in this together, man), and the targetWaypoint is less than a particular threshold. If so, we stop moving, and then skip down to Step 7. If we’re not, go down to the next step.
  5. After that, we check to see if our distance between us and the Waypoint we’re heading towards is less than a particular threshold. If we are, then we go to the next step, but if we aren’t, then we set our isMoving flag to true, and skip on down to Step 7.
  6. So, if we’re in range of the currentWaypoint, we set our isMoving flag back to false, and check how many elements are left in our currentPath. Then…
    1. If we have more than 1 element in the currentPath, then we remove the first item in the currentPath. We set our previousWaypoint to our currentWaypoint, set our currentWaypoint to the new first element in currentPath, and finally call OnNextWaypoint.
    2. If we have 1 or less elements in the currentPath, then we simply call RecalculatePath, and return from the entire Update function.
  7. Now we simply increment our currentDelay by Δt.
  8. Now we check if isCalculating is false, and isMoving is false, and currentDelay is greater than/equal to recalculateDelay, then we call RecalculatePath.

All that to move along a path. Trust me, it reads better in code. Speaking of which, here you go:

void Update () {
    if (currentPath == null)
        return;
    if (isCalculating == false)
    {
        transform.position = Vector3.MoveTowards(transform.position, currentWaypoint.transform.position, moveSpeed * MoveSpeedModifier() * Time.deltaTime);
        if (Vector3.Distance(transform.position, targetWaypoint.transform.position) > Mathf.Epsilon)
        {
            if (Vector3.Distance(transform.position, currentWaypoint.transform.position)  1)
                {
                    currentPath.RemoveAt(0);
                    previousWaypoint = currentWaypoint;
                    currentWaypoint = currentPath[0];
                    OnNextWaypoint();
                }
                else
                {
                    RecalculatePath();
                    return;
                }
            }
            else
            {
                isMoving = true;
            }
        }
        else
        {
            isMoving = false;
        }
    }
    currentDelay += Time.deltaTime;

    if (isCalculating == false && isMoving == false && currentDelay >= recalculateDelay)
    {
        RecalculatePath();
    }
	
}

There we go! That’s our controller! You could go ahead and put this in our scene right now, but… it won’t really be that much fun, to be honest. Lets keep going and make some child classes!

Dragon this out!

Alright, so we’re all set to actually have some action in Programma Arte! We’re going to have a terrible Dragon flying (keyword) around the world, randomly traveling from Waypoint to Waypoint, and we have 4 brave Knights chasing the Dragon. So lets define 2 classes that’ll derive from KMStarController: DragonController and KnightController.

DragonController is pretty simple:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class DragonController : KMStarController
{
    protected override void PreFindPath()
    {
        Waypoint randTarget = pathfinding.wayPoints[Random.Range(0, pathfinding.wayPoints.Length)];
        if (randTarget != null && randTarget != currentWaypoint)
        {
            targetWaypoint = randTarget;
        }
    
    }
}

Simple! In PreFindPath, the dragon goes and grabs a random Waypoint from the KMStar‘s container of Waypoints.

Now, the KnightController is a bit more… involved…

Knight Time!

See, the Knights don’t fly, so they need to travel over all the terrain of Programma Arte. This is where the WaypointTypes come in. Each Knight has a mapping for how fast they move to and from Waypoints. For this, we set up a small nested class inside of KnightController called WayPointSpeedModifiers.

[System.Serializable] // <- This is here so we can edit this in the Inspector
public class WayPointSpeedModifiers
{
    public float NullMod = 1.0f;
    public float GrassMod = 1.0f;
    public float WaterMod = 1.0f;
    public float SandMod = 1.0f;
    public float SnowMod = 1.0f;
    public float MountainMod = 1.0f;
    public float BridgeMod = 1.0f;
    public float TownMod = 1.0f;
}

Now that we have that, lets look at the members of KnightController:

public KMStarController dragon;
public float speedMod = 1.0f;
public WayPointSpeedModifiers FromModifiers;
public WayPointSpeedModifiers ToModifiers;

Alright! So far so good. Lets break this down a bit.

  • KMStarController dragon – The KnightController is going to follow the Dragon. We hold onto KMStarController component from the Dragon in here.
  • float speedMod – While KMStarController holds our base speed, the KnightController will contain our modified speed (hence, speedmod). You’ll see when we modify our speed later…
  • WayPointSpeedModifiers FromModifiers and WayPointSpeedModifiers ToModifiers – OK, let me explain this one a bit. We’re setting this up in a way that, when the Knight is on a particular tile type, its’ speed gets modified (FromModifiers), and when it moves to another tile, its’ speed is modified further (ToModifiers). If our Knight is set up to have a base speed of 10, to move at 3/4 its base speed when on a Snow tile, and 3/4 the speed when moving to a Snow tile, then going from Snow-to-Snow will have it moving at (10 * 0.75 * 0.75) 5.625 units.

OK. So that’s going to be a bit on the heavy side, but, I promise, it sounds scarier than it is. Lets start off with some overrides! First off, OnGetPath is not doing anything special. Just call its base class’s OnGetPath and move on.

protected override void OnGetPath(List path)
{
	base.OnGetPath(path);
}

PreFindPath is a different story, though. if you remember in KMStarController.RecalculatePath, we call PreFindPath before we start looking for a new path to the goal. In the DragonController, that goal was random. In here, the goal is the current tile that the Dragon is sitting on. That’s why we needed access to the Dragon’s KMStarController; so we could have access to its currentWaypoint.

protected override void PreFindPath()
{
	this.targetWaypoint = dragon.currentWaypoint;
}

Lastly, we define MoveSpeedModifier, which, as you can expect, acts as an accessor to speedMod.

protected override float MoveSpeedModifier()
{
	return speedMod;
}

OK, little guys out of the way, here’s the big override: OnNextWaypoint.

I’m not even going to beat around the bush. Here’s the code:

protected override void OnNextWaypoint()
{
    if(previousWaypoint != null && currentWaypoint != null)
    {
        WaypointType wptypeFrom = previousWaypoint.GetComponent();
        WaypointType wptypeTo = currentWaypoint.GetComponent();
        if (wptypeFrom != null)
        {
            switch (wptypeFrom.Value)
            {
                case WaypointType.WPType.Null:
                    speedMod = FromModifiers.NullMod;
                    break;
                case WaypointType.WPType.Grass:
                    speedMod = FromModifiers.GrassMod;
                    break;
                case WaypointType.WPType.Water:
                    speedMod = FromModifiers.WaterMod;
                    break;
                case WaypointType.WPType.Sand:
                    speedMod = FromModifiers.SandMod;
                    break;
                case WaypointType.WPType.Snow:
                    speedMod = FromModifiers.SnowMod;
                    break;
                case WaypointType.WPType.Mountain:
                    speedMod = FromModifiers.MountainMod;
                    break;
                case WaypointType.WPType.Bridge:
                    speedMod = FromModifiers.BridgeMod;
                    break;
                case WaypointType.WPType.Town:
                    speedMod = FromModifiers.TownMod;
                    break;
            }
        }
        else
        {
            speedMod = 1.0f;
        }
        if (wptypeTo != null)
        {
	    switch (wptypeTo.Value)
            {
                case WaypointType.WPType.Null:
                    speedMod *= ToModifiers.NullMod;
                    break;
                case WaypointType.WPType.Grass:
                    speedMod *= ToModifiers.GrassMod;
                    break;
                case WaypointType.WPType.Water:
                    speedMod *= ToModifiers.WaterMod;
                    break;
                case WaypointType.WPType.Sand:
                    speedMod *= ToModifiers.SandMod;
                    break;
                case WaypointType.WPType.Snow:
                    speedMod *= ToModifiers.SnowMod;
                    break;
                case WaypointType.WPType.Mountain:
                    speedMod *= ToModifiers.MountainMod;
                    break;
                case WaypointType.WPType.Bridge:
                    speedMod *= ToModifiers.BridgeMod;
                    break;
                case WaypointType.WPType.Town:
                    speedMod *= ToModifiers.TownMod;
                    break;
            }
        }
    }
}

So, the scary part of all this is just those 2 big switch statements. But I’m going to break this down, very frankly, to get the basic ideas across.

  • First off, we check to make sure neither our previousWaypoint and currentWaypoint are null.
  • Next, we go and grab the WaypointTypes from the previousWaypoint and currentWaypoint.
  • Then, we check to make sure our WaypointTypes are not null, and then drop into the switch statements, where we modify the speedMod. That’s all.

Big and scary, yet not at all.

OK! That’s it for the code! Now it’s time to put all of together!

Make The World Come Alive!

Alright, it’s time we meet our fearless heroes and fearful dragon!

heroAnims

In the scene, you’re going to make 4 GameObjects, give them some animations/sprites, throw on the DragonController on one, the KnightController on the rest, and set them up as such:

knightCards-Dragon

knightCards-Knight

knightCards-Mage

knightCards-Rogue

knightCards-FishMan

Now that they’re all set up, just place them on the tiles they’re starting at, and it the Play button, and watch them go. You’ll see the Dragon have no regard to heuristic costs, the Knight will follow a path set up strictly by score alone, the Mage will move in fairly straight lines when he can, the Rogue will take some interesting paths, and the FishMa–I mean, Cody– Will try to stay in the water!

And there you have it, folks. A working A* Pathfinding system. Finally complete.

>>> Finally, The Conclusion! >>>

map_heroes

Advertisements