Tìm kiếm theo chiều rộng (BFS)
Tags:
AI
Algorithm
Pathfinding
C# Code
using System.Collections.Generic;
public class BFS {
// Tìm đường đi ngắn nhất trên lưới từ start đến end
public List<Node> FindPath(Grid grid, Node start, Node end) {
Queue<Node> queue = new Queue<Node>();
HashSet<Node> visited = new HashSet<Node>();
Dictionary<Node, Node> parentMap = new Dictionary<Node, Node>();
queue.Enqueue(start);
visited.Add(start);
while (queue.Count > 0) {
Node current = queue.Dequeue();
if (current == end) {
// Đã tìm thấy đích, xây dựng lại đường đi
return RetracePath(parentMap, start, end);
}
foreach (Node neighbor in grid.GetNeighbors(current)) {
if (neighbor.isWalkable && !visited.Contains(neighbor)) {
visited.Add(neighbor);
parentMap[neighbor] = current;
queue.Enqueue(neighbor);
}
}
}
return null; // Không có đường đi
}
private List<Node> RetracePath(...) { /* ... */ }
}Thuật toán tìm kiếm theo chiều rộng (BFS) duyệt qua đồ thị theo từng lớp. Rất hữu ích để tìm đường đi ngắn nhất trên bản đồ không có trọng số (ví dụ: lưới ô vuông).