A* Pathfinding Project

Objects stop moving while pathing


#1

Backstory: I’m trying to iterate on Dragon Force, a Sega Saturn game from 1996. Here’s the type of combat I’m trying to recreate: YouTube

So here’s a video of what I’m seeing. A troop will acquire the nearest target and move towards it. However, with ranged attacks, spells, and knock-backs it’s likely they’ll need to constantly be checking to see if there’s a better target for them.

So here’s my code with the caveat that I’m somewhat new to gamedev but completely new to A* pathfinding. The issue I’m trying to solve is everyone randomly stopping but if you could provide insight or point me in a better direction I’d appreciate that a ton as well.

Each troop is using this mobility script:

using UnityEngine;
using Pathfinding;
using static DragonFauxCore;

public class TroopMobility : MonoBehaviour
{
public Transform target;
public string opponent;

private void Start()
{
       opponent = gameObject.CompareTag("Player") ? "Enemy" : "Player";
        target = GetClosestEnemy(opponent);
        gameObject.GetComponent<TroopDestinationSetter>().target = target;
}

private void Update()
{
if (GetClosestEnemy(opponent) != target)
                {
                    target = GetClosestEnemy(opponent);
                    gameObject.GetComponent<TroopDestinationSetter>().target = target;
                    Debug.Log(gameObject.name + " updating target to " + target);
                }
}

    private Transform GetClosestEnemy(string opponent)
    {
        GameObject[] enemies = GameObject.FindGameObjectsWithTag(opponent);
        Transform bestTarget = null;
        float closestDistance = Mathf.Infinity;
        Vector3 currentPosition = transform.position;

        foreach (GameObject enemy in enemies)
        {
            float distance = Vector3.Distance(enemy.transform.position, currentPosition);
            if (distance < closestDistance)
            {
                closestDistance = distance;
                bestTarget = enemy.transform;
            }
        }
        return bestTarget;
    }
}

The thought is if their current target is the same as their bestTarget then nothing gets pushed to <TroopDestinationSetter> which is literally just the stock <AIDestinationSetter> but I’ve added an offset so the troops aren’t trying to stand on top of each other.

namespace Pathfinding
{
public class TroopDestinationSetter : VersionedMonoBehavior
  {
     . . .
        void Update()
        {
            if (target != null && ai != null) ai.destination = TargetOffset(target);
        }

        private Vector3 TargetOffset(Transform target)
        {
            // We want the target destination to be just to the left or
            // right of the target, not the target itself.

            float offset = (gameObject.transform.position.x > target.transform.position.x) ? .5f : -.5f;
            Vector3 offsetTarget = new Vector3(target.transform.position.x + offset, target.transform.position.y, target.transform.position.z);

            return offsetTarget;
        }
  }
}

That’s what I’ve got so far. I’d also love some insight into how to make the troops go around each other to try and focus an enemy from both sides instead of standing in a line :laughing:but I can keep playing around with that.

Thanks in advance!


#2

Hey,

Looks like you’re already making lots of progress! Good work It’s already starting to look like a game.

This reply has 2 parts; the first going over your code a little and giving a few pointers of improvements that could be made coding wise, no logic changes. Everyone always has their own coding style, so do take my suggestions with a grain of salt, though there are a few ‘beginner’ pitfalls that I want to help you understand and how to work around them :slight_smile: Though if your code works it works, this is purely advice.
Second I’ll try to describe a different approach to your problem and put you in the right direction to solve your problem. There is always multiple solutions to a problem, so keep an open mind to different solutions.

Possible Code Improvements
mobility script

using Pathfinding;
using UnityEngine;

using static DragonFauxCore;

public class TroopMobility : MonoBehaviour
{
    public Transform target;
    public string opponent;

    private TroopDestinationSetter myDestinationSetter;
    private GameObject[] enemies;

    private void Start()
    {
        opponent = gameObject.CompareTag("Player") ? "Enemy" : "Player";

        //Get Component is actually a rather slow function, so in Unity we tend to do try to use it as little as possible,
        //caching the result will save us from having to run this slow function multiple times
        myDestinationSetter = gameObject.GetComponent<TroopDestinationSetter>();

        //Same as the Get component, FindGameObjects is a really slow Unity function, so we want to save the result. 
        //However by doing this agents that die won't be removed from this list.
        //Usually you want to make some sort of manager to hold a reference to all the agents on the field,
        //that manager could have a list shared between all agents that will update when an agent dies.
        enemies = GameObject.FindGameObjectsWithTag(opponent);
    }

    private void Update()
    {
        //Temporarily savign the result of GetClosestEnemy will allow us to only call GetClosestEnemy once, rather than twice :)
        Transform newTarget = GetClosestEnemy();

        if (newTarget != target)
        {
            target = newTarget;
            //use the cached version of our destination setter.
            myDestinationSetter.target = target;

            Debug.Log(gameObject.name + " updating target to " + target);
        }
    }

