Phần mềm tìm đường đi ngắn nhất trên bản đồ dựa trên các thuật toán | Môn Nhập môn trí tuệ nhân tạo - Đại học Bách Khoa Hà Nội

lOMoAR cPSD| 61552889
ĐẠI HỌC BÁCH KHOA HÀ NỘI
──────── * ──────── BÀI TẬP LỚN
NHẬP MÔN TRÍ TUỆ NHÂN TẠO
Đề tài: Phần mềm tìm đường đi ngắn nhất trên bản đồ dựa
trên các thuật toán Mã lớp: 156725
Giáo viên hướng dẫn: TS. Đặng Tuấn Linh Sinh viên Mã số sinh viên Lê Việt Anh 20225689 Nguyễn Sinh Quân 20225909 lOMoAR cPSD| 61552889 MỤC LỤC
PHẦN 1: GIỚI THIỆU PHẦN MỀM.........................................................................3
PHẦN 2: GIỚI THIỆU THUẬT TOÁN....................................................................4
2.1. Thuật toán sinh mê cung.........................................................................................4
2.2. Thuật toán tìm đường..............................................................................................5
2.2.1. Thuật toán A*.......................................................................................................5
2.2.2. Thuật toán BFS.....................................................................................................6
2.2.3. Thuật toán tham lam.............................................................................................7
2.3. Các hàm heuristic....................................................................................................8
PHẦN 3: GIAO DIỆN PHẦN MỀM........................................................................13
KẾT LUẬN.................................................................................................................15
TÀI LIỆU THAM KHẢO.........................................................................................16 lOMoAR cPSD| 61552889
PHẦN 1: GIỚI THIỆU PHẦN MỀM
Phần mềm "Tìm đường đi ngắn nhất trong mê cung sử dụng các thuật toán
" là một công cụ trực quan hóa nhằm hỗ trợ việc học và nghiên cứu môn Trí tuệ nhân tạo (IT3160).
Chức năng chính của phần mềm là mô phỏng quá trình tìm đường ngắn nhất
trong mê cung bằng cách áp dụng các thuật toán tìm kiếm như A*, Greedy Best-First
Search và Breadth-First Search (BFS). Người dùng có thể tùy chọn các thông số như:
 Cho phép hoặc không cho phép di chuyển theo đường chéo.
 Lựa chọn một trong 7 hàm heuristic khác nhau như: Euclide, Manhattan, Chebyshev, Octile,...
 Tuỳ chỉnh mê cung và chọn điểm xuất phát – điểm đích.
Phần mềm hiển thị trực quan quá trình tìm kiếm, bao gồm:
 Số lượng ô đã được xét.
 Chi phí tổng quát của đường đi.
 Thời gian thực hiện thuật toán.
 Đường đi ngắn nhất trên mê cung.
Bên dưới là hình minh hoạ về mê cung
PHẦN 2: GIỚI THIỆU THUẬT TOÁN
2.1. Giới thiệu thuật toán sinh mê cung 2.1.1. Giới thiệu
Thuật toán sinh mê cung bằng tìm kiếm theo chiều sâu (Depth-First Search –
DFS) là một phương pháp đơn giản và hiệu quả để tạo ra các mê cung hoàn chỉnh. Bằng
cách sử dụng kỹ thuật quay lui (backtracking), thuật toán tạo nên một mê cung với đặc
điểm có một và chỉ một đường đi giữa hai điểm bất kỳ. lOMoAR cPSD| 61552889
Thuật toán này hoạt động bằng cách duyệt sâu vào các ô chưa đi qua, “đục”
tường để tạo lối đi, và quay lui khi không còn lựa chọn mở rộng hợp lệ. 2.1.2. Đặc điểm 2.1.2.1 Ưu điểm
 Dễ cài đặt và dễ hiểu nhờ dựa trên DFS.
 Hiệu quả cao với độ phức tạp thời gian tuyến tính theo số ô.
 Tạo ra mê cung đúng nghĩa: chỉ có một đường duy nhất nối hai điểm.
 Kết quả ngẫu nhiên: do lựa chọn lân cận ngẫu nhiên, mỗi lần chạy tạo ra mê cung khác nhau.
2.1.2.2 Nhược điểm
 Cấu trúc mê cung có thể tạo thành cây, ít ngã rẽ nếu không xử lý thêm  Nếu
