Grid System

TrinityCore Development TrinityCore Code Discussion
1

I was giving a look at the Grid System and despite it is working, there a lot of strange things which are really really strange. More in details:

  1. The only documentation about it can be found in Grid.h, in GridLoader.h, and in NGrid.h, which however consists in a few line of comments (most of them full of grammar errors and hard to understand).

  2. A whole class has been commented out (i.e. GridLoader.h) in an old Megamage commit, and no further details can be found over the comments and forum topics about it.

  3. Many, many methods have been commented out without any documented reason (not sure if they have been moved to actual implementation or just deleted)

  4. The terms are quite misleading since the Grid actually seems to be a cell (contained in an NxN grid i.e. NGrid), even though there exists also a Cell which is used in other places and there is no clear distinction between what should be used for what else.

  5. There seems to be no clear distinction between the abstract Grid and its concrete implementation, making it very hard to do whatever change.

Since it seems that ages of partial updates have been done to it, I wanted to ask if there is someone ( more skilled than I am in C++ ) that would like to discuss the problems and go in depth in order to renew this old system that hasn’t seen a real update since the beginning.

2

The points above are nothing strange or a problem, it’s the average code quality of tc sources. You seem to face the common issues of Code Refactoring

3

+1 for finaly rewrite the grid system.

As long as i know Trinity (~2010) people and devs discuss about “rewriting the grid monster” and it could be realy a benefit for TC, but who takes the time for it? who has the skills, and will this grid be better then the old one?

… who knows …

4

Further investigation has to be done. IMHO the toughest part is not to rethink the Grid System, but instead to understand its components right now, and to understand which was the original meaning for all of them. Once we have a clear idea of the overall, it will not be too complex to rewrite it, and to do it in such a way that future generations can understand it.

5

I’ve been looking more in depth the current system and two completely separated actions should be considered:

[ol]
[li] Refactoring the classes: seems the most crucial at this time since they make things more complicated than they actually are.[/li]This is probably what i will focus more in the upcoming days.
[li] Change the data structures and algorithms: this point which has been discussed some times in community topics is much more delicate.[/li]
More precisely the current data structure is a two-level matrix which basically divides each map in 4096 grids which are themselves made of 64 cells. (Which gives a total of 262.144 cells per map).

Pros: In-game coordinates are translated in grid&cell coordinates and so direct access to the actual cell is possible in nearly no time (O(1) complexity).
Cons: there are just 2 possible levels of preloading: map-preloading (i.e. all grids related to a map are loaded ahead of time) or grid-preloading (i.e. a specific area of 64 cells of the map is preloaded). This makes bad performance for low-populated servers where most of the grids have to be reloaded nearly with every request, while it makes quite good performance for high-populated servers because if all grids are loaded the access time to a specific cell is very low. Furthermore a generic search of a generic object in the grid requires in the worst case to navigate all the cells (O(n) complexity).

A suggestion on this topic is about switching to a quadtree data structure (since 49 is 262.144, a 9-level quadtree would be the equivalent to the current grid in terms of cells number).

Pros: refinable preloading, thanks to the 9 level of depth a conf flag would make it possible to choose the size of the grid preloading, which is a big benefit for small servers. A generic search of a generic object in the grid would require a maximum of 9 levels of loop (O(h) complexity).

Cons: a tree is more complex than an array, so the overall memory amount of the grid would be higher, making it bad for big servers. Furthermore the access to a specific cell requires 9 levels of loop, which is not much, but still worse than the current system.
[/ol]
While the first point is quite easy and immediate, the second requires more analysis, since IMHO it all depends on the most common operations that are done on the grid (I don’t have any information about this yet).

Please share your opinion or feel free to ask if something wasn’t clear enough /emoticons/default_smile.png

6

iirc its also currently not possible to have different visibility range values for certain mobs. Back in the day on retail I remember that i could see Fel Reaver walking around in Hellfire Peninsula from far far away.

Edit: I just got told that “void WorldObject::setActive(bool on)” does exactly this. but for ~500 yards max.

7

​could you link the sources related to this data ?

8

The following should be the exact code lines. Note that the Grid type actually is a Cell, at least this is what comments in NGrid class say (and it did make sense to me)

In Map.h - line 647 :

NGridType* i_grids[MAX_NUMBER_OF_GRIDS][MAX_NUMBER_OF_GRIDS];In NGrid.h - line 190 :

GridType i_cells[N][N]And in GridDefines.h lines 35 - 37 & lines 82-83 :

