Lưu Trữ Lộ Trình Trong Mạng Lưới Đường Xá

Trong trò chơi mà chúng tôi đang phát triển, hệ thống giao thông và hậu cần vận hành dựa trên mạng lưới đường bộ. Về bản chất, mạng đường bộ là một đồ thị vô hướng với các giao lộ đóng vai trò đỉnh và các đoạn đường là cạnh nối giữa chúng. Do số lượng phương tiện di chuyển trên mạng cực kỳ lớn, chúng tôi cần một phương pháp lưu trữ lộ trình của các xe này sao cho tối ưu về mặt không gian.

Trong đa số trường hợp, các phương tiện đều tuân theo nguyên tắc chọn đường đi ngắn nhất duy nhất. Điều này đồng nghĩa với việc nếu tồn tại một lộ trình xác định từ giao lộ A đến giao lộ B, toàn bộ xe đều sẽ đi theo con đường đó. Lợi dụng đặc điểm này, chúng tôi có thể hợp nhất việc lưu trữ nhiều lộ trình khác nhau.

Giải pháp được áp dụng là sử dụng một bảng băm với khóa chính là cặp (id giao lộ hiện tại, id giao lộ đích), và giá trị tương ứng là id giao lộ tiếp theo cần di chuyển. Cấu trúc này cho phép chúng tôi trước tiên dùng thuật toán Dijkstra để tính toán lộ trình tối ưu từ điểm xuất phát đến đích, sau đó phân rã lộ trình đó thành các đoạn nhỏ và lưu vào bảng băm.

Khi một phương tiện đến một giao lộ bất kỳ, hệ thống chỉ cần tra cứu bằng cặp khóa (vị trí hiện tại, điểm đến cuối cùng) để xác định hướng di chuyển tiếp theo. Cấu trúc này rất phù hợp để triển khai trong Lua table, thậm chí có thể tích hợp metatable để kích hoạt tính toán động cho những lộ trình chưa được tiền xử lý. Đặc biệt, bảng lộ trình này bản chất là bộ nhớ đệm nên có thể xóa bỏ và xây dựng lại bất kỳ lúc nào.

Khi mạng lưới đường xá đã ổn định, chúng tôi còn có thể tối ưu hóa thêm về mặt bộ nhớ bằng cách chuyển sang cấu trúc dữ liệu đặc biệt. Mỗi giao lộ trong trò chơi chỉ có tối đa 4 hướng kết nối (giao lộ chữ thập) hoặc 3 hướng (giao lộ chữ T). Chúng tôi đánh số các hướng từ 1 đến 4, và sử dụng 4 mảng riêng biệt để lưu trữ thông tin lộ trình.

Các lộ trình cùng hướng ra khỏi giao lộ sẽ được nhóm chung vào một mảng. Ví dụ, nếu phương tiện từ giao lộ 42 đến giao lộ 100 cần rẽ ở hướng 2 của giao lộ 42, cặp (42,100) sẽ được lưu vào mảng số 2. Mỗi mảng này được sắp xếp thứ tự, cho phép dùng thuật toán tìm kiếm nhị phân để kiểm tra nhanh xem một lộ trình có tồn tại hay không.

Với quy tắc không cho phép quay đầu hoặc quay ngược lại tại giao lộ, việc tra cứu hướng đi tiếp theo tại mỗi giao lộ tối đa chỉ cần 2 phép tìm kiếm nhị phân (và tại điểm xuất phát, 4 lần tra cứu sẽ xác định được tính khả thi của lộ trình). Khi mạng đường cố định, 4 mảng này có thể được lưu trữ trong một vùng nhớ liên tục, hiệu quả hơn cả về tốc độ truy cập lẫn tiết kiệm dung lượng.

Hiện tại, chúng tôi đã hoàn thiện một phiên bản triển khai đơn giản theo phương pháp này.