    private Transform GetClosestEnemy()
    {
        Transform bestTarget = null;
        //Mathf.infinity is personally a bit weird to use, since it doesn't have an actual numerical value.
        //I don't think it's wrong to us it, though I'd have more trust in float.MaxValue
        float closestDistance = float.MaxValue;
        Vector3 currentPosition = transform.position;

        foreach (GameObject enemy in enemies)
        {
            float distance = Vector3.Distance(enemy.transform.position, currentPosition);
            if (distance < closestDistance)
            {
                closestDistance = distance;
                bestTarget = enemy.transform;
            }
        }
        return bestTarget;
    }
}

There is definitely some more room for improvement, though some would require some logic change.
Like adding a manager with 2 lists, one for each type of agent ( player and enemy) that auto updates on player death.
Another performance oriented update is replacing Distance with DistanceSqr since we don’t need the actual distance, but rather just want to know if it’s closer or further. …

TroopsDestinationSetter

//can be simplified into a one liner :)
return target.position + Vector3.right * 0.5f * Mathf.Sign(transform.position.x - target.position.x);

Positioning system
Now to the fun part, getting agents to pick a smart destination.

Here is one suggested solution.
Rather than thinking about it as I have X amount of enemies, think about it as I have N amount of positions to stand, where N positions = X amount of enemies * 2
One left of the enemy, one to the right of the enemy.
Now you need to find what Agent needs to go to which position. For this you could find the closest position and assign it.
Or you could do some fancy patsy stuff, and use an algorithm ( for example the Hungarian Algorithm ) to make more informed decisions of what agent should go where.

I hope that gave you some new thoughts and ideas to play with, let us know what your results were :slight_smile:
If you have any further questions, feel free to reach out

Toasty - Wolf


#3

Wow, thank you so much! So thorough and kind. However, this is honestly a blessing and a curse :sweat_smile:- first, because I learned a lot and if 200+ troops are trying to run this script on every frame it’s gonna get real slow real fast. But the curse piece is now I’m second-guessing everything else I’m doing :laughing:

Performance Tweaks

I dropped in all of your suggested changes plus I made a CombatManager who houses the lists of troops (and will handle other stuff like battle time, stats, etc.). It’s an object using the aptly named CombatManager tag for easy location and this simple script:

public class CombatManager : MonoBehaviour
{
    public List<GameObject> PlayerTroops = new List<GameObject>();
    public List<GameObject> EnemyTroops = new List<GameObject>();

    public void Awake()
    {
        PlayerTroops.Clear();
        EnemyTroops.Clear();
    }
}

But then I’m having trouble finding a clean way for my generic troop script to know which list to add/remove itself to/from. Not only will troops need to be removed from the list when they die, but revives/summons will need to add them as well so here’s where I landed but be warned—it’s ugly.

public class Troop : MonoBehaviour
{
    private void Start()
    {
        combatManager = GameObject.FindWithTag("CombatManager").GetComponent<CombatManager>();

        if (gameObject.CompareTag("Player"))
        {
            combatManager.PlayerTroops.Add(gameObject);
        }
        else
        {
            combatManager.EnemyTroops.Add(gameObject);
        }

    }

    private void OnDisable()
    {
        if (gameObject.CompareTag("Player"))
        {
            combatManager.PlayerTroops.Remove(gameObject);
        }
        else
        {
            combatManager.EnemyTroops.Remove(gameObject);
        }
    }
}

I poked around and it doesn’t seem you can call a function from a ternary operator so this was the best option I suppose? The issue I’m running into now is that I’m writing a lot of repetitive code because I’m trying to break functionality out into separate scripts.

For example, my TroopMobility script needs to know about the CombatManager so it can scan the list but so does my Troop core so it can add/remove so now I’m making multiple FindWithTag calls. Then other stuff like how TroopDamage and TroopMobility both need to know what their tag is so they know who their opponent is. Trying to sync all this information across scripts on the same object feels so clunky.

Pathfinding

But honestly, all of that :point_up: has more to do with basic programming and not pathfinding which is why I came here so apologies if it’s too off-topic! Even with the updates, my units are still randomly standing still in the middle of pathing and will sometimes randomly start back up and other times just stay frozen and I can’t figure out why.

At first, I thought it had to do with setting the target too frequently but the whole target != newTarget thing stops that from happening. It seems to happen much more often when there’s a higher number of troops on the field. I’m wondering if it has to do with how I have my Seeker or AIPath settings, but even tweaking those isn’t yielding very different results.

Positioning

While the Hungarian Algorithm was an interesting read, it was way over my head on implementation :laughing:
Honestly, after watching all of the videos and demos on A* I assumed it would handle this kind of thing for me. I can’t figure out why the troops assume their “best path” is to stand in line behind each other instead of moving around the “obstacles” of each other to get to their goal.

