[patch] Speedup grid object search

[Auntie Mangos]

http://getmangos.eu/community/showthread.php?p=84122#post84122

I wonder if my posts are invisible or something..?

[Ambal]

Hi everyone. Want to present you another performance optimization patch. Idea is very old, but benefits are huge.

Currently when player stands on map, he stands in map cell too. Length of cell side is 133 yards. Also player has 8 cells around him. So current algorithms for cell object search (for example AOE spells) must look for mobs in 9(!) cells. Lets say, our AOE damage affects only targets in 30 yards radius. So we have a huge save in CPU power because with so small radius we would never need to search all 9 cells, maximum 4 of them

This patch affect alot of places: chat whispering, visibility calculations, AOE target search, mob assistance, area packet sending etc...

P.S. Current cell walk algorithm in CellImpl.h was taken from Trinity 1, I don't know who author is. But next versions will include more generic calculations from mangos dev team, which will work with any cell sizes and radiuses. Have fun

Update #1: Updated cell search algorithm, cell size reduced to 66 yards. Also fixed a crash with fishing...

Update #2: Another improvements to cell search algorithm. Also packet sending improved to scale with visibility distances. New visible distance options included into server config. MAX_NUMBER_OF_CELLS set to 16 <- this is experimental value. Report any problems with it asap.

Update #3: Fixed some compilation issues with GCC. Restored possibility to use 'reload config' command to reinitialize visibility distance for each map w/o need to restart server.

Update #4: Fixed VisitCircle() algorithm. Now it is more precise.

Update #5: Updated cell coord range checking. Patch supports revs 8182+.

Update #6: Updated grid unload algorithm. Added more security checks for grid/cell coords range checking...

Update #7: Fixed a bug with visibility distance in dungeons/BG/Arenas - it was always the same as on continents until you used .reload config command...

Patch 1.14: http://filebeam.com/6cc48d245ee183b5e5df7fca8894f9cd

Patch 1.13[rev 8277+]: http://filebeam.com/0f565f9494b0869942a4ab47fd1e715c

Patch 1.13: http://filebeam.com/d34652aada593787748884a7e26b9972

Patch 1.12: http://filebeam.com/39ba2fc9a850e686fd3a907135397f15

Patch 1.10: http://filebeam.com/2c9fb21627cb9ee7c639fad863223ffd

Patch 1.09: http://filebeam.com/8b637b44f86831d3bca7669735f071c6

Patch 1.08: http://filebeam.com/c47df9de78907324e7346ce804588623

Patch 1.01: http://filebeam.com/a4e5d66735a33db959dbc9d4c8f9cac2

Patch 1.00: http://filebeam.com/e1389b2727e0e021f23d1f4a64e11563

[imblizzspy]

Thanks for more performance/stability improvements =)

btw, what about maps patch? will it get into git anytime soon, I see tons of your patches are getting in, but not that specific one

P.S: dont forget about 0.12 users

[FeRkEl]

would be nice to see a git branch for all those performance optimizations

[nanounico]

this is best than relocation and visibility from mangos.ru?

thanks really man, very plus for you jeje (Testing)

[Ambal]

this is best than relocation and visibility from mangos.ru?

No, this is just a small addition to that patch I'll see what I can do to provide a git branch for everyone interested...

[Ambal]

First post updated. Cell search algorithm updated. Also we tracked down, why 3.1.3 performance degraded so badly: increasing cell size to 133 yards instead of 66 yards in 0.12 branch caused this. So I reverted this change with no loss to visible range (up to 166 yards). Fixed a crash with fishing :huh:

Check GridDefines.h:

#define MAX_NUMBER_OF_CELLS     8
#define CENTER_GRID_CELL_ID     256

This is how it was in 0.12 branch. You are free to change 3.1.3 sources to get lost performance back

[nanounico]

Check GridDefines.h:

#define MAX_NUMBER_OF_CELLS     8
#define CENTER_GRID_CELL_ID     256

i think this is the realm problem, for all problems with latency actually, i remember, when in 0.12 this problems present, and the lagg after 500 are very bad. later fix this

#define MAX_NUMBER_OF_CELLS 4

#define CENTER_GRID_CELL_ID 128

for

#define MAX_NUMBER_OF_CELLS 8

#define CENTER_GRID_CELL_ID 256

and all problems with the latency over.

[Sephiroth1983]

i think this is the realm problem, for all problems with latency actually, i remember, when in 0.12 this problems present, and the lagg after 500 are very bad. later fix this

Ok but now can we focus on testing the latest branch first? Thanks

[Ambal]

Uploaded a new version. Cell search algorithm improved. Also there are improvements in server config, added 3 more options:

Visibility.Distance.Continents    = 90
Visibility.Distance.Instances     = 120
Visibility.Distance.BGArenas      = 180

Now you are able to control visibility distances on continents, in instances and in Arenas/BGs separately. Some old values aka Visibility.Distance.Creature and Visibility.Distance.Player removed.

WARNING: I set up MAX_NUMBER_OF_CELLS 16, so report any problems with functionality/server stability with it. And don't forget about crashdumps

