Trong Java (Swing), nói rằng tôi có một trò chơi 2D, nơi tôi có nhiều loại thực thể khác nhau trên màn hình, chẳng hạn như người chơi, kẻ xấu, powerups, v.v. người chơi di chuyển trên màn hình, để kiểm tra hiệu quả những gì đang ở trong vùng lân cận của người chơi, tôi nghĩ tôi muốn truy cập chỉ mục vào những thứ gần nhân vật dựa trên vị trí của họ.Ánh xạ hiệu quả các vị trí thực thể trò chơi trong Java
Ví dụ, nếu người chơi 'P' bước vào yếu tố 'E' trong ví dụ sau ...
| | | | | |
| | | |P| |
| | |E| | |
| | | | | |
... sẽ làm điều gì đó như:
if(player.getPosition().x == entity.getPosition().x &&
entity.getPosition.y == thing.getPosition().y)
{
//do something
}
Và thats tốt, nhưng điều đó ngụ ý rằng các thực thể giữ vị trí của họ, và nếu tôi có MANY thực thể trên màn hình tôi sẽ phải lặp qua tất cả các thực thể có sẵn và kiểm tra từng vị trí chống lại vị trí người chơi. Điều này có vẻ thực sự không hiệu quả đặc biệt là nếu bạn bắt đầu nhận được tấn của các thực thể.
Vì vậy, tôi sẽ nghi ngờ tôi muốn một số loại bản đồ như
Map<Point, Entity> map = new HashMap<Point, Entity>();
Và lưu trữ thông tin quan điểm của tôi ở đó, vì vậy mà tôi có thể truy cập vào các thực thể trong thời gian liên tục. Vấn đề duy nhất với cách tiếp cận đó là, nếu tôi muốn chuyển một thực thể đến một điểm khác trên màn hình, tôi phải tìm kiếm thông qua các giá trị của HashMap cho thực thể mà tôi muốn di chuyển (không hiệu quả vì tôi không biết nó Vị trí điểm trước thời hạn), và sau đó một khi tôi đã tìm thấy nó loại bỏ nó từ HashMap, và chèn lại nó với các thông tin vị trí mới.
Bất kỳ đề xuất hoặc lời khuyên nào về cấu trúc dữ liệu/định dạng lưu trữ nào tôi phải sử dụng ở đây để có quyền truy cập hiệu quả vào các thực thể dựa trên vị trí của chúng cũng như vị trí dựa trên thực thể?
Cảm ơn lời khuyên, tôi sẽ nghiên cứu phân vùng không gian hơn. –
Tôi sắp xếp hai bản cài đặt bảng trò chơi để chứa 1.000.000 thực thể được thêm ngẫu nhiên vào khu vực 1920x1080. Sử dụng một vùng chứa 1080x1920, tôi đã có 0,004 ms để chèn, 0,003 ms khi xóa và 0,00 ms để yêu cầu danh sách tất cả vùng chứa trong vùng 3x3. Sử dụng phân vùng không gian nhị phân động, tôi đã chèn 0,007 ms, 0,003 ms xoá và 0,007 ms truy vấn cho các phân vùng giao nhau với vùng 3x3. Hiệu suất và mức sử dụng bộ nhớ trên BSP sẽ tốt hơn đối với các thực thể không được phân bổ thống nhất. – Gunslinger47