Question How should I manage a grid on a dynamic map game?

I am starting a new game where dungeon rooms are generated randomly across a grid in a map. I have made a couple games with dynamic maps like this and some of these early decisions I make haunt me for the rest of the development process, and I am self taught so I really wonder what more experienced game developers would tell me about this.

The way I see it, there are two ways I can track the rooms in a dungeon.

- The first one is to just keep an array of rooms, every time one is added, it goes to the back of the array. So they would be sorted in creation order. Coordinates of the room would be recorded in the room's class.This is simple. But the thing is, when a room is created, it needs to check adjacent rooms in each 4 directions, and if there is one a path is created connecting them. And so I need to loop through all rooms when a new is generated to check where paths will be added. This is obviously not great on performance, specially when rooms are getting generated all the time.

- So my solution, which I've done in my last game, is to use a two-dimensional array to track the rooms. So when a room is added, it goes to a position in the array of arrays based on it's actual position in the game map. This way, when a room is created and starts checking the adjacent rooms, we don't need to loop anything, I can just use the expected adjacent coordinates to get the rooms I need to check.This makes programming a bit more complicated for me and therefore slower, as every time rooms are added to the left or bottom, the whole grid needs to be shifted, and calculations need to be made. I usually miss something and create bugs later on. But maybe this is how it has to be?

- I am now thinking I can just stick to the first method, and also use a system like the second one just to record the array indexes of the rooms, and make them easier to find. But maybe there's a nice little tool I don't know about that could help with this?

Sorry if this is a stupid or duplicate question, I wasn't able to find much when searching.

 

Put it all behind some kind of API so you don't care about how it is stored.

Likely a Dictionary indexed by a Vector2Int is a good starting point.

Define what is in the data structure based on what you want to store at a location:

- blocked
- walkable
- deadly (lava)

Define the API based on what you need to do with it:

- clear entire world
- set a cell to a value
- read a cell's value

You may even want several layers of stuff:

- the floor (or not) so you can have an abyss
- the walls (or not) so you can pass through them
---> doors might go in the walls layer

But keep it simple and layer stuff on as you go.

In the future you might extend the datastore to support pathing, some kind of "give me a grid of navigable positions here" for instance.

 

Why would you have to shift the grid? Is having negative coordinates a problem? Maybe I am missing something.

 

Wouldn't that make it rely on an internet connection? Is there a way to run a local db and API when running a unity game?

 

Well cause arrays can't have negative indexes, and the starting point would be 0,0 so. Unless there is a kind of List or something that accepts negative indexes?

 

By API I mean an interface between your game and your dungeon storage, nothing more.

It's still inside the program, it's just a set of operations that you consider necessary, as I listed above:

That's the lowest level API... one cell at a time, the part that handles, as you put it:

Creating an API helps you identify and scope the data and operations without agonizing about how you store or represent it.

Same thing applies to the next level up, essentially the "larger things made out of portions of the underlying grid" level of the application. Different logic is applied there, logic that may have backing in a graph theory of interconnected rooms, how to ensure all rooms are reachable, no subsets of rooms are isolated, etc.

Here's some more interesting reading you may enjoy:

https://journal.stuffwithstuff.com/category/roguelike/

 

Of course, my bad. Found this on stackoverflow. Keep track of positive and negative indexes in separate arrays.

Code (CSharp):

1. class MyArray {
2.     private MyMapType[] positives = new myMapType[size]
3.     private MyMapType[] negatives = new myMapType[size-1]
4.     MyMapType this[index] {
5.        get{return index >= 0 ? positives[index] : negatives[1-index];}
6.     }
7.  
8. }

Or maybe use a Dictionary with (Double, Double) as key, and dungeon data as value.

This may be different for you, but what works best for me isto use the solution that kind of follows my own logic. That doesn't mean you should never try new stuff. There is a lot of fun stuff to learn and use. This can still happen after you got it working one way and want to try for a "better" way.

 

Great responses! Thanks a lot Kurt-Dekker and ijmmai, can't believe I didn't think of the idea of using a separate array for negative indexes!
And yeah if I keep everything separated into a dungeon-storage interface, should be easy to change it later on if I run into trouble with this setup.