[Solved!] A* Pathfinding Issues

[iTz_WyTe]

Hey there!

I’ve started working on my very first project with a friend and things have been going swimmingly! We have encountered one problem that has caused us quite and issue, though.

ITz_WyTe's Pastebin - Pastebin.com

(Second Error) Imgur: The magic of the Internet

In the scripts below, I call “UpdatePath” every time a node changes (i.e. a tower is placed or destroyed on the grid of nodes) so that the units will recalculate their path and go around the towers. The bit of code at the bottom of the PathRequestManager script is the last solution I found to updating every unit’s path. This worked perfectly, however it seems that if a unit dies while this is happening I get a ‘Reference is null’. I also get an error if I run “UpdatePath” when a unit is within 1 node from the end of the path. This gives me an 'Array Index is out of Range" error.
I have tried putting in if(unit == null) return; checks everywhere, I have tried to create a static list of active units to update and have units remove when they die. I just cannot seem to shake these 2 errors. Please. Any help you can provide will truly be appreciated. Thank you!

First Error:

IndexOutOfRangeException: Array index is out of range.

Unit+c__Iterator0.MoveNext () (at Assets/Scripts/Unit.cs:51)

UnityEngine.SetupCoroutine.InvokeMoveNext (IEnumerator enumerator, IntPtr returnValueAddress) (at C:/buildslave/unity/build/Runtime/Export/Coroutines.cs:17)

UnityEngine.MonoBehaviour:StartCoroutine(String)

Unit:OnPathFound(Vector3[ ], Boolean) (at Assets/Scripts/Unit.cs:43)

PathRequestManager:FinishedProcessingPath(Vector3[ ], Boolean) (at Assets/Scripts/PathRequestManager.cs:37)

c__Iterator0:MoveNext() (at Assets/Scripts/Pathfinding.cs:80)

UnityEngine.SetupCoroutine:InvokeMoveNext(IEnumerator, IntPtr)

Second Error:

MissingReferenceException: The object of type ‘Unit’ has been destroyed but you are still trying to access it.

Your script should either check if it is null or you should not destroy the object.

Unit.OnPathFound (UnityEngine.Vector3[ ] newPath, Boolean pathSuccessful) (at Assets/Scripts/Unit.cs:42)

PathRequestManager.FinishedProcessingPath (UnityEngine.Vector3[ ] path, Boolean success) (at Assets/Scripts/PathRequestManager.cs:37)

Pathfinding+c__Iterator0.MoveNext () (at Assets/Scripts/Pathfinding.cs:80)

UnityEngine.SetupCoroutine.InvokeMoveNext (IEnumerator enumerator, IntPtr returnValueAddress) (at C:/buildslave/unity/build/Runtime/Export/Coroutines.cs:17)

[manifestus]

Hey!

Your first error is quite simple, try increment your map size by 1 when creating your map; when Unit reaches the edge of your map it throws index out of range, because your map size is one node short.

And your second error I assume that you Unit reaches goal and dies while still searching for path. What happens is your PathRequestManager tries to access a destroyed unit.
Here’s few things you could do to avoid this:

1. Don’t search for path if Unit is close to the target. (Currently you are checking if gameObject is null in your Unit script, this will always be false, since the script is called anyways) Try checking the distance:

if(Vector3.Distance(transform.position, target.position) < 1f) return;

2. You could save path requesting GameObject to the pathRequest info and check if gameobject is null when PathRequestManager finds a path.

Let me know if these solutions help you

[lordconstant]

When a unit gets to the end you could set it to inactive and add it to a list of to be destroyed, then wait for a good time to destroy and also avoid running extra actions on a gameobject prepped to destroy.

[iTz_WyTe]

@manifestus

Hey!

Your first error is quite simple, try increment your map size by 1 when creating your map; when Unit reaches the edge of your map it throws index out of range, because your map size is one node short.

And your second error I assume that you Unit reaches goal and dies while still searching for path. What happens is your PathRequestManager tries to access a destroyed unit.
Here’s few things you could do to avoid this:

1. Don’t search for path if Unit is close to the target. (Currently you are checking if gameObject is null in your Unit script, this will always be false, since the script is called anyways) Try checking the distance:

if(Vector3.Distance(transform.position, target.position) < 1f) return;

2. You could save path requesting GameObject to the pathRequest info and check if gameobject is null when PathRequestManager finds a path.

Let me know if these solutions help you

Hey, thanks a TON for replying, I really appreciate it!