#define MAX_NUMBER_OF_CELLS 8 #define MAX_NUMBER_OF_GRIDS 64 ... typedef Grid<Player, AllWorldObjectTypes, AllGridObjectTypes> GridType; typedef NGrid<MAX_NUMBER_OF_CELLS, Player, AllWorldObjectTypes, AllGridObjectTypes> NGridType;

9

First of all, nice explanations @Polaretto for me its totaly clear, and i think a lot of people will thank you for this if they want to dive into the grid system code as well.

A QuadTree Structure gives you more level, for sure it gives you the possability to improve preloading, but is preloading “groups” of cels realy so important, and whats about npcs traveling between this groups… for me personaly even on low populated servers it was never a problem to keep grids active, there are much more other tings who are consuming much more performance (LOS / pathfinding and AI stuff)

Maybe its usefull generaly, but normaly on small servers you have more resources free, and it’s not so important to save resources then on big servers.

For the Grid Search, there would be nice to have a kind of “Indexing Structure” like a DB server does,
the Grid it self is a “Data Table” and there are several index, (most Hashsets (unique)) with pointer to the related cells.
for example you search for a creature in Grid (by GUID or by Entry (2 different “index”)) you get quickly the related cell or list of cells by using a Hashset with key for Guid / Entry (O(1)) in Theory.
It stores only the pointer or the cell and consumes not much memory (btw memory is cheap even on servers)

For sure there are much more complex grid searcher, but a lot can be indexed.

Index lists will be updated if needed on Update Cycle

[only a idea, don’t know if similar stuff already exists…]

But how ever preloading is not only related to server population, there are for example active npcs without any player in grid, maybe even traveling between cells by waypoints like “caravans” or similar. This is problematic because the grid needs to be active, if not the path resets and the npc will be found all times a player enters the grid on a low populated server at the start point. this is not like on blizz.

I must tell you the truth, i never looked at the grid code since 2012 and if there are made improvements for this text uppon could be depricated…
but how ever, this are my two cents, nothing more

PS: @MidnaAT Hi, its nice to see you still around somewhere /emoticons/default_wink.png

10

​Indexing is basically what grids and data structures more in general exist for. /emoticons/default_smile.png

But how ever preloading is not only related to server population, there are for example active npcs without any player in grid, maybe even traveling between cells by waypoints like “caravans” or similar. This is problematic because the grid needs to be active, if not the path resets and the npc will be found all times a player enters the grid on a low populated server at the start point. this is not like on blizz.

And that is the point about changing the grid system.

More practically from the previous posts, I must say that I agree with most of the developers that say that there’s no need to change the grid (at least about the low level part).
IMHO it’s all about the trade-offs between direct access and search and between complexity and simplicity. It’s clear that the current grid doesn’t work good with events and in non-player changes, but it’s also clear that these problems mainly exist when the grid is not fully loaded. Since memory cost decreases quite rapidly, it’s not a big problem as it used to be.

By looking at how Blizz does this it is also clear that their grid is always loaded, even though we have no data about how do they store it.
So finally, many things could be done but probably it’s better to focus on higher level problems, since after all the grid works just fine.

Note: There are many ways in which the existing problems may be fixed, for example by using a “layered grid”, where for example an “event layer” is always loaded and can interact only with things at the same layer.

11

[COLOR=rgb(82,82,82)]Indexing is basically what grids and data structures more in general exist for.

Sure, but wat i wanted to tell is that the Grid index data in a certain way, this has the effect that some seachs are fast ~O(1) and some need to loop around ~O(n), like you have told in the first example,

this is not only a marginal scenario, some searches are heavily used, and could proft from a “own index” to execute this searchs faster ~O(1)

About Bizz, i’m agree with you that their grid must be always loaded (or similar state, how ever) but this doesn’t make much sense for smaller servers.

i agree as well hat higher level problems are more accute to fix and the grid work as it is, but a “refactored grid” would be maybe open new possabilities to resolve problems with visibility range, or active objects in grid, (most performance related problems)

a layered grid would cause the same problems if blizz decides (or maybe already exists) a npc, or what ever moving / acting over the layer limits!

for me the grid must be flexible enougth to handle stuff like on blizz, and don’t add new limitations only to gain performance.

For me this could be done with the actual grid structure, without layers or anything, the key point of refatoring could be the loading / reloading / unloading part, maybe to separate handling for active NPC cells from cells only activated by player

example:

