[Thảo Luận] Bài Toán Tìm Đường

Focker_c

Dạo này vẫn make game nhưng ít lên TTC quá
Điều cơ bản vẫn là ko có mem trong box của mình

Hôm nay đang đau đầu vs cái case này mà vẫn chưa giải quyết đc.
Nó ko phải là game maker mà chỉ là một bài toán yêu cầu tìm ra cách di chuyển tới mục tiêu theo một mẫu điều kiện thôi.

Hình :


Bài Toán : Tìm đường để vật thể đi từ A đến B theo từng ô.
Tọa độ :
X tính theo chiều ngang ( tăng dần từ trái qua phải)
Y tính theo chiều dọc (tăng dần từ trên xuống)

Ví dụ : Bước đầu tiên , vì tọa độ Y của A nhỏ hơn tọa độ Y của B, cho nên sẽ tiến xuống 1 bước.

Câu lệnh :

If (YcủaA) < (YcủaB)
then : Move down 1 ô

Nhưng theo câu lệnh trên thì đi đến ô 3 thì ko tiến đc nữa mà phải rẽ trái hoặc rẽ phải, ta sửa lại đoạn trên như sau :

If ( (YcủaA) < (YcủaB) ) và phía down phải có đường
then : Move down 1 ô

Và hiện tại vẫn chưa nghĩ ra điều kiện để rẽ trái hay phải :D

Nếu các bạn xài các Engine khác thì cũng phải trải qua bước lập trình "Path planning" này chứ ,

ducnguyendev

Mình không phải programmer nên không biết về mấy thứ nầy. Nhưng theo cơ chế bạn mô tả thì mình có thể bày ra được gợi ý dưới đây. Bạn coi rồi làm thử nhé ^

[size=medium]Cho vật thể là một char, luôn cho một object "checker" nằm cách 1 ô trước MẶT char.

Nếu cho char đi từ A đến ô 3 như hình trên thì MẶT char chà tường - tức là checker nằm trong tường (kiểm tra tường lần 1) thì không tiến tiếp được nữa.

Sau đó cho char quay qua phải tức MẶT char quay qua phải tức checker nằm trước mặt char cũng chuyển sang phải. Từ đây nếu checker kiểm tra tường lần 2 không bị nằm trong tường tức đường đi được, còn ngược lại thì đường k đi được.

Nếu đường k đi được, cho char quay ngược lại phía sau lưng (tức bên trái trên hình) để checker kiểm tra tường tiếp lần 3. Vẫn như trên - nếu k có tường thì tiến lên tiếp. Còn ngược lại thì cho char quay mặt qua phải của nó (tức quay lên phía trên). Lúc này chắc chắn phía trên sẽ k có tường vì đó là vị trí char bắt đầu khởi hành.

=> Cứ cho checker trước MẶT char kiểm tra tường 4 phía như vậy, chỗ nào k có tường thì đi. Đi sai đường thì tự mò đi lại tới khi nào đến đích thì ngưng hoạt động của checker và k cho char di chuyển nữa[/size].

Focker_c

@ducnguyendev : Cảm ơn bạn góp ý. Nhưng mình muốn A chọn luôn đc đường đi được hay đường ngắn nhất mà ko cần đi thử các đường.
^^

Nagi

Mình không rành mấy cái này nhưng chắc là google: algorithm pathfinding có thể sẽ hữu ích. :duanghich:

Death

Focker_c wrote:

@ducnguyendev : Cảm ơn bạn góp ý. Nhưng mình muốn A chọn luôn đc đường đi được hay đường ngắn nhất mà ko cần đi thử các đường.
^^

Checker đi thử các đường chứ đâu bắt A phải đi ?

Focker_c

Oh`, như vậy là checker đi check đường , nếu đường tới được B thì A sẽ đi.
Và nếu thế thì khi gặp ngã 3 thì tạo ra 2 checker
Mỗi thằng 1 ngả đường, rồi báo lại quãng đường cho chủ
Đường nào đến đc B và đi ít ô nhất sẽ đc lựa chọn

Nhưng thời gian để checker đi dò liệu có mất thời gian ko nhỉ ?
Kiểu như A đi tới ngã 3 , đứng yên đc 1 lúc mới đi thì hài

Nagi

Focker_c wrote:

Oh`, như vậy là checker đi check đường , nếu đường tới được B thì A sẽ đi.
Và nếu thế thì khi gặp ngã 3 thì tạo ra 2 checker
Mỗi thằng 1 ngả đường, rồi báo lại quãng đường cho chủ
Đường nào đến đc B và đi ít ô nhất sẽ đc lựa chọn

Nhưng thời gian để checker đi dò liệu có mất thời gian ko nhỉ ?
Kiểu như A đi tới ngã 3 , đứng yên đc 1 lúc mới đi thì hài

Không đâu... nó check nhanh lắm... :duanghich:

Focker_c

Để tối nay ngồi viết code test thử xem :D
Cảm ơn mọi người nhé.

Nói vậy chứ đường xa vẫn check mất thời gian chán

Focker_c

Ai có ý tưởng gì về cách checker báo đường về cho object chủ ko ? ^^

Vistrifa

Cái này tựa tựa như cái thuật toán pikachu ấy kiếm về mà mò

Focker_c

oh` :D thuật toán pikachu ^^
Cái này với mình khá hot
Để search trước đã, vì cũng đang code script dựa trên cái idea phía trên :D

Dang_Khoa

Thuật toán Pikachu =))