3DPathFinding : tìm đường 3D đơn giản trong game !

Chuẩn bị cho game mới,mình làm lại hệ thống trợ giúp tìm đường trong máy tính.
Hệ thống này được lập trình không yêu cầu độ chính xác cao mà chỉ cần gần đúng và nhất là phải có tốc độ xử lý nhanh để có thể chạy realtime trong game !
Mới làm được thế này thôi :
Ảnh minh họa :

Mình sẽ cập nhật thêm các nâng cáp tiếp theo !
Nâng cấp nhân vật khác !

Clip mới ! 

Mới làm xong phần nhân vật đi theo nhân vật chính !

Nhân vật bơi được ! (tạm đủ dùng thôi vì đây không phải nhân vật chủ lực),mình cũng đã làm nhân vật bay được xong rồi ! tương tự nhau thôi !

Còn tiếp !
Hoàn thiện tìm đường cho các loại nhân vật => làm xong phần Debug datda tìm đường !
Screenshot !

Clip mô tả hoạt động hệ thống tìm đường :

Phần giới thiệu này tạm xong ! => chuyển qua thực hiện phần khác : nhân vật đu dây, leo tường....tư thế chết Ragdoll  => lập trình cho nhân vật hành động !

TrainingChess - Học đánh cờ Vua

Từ trước tới giờ mình chỉ đánh toàn cờ tướng và đánh cũng không hay ! Vừa rồi ,mới mua đồ chơi cho cu Tin nhà mình . Mình chọn một bộ cờ Vua ! Nghĩ là chắc đánh chơi thôi ai dè càng đánh thì thấy nó càng khó, cách đi quân , dùng quân không giống cờ tướng chúc nào (ai nói giống chắc chưa chơi). Chọn một trò chơi cờ online thấy cũng ổn,nhưng tốc độ đánh và nhất là hiển thị quân sắp bị ăn,nước đi,...thì chưa!

Quyết định dùng kinh nghiệm lập trình cờ tướng của mình làm luôn cho cờ Vua. Tưởng dễ nhưng quá ra cờ Vua có nhiều ngoại lệ trong lập trình hơn cờ tướng.

- Vua cờ Vua đi thoài mái

- Tốt cờ Vua cóthể chuyển đổi thành quân cờ khác

- Tốt đi ban đầu có thể là 1 đến 2 ô, còn quân Vua thì có thể nhập thành....

Bao nhiêu đó thôi , để làm được chương trình cờ Vua thì mình thất mệt hơn cờ tướng. Nhưng số nước sinh ra trong cờ Vua thì không nhiều bằng cờ tướng (8x8 ô cờ thì làm sao nhiều bằng 9x10 ô)

Kết quả bước đầu của mình là :

Tạm xong phần lập trình cờ Vua trên máy tính với giao diện tương tự chương trình cờ tướng EasyChess mình lập trước đó.

Đã Xong phần chuyển sang hệ điều hành Android. Chưa xuất bản lên Google Play.

Chương trình cờ này có thể giúp cu Tin nhà mình tự học đánh cờ Vua ! Vì mình cũng không đánh lại nó. Thua quá trời. Chắc là 2 cha con cùng học. Mình làm programer còn cu Tin nà mình làm Tester !

-Mới cải tiến lại bộ font Unicode để hiện thị trên điện thoại độ phân giải cao một cách dễ nhất (chương trình sẽ tự thay đổi độ lớn font chữ tùy theo độ phân giải màn hình)
Ảnh chụp màn hình :






Sẽ up lên googlePlay sớm nhất có thể !
=> Đã xuất hiện trên googlePlay :

https://play.google.com/store/apps/details?id=com.TrainingChess.example

Cải tiến AStar có thêm collision

Mình chỉ làm kiểm tra va chạm một cách đơn giản thôi. Lý do là để không làm giảm tốc độ tìm kiếm của A* sao cho nó phù hợp với game.

Đây chỉ là một bước nâng cấp,nhưng nếu dùng cho game Kiến Trinh Sát thì đã quá tốt rồi. Mình không muốn chú kiến đi xuyên cây hay chướng ngại vật thêm vào trong địa hình như thế thì kỳ lắm.

Sau đây là clip mình mới cập nhật :

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ó :

Tìm đường địa hình 3D

theo thuật tóan A*

- Mình đang chuyển sang nghiên cứu làm chương trình tìm đường đi trong Map địa hình 3D bằng thuật giải A*. Kết quả cũng khá tốt !

- Mình đã thực hiện chuyển từ chương trình tìm đường bằng thuật tóan A* áp dụng trên Map 2D thành Map 3D.

- Trong dữ liệu Terrain của Irrlicht có phần LOD của nó, trong đó nó có chia ra làm nhiều phần Patch sẳn, mình lấy các dữ liệu này làm thành dữ liệu tìm kiếm ban đầu của chương trình.

- Phần tìm kiếm thứ 2 mình sẹ thực hiện là tìm kiếm chuẩn hơn áp dụng cho việc di chuyển từ Patch này sang Patch khác của Terrain. ( Cái này mình chưa thực hiện xong)

- Kết quả ban đầu của việc tìm kiếm dựa trên Patch của Terrain với Map là 257x257 thì kết quả trung bình <=1ms. Rất khả quan.

- Công việc còn lại là thực hiện tìm kiếm A* một lần nữa từ patch này sang patch khác kế cận. Cái này thì không dễ chút nào. Mình đang nghiên cứu template class Array của Irrlicht để ứng dụng nó một cách có hiệu quả nhất.

* Sau khi hòan tất chương trình này mình sẽ bắt tay làm game "Cô kiến trinh sát" với tòan bộ các phần mình đã nghiên cứu trước đó, và thêm một số phần mới : dữ liệu của game thì engine sẽ chịu trách nhiệm lưu và nạp tòan bộ một cách tự động, mình sẽ không làm gì cả.

* Hẹn gặp lại các bạn trong các entry kế tiếp ! Mình sẽ Update các kết quả của chương trình này vào phần commnet của nó.

- Clip mình mới thực hiện đây !