[Homenixx]

I apply the last patches, not crashes but my CPU usage is up to 90% everytime.

Intel Xeon Quad Proccesor 4x 2.83+ GHz

8 GB de RAM

Up to 700+ online.

Vmaps Disable and PosCollition = 0

GridUnload = 0

Sometimes the CPU usage on 100% ... and experience lag issues ingame.

Sorry 4 my bad english ;-)

[Ambal]

Homenixx, could you provide more details about visibility distances you use? Didn't you forget to update your server config?

[Homenixx]

More info:

# VISIBILITY CONFIG:

Visibility.GroupMode = 0

Visibility.Distance.Continents = 90

Visibility.Distance.Instances = 120

Visibility.Distance.BGArenas = 180

Visibility.Distance.Object = 100

Visibility.Distance.InFlight = 100

Visibility.Distance.Grey.Unit = 1

Visibility.Distance.Grey.Object = 10

# PERFORMANCE SETTINGS:

UseProcessors = 0

ProcessPriority = 1

Compression = 1

PlayerLimit = 2500

SaveRespawnTimeImmediately = 1

MaxOverspeedPings = 2

GridUnload = 0

SocketSelectTime = 10000

GridCleanUpDelay = 300000

MapUpdateInterval = 100

ChangeWeatherInterval = 600000

PlayerSaveInterval = 300000

vmap.enableLOS = 0

vmap.enableHeight = 0

vmap.ignoreMapIds = "369,530,0,1"

vmap.ignoreSpellIds = "7720"

DetectPosCollision = 0

TargetPosRecalculateRange = 1.5

UpdateUptimeInterval = 10

MaxCoreStuckTime = 0

AddonChannel = 1

# MaNGOS REV: 8158 x64 Compilation

# SD2 REV: 1205

# DATABASE: YTDB rev 499

# SO: windows server 2003 x64

# CPU USAGE: 80-100% (for one proccesor, the other 3 are ok with cpu usage between 10%-50%

# MEMORY: 5,39 GB RAM / 8,00 GB

# TESTERS ONLINE: 754

[Ambal]

Ok, thank you. Could you lower your settings to

Visibility.Distance.Continents = 90

Visibility.Distance.Instances = 90

Visibility.Distance.BGArenas = 90

Visibility.Distance.Object = 90

Visibility.Distance.InFlight = 90

and tell if this help. Standart setting are offlike + we have very unoptimized visibility calculations right now. This is why you might experience lags.

P.S. Most of servers have even lower visibility distances:

Visibility.Distance.Continents = 66

Visibility.Distance.Instances = 66

Visibility.Distance.BGArenas = 66

Visibility.Distance.Object = 66

Visibility.Distance.InFlight = 66

So you can try these too.

[Homenixx]

ohh thaks I try now!!

for visibility settings i must restart the server or only .reload config ?

Thanks you. And if you could update the maps patch to latest rev i apply to test it together.

[Ambal]

for visibility settings i must restart the server or only .reload config ?

You need to restart your server for changes to take effect. I'll try think how to update visibility distances with .reload config option.

[Homenixx]

Ambal... i have a problem When i try apply both of your patches i have error because of map.cpp

How i can apply the both patches ?

Thanks ;-)

And you config details improve my CPU usage now 80%-90% ;-)

[Diablox]

What settings did you use

Visibility.Distance.Continents = 90

Visibility.Distance.Instances = 90

Visibility.Distance.BGArenas = 90

Visibility.Distance.Object = 90

Visibility.Distance.InFlight = 90

or

Visibility.Distance.Continents = 66

Visibility.Distance.Instances = 66

Visibility.Distance.BGArenas = 66

Visibility.Distance.Object = 66

Visibility.Distance.InFlight = 66

Does anyone know how far do you see on retail?

[caeruleaus]

it actually depends on the creature and your settings in the video options....

Like Fel Reavers in Hellfire Peninsula have almost unlimited visibility distance while regular mobs are about 100-150 yards.

EDIT: That's with max visibility settings on.

[cyrex]

With full distance on my PC i can assure you i can see more than 100, much MUCH more than 100. This is for mobs, objects and everything. If i had to guess it would be about 30 to 50% more than 100. Checked on outland, kalimdor and icecrown with some friends.

[Diablox]

it actually depends on the creature and your settings in the video options....

Like Fel Reavers in Hellfire Peninsula have almost unlimited visibility distance while regular mobs are about 100-150 yards.

We are not even near to achieve something like that!!

[caeruleaus]

actually i just did some tests, creatures become visible at about 150 yards and then when you are moving away from them they stay visible for about 250-300 yards.

[Homenixx]

What settings did you use

or

Does anyone know how far do you see on retail?

I use the first settings

[Ambal]

Homenixx, what CPU usage do you have w/o this patch? And what are the values of Visibility.Distance.Creature and Visibility.Distance.Player in your config?

[cyrex]

actually i just did some tests, creatures become visible at about 150 yards and then when you are moving away from them they stay visible for about 250-300 yards.

This is exactly right. Perfect