Cấu trúc dữ liệu để đại diện cho một mê cung

Question

Tôi đang viết một trò chơi mê cung năng động, sau mỗi lần cấu trúc mê cung sẽ thay đổi (Một số cửa sẽ đóng lại và một số cửa sẽ mở ra. Một số thứ như Triwazard in HP4). Bất cứ ai có thể gợi ý cho tôi cấu trúc dữ liệu nào sẽ phù hợp nhất để đại diện cho điều này?

Answer 1

Mê cung có phải là lưới hình chữ nhật không? Thứ gì khác?

Nó cũng phụ thuộc vào số lượng bản đồ sẽ chứa thông tin hữu ích (vé hoặc đồ vật).

Nếu đó là lưới hình chữ nhật và hầu hết ô vuông sẽ chứa SOMETHING, cấu trúc dữ liệu tốt là mảng 2D (mảng mảng), với mỗi phần tử của mảng đại diện cho 1 hàng, mỗi phần tử của mảng bên trong đại diện cho 1 ô trong hàng đó, là một đối tượng chứa dữ liệu liên quan đến ô đó (các ô lân cận nào có thể được di chuyển đến, ô nào chứa, có một ký tự trên đó).

Tuy nhiên, nếu mê cung không phải là hình chữ nhật HOẶC nếu phần lớn các ô trong mê cung lớn không thực sự chứa bất kỳ hữu ích nào (ví dụ: các khối không thể chuyển được), thì cấu trúc dữ liệu tốt là biểu đồ.

Mọi đỉnh của biểu đồ là ô có thể thực hiện được. Các cạnh đại diện cho các cặp ô mà bạn có thể di chuyển giữa (bạn có thể biến nó thành đồ thị được chỉ dẫn nếu một số cửa là chỉ một chiều). Mỗi đỉnh/ô là một đối tượng chứa thông tin trên ô đó (ví dụ: vị trí của nó trong mê cung vật lý sẽ được vẽ, v.v ...).

Lợi ích cấu trúc mảng mảng là nó rất dễ dàng để vẽ nó, và khá thẳng về phía trước để xử lý (bất kỳ di chuyển chỉ là trong/de-crement của một chỉ mục). Thêm/loại bỏ các bức tường dễ dàng như việc thay đổi dữ liệu trong 2 phần tử mảng của các ô lân cận.

Lợi ích cấu trúc biểu đồ là chiếm ít không gian hơn nhiều nếu mê cung vượt quá rất thưa thớt (ví dụ: chỉ có 1/100 trường vượt qua); đó là cấu trúc duy nhất có thể đại diện cho hình học ngẫu nhiên (ví dụ: không phải hình chữ nhật lưới) và quá trình xử lý khá đơn giản. Thêm/xóa tường dễ dàng vì nó chỉ thêm cạnh vào biểu đồ.