Even in the simplest example like you said where there are 2 positions per enemy: front and back. How am I to tell a troop that the front position is “taken” or “occupied” and they should go around back? I came across a bit about MultiTargetPath in the docs which sounds like it may do the deed but I’d need to upgrade to pro first. But is that at least on the right track?


#4

I’m happy to help :slight_smile:

To prevent code duplication between player troops and enemy troops you could split the code up even more. I’ve quickly written down a very bare manager, based on what you already have here :slight_smile:

This isn’t perfect, but I hope it should give you some insight of how you can structure some of these components. Also I didn’t write this in engine, I wrote them by heart, so there might be a few small mistakes + some components you still have to fill in.

public class CombatManager : MonoBehaviour
{
    public TroopManager playerTroopManager;
    public TroopManager enemyTroopManager;

    public void Start()
    {
        playerTroopManager = new TroopManager();
        enemyTroopManager = new TroopManager();

        playerTroopManager.Initalize(this, enemyTroopManager);
        enemyTroopManager.Initalize(this, playerTroopManager);
    }

    public void Update()
    {
        playerTroopManager.UpdateTargetPositions();
        enemyTroopManager.UpdateTargetPositions();
    }
}

public class TroopManager
{
    public CombatManager combatManager { get; private set; };
    public TroopManager oposingTroopManager { get; private set; };

    public List<Troop_Core> myTroops = new List<Troop_Core>();

    private List<Vector3> allGeneratedTargetPositions = new List<Vector3>();

    public void Initialize(CombatManager combatManager, TroopManager oposingTroopManager)
    {
        combatManager = combatManager;

        for (int i = 0; i < intAmountOfTroops; i++)
        {
            GameObject newTroopGameObject = Instantiate(TroopGameObject);
            Troop_Core newTroop = newTroopGameObject.GetComponent<Troop_Core>();
            myTroops.Add(newTroop);
        }

        foreach (Troop_Core troop in myTroops)
        {
            newTroop.Initalize(this);
        }
    }

    //Only used to add troops when the game has already started
    public void AddTroop(Troop_Core newTroop)
    {
        myTroops.Add(newTroop);
        newTroop.Initalize(this);
    }

    public void RemoveTroop(Troop_Core troopToRemove)
    {
        myTroops.Remove(troopToRemove);
    }

    public void UpdateTargetPositions()
    {
        List<Vector3> allTargetPositions = oposingTroopManager.GetAllTargetPositions();
        foreach (Troop_Core troop in myTroops)
        {
            Vector3 troopPos = troop.transform.position;

            Vector3 closestTargetPos = troopPos;
            float closestDistanceSqr = float.MaxValue;

            foreach (Vector3 targetPos in allTargetPositions)
            {
                float distanceSqr = Vector3.distanceSqr(troopPos, targetPos);
                if (distanceSqr < closestDistanceSqr)
                {
                    closestDistanceSqr = distanceSqr;
                    closestTargetPos = targetPos;
                }
            }

            if (closestDistanceSqr != float.MaxValue)
            {
                allTargetPositions.Remove(closestTargetPos);
            }

            troop.SetDestination(closestTargetPos);
        }
    }

    public List<Vector3> GetAllTargetPositions()
    {
        allGeneratedTargetPositions.Clear();

        foreach (Troop_Core troop in myTroops)
        {
            Vector3 troopPos = troop.transform.position;
            Vector3 offset = 0.5f * Vector3.Right;

            allGeneratedTargetPositions.add(troopPos + offset);
            allGeneratedTargetPositions.add(troopPos - offset);
        }

        return allGeneratedTargetPositions;
    }
}

Rather than using the tags on the game objects you could structure your data to already know what are enemies or player troops.

secondly you might have noticed that I don’t treat toops as Transforms, but Troop_Core, the goal of Troop_Core is to connect all sub troop scripts together, something like:

public class Troop_Core : MonoBehaviour
{
    public Troop_Health troopHealth;
    public Troop_Movement troopMovement;
    public Troop_Animation troopAnimation;
    ...

    public TroopManager myManager;

    public void Initalize(TroopManager manager)
    {
        myManager = manager;
    }

    public void SetDestination(Vector3 targetPos)
    {
        troopMovement.destination = targetPos;
    }
}

Positioning
In the manager example I already added a quick implementation of a possible solution to finding final target positions.
However I also have a bit better understanding of the root of your problem. A* pathfinding does NOT care where other agents are. It only finds a path form A to B.
In the pro version of A* you get access to RVO which is a local avoidance system, a system that influences all agents movement directions based on their desired directions.
Though in your case you might get away by blocking the Graph Node underneath fighting agents.
There is a small tutorial on how to implement this available here: https://arongranberg.com/astar/docs/turnbased.html


#5

Hey I’ve been caught up with work lately and haven’t had a chance to hop back on this just yet but I didn’t want to completely ghost you: thank for you all of this, I’m excited to dive back in with this info when I can!