Lesson 15 — Tilemap & Pathfinding (lưới ô & tìm đường A*)
Ba bộ công cụ tương tác: (1) A* pathfinder — vẽ tường, đặt start/goal, chạy từng bước thấy open/closed + g/h/f mỗi ô; (2) So thuật toán — BFS vs Dijkstra vs A* đếm số ô thăm; (3) Heuristic — đổi Manhattan / Euclid / zero(=Dijkstra) xem vùng thăm đổi. Bài cuối lĩnh vực GameDev.
1. A* Pathfinder — vẽ & chạy từng bước
Chọn công cụ rồi kéo chuột trên lưới: ✏ Tường để vẽ/xoá tường, 🟢 Start, 🔴 Goal.
Bấm Bước để chạy A* một vòng (pop ô f nhỏ nhất, đóng nó, relax hàng xóm) — mỗi ô hiện g (góc trên-trái), h (trên-phải), f (giữa, to). Hoặc Tự chạy.
2. So thuật toán — BFS vs Dijkstra vs A*
Chạy cả ba trên cùng lưới (lưới bạn đã vẽ ở module 1) và đếm số ô thăm (số ô đã đóng). A* thường thăm ít nhất vì heuristic định hướng. Mỗi ô tô màu theo thuật toán đã thăm nó.
| Thuật toán | Số ô thăm | Độ dài đường (g) | Đặc điểm |
|---|---|---|---|
| BFS | — | — | ít ô nhất khi mọi bước = 1 |
| Dijkstra | — | — | đúng cho trọng số (bùn) |
| A* | — | — | thăm ít nhất nhờ heuristic |
3. Heuristic — đổi để thấy vùng thăm đổi
Cùng một lưới, đổi heuristic h và xem A* thăm rộng cỡ nào. zero → A* thoái hoá thành Dijkstra (loang đều). Manhattan/Euclid kéo tìm kiếm về đích → vùng thăm thu hẹp về hướng goal.