seblague / pathfinding Goto Github PK

Hi guys , i have this problem , anyone know how to solve it? I think is something about corners but idk sure . I want the unit to not be able to go between them .

Hello Seblague,
Great projects and great scripting also just wanted to ask how can i make the path be updated dynamically while run time to make the seekers always follow the target whenever the target is moved during runtime.
if you have any idea please reply i will be a great help.
Thank in advance.

I know it's minor changes, but the code changes from E06 aren't here, and would be appreciated, I'm sure :)

Referring to Wikipedia, there, hCost( Wiki call it fScore) should be the sum of distance and gCost.

I didn't compile your script, but I implemented it in Python, and in the beginning, I always find something wrong. After I changed it in the Wiki's way, it worked.

Implementation returns sub-optimal paths in rare occasions.

Example:
The path to the right side is sub-optimal.

This is due to the implementation skipping neighbor nodes in the closedSet without checking their comparative gCost to the currently opened cell's selected neighbor, resulting in a neighbor with a higher cost occasionally being selected.

Code illustration & proposed fix:
Starting at line 44 in episode 4

				foreach (Node neighbour in grid.GetNeighbours(currentNode)) {
					if (!neighbour.walkable || closedSet.Contains(neighbour)) {
						continue;
					}
					
					int newMovementCostToNeighbour = currentNode.gCost + GetDistance(currentNode, neighbour);
					if (newMovementCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour)) {

Fix:

				foreach (Node neighbour in grid.GetNeighbours(currentNode)) {
					if (!neighbour.walkable || (closedSet.Contains(neighbour) && newMovementCostToNeighbour >= neighbour.gCost)) {
						continue;
					}
					
					int newMovementCostToNeighbour = currentNode.gCost + GetDistance(currentNode, neighbour);
					if (newMovementCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour)) {

It could be that you left this out for optimisation reasons, seeing as you could easily implement a way to check if one of the neighbours is your target tile before even calling the regular algorithm,

But the algorithms implementation (at least after episode 5) cannot find the path to it's direct neighbour.

Here's a proposed fix:

// in Pathfinding.cs

// in
    Vector3[] SimplifyPath(List<Tile> path)
    {
        List<Vector3> waypoints = new List<Vector3>();
        Vector2 directionOld = Vector2.zero;

        // ***************
        // Add this to make sure we do not just ignore the case where path.Count == 1
        // before even checking the rest
        //  **************
        if (path.Count == 1)
        {
            waypoints.Add(path[0].worldPos);
            return waypoints.ToArray();
        }

        for (int i = 1; i < path.Count; i++)
        {
            Vector2 directionNew = new Vector2(path[i - 1].gridCoords.x - path[i].gridCoords.x,
                                               path[i - 1].gridCoords.y - path[i].gridCoords.y);
            if (directionNew != directionOld)
            {
                // Also of importance: 
                // We start at i = 1, but we need to check all the way to the origin! so [i-1]
                waypoints.Add(path[i-1].worldPos);
            }
            directionOld = directionNew;
        }
        return waypoints.ToArray();
    }

This does only set another node as current if the h-cost is also lower not just the f-cost - also the first if does not make much sens since it can be rewritten as a single <=. In the respective video you use another version (https://youtu.be/mZfyt03LDH4?t=331) that might actually work because of associativity rules of || and && essentially leading to something like "lower f OR (equal f AND lower h)".

I was implementing a-star in plain C for fun after watching your videos and that bit confused me because I of course though I made an error somewhere else. Thanks for the inspiration - your videos are great.

How to walk to the next target when reach the current target object ?
-I need use the bot character collect all coin(game object) in the game.

Not sure how to fix or address this. I'd like to add multiple layers to unwalkable.
Doesn't seem to work, I thought the checking multiple in the editor drop down would work.

Looked a bit deeper and I guess because my 'water' layer is under everything it makes the whole area "unwalkable" ??

I might be sleepy but shouldn't this

say something like new Thread(threadStart).Start(); instead of threadStart.Invoke(); since ThreadStart only is a delegate and not a threadwrapper.

i think in penalties horizontal u swap between raw and columns
`

for (int y = 0; y < gridSizeY; y++) {
			for (int x = -kernelExtents; x <= kernelExtents; x++) {
				int sampleX = Mathf.Clamp (x, 0, kernelExtents);
				penaltiesHorizontalPass [0, y] += grid [sampleX, y].movementPenalty;
			}

			for (int x = 1; x < gridSizeX; x++) {
				int removeIndex = Mathf.Clamp(x - kernelExtents - 1, 0, gridSizeX);
				int addIndex = Mathf.Clamp(x + kernelExtents, 0, gridSizeX-1);

				penaltiesHorizontalPass [x, y] = penaltiesHorizontalPass [x - 1, y] - grid [removeIndex, y].movementPenalty + grid [addIndex, y].movementPenalty;
			}
		}

cause for this it should go vertically right not horizontal correct me if i'am wrong

Hello Sebastian Lague,

I would like to ask how to prevent my prefabs using Astar from stopping movement when one of them has already found the target, and how to reactivate pathfinding when the prefab has already reached the target.

Thank you for this project. It's really great. I'm using it in my Never Split the Party game.

Unfortunately, it's doing a ton of unnecessary memory allocation. Something like 30k of memory for each path find in my usage. With several enemies updating their paths often it was often allocating 150k per frame!

Here's how I optimized it.

Change Point from a class to a struct. Value types are allocated on stack instead of heap. They also do better in arrays since there's no reference operation.

In PathFinding._ImpFindPath make openSet and closedSet static and just clear them instead of recreating them. That makes them non-thread safe but I'm not doing anything fancy with threads I don't think.

Changed Grid.GetNeighbours to be an IEnumerable.

`
///

        switch (distanceType)
        {
            case Pathfinding.DistanceType.Manhattan:
                y = 0;
                for (x = -1; x <= 1; ++x)
                {
                    var neighbor = AddNodeNeighbour(x, y, node);
                    if (neighbor != null)
                        yield return neighbor;
                }

                x = 0;
                for (y = -1; y <= 1; ++y)
                {
                    var neighbor = AddNodeNeighbour(x, y, node);
                    if (neighbor != null)
                        yield return neighbor;
                }
                break;

            case Pathfinding.DistanceType.Euclidean:
                for (x = -1; x <= 1; x++)
                {
                    for (y = -1; y <= 1; y++)
                    {
                        var neighbor = AddNodeNeighbour(x, y, node);
                        if (neighbor != null)
                            yield return neighbor;
                    }
                }
                break;
        }
    }

    /// <summary>
    /// Adds the node neighbour.
    /// </summary>
    /// <returns><c>true</c>, if node neighbour was added, <c>false</c> otherwise.</returns>
    /// <param name="x">The x coordinate.</param>
    /// <param name="y">The y coordinate.</param>
    /// <param name="node">Node.</param>
    /// <param name="neighbours">Neighbours.</param>
    Node AddNodeNeighbour(int x, int y, Node node)
    {
        if (x == 0 && y == 0)
            return null;

        int checkX = node.gridX + x;
        int checkY = node.gridY + y;

        if (checkX >= 0 && checkX < gridSizeX && checkY >= 0 && checkY < gridSizeY)
        {
            return nodes[checkX, checkY];
        }

        return null;
    }

`
I might convert _ImpFindPath to be an IEnumerable as well.

Hello Sebastian and everyone!

In Ep05, everything is working correctly.

CreateGrid() and Gizmos.Draw() recognize the objects on the Unwalkable layer even in different scenes.
However, when the unit goes to follow the path on Play, it is ignoring objects on the Unwalkable Layer that are in another scene.

Can someone help me?

Thanks in advance!

UPDATE:

Apparently, the order and place of CreateGrid() and Gizmos.Draw() in Grid.cs, and also RequestPath() in PathRequestManager.cs, can cause this problem.

Still looking for the solution!