How would you store a grid-based map?

[Undac]

Hello everyone! For a grid-based game, what would you use to store the grid?

 

Let's suppose we have this map (green cells are accessible to the player if there isn't another entity there, the white ones are never accessible to the player):

 

Right now I use:

struct gridCell{

vec3 position;

Entity *entity;

bool restricted;

}

 

and a matrix of MapGridHCellcount / MapGridWCellCount to store the grind.

 

The problem however is that in the exemple above, more than 60% of the cells are not accessible to the player... and this isn't even the worst scenario because my end result should look something like this:

 

What would you use in this situation? I've been thinking of using a graph implemented with adjacent lists, but I don't know if it's a good idea and the the thing is that I spend quite some time with the matrix implementation, so... I don't really want that to happen again.

 

PS: For the big map, the grid does not change, which means that instead of generating it each time I open the map, I could just create it by hand, save it in a file associated with the map and load it when the map is loaded.

 

PPS: Of course, another solution would be split my big map in a lot of smaller ones and keep the current system. I would like however, if it's possible, to have one big map.

[Rick]

If it's a game like Kings Bounty and the map is static once it's built why are you wanting to use a grid system at all? Why are you thinking this needs to be a grid based game? Build it in the editor and use LE's built in navigation system for movement.

[Undac]

That's a very good question, and I will try to explain why I opt for a grid system by describing the core idea of my game. Just like King's Bounty, it consists of two parts: the map-part, in which you move the group, interact with NPC, pick quests, manage your group, start fights etc; and the battles (in which you resolve disputes). My game however is set in a realistic setting (XV century South Africa) and you control this group of africans who managed to run after their village was pillaged and family enslaved. This group is often chased by animals, slave merchants or rival tribes from whom they stole supplies. This means that for me it is important to know on what kind of terrain do they travel on (rough terrain drains their stamina faster), what distance can they travel until they have to rest, where do they camp (popular paths means that they are more likely to get attacked), what ressource(s) can they find on the tile they camp on (if they camp near a river, they can fish and get bonus stamina) and so on.

 

Ok, now this is why I want a grid-system:

- it is easy to store all the information I need about the terrain using this tile-system;

- navmesh is a bit slow to load even for small maps (at least on my computer). By using the grid system, it would be not-very-hard to create a navigation system which "looks good", does not use physics and does not require 10sec to load every time I switch from battle to map;

- It is a design decision: I really love TBS games and I think that the grid system makes the rules clearer and easier to understand for the player.

[Rick]

OK, we are using a grid system with A* pathfinding so I understand your decisions now. If I was to look at your grid cell I'd say you don't need to store position in it. By using a 2D array you can calculate (easily and without any performance hit really) the cell position whenever you need to. It's very easy to convert from 3D position to cell position and cell position to 3D position (center point of the cell anyway). You also don't need to store the entity in a cell in LE. Curious as to why you think you'd need to store an entity per cell?

 

In our game the 2D map is a pathfinding map combined with SOME information. What does that mean? It means each cell just stores an int. 0 means it can be walked on and a non 0 means it can't be walked on. This tells the A* pathfinding library where things can walk. The non 0 part is the "some information" I talked about. We use these numbers to identify things about non walkable areas. For example 1 could mean nothing special but just can't walk here. 2 might mean water, 3 might mean something else, etc.

 

So now you have a 2D array that solves a lot of your problems.

[Undac]

For my project the 2d array is not a good solution, and here's why: I work alone and even if I cannot afford to make my world as big as King's bounty one, I would like it to be as big as 6 maps of that game (combined into a big one, which I hope that will give the impression of a big world!). Each King's bounty map is 64x64, which means that for my map, I would need a 64*64*6 (~=25.000 cells) matrix, out of which I will probably use only 35%. Another solution is to make the map like a maze, which means that I will save space, but I won't really get the desired map design.

 

If a use a structure like this one:

struct gridCell{

Vec3 position;

gridCell *left, *right, *topLeft, *topRight, *bottomLeft, *bottomRight;

//other data

}

I only need to store the cells which can be traveled. But now I cannot use Dijkstra's shortest path algorithm anymore. I probably have to know a standard distance between the center of any two cells (which means that I have to use circles instead of squares - not really a problem) and do backtracking on an area defined by standard distance between two tiles * how many tiles the group can travel, in order to find the shortest path. Is this a good idea? If not, which would be a good idea?

