Data structure for representing the maze

I am writing a game with a dynamic maze in which after each change in the structure of the maze (some doors will be closed and some doors will open. Something like Triwazard in HP4). Can someone suggest me which data structure is best for representing this?

+8
data-structures maze
source share
1 answer

Will the maze be a rectangular grid? Something else?

It also depends on which part of the map will contain useful information (walkways or objects).

If the rectangular grid and most of the grid squares contain SOMETHING, then a good data structure is a 2D array (array of arrays), with each element of the array representing 1 row, each element of the internal arrays representing 1 cell in this row, which is an object, containing data related to this cell (to which neighboring cells can be moved, what the cell contains, there is a symbol on it).

However, if the maze is not a rectangle, OR, if most of the cells in the large maze do not actually contain any useful ones (for example, non-transition blocks), a graph is a good data structure.

Each vertex of the graph is a cell that passes. Edges are pairs of cells that you can move between them (you can make this an oriented graph if some doors are only one way). Each vertex / cell is an object containing information about this cell (for example, its location in the physical maze to be drawn, etc.).

The advantage of the structure of the array array is that it is VERY easy to draw and process it fairly straightforwardly (any move only in / index decomposition). Adding / removing walls is as simple as modifying the data in the elements of an array of 2 neighboring cells.

The advantage of the graph structure is that it takes up much less space if the maze passes very rarely (for example, only 1 / 100th of the field passes); this is the only structure that can be an arbitrary (for example, not a rectangular grid) geometry, and the processing is quite simple. Adding / removing walls is easy as it simply adds an edge to the chart.

+11
source share

Source: https://habr.com/ru/post/650515/


All Articles