admin 管理员组文章数量: 1086019
I'm developing my own pathfinding algorithm for a 2D grid-based game in Unity 2D, and I've run into an issue affecting how enemies navigate toward their target.
Problem Currently, when an enemy calculates a path to its target (e.g., the player), it only considers a single tile of the target's position, ignoring the fact that the target may occupy multiple tiles in the grid.
Example:
If the target has a size of 3x2 tiles, the enemy may calculate the shortest path to just one tile of that space, rather than the closest or most accessible tile within the occupied area.
This causes the enemy to not always choose the best route and, in some cases, overlap with the target instead of stopping at an adjacent tile.
What I Need
A way to efficiently consider all the tiles occupied by the target in the grid.
Ensure the enemy chooses the shortest path to the most accessible tile within that area.
Prevent the enemy from overlapping with the target when reaching its destination.
What would be the best approach to solve this? How can I modify my pathfinding algorithm to correctly handle a target that occupies multiple tiles?
Here is my current code:
using UnityEngine;
using System.Collections.Generic;
using System.Linq;
public class AStarPathfinder
{
private NavigationRegion _region;
public AStarPathfinder(NavigationRegion region)
{
_region = region;
}
public List<Vector3Int> FindPath(Vector3Int start, Vector3Int target)
{
Dictionary<Vector3Int, Node> nodes = new Dictionary<Vector3Int, Node>();
List<Node> openList = new List<Node>();
HashSet<Vector3Int> closedSet = new HashSet<Vector3Int>();
Node startNode = new Node(start);
startNode.GCost = 0;
startNode.HCost = GetManhattanDistance(start, target);
nodes[start] = startNode;
openList.Add(startNode);
while (openList.Count > 0)
{
Node currentNode = openList.OrderBy(x => x.FCost).First();
openList.Remove(currentNode);
closedSet.Add(currentNode.Position);
if (currentNode.Position == target)
{
return RetracePath(startNode, currentNode);
}
foreach (Vector3Int neighborPos in GetNeighbors(currentNode.Position))
{
if (closedSet.Contains(neighborPos) || !_region.IsWalkable(neighborPos))
continue;
int tentativeGCost = currentNode.GCost + 1;
Node neighbor;
if (!nodes.TryGetValue(neighborPos, out neighbor))
{
neighbor = new Node(neighborPos);
nodes[neighborPos] = neighbor;
}
if (tentativeGCost < neighbor.GCost)
{
neighbor.GCost = tentativeGCost;
neighbor.HCost = GetManhattanDistance(neighborPos, target);
neighbor.Parent = currentNode;
if (!openList.Contains(neighbor))
openList.Add(neighbor);
}
}
}
return null;
}
private List<Vector3Int> RetracePath(Node start, Node end)
{
List<Vector3Int> path = new List<Vector3Int>();
Node currentNode = end;
while (currentNode != start)
{
path.Add(currentNode.Position);
currentNode = currentNode.Parent;
}
path.Reverse();
return path;
}
private int GetManhattanDistance(Vector3Int a, Vector3Int b)
{
return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
}
private List<Vector3Int> GetNeighbors(Vector3Int pos)
{
return new List<Vector3Int>
{
new Vector3Int(pos.x + 1, pos.y, pos.z),
new Vector3Int(pos.x - 1, pos.y, pos.z),
new Vector3Int(pos.x, pos.y + 1, pos.z),
new Vector3Int(pos.x, pos.y - 1, pos.z)
};
}
}
I'm developing my own pathfinding algorithm for a 2D grid-based game in Unity 2D, and I've run into an issue affecting how enemies navigate toward their target.
Problem Currently, when an enemy calculates a path to its target (e.g., the player), it only considers a single tile of the target's position, ignoring the fact that the target may occupy multiple tiles in the grid.
Example:
If the target has a size of 3x2 tiles, the enemy may calculate the shortest path to just one tile of that space, rather than the closest or most accessible tile within the occupied area.
This causes the enemy to not always choose the best route and, in some cases, overlap with the target instead of stopping at an adjacent tile.
What I Need
A way to efficiently consider all the tiles occupied by the target in the grid.
Ensure the enemy chooses the shortest path to the most accessible tile within that area.
Prevent the enemy from overlapping with the target when reaching its destination.
What would be the best approach to solve this? How can I modify my pathfinding algorithm to correctly handle a target that occupies multiple tiles?
Here is my current code:
using UnityEngine;
using System.Collections.Generic;
using System.Linq;
public class AStarPathfinder
{
private NavigationRegion _region;
public AStarPathfinder(NavigationRegion region)
{
_region = region;
}
public List<Vector3Int> FindPath(Vector3Int start, Vector3Int target)
{
Dictionary<Vector3Int, Node> nodes = new Dictionary<Vector3Int, Node>();
List<Node> openList = new List<Node>();
HashSet<Vector3Int> closedSet = new HashSet<Vector3Int>();
Node startNode = new Node(start);
startNode.GCost = 0;
startNode.HCost = GetManhattanDistance(start, target);
nodes[start] = startNode;
openList.Add(startNode);
while (openList.Count > 0)
{
Node currentNode = openList.OrderBy(x => x.FCost).First();
openList.Remove(currentNode);
closedSet.Add(currentNode.Position);
if (currentNode.Position == target)
{
return RetracePath(startNode, currentNode);
}
foreach (Vector3Int neighborPos in GetNeighbors(currentNode.Position))
{
if (closedSet.Contains(neighborPos) || !_region.IsWalkable(neighborPos))
continue;
int tentativeGCost = currentNode.GCost + 1;
Node neighbor;
if (!nodes.TryGetValue(neighborPos, out neighbor))
{
neighbor = new Node(neighborPos);
nodes[neighborPos] = neighbor;
}
if (tentativeGCost < neighbor.GCost)
{
neighbor.GCost = tentativeGCost;
neighbor.HCost = GetManhattanDistance(neighborPos, target);
neighbor.Parent = currentNode;
if (!openList.Contains(neighbor))
openList.Add(neighbor);
}
}
}
return null;
}
private List<Vector3Int> RetracePath(Node start, Node end)
{
List<Vector3Int> path = new List<Vector3Int>();
Node currentNode = end;
while (currentNode != start)
{
path.Add(currentNode.Position);
currentNode = currentNode.Parent;
}
path.Reverse();
return path;
}
private int GetManhattanDistance(Vector3Int a, Vector3Int b)
{
return Mathf.Abs(a.x - b.x) + Mathf.Abs(a.y - b.y);
}
private List<Vector3Int> GetNeighbors(Vector3Int pos)
{
return new List<Vector3Int>
{
new Vector3Int(pos.x + 1, pos.y, pos.z),
new Vector3Int(pos.x - 1, pos.y, pos.z),
new Vector3Int(pos.x, pos.y + 1, pos.z),
new Vector3Int(pos.x, pos.y - 1, pos.z)
};
}
}
- There's no point in using tiles if a game object can occupy more than on tile. The "tiles" might as well be "points"; which would allow for any type of movement and size of game object. – Gerry Schmitz Commented Mar 29 at 23:43
1 Answer
Reset to default 3It is quite trivial to extend your typical A* to accept multiple targets. Just change
Vector3Int target
to
HashSet<Vector3Int> targets
and
currentNode.Position == target
to
targets.Contains(currentNode.Position)
Presuming that your Vector3Int is suitable for use in a HashSet, i.e. the hashcode never changes, valid equals implementation etc. You can also extend it to accept multiple start nodes by just adding all of them to the open set at the start.
For the heuristic you can just take the minimum estimation for all targets. As long as you underestimate the cost you should be fine.
Note that sorting the entire open set each iteration is quite inefficient. The typical recommendation is to use a min heap, either your own or the built in priority queue.
本文标签： cPathfinding Issue in Unity 2D GridBased Game Target Occupies Multiple TilesStack Overflow
版权声明：本文标题：c# - Pathfinding Issue in Unity 2D Grid-Based Game: Target Occupies Multiple Tiles - Stack Overflow 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/p/1744001482a2516521.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论