2 - Pathfinding for Games
Pathfinding is a crucial component of game development, enabling characters to navigate through game worlds intelligently. This section covers pathfinding algorithms specifically tailored for game development scenarios.
Game-Specific Pathfinding Challenges
Pathfinding in games presents unique challenges compared to general pathfinding:
- Real-time Constraints: Paths must be computed quickly to maintain smooth gameplay.
- Dynamic Environments: Game worlds change frequently, requiring path recalculation.
- Multiple Agents: Many characters may need paths simultaneously.
- Varied Terrain: Different terrain types may affect movement costs.
- Formation Movement: Groups of characters may need to move together.
- Path Smoothing: Raw pathfinding results often need smoothing for natural movement.
- Partial Planning: Sometimes only partial paths are needed, with further planning done later.
Grid-Based Pathfinding
Grid-based pathfinding is common in many games, especially those with tile-based worlds or discrete movement.
Implementation of A* for Grid-Based Games
/// <summary>
/// Represents a 2D integer vector used for grid-based pathfinding.
/// </summary>
public struct Vector2Int : IEquatable<Vector2Int>
{
/// <summary>
/// The x component of the vector.
/// </summary>
public int x;
/// <summary>
/// The y component of the vector.
/// </summary>
public int y;
/// <summary>
/// Initializes a new instance of the Vector2Int struct.
/// </summary>
/// <param name="x">The x component of the vector.</param>
/// <param name="y">The y component of the vector.</param>
public Vector2Int(int x, int y)
{
this.x = x;
this.y = y;
}
/// <summary>
/// Calculates the Euclidean distance between two vectors.
/// </summary>
/// <param name="a">The first vector.</param>
/// <param name="b">The second vector.</param>
/// <returns>The Euclidean distance between the vectors.</returns>
public static float Distance(Vector2Int a, Vector2Int b)
{
int dx = a.x - b.x;
int dy = a.y - b.y;
return MathF.Sqrt(dx * dx + dy * dy);
}
/// <summary>
/// Determines whether this vector is equal to another vector.
/// </summary>
/// <param name="other">The vector to compare with this vector.</param>
/// <returns>true if the vectors are equal; otherwise, false.</returns>
public bool Equals(Vector2Int other)
{
return x == other.x && y == other.y;
}
/// <summary>
/// Determines whether this vector is equal to another object.
/// </summary>
/// <param name="obj">The object to compare with this vector.</param>
/// <returns>true if the object is a Vector2Int and equal to this vector; otherwise, false.</returns>
public override bool Equals(object obj)
{
return obj is Vector2Int other && Equals(other);
}
/// <summary>
/// Returns a hash code for this vector.
/// </summary>
/// <returns>A hash code for this vector.</returns>
public override int GetHashCode()
{
return HashCode.Combine(x, y);
}
/// <summary>
/// Returns a string representation of this vector.
/// </summary>
/// <returns>A string representation of this vector.</returns>
public override string ToString()
{
return $"({x}, {y})";
}
}
/// <summary>
/// Implements the A* pathfinding algorithm for grid-based games.
/// </summary>
public class GridPathfinding
{
/// <summary>
/// The grid representation where 0 indicates walkable cells and 1 indicates obstacles.
/// </summary>
private readonly int[,] grid;
/// <summary>
/// The width of the grid.
/// </summary>
private readonly int width;
/// <summary>
/// The height of the grid.
/// </summary>
private readonly int height;
/// <summary>
/// The cost of moving horizontally or vertically.
/// </summary>
private readonly float orthogonalCost = 1.0f;
/// <summary>
/// The cost of moving diagonally.
/// </summary>
private readonly float diagonalCost = 1.414f; // Approximately sqrt(2)
/// <summary>
/// Initializes a new instance of the GridPathfinding class.
/// </summary>
/// <param name="grid">The grid representation where 0 indicates walkable cells and 1 indicates obstacles.</param>
/// <exception cref="ArgumentNullException">Thrown when the grid is null.</exception>
/// <exception cref="ArgumentException">Thrown when the grid has zero dimensions.</exception>
public GridPathfinding(int[,] grid)
{
this.grid = grid ?? throw new ArgumentNullException(nameof(grid), "Grid cannot be null.");
width = grid.GetLength(0);
height = grid.GetLength(1);
if (width == 0 || height == 0)
{
throw new ArgumentException("Grid must have non-zero dimensions.", nameof(grid));
}
}
/// <summary>
/// Finds the shortest path from the start position to the goal position using the A* algorithm.
/// </summary>
/// <param name="start">The starting position.</param>
/// <param name="goal">The goal position.</param>
/// <returns>A list of positions representing the path from start to goal, or an empty list if no path exists.</returns>
/// <exception cref="ArgumentException">Thrown when the start or goal position is invalid or not walkable.</exception>
public List<Vector2Int> FindPath(Vector2Int start, Vector2Int goal)
{
// Validate start and goal positions
if (!IsValidPosition(start))
throw new ArgumentException("Start position is outside the grid bounds.", nameof(start));
if (!IsValidPosition(goal))
throw new ArgumentException("Goal position is outside the grid bounds.", nameof(goal));
if (!IsWalkable(start))
throw new ArgumentException("Start position is not walkable.", nameof(start));
if (!IsWalkable(goal))
throw new ArgumentException("Goal position is not walkable.", nameof(goal));
// If start and goal are the same, return a path with just the start position
if (start.Equals(goal))
return new List<Vector2Int> { start };
// Priority queue for open set (nodes to be evaluated)
// Lower f-scores have higher priority
var openSet = new PriorityQueue<Vector2Int, float>();
openSet.Enqueue(start, 0);
// Dictionary to store the most efficient previous step for each position
var cameFrom = new Dictionary<Vector2Int, Vector2Int>();
// Dictionary to store the cost from start to each position
var gScore = new Dictionary<Vector2Int, float>();
gScore[start] = 0;
// Dictionary to store the estimated total cost from start to goal through each position
var fScore = new Dictionary<Vector2Int, float>();
fScore[start] = HeuristicCost(start, goal);
// Set to keep track of nodes in the open set for faster lookups
var openSetContains = new HashSet<Vector2Int> { start };
// Main A* algorithm loop
while (openSet.Count > 0)
{
// Get the position with the lowest f-score
Vector2Int current = openSet.Dequeue();
openSetContains.Remove(current);
// If we've reached the goal, reconstruct and return the path
if (current.Equals(goal))
{
return ReconstructPath(cameFrom, current);
}
// Check all neighbors
foreach (Vector2Int neighbor in GetNeighbors(current))
{
// Calculate the movement cost between current and neighbor
float movementCost = (neighbor.x != current.x && neighbor.y != current.y) ? diagonalCost : orthogonalCost;
// Calculate tentative g-score (cost from start to neighbor through current)
float tentativeGScore = gScore[current] + movementCost;
// If this path to neighbor is better than any previous one
if (!gScore.ContainsKey(neighbor) || tentativeGScore < gScore[neighbor])
{
// Record this path
cameFrom[neighbor] = current;
gScore[neighbor] = tentativeGScore;
// Calculate f-score (g-score + heuristic)
float estimatedTotalCost = tentativeGScore + HeuristicCost(neighbor, goal);
fScore[neighbor] = estimatedTotalCost;
// Add to open set if not already there
if (!openSetContains.Contains(neighbor))
{
openSet.Enqueue(neighbor, estimatedTotalCost);
openSetContains.Add(neighbor);
}
// Note: If the neighbor is already in the open set with a higher priority,
// we can't update its priority directly in .NET's PriorityQueue.
// In a production implementation, you might want to use a custom priority queue
// that supports priority updates.
}
}
}
// No path found
return new List<Vector2Int>();
}
/// <summary>
/// Gets all walkable neighbors of the specified position.
/// </summary>
/// <param name="position">The position to get neighbors for.</param>
/// <returns>A list of walkable neighboring positions.</returns>
private List<Vector2Int> GetNeighbors(Vector2Int position)
{
var neighbors = new List<Vector2Int>();
// Check all 8 adjacent cells (orthogonal and diagonal)
for (int dx = -1; dx <= 1; dx++)
{
for (int dy = -1; dy <= 1; dy++)
{
// Skip the current position
if (dx == 0 && dy == 0)
continue;
int newX = position.x + dx;
int newY = position.y + dy;
Vector2Int newPos = new Vector2Int(newX, newY);
// Check if the position is valid and walkable
if (IsValidPosition(newPos) && IsWalkable(newPos))
{
// For diagonal movement, ensure both adjacent cells are walkable
// This prevents cutting corners around obstacles
if (dx != 0 && dy != 0)
{
Vector2Int horizontalNeighbor = new Vector2Int(position.x + dx, position.y);
Vector2Int verticalNeighbor = new Vector2Int(position.x, position.y + dy);
if (!IsWalkable(horizontalNeighbor) || !IsWalkable(verticalNeighbor))
continue; // Can't cut corners
}
neighbors.Add(newPos);
}
}
}
return neighbors;
}
/// <summary>
/// Calculates the heuristic cost (estimated distance) between two positions.
/// </summary>
/// <param name="a">The first position.</param>
/// <param name="b">The second position.</param>
/// <returns>The estimated cost to move from position a to position b.</returns>
private float HeuristicCost(Vector2Int a, Vector2Int b)
{
// Euclidean distance - works well for 8-directional movement
return Vector2Int.Distance(a, b);
// Alternative heuristics (uncomment to use):
// Manhattan distance - works well for 4-directional movement
// return Math.Abs(a.x - b.x) + Math.Abs(a.y - b.y);
// Chebyshev distance - works well for 8-directional movement with uniform cost
// return Math.Max(Math.Abs(a.x - b.x), Math.Abs(a.y - b.y));
// Octile distance - most accurate for 8-directional movement with sqrt(2) diagonal cost
// int dx = Math.Abs(a.x - b.x);
// int dy = Math.Abs(a.y - b.y);
// return orthogonalCost * Math.Max(dx, dy) + (diagonalCost - orthogonalCost) * Math.Min(dx, dy);
}
/// <summary>
/// Reconstructs the path from the start position to the current position.
/// </summary>
/// <param name="cameFrom">Dictionary mapping each position to the position it came from.</param>
/// <param name="current">The current (end) position.</param>
/// <returns>A list of positions representing the path from start to current.</returns>
private List<Vector2Int> ReconstructPath(Dictionary<Vector2Int, Vector2Int> cameFrom, Vector2Int current)
{
// Start with the current position
var path = new List<Vector2Int> { current };
// Follow the chain of positions back to the start
while (cameFrom.ContainsKey(current))
{
current = cameFrom[current];
path.Add(current);
}
// Reverse to get the path from start to goal
path.Reverse();
return path;
}
/// <summary>
/// Determines whether the specified position is within the grid bounds.
/// </summary>
/// <param name="position">The position to check.</param>
/// <returns>true if the position is within the grid bounds; otherwise, false.</returns>
private bool IsValidPosition(Vector2Int position)
{
return position.x >= 0 && position.x < width &&
position.y >= 0 && position.y < height;
}
/// <summary>
/// Determines whether the specified position is walkable.
/// </summary>
/// <param name="position">The position to check.</param>
/// <returns>true if the position is walkable; otherwise, false.</returns>
private bool IsWalkable(Vector2Int position)
{
return grid[position.x, position.y] == 0;
}
/// <summary>
/// Gets the grid cell value at the specified position.
/// </summary>
/// <param name="position">The position to get the value for.</param>
/// <returns>The grid cell value (0 for walkable, 1 for obstacle).</returns>
/// <exception cref="ArgumentException">Thrown when the position is outside the grid bounds.</exception>
public int GetCellValue(Vector2Int position)
{
if (!IsValidPosition(position))
throw new ArgumentException("Position is outside the grid bounds.", nameof(position));
return grid[position.x, position.y];
}
/// <summary>
/// Visualizes the path on the grid for debugging purposes.
/// </summary>
/// <param name="path">The path to visualize.</param>
/// <returns>A string representation of the grid with the path marked.</returns>
public string VisualizeGrid(List<Vector2Int> path)
{
var pathSet = new HashSet<Vector2Int>(path);
var sb = new System.Text.StringBuilder();
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
Vector2Int pos = new Vector2Int(x, y);
if (pathSet.Contains(pos))
{
sb.Append('*'); // Path
}
else if (grid[x, y] == 1)
{
sb.Append('#'); // Obstacle
}
else
{
sb.Append('.'); // Walkable
}
}
sb.AppendLine();
}
return sb.ToString();
}
}
Optimizations for Grid-Based Pathfinding
- Jump Point Search (JPS): An optimization of A* for uniform-cost grid maps that skips redundant nodes.
- Hierarchical Pathfinding: Dividing the grid into clusters and finding paths at multiple levels of abstraction.
- Direction Prioritization: Prioritizing directions that align with the goal.
// Example of direction prioritization
private List<Vector2Int> GetNeighborsPrioritized(Vector2Int position, Vector2Int goal)
{
var neighbors = GetNeighbors(position);
// Sort neighbors by their distance to the goal
neighbors.Sort((a, b) =>
Vector2Int.Distance(a, goal).CompareTo(Vector2Int.Distance(b, goal)));
return neighbors;
}
Navigation Meshes
Navigation meshes (navmeshes) are a more advanced approach to pathfinding, representing walkable areas as polygons.
Basic NavMesh Implementation
public class NavMesh
{
private List<NavMeshTriangle> triangles = new List<NavMeshTriangle>();
public NavMesh(List<NavMeshTriangle> triangles)
{
this.triangles = triangles;
// Build connectivity between triangles
BuildConnectivity();
}
private void BuildConnectivity()
{
// For each triangle, find its neighbors
foreach (var triangle in triangles)
{
foreach (var otherTriangle in triangles)
{
if (triangle == otherTriangle)
continue;
// Check if triangles share an edge
if (SharesEdge(triangle, otherTriangle))
{
triangle.Neighbors.Add(otherTriangle);
}
}
}
}
private bool SharesEdge(NavMeshTriangle a, NavMeshTriangle b)
{
int sharedVertices = 0;
foreach (var vertexA in a.Vertices)
{
foreach (var vertexB in b.Vertices)
{
if (Vector3.Distance(vertexA, vertexB) < 0.001f)
{
sharedVertices++;
break;
}
}
}
return sharedVertices >= 2; // Two or more shared vertices means a shared edge
}
public List<Vector3> FindPath(Vector3 start, Vector3 goal)
{
// Find the triangles containing start and goal points
NavMeshTriangle startTriangle = FindTriangleContaining(start);
NavMeshTriangle goalTriangle = FindTriangleContaining(goal);
if (startTriangle == null || goalTriangle == null)
return new List<Vector3>();
// If start and goal are in the same triangle, return a direct path
if (startTriangle == goalTriangle)
return new List<Vector3> { start, goal };
// Find a path between triangles using A*
List<NavMeshTriangle> trianglePath = FindTrianglePath(startTriangle, goalTriangle);
if (trianglePath.Count == 0)
return new List<Vector3>();
// Convert triangle path to a point path
return CreatePointPath(start, goal, trianglePath);
}
private NavMeshTriangle FindTriangleContaining(Vector3 point)
{
foreach (var triangle in triangles)
{
if (IsPointInTriangle(point, triangle))
return triangle;
}
return null;
}
private bool IsPointInTriangle(Vector3 point, NavMeshTriangle triangle)
{
// Implement point-in-triangle test
// (Barycentric coordinates or other methods)
// Simplified version:
Vector3 v0 = triangle.Vertices[0];
Vector3 v1 = triangle.Vertices[1];
Vector3 v2 = triangle.Vertices[2];
// Project to 2D for simplicity
Vector2 p = new Vector2(point.x, point.z);
Vector2 a = new Vector2(v0.x, v0.z);
Vector2 b = new Vector2(v1.x, v1.z);
Vector2 c = new Vector2(v2.x, v2.z);
// Compute barycentric coordinates
float areaABC = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
float areaPBC = (b.x - p.x) * (c.y - p.y) - (b.y - p.y) * (c.x - p.x);
float areaPCA = (c.x - p.x) * (a.y - p.y) - (c.y - p.y) * (a.x - p.x);
float alpha = areaPBC / areaABC;
float beta = areaPCA / areaABC;
float gamma = 1 - alpha - beta;
return alpha >= 0 && beta >= 0 && gamma >= 0;
}
private List<NavMeshTriangle> FindTrianglePath(NavMeshTriangle start, NavMeshTriangle goal)
{
// A* implementation for finding a path through triangles
var openSet = new PriorityQueue<NavMeshTriangle, float>();
openSet.Enqueue(start, 0);
var cameFrom = new Dictionary<NavMeshTriangle, NavMeshTriangle>();
var gScore = new Dictionary<NavMeshTriangle, float>();
gScore[start] = 0;
var fScore = new Dictionary<NavMeshTriangle, float>();
fScore[start] = HeuristicCost(start, goal);
while (openSet.Count > 0)
{
NavMeshTriangle current = openSet.Dequeue();
if (current == goal)
return ReconstructPath(cameFrom, current);
foreach (var neighbor in current.Neighbors)
{
float tentativeGScore = gScore[current] + Distance(current, neighbor);
if (!gScore.ContainsKey(neighbor) || tentativeGScore < gScore[neighbor])
{
cameFrom[neighbor] = current;
gScore[neighbor] = tentativeGScore;
float estimatedTotalCost = tentativeGScore + HeuristicCost(neighbor, goal);
fScore[neighbor] = estimatedTotalCost;
if (!openSet.UnorderedItems.Any(item => item.Element == neighbor))
{
openSet.Enqueue(neighbor, estimatedTotalCost);
}
}
}
}
return new List<NavMeshTriangle>();
}
private float HeuristicCost(NavMeshTriangle a, NavMeshTriangle b)
{
// Use the distance between triangle centers as a heuristic
Vector3 centerA = (a.Vertices[0] + a.Vertices[1] + a.Vertices[2]) / 3;
Vector3 centerB = (b.Vertices[0] + b.Vertices[1] + b.Vertices[2]) / 3;
return Vector3.Distance(centerA, centerB);
}
private float Distance(NavMeshTriangle a, NavMeshTriangle b)
{
// For adjacent triangles, use the distance between their centers
Vector3 centerA = (a.Vertices[0] + a.Vertices[1] + a.Vertices[2]) / 3;
Vector3 centerB = (b.Vertices[0] + b.Vertices[1] + b.Vertices[2]) / 3;
return Vector3.Distance(centerA, centerB);
}
private List<NavMeshTriangle> ReconstructPath(Dictionary<NavMeshTriangle, NavMeshTriangle> cameFrom, NavMeshTriangle current)
{
var path = new List<NavMeshTriangle> { current };
while (cameFrom.ContainsKey(current))
{
current = cameFrom[current];
path.Add(current);
}
path.Reverse();
return path;
}
private List<Vector3> CreatePointPath(Vector3 start, Vector3 goal, List<NavMeshTriangle> trianglePath)
{
var pointPath = new List<Vector3> { start };
// Find the portal edges between adjacent triangles
for (int i = 0; i < trianglePath.Count - 1; i++)
{
NavMeshTriangle current = trianglePath[i];
NavMeshTriangle next = trianglePath[i + 1];
// Find the shared edge (portal)
Vector3[] portal = FindSharedEdge(current, next);
if (portal != null)
{
// Add the midpoint of the portal as a waypoint
pointPath.Add((portal[0] + portal[1]) / 2);
}
}
pointPath.Add(goal);
// Apply path smoothing
return SmoothPath(pointPath);
}
private Vector3[] FindSharedEdge(NavMeshTriangle a, NavMeshTriangle b)
{
List<Vector3> sharedVertices = new List<Vector3>();
foreach (var vertexA in a.Vertices)
{
foreach (var vertexB in b.Vertices)
{
if (Vector3.Distance(vertexA, vertexB) < 0.001f)
{
sharedVertices.Add(vertexA);
break;
}
}
}
if (sharedVertices.Count >= 2)
return sharedVertices.ToArray();
return null;
}
private List<Vector3> SmoothPath(List<Vector3> path)
{
// Simple path smoothing by removing redundant waypoints
if (path.Count <= 2)
return path;
var smoothedPath = new List<Vector3> { path[0] };
for (int i = 1; i < path.Count - 1; i++)
{
Vector3 prev = path[i - 1];
Vector3 current = path[i];
Vector3 next = path[i + 1];
// If the current point is not significantly changing the direction, skip it
Vector3 dir1 = (current - prev).normalized;
Vector3 dir2 = (next - current).normalized;
if (Vector3.Dot(dir1, dir2) < 0.95f) // Threshold for considering a significant direction change
{
smoothedPath.Add(current);
}
}
smoothedPath.Add(path[path.Count - 1]);
return smoothedPath;
}
}
public class NavMeshTriangle
{
public Vector3[] Vertices { get; } = new Vector3[3];
public List<NavMeshTriangle> Neighbors { get; } = new List<NavMeshTriangle>();
public NavMeshTriangle(Vector3 v1, Vector3 v2, Vector3 v3)
{
Vertices[0] = v1;
Vertices[1] = v2;
Vertices[2] = v3;
}
}
Advantages of Navigation Meshes
- Efficiency: More efficient than grid-based approaches for large open areas.
- Accuracy: Better represents the actual walkable space.
- Flexibility: Can represent complex 3D environments, including slopes and multi-level structures.
- Memory Efficiency: Typically requires less memory than grid representations.
Path Smoothing
Raw pathfinding results often produce jagged paths that look unnatural. Path smoothing techniques create more realistic movement.
Simple Path Smoothing
public List<Vector2> SmoothPath(List<Vector2> path, int[,] grid)
{
if (path.Count <= 2)
return path;
var smoothedPath = new List<Vector2> { path[0] };
int current = 0;
while (current < path.Count - 1)
{
int furthest = current + 1;
// Find the furthest point that has a clear line of sight
for (int i = current + 2; i < path.Count; i++)
{
if (HasLineOfSight(path[current], path[i], grid))
{
furthest = i;
}
else
{
break;
}
}
smoothedPath.Add(path[furthest]);
current = furthest;
}
return smoothedPath;
}
private bool HasLineOfSight(Vector2 start, Vector2 end, int[,] grid)
{
// Bresenham's line algorithm to check if there's a clear path
int x0 = (int)start.x;
int y0 = (int)start.y;
int x1 = (int)end.x;
int y1 = (int)end.y;
int dx = Math.Abs(x1 - x0);
int dy = Math.Abs(y1 - y0);
int sx = x0 < x1 ? 1 : -1;
int sy = y0 < y1 ? 1 : -1;
int err = dx - dy;
while (x0 != x1 || y0 != y1)
{
if (x0 < 0 || x0 >= grid.GetLength(0) || y0 < 0 || y0 >= grid.GetLength(1) || grid[x0, y0] == 1)
return false;
int e2 = 2 * err;
if (e2 > -dy)
{
err -= dy;
x0 += sx;
}
if (e2 < dx)
{
err += dx;
y0 += sy;
}
}
return true;
}
Bezier Curve Smoothing
public List<Vector2> SmoothPathWithBezier(List<Vector2> path, int segments = 10)
{
if (path.Count <= 2)
return path;
var smoothedPath = new List<Vector2>();
// Add the first point
smoothedPath.Add(path[0]);
for (int i = 0; i < path.Count - 2; i++)
{
Vector2 p0 = path[i];
Vector2 p1 = path[i + 1];
Vector2 p2 = path[i + 2];
// Create control points for the Bezier curve
Vector2 control1 = p0 + (p1 - p0) * 0.5f;
Vector2 control2 = p1 + (p2 - p1) * 0.5f;
// Generate points along the Bezier curve
for (int j = 1; j <= segments; j++)
{
float t = j / (float)segments;
Vector2 point = QuadraticBezier(p0, control1, control2, t);
smoothedPath.Add(point);
}
}
// Add the last point
smoothedPath.Add(path[path.Count - 1]);
return smoothedPath;
}
private Vector2 QuadraticBezier(Vector2 p0, Vector2 p1, Vector2 p2, float t)
{
float u = 1 - t;
float tt = t * t;
float uu = u * u;
Vector2 p = uu * p0; // (1-t)^2 * P0
p += 2 * u * t * p1; // 2(1-t)t * P1
p += tt * p2; // t^2 * P2
return p;
}
Dynamic Pathfinding
Games often have dynamic environments where obstacles move or change. Dynamic pathfinding adapts to these changes.
Path Replanning
public class DynamicPathfinder
{
private GridPathfinding pathfinder;
private int[,] grid;
private Dictionary<GameObject, List<Vector2Int>> agentPaths = new Dictionary<GameObject, List<Vector2Int>>();
public DynamicPathfinder(int[,] grid)
{
this.grid = grid;
pathfinder = new GridPathfinding(grid);
}
public void UpdateGrid(int x, int y, int value)
{
// Update the grid
grid[x, y] = value;
// Check if this affects any agent's path
foreach (var agent in agentPaths.Keys.ToList())
{
var path = agentPaths[agent];
// Check if the path goes through the updated cell
bool pathAffected = path.Any(p => p.x == x && p.y == y);
if (pathAffected)
{
// Replan the path
Vector2Int currentPos = new Vector2Int((int)agent.Position.x, (int)agent.Position.y);
Vector2Int goalPos = path[path.Count - 1];
var newPath = pathfinder.FindPath(currentPos, goalPos);
if (newPath.Count > 0)
{
agentPaths[agent] = newPath;
agent.SetPath(newPath); // Assuming GameObject has a SetPath method
}
}
}
}
public List<Vector2Int> FindPath(GameObject agent, Vector2Int start, Vector2Int goal)
{
var path = pathfinder.FindPath(start, goal);
if (path.Count > 0)
{
agentPaths[agent] = path;
}
return path;
}
public void RemoveAgent(GameObject agent)
{
agentPaths.Remove(agent);
}
}
Incremental Pathfinding
Incremental pathfinding algorithms update existing paths rather than recomputing them from scratch.
public class IncrementalPathfinder
{
private int[,] grid;
private Dictionary<Vector2Int, float> gScores = new Dictionary<Vector2Int, float>();
private Dictionary<Vector2Int, Vector2Int> cameFrom = new Dictionary<Vector2Int, Vector2Int>();
public IncrementalPathfinder(int[,] grid)
{
this.grid = grid;
}
public List<Vector2Int> UpdatePath(List<Vector2Int> currentPath, Vector2Int start, Vector2Int goal, List<Vector2Int> changedCells)
{
// If the path is empty or the goal has changed, compute a new path
if (currentPath.Count == 0 || !currentPath[currentPath.Count - 1].Equals(goal))
{
return ComputeNewPath(start, goal);
}
// Check if any changed cells affect the current path
bool pathAffected = currentPath.Any(p => changedCells.Contains(p));
if (!pathAffected)
{
return currentPath; // Path is still valid
}
// Find the first affected point in the path
int affectedIndex = 0;
for (int i = 0; i < currentPath.Count; i++)
{
if (changedCells.Contains(currentPath[i]))
{
affectedIndex = i;
break;
}
}
// Reuse the unaffected part of the path
var newStart = currentPath[affectedIndex - 1];
var partialPath = ComputeNewPath(newStart, goal);
if (partialPath.Count == 0)
{
// If no partial path is found, compute a completely new path
return ComputeNewPath(start, goal);
}
// Combine the unaffected part with the new partial path
var result = currentPath.Take(affectedIndex).ToList();
result.AddRange(partialPath.Skip(1)); // Skip the first point to avoid duplication
return result;
}
private List<Vector2Int> ComputeNewPath(Vector2Int start, Vector2Int goal)
{
// Clear previous search data
gScores.Clear();
cameFrom.Clear();
// Implement A* pathfinding
// (Similar to the GridPathfinding.FindPath method shown earlier)
// For brevity, assuming we have a method that computes the path
return ComputePath(start, goal);
}
private List<Vector2Int> ComputePath(Vector2Int start, Vector2Int goal)
{
// A* implementation (simplified for brevity)
// In a real implementation, this would be a full A* algorithm
// Placeholder return
return new List<Vector2Int>();
}
}
Group Movement and Formations
Many games require characters to move in groups or formations.
Simple Formation Movement
public class FormationController
{
private List<GameObject> units = new List<GameObject>();
private Vector2 leaderPosition;
private Vector2 targetPosition;
private List<Vector2> formationOffsets = new List<Vector2>();
public FormationController(List<GameObject> units, FormationType formationType)
{
this.units = units;
leaderPosition = units[0].Position;
// Generate formation offsets based on the formation type
GenerateFormationOffsets(formationType);
}
private void GenerateFormationOffsets(FormationType formationType)
{
formationOffsets.Clear();
switch (formationType)
{
case FormationType.Line:
for (int i = 0; i < units.Count; i++)
{
formationOffsets.Add(new Vector2(i - units.Count / 2, 0) * 2.0f);
}
break;
case FormationType.Circle:
float radius = units.Count * 0.5f;
for (int i = 0; i < units.Count; i++)
{
float angle = i * (2 * MathF.PI / units.Count);
formationOffsets.Add(new Vector2(MathF.Cos(angle), MathF.Sin(angle)) * radius);
}
break;
case FormationType.Wedge:
for (int i = 0; i < units.Count; i++)
{
int row = i / 5;
int col = i % 5;
formationOffsets.Add(new Vector2(col - 2, row) * 2.0f);
}
break;
}
}
public void MoveTo(Vector2 target)
{
targetPosition = target;
// Find a path for the leader
List<Vector2> leaderPath = FindPath(leaderPosition, targetPosition);
// Assign paths to each unit based on formation offsets
for (int i = 0; i < units.Count; i++)
{
Vector2 offset = formationOffsets[i];
// Rotate the offset based on the movement direction
Vector2 direction = (targetPosition - leaderPosition).normalized;
float angle = MathF.Atan2(direction.y, direction.x);
Vector2 rotatedOffset = RotateVector(offset, angle);
// Calculate the unit's target position
Vector2 unitTarget = targetPosition + rotatedOffset;
// Find a path for the unit
List<Vector2> unitPath = FindPath(units[i].Position, unitTarget);
// Assign the path to the unit
units[i].SetPath(unitPath);
}
}
private Vector2 RotateVector(Vector2 v, float angle)
{
float cos = MathF.Cos(angle);
float sin = MathF.Sin(angle);
return new Vector2(
v.x * cos - v.y * sin,
v.x * sin + v.y * cos
);
}
private List<Vector2> FindPath(Vector2 start, Vector2 goal)
{
// Implement pathfinding or use an existing pathfinder
// For brevity, returning a direct path
return new List<Vector2> { start, goal };
}
public enum FormationType
{
Line,
Circle,
Wedge
}
}
Flocking Behavior
Flocking creates natural group movement using simple rules.
public class FlockingController
{
private List<GameObject> units = new List<GameObject>();
private Vector2 targetPosition;
// Flocking parameters
private float separationWeight = 1.5f;
private float alignmentWeight = 1.0f;
private float cohesionWeight = 1.0f;
private float targetWeight = 1.0f;
private float neighborRadius = 5.0f;
public FlockingController(List<GameObject> units)
{
this.units = units;
}
public void SetTarget(Vector2 target)
{
targetPosition = target;
}
public void Update(float deltaTime)
{
foreach (var unit in units)
{
// Get neighbors within radius
var neighbors = units.Where(u => u != unit && Vector2.Distance(u.Position, unit.Position) <= neighborRadius).ToList();
if (neighbors.Count == 0)
continue;
// Calculate flocking forces
Vector2 separation = CalculateSeparation(unit, neighbors);
Vector2 alignment = CalculateAlignment(unit, neighbors);
Vector2 cohesion = CalculateCohesion(unit, neighbors);
Vector2 target = CalculateTargetDirection(unit);
// Combine forces
Vector2 acceleration = separation * separationWeight +
alignment * alignmentWeight +
cohesion * cohesionWeight +
target * targetWeight;
// Apply acceleration to velocity
unit.Velocity += acceleration * deltaTime;
// Limit velocity
if (unit.Velocity.magnitude > unit.MaxSpeed)
{
unit.Velocity = unit.Velocity.normalized * unit.MaxSpeed;
}
// Update position
unit.Position += unit.Velocity * deltaTime;
}
}
private Vector2 CalculateSeparation(GameObject unit, List<GameObject> neighbors)
{
Vector2 steeringForce = Vector2.zero;
foreach (var neighbor in neighbors)
{
Vector2 toNeighbor = unit.Position - neighbor.Position;
float distance = toNeighbor.magnitude;
// The closer the neighbor, the stronger the separation force
steeringForce += toNeighbor.normalized / distance;
}
return steeringForce.normalized;
}
private Vector2 CalculateAlignment(GameObject unit, List<GameObject> neighbors)
{
Vector2 averageVelocity = Vector2.zero;
foreach (var neighbor in neighbors)
{
averageVelocity += neighbor.Velocity;
}
averageVelocity /= neighbors.Count;
return averageVelocity.normalized;
}
private Vector2 CalculateCohesion(GameObject unit, List<GameObject> neighbors)
{
Vector2 centerOfMass = Vector2.zero;
foreach (var neighbor in neighbors)
{
centerOfMass += neighbor.Position;
}
centerOfMass /= neighbors.Count;
return (centerOfMass - unit.Position).normalized;
}
private Vector2 CalculateTargetDirection(GameObject unit)
{
return (targetPosition - unit.Position).normalized;
}
}
Conclusion
Pathfinding is a critical component of game development, enabling characters to navigate through game worlds intelligently. By understanding and implementing these algorithms, you can create more immersive and realistic game experiences.
The techniques covered in this section provide a foundation for implementing pathfinding in games, but there are many more advanced techniques and optimizations that can be explored based on the specific requirements of your game.