Chào anh chị.
Em có một trò chơi dạng grid sử dụng A* để tìm đường đi. Em thấy nó tìm đường khá tốt ngoại trừ trường hợp không tìm được đường tới đích, trường hợp này nó phải duyệt qua khá nhiều ô làm cho chương trình chạy khá chậm. Em muốn hỏi là liệu có cách nào để biết một điểm muốn đến là không thể đến được không ? Ví dụ một nhân vật muốn đến một điểm bị bao quanh bởi 4 bức tường thì nhân vật này sẽ không thể đến đó. Như vậy nếu biết là không thể đến thì em sẽ không phải sử dụng A* để tìm đường nữa, cải thiện tốc độ chương trình !
Em xin cám ơn .
Kiểm tra nếu đích đến bị chặn
map của em là map động hay map tĩnh :V Nếu map tĩnh hay ko thể xây hoặc phá các bức tường đã có sẵn thì em chạy loang map của em trước, chia thành nhiều mảnh kết nối với nhau, đánh số từng ô thuộc về mảnh nào. Khi lấy đường đi từ ô A tới ô B thì em ktra A B cùng thuộc 1 mảnh thì mới chạy A* :V
ví dụ
. . # . . .
. # . . . .
# . # . . .
. # . . . .
. . . . . .
thì sau khi loang sẽ chia thành 3 mảnh:
1 1 # 2 2 2
1 # 2 2 2 2
# 3 # 2 2 2
2 # 2 2 2 2
2 2 2 2 2 2
đi từ mảnh 2 tới mảnh 3 hoặc mảnh 1 là bất khả thi :V Đi từ mảnh 2 tới bất kì mảnh 2 nào khác thì ok :V
map động thì khi xây/phá tường thì chạy lại loang lại 1 lần nữa? Chắc ko khả thi :V :V :V Mà map của em rộng bao nhiêu :V 300x300 thì chắc A* luôn ko tệ đâu :V
4 Likes
Map của em tầm 50 * 50 mà sao em đã thấy khá nặng nhỉ, em kiểm tra thì mỗi lần duyệt qua cái A* đó chỉ mất tầm 1 ms, còn đối với mỗi lần mà không tìm được đường nó mất tầm 23 ms trở lên. Map em là map động, vì có khoảng 15-20 đối tượng sẽ liên tục di chuyển từ ô này sang ô kia. Em cũng có tìm trên mấy trang nước ngoài, hình như cách anh giống kiểu fill flood, không biết đúng không nhỉ. Em thấy cái đó có vẻ không ổn, ví dụ có một đối tượng đứng ở một ô, thì coi như ô đó bị chặn rồi, vậy nếu một vòng lặp có nhiều đối tượng cùng di chuyển thì phải loang lại nhiều lần, em nghĩ nếu Map rộng thì loang lại quá nhiều sẽ khiến chương trình bị chậm.
1 Like
50x50 mà mất 23ms (duyệt tất cả 50*50=2500 ô) mỗi lần chạy A* cho 1 đối tượng thì 15-20 đối tượng là mất nửa giây rồi :V vậy chắc implementation hoặc lựa chọn ctdl của em có vấn đề :V
4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?