Thuật Toán Tìm Đường Trong Game Kiểu COC
Bài viết này thuộc thể loại tài liệu cũ, được viết vào đầu năm 2013 khi tôi vừa trải nghiệm game COC và chia sẻ nội bộ trong công ty. Lúc bấy giờ công ty chưa quyết định phát triển dự án mobile, tuy nhiên có ý định xây dựng sản phẩm theo mô hình COC-like với yêu cầu bảo mật cao trong quá trình nghiên cứu, vì vậy các tài liệu kỹ thuật liên quan đều chưa công bố chính thức.
Hiện nay game của chúng tôi đã ra mắt thị trường, vì vậy tôi sẽ lần lượt đăng tải các tài liệu nghiên cứu từng lưu giữ lên blog công ty.
Hệ thống tọa độ bản đồ
Bản đồ trong COC có kích thước 40x40 ô, ngoài ra có thêm 2 ô ở rìa bản đồ không thể đặt công trình. Như vậy toàn bộ bản đồ thực tế là 44x44 ô vuông. Tuy nhiên về mặt xử lý tọa độ, nếu chỉ dựa trên ô vuông thì không đủ độ chính xác. Phiên bản chính thức của COC có vẻ sử dụng hệ thống phân giải theo pixel, điều này khác với phương pháp chúng tôi đề xuất trong bài viết này. Ở đây chúng tôi giới thiệu một cấu trúc dữ liệu khả thi.
Hệ thống bản đồ cần được xây dựng dựa trên các đỉnh của lưới ô vuông. Mỗi ô vuông được xác định bởi tâm điểm và bốn góc, tạo thành 9 điểm tọa độ. Điều đó có nghĩa là đơn vị tối thiểu là nửa ô vuông. Hệ tọa độ sử dụng phạm vi [0,88], như minh họa dưới đây:
|
|
Đặc điểm công trình và không gian chiếm dụng
Ngoài diện tích hiển thị ban đầu, mỗi công trình còn có kích thước vật lý thực tế. Ví dụ đối với mỏ tài nguyên, diện tích bề ngoài là 3x3 ô nhưng không gian thực tế có thể như sau:
|
|
Điều này cho thấy công trình 3x3 chiếm 9 điểm tọa độ (#). Khi lính bộ tiến hành tấn công, họ cần đứng ở các điểm xung quanh (+). Thiết kế không vuông vức giúp binh lính bao vây theo hình bát giác thay vì hình vuông. Đối với công trình 2x2:
|
|
Trại lính với kích thước 5x5 tuy chiếm diện tích lớn hơn 3x3 nhưng binh lính vẫn có thể tiếp cận gần để tấn công. Khi tấn công, binh lính phải đối mặt trực tiếp với công trình nhưng hướng phát động động tác lại hướng về tâm công trình.
Phương pháp tìm đường
Khác với thể loại game RTS truyền thống, COC chủ yếu yêu cầu đơn vị di chuyển để tấn công công trình cố định (trừ trường hợp lính đánh nhau). Trước khi địa hình bị phá hủy, tuyến đường di chuyển chủ yếu cố định. Số lượng công trình có giới hạn, kết hợp với kích thước bản đồ nhỏ, mở ra không gian tối ưu hóa lớn cho module tìm đường.
Theo tôi, việc tiền xử lý có thể giảm tải tính toán đáng kể. Chúng tôi thiết lập một bản đồ đường đi riêng cho từng loại công trình. Lấy công trình 3x3 làm ví dụ:
|
|
Trong đó các số 0,1,2 đại diện cho khoảng cách thực tế đến công trình. Chỉ cần thực hiện quét toàn bản đồ một lần, chúng ta có thể ghi nhận khoảng cách ngắn nhất từ mọi điểm tọa độ đến công trình. Khi di chuyển, lính bộ chỉ cần chọn điểm lân cận trong 8 hướng có khoảng cách ngắn hơn để di chuyển đến. Khi khoảng cách bằng 0 thì triển khai tấn công. Cần lưu ý rằng di chuyển chéo không nhanh hơn di chuyển ngang dọc.
Đối với đơn vị có tầm tấn công khác nhau, chúng ta tạo bản đồ riêng biệt. Nhờ đó lính cung sẽ triển khai bắn ở vị trí vừa đủ tầm xa nhất.
Xử lý tường thành
Tường không được tính là công trình, ngoại trừ lính nổ mìn, tất cả đơn vị khác đều không coi tường là mục tiêu di chuyển. Do đó tường không cần bản đồ riêng (trừ trường hợp đặc biệt của lính nổ mìn). Đối với hệ thống đường đi, tường là chướng ngại vật với trọng số cao (có thể bỏ qua khi dùng lính có khả năng nhảy). Ví dụ, công trình 3x3 được bao bọc bởi tường như sau (với 2 lối vào):
|
|
Thể hiện dưới dạng tọa độ:
|
|
Nếu quy ước độ khó phá tường là 6 (nghĩa là phá tường dễ hơn di chuyển qua 6 ô), ta có thể ghi nhãn bản đồ như sau:
|
|
Khi đường đi gặp tường, đơn vị sẽ ưu tiên tấn công tường trước.
Tổng kết phương pháp
Thực tế, chúng ta chỉ cần tạo bản đồ đường đi riêng cho từng loại lính dựa trên mục tiêu công trình ưa thích. Bản đồ này cho biết tại bất kỳ vị trí nào trên bản đồ,