Tổng quan

Trong phát triển game thuật toán tìm đường được ứng dụng rất phổ biến từ các game AAA cho đến cả những game puzzle trên mobile.

Như cái tên của nó. Thuật toán tìm đường giúp tìm ra con đường từ điểm A tới điểm B tránh khỏi các chướng ngại vật với một lộ trình tối ưu nhất.

Ví dụ trong game moba. Thuật toán tìm đường giúp nhân vật tự động di chuyển đến điểm người chơi đã chọn, giúp creep chạy về phía nhà chính đối phương và né khỏi các chướng ngại vật trên đường đi như trụ, nhà lính, tường. Trong pikachu, thuật toán tìm đường được sử dụng để để kiểu tra 2 con pikachu có match được với nhau không.

Các thuật toán tìm đường thường gặp.

	Dijkstra	A*	BFS (Breadth-first search)
Định nghĩa	Tìm đường đi với chi phí thấp nhất bằng cách duyệt qua tất cả các node trên bản đồ và tính toán khoảng cách ngắn nhất từ gốc đến mỗi node.	Tìm đường đi tối ưu nhất (khoảng cách và chi phí) dựa trên hằng số heuristic để dự đoán khoảng cách từ node đến đích.	Thuật toán tìm kiếm theo chiều rộng . Tìm kiếm theo từng lớp bắt đầu từ node gốc sau đó chuyển sang các lớp kế tiếp.
Ưu điểm	Đảm bảo tìm ra đường đi ngắn nhất.	- Tìm đường nhanh, chính xác - Hiệu quả với bản đồ lớn.	- Đơn giản, dễ triển khai. - Hiệu quả với bản đồ không có trọng số
Nhược điểm	Tốn kém (bộ nhớ và CPU) với bản đồ lớn.	Phụ thuộc vào hàm heuristic (nếu hàm không tốt có thể gây tốn tài nguyên).	- Không tối ưu cho tìm đường đi ngắn nhất - Tốc độ chậm với các bản đồ lớn.

Ghi chú:
- Hàm heuristic là một hàm ước lượng khoảng cách từ một node dến đích.
- Bản đồ ở đây là một tập hợp các node và các cạnh nối giữa chúng.