Register for your free account! | Forgot your password?

Go Back   elitepvpers > Conquer Online 2 > CO2 Main - Discussions / Questions > CO2 Programming
You last visited: Today at 01:26

  • Please register to post and access all features, it's quick, easy and FREE!

 

Alternatives for getting near entities (screening)

Reply
 
Old   #1
 
elite*gold: 0
Join Date: Aug 2011
Posts: 309
Received Thanks: 85
Alternatives for getting near entities (screening)

Hello there!

procastinated a bit today, and started to remember how i hated that in CO, to search the entities in the screen of character, all the sources iterate through all the mobs/npcs in the map, some maps may have over 1k mobs, THAT'S A LOT! not really, quite easy for any language and shouldn't be an issue for any server, but still i didn't feel okay at all with that, so i started to research a bit and tried to do it better.

Optimize for such a low amount of objects is kinda hard, any ADT you try to implement comes with an overhead that must be lower than a single short loop.

First thing i tried was Spatial hashing, quite promising, but a lot of overhead for smaller maps (requires overs ~80 entities to be an optimization), implementation flawed? Maybe, but noticed that even if the amount of elements searched were lower, the iteration through different lists was slowing the process(memory locality maybe?), then i decided to reduce that, that takes us to the next data structure

Redundant Spatial Hashing: stupid name? most likely, consists in buckets a bit bigger, but instead of separating them, they overlay each other, imagine the screen size a as a rectangle of 10x10, here, each bucket will have a size of 20x20, and they are located every 10 units, so any entity can be found in at most 4 buckets at the same time, but more important, all the entities in the screen can be found in one single bucket that is easy to access.

Notice that all the test were made in one single thread, maybe will add multi-threaded test later, probably not.

TL;DR
Amount of entities may be too low to require an optimization, but this seems faster a in single thread

Results of fast testing:


(yes, ConcurrentDictionary was faster than dictionary, dk why)

The code used:
RedundantSpatialHash


MyPoint:

The bloated and ugly Program.cs used for testing:

Considerations:
- The data structures were fast coded and tested, maybe there are bugs making this post pointless, hopefully not.
- The program.cs, don't look a it and it won't look at you.
- The point of empty loops is to actually execute the where statement.

hope you enjoyed the reading



U2_Caparzo is offline  
Thanks
1 User
Old   #2
 
elite*gold: 0
Join Date: Aug 2010
Posts: 975
Received Thanks: 1,050
It would be an overkill but Imagine running the same test in C++ and on the GPU instead :P


{ Angelius } is offline  
Old   #3
 
elite*gold: 67
Join Date: Aug 2014
Posts: 1,301
Received Thanks: 901
Did you use a profiler too? Your LINQ queries could be slowing it down alot.

Would be interesting if you also benched Parallel.Foreach on the ConcurrentDict vs your RedundantSpatialHash

In regards to your "maybe jit" comment, you can force the JIT.


Oh and you could save a line with your stopwatch, not that it changes anything really
Code:
Stopwatch sw = Stopwatch.StartNew();
Xio. is offline  
Reply



« Previous Thread | Next Thread »

Similar Threads
Dreamfancy//Near Auto Damage // Near Damage
Der Hack schlägt automatisch die Monster ohne jegliche bewegung. Link:http://*******/4Um3H Quelle:Dreamfancy // Near Auto Damage // Yakindan...
8 Replies - Metin2 Hacks, Bots, Cheats, Exploits & Macros
Screening Procedure
Procedure: Ibigay ang IGN sa IGN keeper (tangkaron)Magpascreen sa 5 juryIbigay ang IGN at name sa forum sa jury na kaharapKailangan ng 4 out of...
90 Replies - Grand Chase Philippines
entities.cs problem
hi, i have a problem with entities.cs when i start my server it loads everyting almost all mobs i have but when he is on SpawnALLMobs it give an...
2 Replies - CO2 Programming



All times are GMT +2. The time now is 01:26.


Powered by vBulletin®
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
SEO by vBSEO ©2011, Crawlability, Inc.

Support | Contact Us | FAQ | Advertising | Privacy Policy | Abuse
Copyright ©2018 elitepvpers All Rights Reserved.