Kỹ Thuật Rendering Bản Đồ Trong Game Góc Nhìn Isometric

Anonymous trong So Sánh và Hệ Thống Nhúng

2014-01-01 Khoảng 1300 từ 6 phút

Bài viết này được hoàn thành từ hơn nửa năm về trước, khi dự án game mobile của chúng tôi vừa mới bước vào giai đoạn nghiên cứu tiền khả thi. Đây là bài chia sẻ nội bộ dành cho đồng nghiệp trong công ty. Vì yêu cầu bảo mật thông tin dự án trong giai đoạn phát triển nên bài viết chưa từng được công bố công khai trên blog.

Hiện tại sản phẩm đã chính thức ra mắt thị trường, không còn yêu cầu giữ bí mật thông tin, tôi sẽ dần đăng tải những nội dung kỹ thuật thú vị đã được nghiên cứu trong quá trình phát triển sản phẩm.

Công nghệ render isometric tileset - hay còn gọi là “động cơ góc nhìn nghiêng” trong cộng đồng quốc tế - từng được ứng dụng rộng rãi trong thời kỳ đầu của ngành công nghiệp game. Vào thời điểm tài nguyên tính toán còn hạn chế, đây là giải pháp tối ưu để tạo cảm giác không gian 3D trên nền tảng 2D. Tuy nhiên, khi bộ nhớ trở nên dồi dào hơn, công nghệ này dần ít được sử dụng. Một trong những thách thức lớn nhất của engine này là việc thiếu cơ chế Z-Buffer, khiến thứ tự render phải được xử lý cực kỳ cẩn trọng. Ví dụ như sơ đồ dưới đây:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


      /\
      / \
     /  \
     /   / /\
 /\  / B / /C \
 /A \ /   / \ /
 \ / /   /  \/
 \/ /   /
   \  /
   \ /
    \/

Khi ba hình thoi A, B, C đại diện cho vị trí đặt ba đối tượng công trình, thứ tự render chính xác sẽ như thế nào? Trong trường hợp không có Z-Buffer, chúng ta phải sử dụng thuật toán vẽ tranh (painter’s algorithm) - bắt đầu từ các đối tượng ở xa, dần tiến tới các đối tượng gần camera. Cụ thể, thứ tự render sẽ là A → B → C. Điều này có thể dễ dàng hình dung khi tất cả các công trình đều có chiều cao nhất định: B sẽ che khuất A, C lại che khuất B.

Tuy nhiên, giữa A và C có phải luôn ưu tiên vẽ A trước không? Câu trả lời là không hoàn toàn như vậy. Thứ tự này còn phụ thuộc vào vị trí của B. Như trường hợp sau khi A và C giữ nguyên vị trí, nhưng B được đặt theo hướng khác:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


    /\ 
    / \  
   /  \  
   /   \  /\
 /\ \  B \ /C \
 /A \ \    \ \ /
 \ / \    \ \/
 \/  \   /
     \  /
     \ /
      \/

Trong tình huống này, thứ tự render hợp lý sẽ là C → B → A. Điều này chứng minh rằng việc xác định thứ tự render giữa hai đối tượng không thể chỉ dựa vào tọa độ không gian của từng đối tượng riêng lẻ.

(P/s: Nếu tất cả các đối tượng đều có dạng hình vuông, vấn đề này sẽ không xảy ra. Khi đó ta chỉ cần sắp xếp theo tâm đối xứng của từng khối.)

Vậy làm thế nào để giải quyết bài toán này? Trong động cơ isometric tileset, mối quan hệ render giữa hai đối tượng bất kỳ có ba trạng thái: A ở trước B, A ở sau B, hoặc A và B không có quan hệ thứ tự. Mỗi đối tượng hình thoi A đều có một vùng không gian mở rộng phía trên gọi là “phạm vi ảnh hưởng” (tham khảo sơ đồ dưới). Mọi đối tượng nằm trong phạm vi này đều phải được render trước A.

1
2
3
4
5
6
7
8


\............../
 \....Vùng ảnh hưởng..../
 \........../
  \......../
  \../\../
   \/A \/
   \ /
    \/

Khi hai đối tượng A và B không nằm trong vùng ảnh hưởng của nhau, ta coi chúng không có quan hệ thứ tự render. Một phương pháp đơn giản là sử dụng thuật toán sắp xếp nổi bọt (bubble sort). Bắt đầu bằng việc quét toàn bộ danh sách để tìm ra đối tượng không bị ảnh hưởng bởi bất kỳ đối tượng nào còn lại, đưa nó lên vị trí đầu tiên. Cứ tiếp tục thực hiện cho đến khi hoàn tất danh sách. Phương pháp này dễ hiểu nhưng hiệu suất xử lý không cao.

Giải pháp tối ưu hơn không cần sắp xếp toàn bộ mà dùng cơ chế ngăn xếp (stack). Để minh họa rõ hơn, hãy tưởng tượng bản đồ được xoay 45 độ để nhìn như hình vuông thông thường. Xét ví dụ sau:

1
2
3
4
5
6


       +-+
   +---+ |C|
   | B | +-+
 +-+ |  |  
 |A| +---+ 
 +-+

Sau khi xoay 45 độ, đây chính là trường hợp tương tự như ví dụ đầu tiên. Thứ tự render đúng là A → B → C. Bắt đầu quét từ hàng đầu tiên từ trái sang phải, cho đến khi gặp đối tượng đầu tiên là C:

1
2
3
4
5
6


 ----------> +-+
   +---+ |C|
   | B | +-+
 +-+ |  |  
 |A| +---+ 
 +-+

Kiểm tra xem bên trái C đã được xử lý hết chưa. Nếu chưa, ta đẩy C vào ngăn xếp và bắt đầu một hàng quét mới, đảm bảo không lặp lại các khu vực đã xử lý. Nếu bên trái C đã hoàn tất, ta tiến hành render C và tiếp tục từ bên phải của C.

1
2
3
4
5
6


 ............+-+
 .... +---+ |C|
 ---> | B | +-+
 +-+ |  |  
 |A| +---+ 
 +-+

Theo quy tắc này, A sẽ được xử lý đầu tiên, tiếp đến là B và cuối cùng là C. Bởi nửa dưới của B bị A che khuất nên B sẽ phải nằm trong ngăn xếp cho đến khi A hoàn tất quá trình render. Chiều sâu tối đa của ngăn xếp không vượt quá số hàng của bản đồ. Với mỗi hàng quét, ta chỉ cần một mảng có kích thước tương ứng với số hàng để lưu trữ trạng thái quét. Giải thuật này có độ phức tạp thời gian và không gian đều là O(n). Cá nhân tôi đã triển khai thành công giải thuật này chỉ với khoảng 60 dòng mã C.

Từ quá trình render nêu trên, chúng ta thấy rằng để render toàn bộ cảnh vật chính xác, chỉ cần nắm rõ bốn thông tin cơ bản: có những gì trên bản đồ, từng đối tượng là gì, vị trí ở đâu và kích thước bao nhiêu. Những dữ liệu khác đều không cần thiết.

Dựa trên yêu cầu này, tôi đã thiết kế một cấu trúc dữ liệu tối giản, phục vụ đồng thời cho quá trình render và việc tạo bản đồ đường đi sẽ được đề cập ở phần sau. API quản lý thứ tự render chỉ cần một chức năng duy nhất: từ tọa độ hiện tại, tìm kiếm tọa độ của đối tượng cần render tiếp theo. Dữ liệu cần thiết cho API này chỉ là một mảng 2D, trong đó mỗi phần tử chứa thông tin về kích thước công trình tại vị trí tương ứng.