👀 Views: 149 💬 Answers: 1 📅 Created: 2025-06-12

pathfinding algorithm unity3d C#

I'm migrating some code and I'm currently implementing the A* pathfinding algorithm in my Unity game, and I'm encountering unexpected behavior when using the Manhattan distance as my heuristic. The grid is a 2D array representing walkable and non-walkable tiles, but the pathfinding occasionally returns suboptimal paths, especially when there are obstacles present. Here's a snippet of my `Node` class and the A* implementation: ```csharp public class Node { public Vector2Int Position; public Node Parent; public float GCost; // Cost from start to this node public float HCost; // Heuristic cost to end public float FCost => GCost + HCost; public Node(Vector2Int position) { Position = position; } } public List<Node> AStar(Vector2Int start, Vector2Int goal) { List<Node> openSet = new List<Node>(); HashSet<Node> closedSet = new HashSet<Node>(); Node startNode = new Node(start); Node goalNode = new Node(goal); openSet.Add(startNode); while (openSet.Count > 0) { Node currentNode = openSet.OrderBy(n => n.FCost).ThenBy(n => n.HCost).First(); if (currentNode.Position == goalNode.Position) { return RetracePath(startNode, currentNode); } openSet.Remove(currentNode); closedSet.Add(currentNode); foreach (Node neighbour in GetNeighbours(currentNode)) { if (closedSet.Contains(neighbour) || !IsWalkable(neighbour.Position)) { continue; } float newCostToNeighbour = currentNode.GCost + GetDistance(currentNode, neighbour); if (newCostToNeighbour < neighbour.GCost || !openSet.Contains(neighbour)) { neighbour.GCost = newCostToNeighbour; neighbour.HCost = GetManhattanDistance(neighbour.Position, goalNode.Position); neighbour.Parent = currentNode; if (!openSet.Contains(neighbour)) { openSet.Add(neighbour); } } } } return new List<Node>(); // Return empty path if no path found } ``` I've tried logging the values of the GCost and HCost for each node being processed, and the results seem consistent with what I expect. However, when I manually trace through the paths, the algorithm sometimes takes a longer route around obstacles instead of cutting through when it seems like a better option. I'm using Unity 2023.1.0 and have set up my grid system with dimensions of 10x10. The walkable tiles are randomly generated during runtime, and I suspect that the way I'm handling the neighbors might be causing issues. The function `GetNeighbours` is designed to return valid neighboring nodes. I've also tried adjusting the heuristic weights but to no avail. Is there something I might be overlooking in the way I'm calculating the costs or handling the open/closed sets? Any insights into why the paths are suboptimal would be greatly appreciated! I'm using C# LTS in this project. I'm working with C# in a Docker container on macOS.