Một Thuật Toán Tìm Đường Đơn Giản

Một thuật toán tìm đường đơn giản

Cuối tuần trò chuyện cùng đồng nghiệp, hỏi qua về một số yêu cầu mới của dự án công ty. Phát hiện ra rằng dù là game thủ hay nhân viên thiết kế, gần đây đều mong chờ engine có thể thực hiện tìm đường tự động. Mặc dù tôi không quá coi trọng vấn đề này, nhưng thực ra đây cũng không phải chuyện khó khăn gì, định làm đại một cái vậy.

Hiện tại engine của chúng tôi dùng các đoạn thẳng vector để mô tả chướng ngại vật trong cảnh quan. Những đoạn thẳng này có thể được đánh dấu thủ công, hoặc tự động sinh ra từ mô hình cảnh quan, thậm chí là chuyển đổi từ phương pháp chia ô truyền thống. Trong môi trường vector này, việc tìm đường thực ra không quá phức tạp.

Chúng ta chỉ cần đánh dấu một số điểm mốc (waypoint) trong cảnh quan - những điểm này thường nằm ở trung tâm các khu vực rộng lớn không chướng ngại, hoặc tại các ngã rẽ. Việc cố ý thiết kế mê cung quanh co khiến người chơi vất vả mà không mang lại trải nghiệm thú vị thực sự là không cần thiết (trừ những game đặc thù như “Mê cung kỳ diệu” nơi mê cung là yếu tố cốt lõi). Phần lớn các cảnh quan game đều có độ phức tạp về mặt kết nối không quá cao, nên việc thiết lập waypoint thủ công là hoàn toàn khả thi.

Nhân tiện, việc tự động sinh waypoint cũng không khó khăn. Dù sao đây không phải yếu tố ảnh hưởng lớn đến hiệu năng, việc máy sinh waypoint cũng không kém xa cách so với thiết lập thủ công. Về thuật toán cụ thể thì xin phép không đi sâu. Yêu cầu chính khi thiết lập waypoint là: mọi khu vực có thể tiếp cận được trong cảnh quan phải có ít nhất một waypoint nhìn thấy được - điều này hoàn toàn có thể kiểm tra bằng lập trình.

Chúng ta sẽ nối tất cả các waypoint có thể kết nối trực tiếp với nhau, tạo thành một đồ thị. Đồ thị này có thể được lưu trữ sẵn để phục vụ cho các công việc tiếp theo một cách đơn giản.

Khi cần tìm đường giữa hai điểm bất kỳ trong cảnh quan, chỉ cần lấy từ điểm bắt đầu và điểm đích các waypoint gần nhất mà chúng có thể nhìn thấy. Sau đó dùng thuật toán Dijkstra để tìm đường đi ngắn nhất giữa hai waypoint này trên đồ thị.

Khi nhân vật di chuyển, cứ cách một khoảng thời gian lại kiểm tra xem có thể nhìn thấy waypoint tiếp theo trên đường đi không. Nếu có, sẽ di chuyển theo đường thẳng đến waypoint xa nhất có thể nhìn thấy. Kết quả là ta sẽ có một hành trình di chuyển tự nhiên.

Thực ra đây không phải thuật toán cao siêu gì, viết đại cũng có thể triển khai được.

Gần đây tôi mua thẻ tập gym một năm ở khu nhà gần công ty. Vài năm nay không tập luyện, thể lực và sức mạnh giảm sút rõ rệt. Quan trọng là tinh thần dạo này cũng không tốt như trước, cảm giác thiếu năng lượng. Đúng là nên bắt đầu đổ mồ hôi mỗi ngày, ăn uống ngủ nghỉ điều độ thì đầu óc mới minh mẫn.

Đã kiên trì đi ba lần rồi, tập với tạ nặng một chút đã thấy choáng váng, phải kiểm soát lại. Mới tập lại nên toàn thân đau nhức cơ bắp. Hôm qua làm vài hiệp squat, hôm nay đi lại còn thấy đau. Nhưng lạ là mấy ngày nay ăn uống lại rất ngon miệng. Một đĩa bò tái chanh có thể ăn sạch, trứng trong tủ lạnh cũng hết veo. Coi như tín hiệu tích cực đáng mừng.