không "đục ngẫu nhiên" bổ sung, mê cung sẽ quá tuyến tính và dễ giải.
 Không dễ kiểm soát mức độ rối rắm của mê cung nếu không điều chỉnh tham số. 2.1.2.3 Áp dụng
 Dùng trong trò chơi, bài toán huấn luyện AI, giáo dục trực quan thuật toán.
 Là bước đầu quan trọng trước khi áp dụng các thuật toán tìm đường như A*, BFS, ...
2.1.3. Cài đặt thuật toán 2.1.3.1 Quy ước
 Mê cung được biểu diễn dưới dạng ma trận 2 chiều grid[][].
 Mỗi ô có hai trạng thái:
 0: tường (không thể đi)  1: đường (có thể đi qua)
 markTable[][]: đánh dấu ô đã đi.
 Mỗi bước đi được thực hiện cách 2 đơn vị (để giữ lại tường giữa các ô liền kề).
2.1.3.2 Cài đặt các bước
1. Khởi tạo mê cung
 Tạo lưới grid có kích thước xác định, tất cả đều là tường (0).
 Đánh dấu markTable là chưa đi (false).
2. Chọn ô bắt đầu
 Thường chọn ngẫu nhiên trên mép lưới (ví dụ: (0, randomY)). 3.
Khởi tạo ngăn xếp (stack)
 Đưa ô bắt đầu vào stack.
4. Duyệt mê cung bằng DFS  Trong khi stack chưa rỗng:
 Lấy ô hiện tại node = stack.pop()
 Tìm các ô hàng xóm cách 2 đơn vị (trên, dưới, trái, phải).
 Với mỗi ô hàng xóm chưa đánh dấu: 
Đục tường giữa ô hiện tại và ô hàng xóm. 
Đánh dấu đã đi (markTable = true, grid = 1). 
Thêm ô hàng xóm vào stack để tiếp tục duyệt.
5. Đục ngẫu nhiên thêm (drill)
 Lặp lại toàn bộ mê cung, với một xác suất ngẫu nhiên để biến một số tường (0) thành