I tried your solution for the first problem and it doesn’t seem to fix the issue. I kind of found the reasoning behind it myself. In the Pathfinding script at line 105 we added a -1 to waypoints.Add(path*.worldPosition); in order to make the units move all the way into the final node instead of reaching their destination as soon as they’re 1 node away. If we remove this -1 it actually fixes the problem, but then we’re stuck with the units stopping 1 node short of completing the path. Although this is functional, it doesn’t quite achieve the aesthetic we would like. With this knowledge, do you see a solution to how we could complete the path and fix the first issue?*
Your solution for the second issue was close, but the issue does not have to do with just when units are toward the end of the path. If a unit finishes the path OR if a unit is destroyed by a tower, the error will show. I really just need a way to check if the unit is destroyed before it tries to update the path. I though maybe it would work if I put checks in the “UpdatePaths” function of the PathRequestManager, but it doesn’t seem to do the trick.
Again, thank you so much for your help, I really appreciate it! Let me know if there’s anything I can do to elaborate or make this clearer!

[iTz_WyTe]

@manifestus

Hey!

Your first error is quite simple, try increment your map size by 1 when creating your map; when Unit reaches the edge of your map it throws index out of range, because your map size is one node short.

And your second error I assume that you Unit reaches goal and dies while still searching for path. What happens is your PathRequestManager tries to access a destroyed unit.
Here’s few things you could do to avoid this:

1. Don’t search for path if Unit is close to the target. (Currently you are checking if gameObject is null in your Unit script, this will always be false, since the script is called anyways) Try checking the distance:

if(Vector3.Distance(transform.position, target.position) < 1f) return;

2. You could save path requesting GameObject to the pathRequest info and check if gameobject is null when PathRequestManager finds a path.

Let me know if these solutions help you

OH HEY!

Second follow up quick!

I fixed the second error by passing in a check to see if the unit’s health was > 0 on the “OnPathFound” function on the Unit script. I then have its health set to 0 before being destroyed. This problem is fixed!

As far as the first error is concerned- the ray index error. This is still a problem Although removing the -1 did fix the issue of the error showing up, it does actually make the pathfinding kind of wonky. The units cut corners when pathing without this -1 included. Any ideas on how we might work around that?

[lordconstant]

@iTz_WyTe

OH HEY!

Second follow up quick!

I fixed the second error by passing in a check to see if the unit’s health was > 0 on the “OnPathFound” function on the Unit script. I then have its health set to 0 before being destroyed. This problem is fixed!

As far as the first error is concerned- the ray index error. This is still a problem Although removing the -1 did fix the issue of the error showing up, it does actually make the pathfinding kind of wonky. The units cut corners when pathing without this -1 included. Any ideas on how we might work around that?

There is an issue in your simplify path function, when a change of direction occurs you add a new node, but if there is a straight line to the end it wont and the target position you are actually trying to get to. Keep the -1, but after the loop add the end nodes position regardless.

The reason the cut cornering is occurring is due to the direction change getting picked up by the next node along, not the node at the corner. E.g. A to B is forward, with -1 A gets added, without it B does. B to C is also forward so its ignored. C to D is a left, with -1 C is the added point, making our first line A to C, but if you drop the -1 D gets added, so its B to D causing the cut corner.

[lordconstant]

Finally tracked down your array index error. In Unit.FollowPath you call path[0], but you dont have a path. Your path finder finds one node, the node the units stood on. It then says the path find was a success, it goes to simplify and since your list is only 1 in length and your loop starts at 1 not 0 the loop never runs, so no nodes are added.

You may want to change your simplify path function so that it adds the first node, starts the loop at 1, looks forward instead of backwards so + 1 instead of -1, that way you can drop the -1 when adding a new point, loop to length - 1. Then add the last node, if the path is longer than 1.

[iTz_WyTe]

@lordconstant

Finally tracked down your array index error. In Unit.FollowPath you call path[0], but you dont have a path. Your path finder finds one node, the node the units stood on. It then says the path find was a success, it goes to simplify and since your list is only 1 in length and your loop starts at 1 not 0 the loop never runs, so no nodes are added.

You may want to change your simplify path function so that it adds the first node, starts the loop at 1, looks forward instead of backwards so + 1 instead of -1, that way you can drop the -1 when adding a new point, loop to length - 1. Then add the last node, if the path is longer than 1.

Thanks for responding, lordconstant!

I see what you’re saying and I tried to implement such a thing, but it seems I’m not quite getting it correct. I tried making these changes to the SimplifyPath:

