Cấu trúc dữ liệu hai chiều cho tình huống này

Question

Tôi đang nghiên cứu một phần nhỏ của công cụ trò chơi của mình và tự hỏi cách tối ưu hóa một số phần.

Tình hình là khá đơn giản và nó là như sau:

• Tôi có một bản đồ của Tile s (được lưu trữ trong một mảng bi-chiều) (~ gạch 260k, nhưng giả nhiều hơn nữa)
• tôi có một danh sách các Item s mà luôn luôn là ít nhất và nhiều nhất là một gạch
• một Tile logic có thể chứa lượng vô hạn của Item s
• trong thực hiện trò chơi nhiều Item s là liên tục ly tạo ra và họ bắt đầu từ riêng của họ Tile
• Mỗi Item liên tục thay đổi Tile của mình cho một trong những người hàng xóm (lên, phải, xuống, sang trái)

Đến nay mỗi Item có một tham chiếu đến thực tế của nó Tile và tôi chỉ giữ một danh sách các mục. Mỗi lần di chuyển Item đến một ô liền kề, tôi chỉ cập nhật item->tile = .. và tôi ổn. Điều này hoạt động tốt nhưng nó là một chiều.

Trong khi mở rộng động cơ, tôi nhận ra rằng tôi phải tìm tất cả các vật phẩm có trong ngói nhiều lần và điều này làm giảm hiệu suất (đặc biệt là trong một số trường hợp, từng cái một).

Điều này có nghĩa là tôi muốn tìm cấu trúc dữ liệu phù hợp để tìm tất cả các mục của Tile tốt hơn so với O (n), nhưng tôi muốn tránh nhiều phí trong "di chuyển từ một ô đến một "giai đoạn (bây giờ nó chỉ là chỉ định một con trỏ, tôi muốn tránh làm nhiều hoạt động ở đó, vì nó khá thường xuyên).

Tôi đang suy nghĩ về cấu trúc dữ liệu tùy chỉnh để khai thác thực tế là các mục luôn di chuyển đến ô lân cận nhưng hiện tôi đang dò dẫm trong bóng tối! Bất kỳ lời khuyên nào sẽ được đánh giá cao, ngay cả những cách tiếp cận khôn ngoan hoặc khó hiểu. Thật không may, tôi không thể lãng phí bộ nhớ vì vậy một sự cân bằng tốt là cần thiết.

Tôi đang phát triển nó trong C++ với STL nhưng không có Tăng cường. (Có, tôi biết về multimap, nó không thỏa mãn tôi, nhưng tôi sẽ cố gắng nếu tôi không tìm thấy bất cứ điều gì tốt hơn)

Answer 1

struct Coordinate { int x, y; }; 
map<Coordinate, set<Item*>> tile_items; 

bản đồ này tọa độ trên bản đồ ngói để bộ con trỏ mục chỉ ra những mục đang trên gạch đó. Bạn sẽ không cần một mục nhập cho mọi tọa độ, chỉ có những mục thực sự có các mục trên chúng. Bây giờ, tôi biết bạn nói điều này:

nhưng tôi muốn tránh nhiều overhead trong "di chuyển từ một gạch khác" giai đoạn

Và phương pháp này sẽ bao gồm thêm chi phí hơn ở chỗ giai đoạn. Nhưng có thực sự bạn đã thử một cái gì đó như thế này chưa và xác định rằng đó là một vấn đề?

Answer 2

Với tôi, tôi sẽ bọc std::vector vào loại ma trận (IE áp đặt truy cập 2d trên một mảng 1d) điều này cung cấp cho bạn truy cập ngẫu nhiên nhanh chóng vào bất kỳ gạch của bạn (thực hiện ma trận là tầm thường).

sử dụng

vector_index=y_pos*y_size+x_pos; 

chỉ mục một vector của các kích thước

vector_size=y_size*x_size; 

Sau đó, mỗi mặt hàng có thể có một std :: vector của mặt hàng (nếu số lượng các mặt hàng một ngói có là rất năng động có thể một deque) một lần nữa đây là truy cập ngẫu nhiên chứa với chi phí rất tối thiểu.

Tôi sẽ tránh xa các thùng chứa gián tiếp cho trường hợp sử dụng của bạn.

PS: nếu bạn muốn bạn có thể có mẫu ma trận của mình.

Answer 3

Nếu bạn thực sự nghĩ rằng có mỗi cửa hàng gạch, các mục của nó sẽ khiến bạn tốn quá nhiều dung lượng, hãy cân nhắc sử dụng quadtree để lưu trữ các mục sau đó. Điều này cho phép bạn có hiệu quả có được tất cả các mục trên một gạch, nhưng lá lưới Tile của bạn tại chỗ cho chuyển động mục.