How to represent a map in a top-down perspective game with low algorithm complexity?

Question

This is the first time I develop a video-game, and I am kind of lost.

I would like to know about ways on representing 2D maps on a top-down perspective game...

(Like this one: vengadoravg.github.io/1/game.html btw, this is the first game I develop)

So far, I've found one way to represent a 2D map in a top-down perspective game:

Using a matrix. Where a normal floor place is represented by some number (or character), the obstacles are represented by a different number, and the enemies by another different number. This matrix would allow me to run graph theory algorithms and crazy things, but i think it would be, algorithmically, very complex, because the graph would be really populated and dense. Thus, all the sprites should be the same size, otherwise, the matrix would be really, really big.

Are there any other (better) ways?

In terms of algorithm complexity, which of them are the best to run graph theory algorithms?

I apologize if the question sounds subjective... but i think the superiority of an approach can be determined by its algorithmic complexity :)

Answer 1

I'll refer to map nodes as tiles for the purpose of explanation, but the principles are the same. If you have more than one node in an area, then your "tile" would contain an array or list of nodes. For all of these, graph theoretic applications can be applied, though the method of application becomes more or less complex depending on what specific algorithm you're using.

Now, if by matrix you mean a two dimensional array, that is probably the least algorithmically complex method, besides a one dimensional array where tile[x+y*width] = tile[x, y]. Structured this way you always know the distance of one tile to another, and can always access its neighbors without traversing memory in steps.

Next is a sparse matrix, where the information is structured like so (as a pseudo-structure):

Row : {
    PreviousRow,
    NextRow,
    ArrayOfTiles : { 
        ColumnIndex,
        TileImage
    }
}

Or, as an associative array, such as the .NET Dictionary where the keys encode the XY location and the values are objects containing tile information.

Finally, you can use trees such as Quadtrees for arbitrary tile sizes and/or densities. If your map is totally unordered, then a simple graph where each tile has references to its neighbors will suffice.

Mostly this depends on what your API provides. If you expect to have a lot of empty space then the associative array is going to be the most straightforward to use, since it can be made to act like a regular 2d matrix, without allocating space for unused elements, as well as having an insert, delete, and remove complexity of O(1). Otherwise a plain 2d array is fine.

In general, always pick the least complex data structure for your needs.