đường (1) nhằm tăng tính rối. Mã giả đơn giản function generator(){ let stack = []; lOMoAR cPSD| 61552889 let start = {x: 0, y: randomY}; stack.push(start); while(stack.length > 0){ let node = stack.pop();
let neighbors = tìm_láng_giềng_chưa_đi(node);
while(neighbors.length > 0){ let next
= chọn_ngẫu_nhiên(neighbors); if (hợp_lệ) { đục_tường(node, next); mark[next.x][next.y] = true; stack.push(next); } } }
drill(70); // Đục ngẫu nhiên 70% số tường còn lại } 2.1.3.3 Đánh giá Tiêu chí Đánh giá
Độ phức tạp thời gian O(N*M) với N×M là số ô trong mê cung Không gian bộ nhớ
O(N*M) do cần lưu grid và markTable Mức độ ngẫu nhiên
Cao (nếu có thêm bước "drill") Dễ mở rộng
Dễ kết hợp với tìm đường, hỗ trợ sinh mê cung nhiều lớp
2.2. Giới thiệu thuật toán tìm đường 2.2.1 Thuật toán A*
2.2.1.1. Giới thiệu
Thuật toán A* (A-star) là thuật toán tìm kiếm nổi tiếng, kết hợp giữa độ chính
xác của Dijkstra và tốc độ của Greedy Best-First Search. A* sử dụng một hàm đánh giá
chi phí f(n) = g(n) + h(n) để tìm ra đường đi ngắn nhất từ điểm xuất phát đến điểm đích.
2.2.1.2. Đặc điểm 2.2.1.2.1 Ưu điểm
 Luôn tìm được đường đi ngắn nhất nếu h(n) là admissible.
 Có thể tuỳ biến hành vi bằng cách thay đổi hàm heuristic.
 Hiệu quả hơn BFS trong hầu hết các trường hợp.
2.2.1.2.2 Nhược điểm  Tốn bộ nhớ khi mê cung lớn.
 Phụ thuộc vào chất lượng hàm h(n). 2.2.1.2.3 Áp dụng
 Dùng trong bản đồ, trò chơi (AI pathfinding), robot định hướng, v.v.
2.2.1.3. Cài đặt thuật toán 2.2.1.3.1 Quy ước lOMoAR cPSD| 61552889
 grid[x][y]: mê cung với 1 là ô đi được, 0 là tường.
 source, destination: điểm bắt đầu và kết thúc.
 g(n): chi phí từ nguồn đến n.
 h(n): heuristic – ước lượng từ n đến đích.  f(n) = g(n) + h(n)
 Mỗi ô là một cell có: (x, y, g, f, parent).
2.2.1.3.2 Cài đặt các bước
 Khởi tạo danh sách openList và closeList.
 Thêm ô nguồn vào openList.
 Trong khi openList không rỗng:
 Lấy ô có f(n) nhỏ nhất.
 Nếu là điểm đích → kết thúc.
 Với mỗi ô lân cận: 
Nếu chưa duyệt hoặc tìm được đường ngắn hơn:
 Cập nhật g, h, f và parent. 
Đưa vào openList. 2.2.1.3.3 Đánh giá Tiêu chí Đánh giá Độ phức tạp
Trung bình O(b^d); tốt khi h tốt Tính đúng đắn
Luôn đúng nếu h tốt (admissible + consistent)
Rất cao: nhiều heuristic, hỗ trợ đi chéo Khả năng tùy biến
2.2.2. Thuật toán BFS (Breadth-First Search)
2.2.2.1. Giới thiệu
BFS là thuật toán tìm kiếm theo chiều rộng, duyệt từng lớp từ điểm xuất phát
ra các lân cận. Trong mê cung không có trọng số, BFS luôn tìm được đường đi ngắn nhất. 2.2.2.2 Đặc điểm
2.2.2.2.1 Ưu điểm  Đơn giản, dễ cài đặt.
 Luôn tìm đúng đường đi ngắn nhất (nếu không có trọng số).
2.2.2.2.2 Nhược điểm
 Rất tốn bộ nhớ với mê cung lớn.
 Không ưu tiên hướng đi gần đích. 2.2.2.2.3 Áp dụng
 Tìm kiếm lời giải ngắn nhất trong các bài toán không trọng số.
 Giảng dạy thuật toán cơ bản.
2.2.2.3. Cài đặt thuật toán 2.2.2.3.1 Quy ước
 visited[x][y]: đánh dấu đã đi.
 queue: hàng đợi FIFO để duyệt từng lớp.
 parent[x][y]: lưu lại cha để truy vết.
2.2.2.3.2 Cài đặt các bước
 Khởi tạo queue với điểm nguồn. 
Đánh dấu visited[source] = true. lOMoAR cPSD| 61552889
 Trong khi queue còn phần tử:
 Lấy điểm đầu hàng đợi.
 Nếu là đích → kết thúc.
 Với các ô lân cận chưa duyệt.  Đánh dấu visited. 
Cập nhật parent.  Đưa vào queue. 2.2.2.3.3 Đánh giá Tiêu chí Đánh giá Tính đúng
Tuyệt đối (luôn tìm được đường ngắn nhất) đắn Tốc độ
Chậm với bản đồ lớn do duyệt theo lớp rộng Heuristic
Không dùng, không tối ưu hướng đi
2.2.3. Thuật toán tham lam
2.2.3.1. Giới thiệu
Greedy chọn hướng đi “tham lam” nhất – tức ô có ước lượng h(n) đến đích nhỏ
nhất. Tuy nhanh, nhưng không đảm bảo ra đường ngắn nhất.
2.2.3.2. Đặc điểm 2.2.3.2.1 Ưu điểm
 Nhanh, ưu tiên hướng về đích.
 Dễ cài đặt, chỉ cần h(n).
2.2.3.2.2 Nhược điểm
 Không chính xác trong một số trường hợp.
 Có thể đi lạc hoặc vòng. 2.2.3.2.3 Áp dụng
 Tìm đường trong môi trường cần tốc độ cao mà không yêu cầu độ chính xác tuyệt đối
(ví dụ: AI game NPC di chuyển nhanh).
2.2.3.3. Cài đặt thuật toán 2.2.3.3.1 Quy ước
 Giống A*, nhưng không cần g(n).
 open[]: danh sách các ô tiềm năng.
 h(n): khoảng cách ước lượng đến đích.
2.2.3.3.2 Cài đặt các bước  Đưa ô nguồn vào open[].
 Trong khi open không rỗng:
 Chọn ô có h(n) nhỏ nhất.
 Nếu là đích → kết thúc.
 Với các ô lân cận chưa duyệt: 
Tính h(n), cập nhật parent.  Thêm vào open. 2.2.3.3.3 Đánh giá Tiêu chí Đánh giá Tốc độ
Rất nhanh (ưu tiên gần đích)
Độ chính xác Không đảm bảo đường ngắn nhất
Tối ưu bộ nhớ Tốt hơn A*, tệ hơn BFS nếu lạc hướng lOMoAR cPSD| 61552889 2.3. Các hàm heuristic
2.3.1. Heuristic1 – Euclidean distance 2.3.1.1.
Cài đặt (code): heuristic1(destination){
return Math.sqrt((this.x - destination.x) ** 2 + (this.y - destination.y) ** 2); } 2.3.1.2. Chứng minh:
 Khoảng cách Euclid là chiều dài đoạn thẳng giữa hai điểm.
 Thích hợp khi di chuyển mọi hướng (kể cả chéo).
 Admissible và consistent → đảm bảo A* tìm đúng đường ngắn nhất. 2.3.1.3. Ví dụ:
(x1, y1) = (1,1), (x2, y2) = (4,5)
→ h = √((4-1)² + (5-1)²) = √(9 + 16) = 5 2.3.2.
Heuristic2 – Euclidean squared (bỏ căn) 2.3.2.1. Cài đặt: heuristic2(destination){
return Math.floor(distance(this, destination) ** 2); }
2.3.2.2. Chứng minh:
 Bỏ căn để giảm chi phí tính toán (so sánh thôi).
 Tuy giá trị lớn hơn, nhưng thứ tự so sánh không thay đổi.
 Vẫn admissible nếu khoảng cách thực tế cũng được tính không căn. 2.3.3.3. Ví dụ:
h = (4-1)² + (5-1)² = 9 + 16 = 25 2.3.3.
Heuristic3 – Chebyshev 2.3.3.1. Cài đặt: heuristic3(destination){
return Math.max(Math.abs(destination.x - this.x), Math.abs(destination.y - this.y)); } 2.3.3.2. Chứng minh:
 Dùng khi di chuyển theo lưới 8 hướng với cùng chi phí (diagonals và orthogonals).
 Đảm bảo admissible. 2.3.3.3. Ví dụ:
dx = 3, dy = 4 → h = max(3, 4) = 4
2.3.4. Heuristic4 – Manhattan 2.3.4.1. Cài đặt: heuristic4(destination){
return Math.abs(this.x - destination.x) + Math.abs(this.y - destination.y); } 2.3.4.2. Chứng minh:
 Dùng trong lưới chỉ cho phép đi lên/xuống/trái/phải.
 Luôn admissible vì không đi chéo. 2.3.4.3. Ví dụ:
h = |4 - 1| + |5 - 1| = 3 + 4 = 7
2.3.5. Heuristic5 – Octile distance 2.3.5.1. Cài đặt: lOMoAR cPSD| 61552889
heuristic5(destination){ var dx =
Math.abs(destination.x - this.x); var dy =
Math.abs(destination.y - this.y);
return dx > dy ? dx + sqrt(2) * dy : sqrt(2) * dx + dy; } 2.3.5.2. Chứng minh:
 Thích hợp khi cho phép đi chéo với chi phí √2.
 Là phiên bản cải tiến của Chebyshev. 2.3.5.3. Ví dụ: dx = 3, dy = 4 min = 3, max = 4
h = √2×3 + (4 - 3) = 4.24 + 1 = 5.2 6.
Heuristic6 – Tie-breaking (kết hợp góc)
2.3.6.1. Cài đặt: heuristic6(destination,
source){ var dx1 = this.x - destination.x;
var dy1 = this.y - destination.y; var dx2 =
source.x - destination.x; var dy2 = source.y - destination.y;
return Math.abs(dx1 * dy2 - dx2 * dy1) * 0.001 + this.heuristic2(destination, source); } 2.3.6.2. Chứng minh:
 Ưu tiên các đường đi thẳng hàng với hướng từ source đến destination.
 Thành phần dx1 * dy2 - dx2 * dy1 chính là diện tích hình bình hành giữa các vector
 Tăng độ mượt của đường đi (tránh zig-zag). 2.3.6.3. Ví dụ:
Tính thêm |dx1 * dy2 - dx2 * dy1| * 0.001 → cộng vào heuristic2.
2.3.7. Heuristic7 – Góc lệch Euclid (Angle_Euclid) 2.3.7.1. Cài
đặt: heuristic7(destination, source){ var CS = distance(this,
source); var CD = distance(this, destination); var SD =
distance(source, destination);
var c = -Math.abs(((CS**2 + SD**2 - CD**2) / (2 * CS * SD)));
return this.heuristic2(destination, source) + c; } 2.3.7.2. Chứng minh:
 Dựa trên định lý cosin, c đo mức lệch góc giữa đường đi hiện tại và đích.
 Giá trị c càng nhỏ → đường càng lệch → bị phạt.
 Hướng đi “thẳng hàng” → được ưu tiên. 2.3.7.3. Ví dụ:
Giả sử CS = 3, CD = 4, SD = 5
→ c = -| (9 + 25 - 16) / (2×3×5) | = -|18 / 30| = -0.6
→ Heuristic = heuristic2 + c
BẢNG SO SÁNH CÁC HÀM HEURISTIC lOMoAR cPSD| 61552889 ST Tên Công Cho Admissib Tốc Độ Ghi chú T Heuristic thức phép le độ chính chính chính đi chéo tính xác toán (gần thực tế) 1 Euclid √((dx)² + Có Có Chậm Cao Khoảng cách (dy)²) (có căn) thật sự trên không gian 2D 2 Euclid² (dx)² + Có Có Nhanh Tốt Không cần (dy)² (tương căn bậc hai đối) 3 Chebyshev max(dx, Có Có Rất Gần Dùng cho dy) nhanh đúng bước đi chéo có cùng chi phí 4 Manhattan dx + dy Không Có Rất Mô hình nhanh Chính thành phố – xác (nếu chỉ đi không ngang/dọc chéo) 5 Octile dx + (√2 – Có Có Trung Cao Mô hình chi 1) × bình phí chéo = √2 min(dx, dy) 6
Tie-Breaking Euclid² + dx ·dy₁ Có Có Trung bình 0.001 × ₂ – dx ·dy₂ ₁ 7 Angle_Euclid Có Có Chậm Chính Ưu tiên Euclid² + hơn xác cao đường đi lệch góc cùng phương (theo định với source lý cosin)
ĐÁNH GIÁ HIỆU QUẢ CÁC HÀM HEURISTIC THEO KÍCH THƯỚC MÊ CUNG STT Tên Mê cung nhỏ Mê cung lớn Giải thích Heuristic (≤ 20×20) (≥ 50×50) 1 Euclid Tốt – chính
Chậm – do căn Chi phí tính toán cao hơn, lOMoAR cPSD| 61552889 xác cao bậc hai nhưng hướng dẫn đúng đích 2 Euclid² Rất tốt – nhẹ Tốt Giữ đúng thứ tự so sánh, nhanh hơn Euclid Ưu tiên tốc độ, 3
Chebyshev Tốt nhanh, nhưng Rất nhanh, không tối ưu lệch dễ sai lệch đường
Không tối Chỉ tốt trong 4
Manhattan Tốt nếu không đi ưu nếu có lưới 4 hướng chéo chéo Tốt – Ước lượng sát 5 Octile
Tốt – chính xác, ổn thăng thực tế trong định bằng lưới 8 hướng Ưu tiên đường 6 Tie-Breaking
Mượt, tối ưu Chậm với thẳng, tránh zig- hình lưới lớn zag 7
Angle_Euclid Quá nặng với
Chậm – Tốt về hình dáng mê cung nhỏ
chỉ hợp nhưng tốn nhiều khi cần phép toán phức tạp
KẾT LUẬN GỢI Ý SỬ DỤNG Quy mô mê
Heuristic gợi ý cung Lý do chọn Mê cung nhỏ
Euclid² (heuristic2) hoặc
Cân bằng giữa tốc độ và độ Octile (5) chính xác Mê cung lớn
Octile (5) hoặc Manhattan (4)
Tối ưu hóa hiệu suất tính
toán nếu không đi chéo và vẫn hướng đúng đích
Yêu cầu hình đi Tie-Breaking (6)
Tăng tính thẩm mỹ cho đường thẳng đẹp đi
PHẦN 3: GIAO DIỆN PHẦN MỀM
Giao diện khi mới khởi động: lOMoAR cPSD| 61552889
Giao diện khi không có hàm heuristic:
Giao diện khi đã tìm đường đi:
Giải thích giao diện hiển thị màu khi đã chọn hai điểm Sau
khi người dùng chọn đủ 2 điểm:
 Điểm xuất phát (source) lOMoAR cPSD| 61552889
 Điểm đích (destination)
Thuật toán được kích hoạt và hiển thị các trạng thái tìm đường trên mê cung
bằng các màu sắc khác nhau, giúp người dùng dễ dàng theo dõi quá trình tìm kiếm và kết quả.
1. Màu đỏ – Điểm xuất phát
 Vị trí mà người dùng click đầu tiên.
 Được tô bằng: fill(255, 0, 0) (RGB = Đỏ tươi).
 Luôn hiển thị lại sau mỗi lần vẽ lại.
2. Màu hồng tím – Điểm đích
 Là điểm người dùng chọn sau khi có source.
 Tô bằng: fill(230, 0, 172) (Màu hồng tím).
 Giúp dễ phân biệt với các điểm khác trong mê cung.
3. Màu vàng – Ô đang xét (considered)
 Các ô mà thuật toán đã xem xét nhưng không đi qua trong đường ngắn nhất.
 Màu: fill(255, 255, 77) – Vàng nhạt.
 Hiển thị tuần tự bằng animation theo frameRate(60) để người dùng thấy được quá trình tìm kiếm.
4. Màu cam – Ô được thêm vào openList / đang mở rộng Các ô đã từng được mở
rộng và là ứng viên đi tiếp.
 Điều kiện hiển thị: cell.isConsidered == true.
 Màu: fill(255, 119, 51) – Cam sáng.
5. Màu xanh lá – Đường đi ngắn nhất tìm được
 Là đường được truy ngược từ đích về nguồn sau khi thuật toán tìm xong.
 Hiển thị ở cuối animation.
 Màu: fill(0, 255, 0) – Xanh lá cây. Quy
trình hiển thị hoạt hình (animation)  Khi
người dùng chọn xong điểm đích:
 Gọi search() để chạy thuật toán.
Dữ liệu các ô đã xét (considered[]) sẽ được hiển thị lần lượt trong hàm draw().
Khi considered[] kết thúc, chương trình vẽ toàn bộ result[] (đường đi).
Cuối cùng, điểm đích và điểm xuất phát được tô lại để tránh bị đè màu. Source
code: https://github.com/Yukanimoto/IT3160 lOMoAR cPSD| 61552889 KẾT LUẬN
Việc xây dựng và giải quyết bài toán “Phần mềm tìm đường đi ngắn nhất trên
bản đồ dựa trên các thuật toán” được chúng em thực hiện dựa trên những kiến thức
được học trong môn “Nhập môn Trí tuệ nhân tạo” do cô – TS. Đặng Tuấn Linh giảng
dạy. Trong quá trình học tập cũng như nghiên cứu và phát triển đề tài, nhóm chúng em
đã học được rất nhiều về cách cài đặt và sử dụng các hàm heuristic để xử lý thuật toán
A* và thuật toán tham lam đồng thời xử lý các thuật toán không sử dụng heuristic như
BFS cũng như thuật toán sinh mê cung DFS, cũng qua đó giúp bọn em hiểu rõ về các
thuật toán hơn – thuật toán tìm kiếm thông minh để có thể sử dụng trong việc học tập
cũng như là công việc sau này.
Việc hoàn thành bài tập lớn này không chỉ là sự nỗ lực và cố gắng của cả nhóm
mà còn là sự giảng dạy tận tình của cô – TS. Đặng Tuấn Linh, chúng em cảm ơn cô vì
những kiến thức mà cô đã cung cấp về Trí tuệ nhân tạo để chúng em có thể hoàn thành bài tập của mình.
TÀI LIỆU THAM KHẢO
[1] Slide bài giảng nhập môn Trí tuệ nhân tạo
[2] Giải thuật tìm kiếm A* - https://en.wikipedia.org/wiki/A*_search_algorithm
[3] Tìm đường đi ngắn nhất - https://en.wikipedia.org/wiki/Maze-solving_algorithm
[4] A Study of Heuristic-based Path Planning in Complex Maze Using the A*
Algorithm with Cost Optimization and Visualization