Vector3[ ] SimplifyPath(List path) {
List waypoints = new List ();
Vector2 directionOld = Vector2.zero;

for (int i = 0; i < path.Count; i++) {
Vector2 directionNew = new Vector2 (path [i + 1].gridX, path [i + 1].gridY);
if (directionNew != directionOld) {
waypoints.Add(path*.worldPosition);*
}
directionOld = directionNew;
}
return waypoints.ToArray ();
}
and then I changed unit.FollowPath’s currentWaypoint to 1, but I guess I’m missing something. I don’t mean to ask you to hold my hand hear, but could you clarify what it is I’m missing?
Thanks again!

[lordconstant]

@iTz_WyTe

Thanks for responding, lordconstant!

I see what you’re saying and I tried to implement such a thing, but it seems I’m not quite getting it correct. I tried making these changes to the SimplifyPath:

Vector3[ ] SimplifyPath(List path) {
List waypoints = new List ();
Vector2 directionOld = Vector2.zero;

for (int i = 0; i < path.Count; i++) {
Vector2 directionNew = new Vector2 (path [i + 1].gridX, path [i + 1].gridY);
if (directionNew != directionOld) {
waypoints.Add(path*.worldPosition);*
}
directionOld = directionNew;
}
return waypoints.ToArray ();
}
and then I changed unit.FollowPath’s currentWaypoint to 1, but I guess I’m missing something. I don’t mean to ask you to hold my hand hear, but could you clarify what it is I’m missing?
Thanks again!

You dont need to change Unit.Followpath that was just failing due to simplify path messing up.

The function should look like:

Vector3[] SimplifyPath(List<Node> path) {
        List<Vector3> waypoints = new List<Vector3> ();
        Vector2 directionOld = Vector2.zero;
        waypoints.Add(path[0].worldPosition);
        for (int i = 1; i < path.Count - 1; i++) {
            Vector2 directionNew = new Vector2 (path [i + 1].gridX, path [i + 1].gridY);
            if (directionNew != directionOld) {
                    waypoints.Add(path[i].worldPosition);
            }
            directionOld = directionNew;
        }

        if(path.Count > 1)
             waypoints.Add(path[path.Count-1].worldPosition;
        return waypoints.ToArray ();
    }

[iTz_WyTe]

@lordconstant

You dont need to change Unit.Followpath that was just failing due to simplify path messing up.

The function should look like:

Vector3[] SimplifyPath(List<Node> path) {
        List<Vector3> waypoints = new List<Vector3> ();
        Vector2 directionOld = Vector2.zero;
        waypoints.Add(path[0].worldPosition);
        for (int i = 1; i < path.Count - 1; i++) {
            Vector2 directionNew = new Vector2 (path [i + 1].gridX, path [i + 1].gridY);
            if (directionNew != directionOld) {
                    waypoints.Add(path[i].worldPosition);
            }
            directionOld = directionNew;
        }

        if(path.Count > 1)
             waypoints.Add(path[path.Count-1].worldPosition;
        return waypoints.ToArray ();
    }

So I implemented the code you suggested, and it fixes things in a way. Now it looks as through the units are creating a waypoint for every node between them and the target. This is fine, but my concern would only be about potential performance issues. Is this a reasonable concern do you think?

Also, this fix makes it so that the unit still completes its path 1 node from its target as opposed to ending on the target itself. Any ideas on how we might fix this?

Thanks so much for all you’ve done already. Aside from these things, the pathfinding actually works now, we can more or less play our game without any errors thrown!

[lordconstant]

Sorry I messed up a line:

Vector2 directionNew = new Vector2 (path [i].gridX - path [i + 1].gridX, path [i].gridY - path [i + 1].gridY);

As for the one short issue I cant find any faults on the code that will cause it, it could be in “Node targetNode = grid.NodeFromWorldPoint(targetPos);” if the position is getting the wrong node. Does the Unit still get destroyed or do they not reach the end and stop?

[iTz_WyTe]

Hey no worries, I was able to work out the code above. The units are still destroyed, but they are destroyed 1 node before the target node. I’d like them to be destroyed on the same node as the target.

[iTz_WyTe]

@lordconstant

Sorry I messed up a line:

Vector2 directionNew = new Vector2 (path [i].gridX - path [i + 1].gridX, path [i].gridY - path [i + 1].gridY);

As for the one short issue I cant find any faults on the code that will cause it, it could be in “Node targetNode = grid.NodeFromWorldPoint(targetPos);” if the position is getting the wrong node. Does the Unit still get destroyed or do they not reach the end and stop?

Lordconstant!

You are my hero. After I plugged in the update on directionNew, it completely fixed the problem, it seems. The units are going completely to their target, I’m not getting any array index errors when I’m updating path. It’s perfect. I really appreciate this a ton. You have been an incredible help! Thank you sooooooo much!