1: you have a NPC moving around in 3 cells, even if no player arround…
=> the first cell will be loaded, npc moves to second cell, then first cell goes to idle state
=> first cell will unload after some idle time, but the npc will return and activate the cell again (load)
=> this will happen for all cells
(it could be improved by keep those cells active / idle but don’t unload)

2: you have a player on the map who runns down a lot of cells but its not periodicaly

=> cells will be loaded and unloaded as expeced
=> no need for any changes

this is only a example to give you a idea what i want to tell…

other example: you want to improve the initial loading of the grid (most time consuming) and you have enougth memory:

=> on server startup the core loads already all map / mmap / vmap… data needed to load all possible grids
=> this data will be stored in a already usable format (data structure) for the core
=> now you can load an unload grid (cells) much faster cause you don’t need to load this data from HDD or / and DB.
=> it costs memory but its not the same as a active grid, cause there will be done no Update cycle
=> this can be activated easily by a config value, so its possible to give people the option to use the “new” or “old” method

12

IMO travelling NPCs shouldn’t load and update a whole cell because this will update all the NPCs around even if it’s needed. It could cause also a hostile NPC to attack the travelling one, breaking the path. They should be updated on their own, without even checking if the cell is active/inactive.

As for any performance concern, please make sure to profile the performances before and after any change and compare them.

13

I’ve been thinking a bit about this (not having time to do actual coding, but time to think about some things).

First off, I think for the grid. I don’t think optimising for low-pop servers makes a lot of sense. Why? Well, because I think that as things are now, even an entry level server can handle low populations. Optimising here potentially at the cost to those with a higher populations seems a bit of a move in the wrong direction.

Now, when it comes to handling what’s going on in cells that aren’t active. Of course, generally they are asleep, and I’m certain this is how things are on retail servers. I’ve seen enough artefacts of this while playing to make me reasonably certain this is the case. However, creatures with waypoints that cover multiple cells DO need to have something done about them. I thought of several scenarios.

1: Activate the cells. As Jackpoz says, this is quite overkill for what we want to achieve. However, the side effect is that if somewhere along that path the NPC would legitimately sometimes be held up by fighting, that won’t happen. But, honestly there’s no way to know if this would happen on retail servers either. It would add overheads for something we don’t know if we need.

2: Have the creature Update() and simply move in passive role if the cell is inactive. This would cause some load, but nothing too costly. It wouldn’t require anything too radical either. Probably some process to codify which cells a creature passes through and registering the creature in a container in each cell that can be looked up if a player enters one. What it would mean is that if the NPC was LAST seen in cell 3 of it’s path and player was in cell 5. No matter how much time passed. It would resume from cell 3. Again, you’d need to find a VERY quiet zone on retail to test if this is how it worked on retail. After the realm merges and CRZ etc I don’t know there’s many of these now.

3: This would probably have the lowest impact, provide the a nice result but would need some pre-processing data stored in the DB. How it would work is, the list of cells on the path, the co-ordinates of the first point in the cell the appear in and the time appear there (based from the start of the path) would all need to be stored. In this way, as soon as a player arrives in any of the cells on the path, the time since the last update can be found, and the cell in which the creature SHOULD be derived. It can then be moved to that start position and normal movement begin. Downside is that a lot more data is stored, and the creature would always appear in the same spot in the cell IF the player arrives in the cell it was due to appear in.

Again this isn’t really the grid system, but merely something that would overlap the grid and would need to be implemented within it. In all of the above situations it would mean ALL grids on the path would need to be loaded. This is extra work, but again doesn’t happen on retail because they ARE always loaded. I think an option to load ALL grids should be added too. Just so those with a population and RAM large enough to make use of it, can do so. Although there would be a much longer startup time, it would likely improve performance on these bigger busier servers, when grids don’t need to be loaded the first time, every time.

Likewise the combat with distant creatures PR I submitted. I think this should be drastically changed. The setActive option used, if done on an active server could kill client performance, since the creatures would be rendered at a huge distance. This was never my intention. So I think some “other” solution to this problem is needed. I’ve had some thoughts but I need to flesh them out.

My personal opinion is that the current system is fit for purpose, and just needs to be improved rather than replaced.

14

​I wanted to either add a chat command to check how much RAM all grids take or trigger it with BotFarm but I didn’t have the chance yet to do it

15

Well, to add a function to load all, and not unload wouldn’t be a killer then just look at memory used. It will be gigabytes but I suspect modern servers will take it.