The thing is that I don't know which data structure should I use to store the grid system. (in fact, I don't really know when one should use a certain data structure and when not).

 

Curious as to why you think you'd need to store an entity per cell?

 

 

I use it for navigation purposes (the player's party is not the only moving party in the game and I need to know if the cell is populated or not). You suggestion is valid, but here is why I think it's more convenient to store a pointer value:

When I get into a battle, the party you see on the map reflects what kind of enemies you shall fight in the battle. Sometimes the interactions between player and NPC might move the said NPC or the player's group on a different tile. I obviously need to know on which tile is located a given object. I think it is just easier to get the object with gridCell->entity instead of scanning all the objects and comparing their locations to gridCell->position ; and it's easier to get a gridCell with personaj->currentGridCell ,instead of using a gridCell *getGridCell(Vec3 position) function. Other than that, a pointer to object, which 90% of the time will have nullptr value isn't expensive.

(personaj is just a class that extends model)

[Rick]

Our grid map is a 200x200 2D array (and we can go MUCH higher with no impact) making about double the cells you are thinking about. I feel like you are over optimizing/thinking before you even begin. If you do this your life will be A LOT more simplified in pathfinding and entity placement.

 

I personally think it's easier to get the entities location and do a simple calc to figure out which cell it's on.

 

row = math.floor(entity.position.z / TILE_SIZE)

col = math.floor(entity.position.x / TILE_SIZE)

 

This is a lot easier than having to worry about storing and updating and all the management that comes with swapping pointers between cells as things move. I just see more trouble than it's worth when you can figure all that stuff out. No need to be looping through all the objects. You won't be dealing with all the objects. Most of the time to get entities you are picking with the mouse, or doing a bounding box check to see what entities are in a radius around another entity and LE uses ForEachEntityInAABBDo() for that. Once you have the entities this way you do that simple calc to see what cell they are in and bobs your uncle

 

I just think you're making your life harder right out of the gate for no real advantage. If you want Lua type behavior where your entities can have code that runs every cycle (like UpdateWorld) then you can attach LE callbacks to your entities and handle it that way so you don't have to loop over any sort of list of things on your own.

[nick.ace]

Don't use Djikstra's. That algorithm is good for some things, but pathfinding in games is not one of them. It'll be way too slow. The run time complexities are of different magnitudes.

 

A 35% use rate is not enough to warrant a sparse matrix imo. If you are concerned with space, these can help:

• Avoid a Vec3 in the struct. Use floats instead or make another struct of floats. The Vec3 class has a bunch of overhead.
  
• Storing pointers is worse than storing a 3D array. The array gives you neighbors automatically, but adding up to 26 pointers to cover all directions will cost you more. It looks like you are using a pointer graph rather than an adjacency list.0
  

Space for storing graph the way you are doing:

• 0.35 * 25,000 * (12 bytes for position + 26 * 8 byte addresses on a 64-bit machine) = 1.8 MB
  

Space with just a 3D array:

• 1.0 * 25,000 * (6 levels) = 0.143 MB
  

That's a huge difference in savings! Of course, if you have too much extra information per struct, you could just have a pointer to another struct of class with extra information.

 

Also, using a bunch of pointers the way you are using them is bad for spacial locality, meaning that you are going to be getting a lot more cache misses, so it could slow down your program. You also would have to deference a bunch of objects which would cause even more memory lookups.

 

In the future, other possible solutions could be to have pointers between levels, so it would be a 1D array of 2D arrays. This could be useful if each level is a different size.

[Undac]

Well, I am not home now and I have some time to think about my project. Anyway, I started the thread because I am unsure of some things, so I thank you guys for the replies!

 

I can select and move objects to a certain tile with the mouse (the only thing I am missing here is that, for selected objects, I need to create an "aura" similar to the ones in Diablo 2 - well, more subtle than that, but I will think about it later). I still need however to mark the tile as populated if a character moves there. For entities that are supposed to do something every frame, I use this personaj->Update() function.

Your idea regarding the location is great, Rick, and don't know how I haven't thought of that, but thanks a bunch!

 

I will keep the matrix I already have and change the struct to something like this:

struct gridCell{

struct Position { float x,y,z; }

const bool restricted;

bool populated; // could be combined with restricted by making it an int, with these values: 0 - empy cell | 1 - restricted cell | 2 - populated cell

int terrainType;

char resource; // I could combine this with terrainType; 1003 being "mud" for "10" and fish for "03"

 

Yes, I changed my mind quite a bit regarding this and thanks for explanations and advices, Nick! Also, there would have been only 6 directions because each cell has 6 neighbors (it's a 2d grid and when calculating the path, the neighbors of neighbors would have been accessed with gridCell->left->topLeft or gridCell = gridCell->left; gridCell->topLeft;).

 

PS: Right now, my project actually uses Djikstra to calculate the shortest path on a smaller matrix (21*21 -> since the party can travel maximum 10 squares in any direction until they run off stamina and diagonal travel costs 1.5x straight travel stamina). Do you have a suggestion what to use instead of that?

 

PPS: Also, I am using the ForEachVisibleEntityDo() function each frame to update animations for characters visible on the screen (current camera). Possibly not a good idea because only characters have animations. Any ideas?

[Rick]

I'd still question why you want to store position for a cell. Your cells should be a constant size and because of that you calculate the cells position based on the row/col with (note this is the opposite of my other formula that caled row/col from position):

 

Here are the functions and constants we use in our game. We created a 256 size terrain and this lays a grid over that.

 

 

TERRAIN_HEIGHT = 13.44
TILE_SIZE = 1.28
TERRAIN_SIZE = 256
TERRAIN_GRID=200

-- utilities
function TileToWorld(row, col)
local x = ((col - 1) * TILE_SIZE) - (TERRAIN_SIZE / 2) + (TILE_SIZE / 2)
local z = ((row -1) * -TILE_SIZE) + (TERRAIN_SIZE / 2) - (TILE_SIZE / 2)

return Vec3(x, TERRAIN_HEIGHT, z)
end

function WorldToTile(pos)
local col = math.floor((((TERRAIN_SIZE / 2) + pos.x) / TILE_SIZE)) + 1
local row = math.floor((((TERRAIN_SIZE / 2) - pos.z) / TILE_SIZE)) + 1

return row, col
end

 

 

There is little need to store the position of the grid when you can calc it like this. Save yourself some memory and these calcs are fast and you don't do them all the time anyway. Only when certain things happen and you need to know the information which isn't every cycle usually.

 

 

About your PPS. I still think look into the LE entity callback functions. What I would suggest personally is that you mimic the Lua entity script structure in C++. Below would be the general idea on how you'd do that, but the jist is that there is a Draw() callback that I believe only gets called when the entity is visible. Put your animation update code in there so animations only happen when it's visible.

 

Look at the hooks at the bottom of the page. http://www.leadwerks.com/werkspace/page/api-reference/_/entity. These are all hooks that get called per entity when you attach the hook to an entity. If you are using C++ and OOP my suggestion would be to attach these hooks to the entities that need them (actors and other interactable/movable things). Now the bad part about this is that these are global C function hooks and that generally doesn't mesh very well with OOP. So what I do is the following (and this mimics the Lua entity script system but in C++):

 

 

1) create a base class with virtual functions for each of these hooks. ie.

class GameObject
{
private:
  Entity* e
public:
  GameObject(Entity* enitty) { e = entity; }
  virtual void OnDraw() {}
  virtual void OnCollision(params here) {}
  virtual void OnPostRender(Context* c) {}
  virtual void UpdateWorld() {}
  virtual void UpdatePhysics() {}
  virtual void UpdateMatrix() {}
};

 

2) Create derived classes from this GameObject class for certain entity types like Actor, Mine, Tree, TreasureChest, etc and define their virtual usages of those functions.

 

3) Now after you've loaded your map loop through all the entities and have some way to identify what kind of type it is and make a new instance of that class. If it's a Mine, then create a pointer to a Mine class. Also be sure to hook that entity to all those hooks.

 

