A* Pathfinding

Hẳn là bạn đã từng chơi game hoặc đang phải làm một game nào đó mà có phải điều khiển nhân vật hoặc viết AI cho bot đi từ một điểm A tới một điểm B, đi qua các trở ngại như sông, nhà, tường, … muốn làm được điều đó hãy đọc bài viết này của tui.

Thật ra những bài hướng dẫn về A-star Pathfinding có trên mạng có rất rất nhiều rồi, nhưng mình thấy toàn bài viết dành cho người đã biết cơ bản về A-star rồi. Thiết nghĩ nhiều người chưa biết khả năng đọc chúng sẽ khó hiểu và rất mất công.

Bài viết này sẽ giới thiệu các nguyên tắc cơ bản từ đầu, chúng ta sẽ từng bước thảo luận thuật toán A-star pathfinding làm việc như thế nào, và mình sẽ kèm luôn hình ảnh minh họa.

Với bản thân thì áp dùng Unity 3D vào ví dụ minh họa này sẽ rất rất dễ dàng với mình chỉ nháy mắt là xong bởi vì mình thành thục Unity 3D hơn. Nhưng ví dụ này mình sẽ viết trên Java trên android project để thấy rằng dù có sử dụng bất kỳ ngôn ngữ lập trình hoặc bất cứ nền tảng nào đi chăng nữa bạn đều có thể áp dụng được sau khi đọc bài viết này.

Chém thế thôi, chúng ta bắt đầu thôi nào.

Bài toán Pathfinding của sếp

**Cùng tưởng tượng, trong khu văn phòng bàn ghế được sắp xếp như trong hình dưới. Giả sử ổng sếp ABCS gì đó của tôi(ở đây tôi đưa hình ảnh con cá sấu vào vì không dám đưa ảnh của ổng lên sợ bị kết tội bôi xấu