Lập trình 3D game dùng Irrlicht engine !

Dùng Astar PathFinding trong Irrlicht

Nói đến A* thì không ai còn gì lạ trong thuật toán tìm đường. Nó rất được ưa chuộn trong lập trình tìm đường trong game.
Sau thời gian mài mò mình cũng nghiên cứu được chút ít. Chủ yếu là làm sao dùng A* một cách hiệu quả trong Irrlicht engine.
Mình đã tìm ra được một cách sau :
- Mình dùng A* để tìm đường đi trong địa hình (Terrain) của Irrlicht. Đây là một SceneNode đặc biệt của Irrlicht, nó được dựng nên từ một ảnh 2D và trải ra như một lưới 3D cùng các biến đặc biệt để quản lý nó. Nó có thể được lưu và nạp dễ dàng.
- Mình chia phần tìm đường ra làm 2 cấp : tìm sơ bộ và tìm chi tiết.
+ Tìm sơ bộ :mình dựa vào các Box3D sẳn có được xây dựng trong Terrain mà tạo ra bước tìm kiếm đầu tiên. Nếu bước này thành công hay là vị trí Source và Target nằm cùng một Box3D thì mình sẽ tiến hành tìm chi tiết.
+ Tìm chi tiết : mình xây dựng một map2D nhỏ trong Box3D để tìm từng điểm cụ thể trên map2D đó và từ đó đưa ra đường đi tối ưu trong map2D.
+ Quá trình di chuyển từ source đến target : đầu tiên mình tìm một target tạm nằm trong box3D gần nhất. Thực hiện tìm chi tiết từ source đến target tạm. Di chuyển source đến target tạm. Khi source trùng với target tạm thì tìm target tạm kế tiếp…. cứ như thế cho đến khi source đến được đích.
-Nhược điểm của phương pháp này là đường đi từ source đến đích không được tối ưu cho lắm, không tìm được đường đi chi tiết một cách đầy đủ mà chỉ tìm được trong khoảng cách nhỏ đến target tạm.
- Ưu điểm là tìm rất nhanh phù hợp trong trò chơi đòi hỏi thời gian thực.
- Nâng cấp :
+ Sẽ có một số vị trí mà chương trình không tìm được đường đi.Lúc đó thì chương trình phải thực hiện hành động nào ? Đứng yên hay là đi loanh quanh.
+ Làm sao để chương trình tự tránh được các chướng ngại vật mà ta thêm vào trong game ?
* Mình đang thực hiện phần nâng cấp này…nhưng nói chung là không dễ. Trước hết cứ làm như thế đã.

Sau đây là clip của nó :