4) Now you pass that pointer as user data to the entity itself. That pointer will now stay with that entity wherever it goes. http://www.leadwerks.com/werkspace/page/documentation/_/object/objectsetuserdata-r22

 

5) Now when those global C hooks are called (LE will call them automatically), it'll pass in the entity that it's running that function for. From that entity you get it's user data (your class instance) and cast it to GameObject pointer and call the corresponding virtual function. It's been some time since I've been in C but I believe it's:

 

void Draw(Entity* e)
{
  GameObject* obj = (GameObject*)e->GetUserData()

  if(obj)
     obj->OnDraw();
}

 

 

So now your derived GameObject classes become your entire game for the most part. This really gives you a nice OOP style with LE in C++.

[nick.ace]

EDIT: Sorry Rick! I keep responding while you're responding!

 

Yes, I changed my mind quite a bit regarding this and thanks for explanations and advices, Nick! Also, there would have been only 6 directions because each cell has 6 neighbors (it's a 2d grid and when calculating the path, the neighbors of neighbors would have been accessed with gridCell->left->topLeft or gridCell = gridCell->left; gridCell->topLeft;).

Oh, sorry. I misread that! You can still use an array without pointers though for an n x m matrix. It's relatively trivial to do. Every odd row could have m-1 elements, whereas each even row would have m elements. Just make a macro function (to avoid a function call) for each depending on the row, for example:

• topLeft=[n-1,m-1] for even row, [n-1,m] for odd row
  
• left=[n,m-1] for both
  

PS: Right now, my project actually uses Djikstra to calculate the shortest path on a smaller matrix (21*21 -> since the party can travel maximum 10 squares in any direction until they run off stamina and diagonal travel costs 1.5x straight travel stamina). Do you have a suggestion what to use instead of that?

 

Yeah, use A*. If you have a destination in mind, then A* will be faster because you use a heuristic to first estimate the shortest path and then actually do the calculations. Djikstra just computes everything in the area, which is very inefficient.

 

PPS: Also, I am using the ForEachVisibleEntityDo() function each frame to update animations for characters visible on the screen (current camera). Possibly not a good idea because only characters have animations. Any ideas?

 

I would hope that the view frustum culling is done before sending data to the GPU. If that is the case, you will be gaining nothing by animating like that, and it would even hurt performance (not by much though) if the characters already have scripts. You should just animate in the character's script.

[Ma-Shell]

I agree with Rick and nick.ace: You should really use a 2D-array for that purpose, which also means, you neither have to store the cell's position, nor its row/column, as you can get that from the array. The memory usage should not be a problem.

If you really notice that you have a problem with the memory consumption, you might want to use quadtrees:

Devide the map into four parts. For each part store whether it contains walkable cells. If it does not contain walkable cells, you can just stop there. If it does contain walkable parts, you further divide the tile into four tiles and repeat the procedure until you reach your final grid resolution. That way you can discard big chunks of un-walkable tiles earlier. I hope, you can understand my explanation. Just tell me, if you need further explanation on this.

While you can save some memory with this technique, using quadtrees instead of arrays also comes with a price, because now you actually have a time complexity of O(log(n)) (or something similar; I never liked calculating runtime complexities ) instead of O(1) in order to access the individual cells.

 

To sum this up: You should be fine using an array! If you really don't want to do that because of the memory consumption, use quadtrees/octrees. UNDER NO CIRCUMSTANCES use a linked list for this purpose.

Furthermore, DO NOT explicitly store the position or row/column of the cells, as you can get them as the index of the array.

[Undac]

Sorry, I could not reply earlier, but thanks everyone for the advices!

For now I will drop what you see in the image from the initial post, and just stick with a square grid stored in a 2D array. I remember studying about A* (divide the matrix in squares if obstacle and move on diagonal), but it's been a while and never used it, so I will have to do some research - thanks for the suggestion! Also, thanks for the update animations part, Rick!

 

PS: One last thing: is there a way to create an user interface in Leadwerks? Basically, I draw textures with context::DrawImage and store their locations. If the mouse cursor is over such an "interface object" on LMB event, I proceed to check which children of the said object is selected; otherwise (if the mouse is not over an "interface object"), I do whatever should happen in game on LMB event - and I pretty much call this an "interface". Is there a way to handle interfaces in Leadwerks?

(another layout, but pretty much the same idea).

 

PPS: You also highlighted a thing I did with other classes as well: store extra information which can be easily calculated or obtained otherwise.

[Rick]

No GUI (graphical user interface) in Leadwerks. What you are doing is what we each need to do at this time. Feel free to make a system for others to use