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 20:03

  • 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: 314
Received Thanks: 88
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
3 Users
Old 04/17/2018, 12:55   #2
 
elite*gold: 0
Join Date: Aug 2010
Posts: 985
Received Thanks: 1,064
It would be an overkill but Imagine running the same test in C++ and on the GPU instead :P


{ Angelius } is offline  
Old 04/18/2018, 10:12   #3
 
elite*gold: 67
Join Date: Aug 2014
Posts: 1,314
Received Thanks: 921
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  
Old 05/04/2018, 12:53   #4
 
elite*gold: 0
Join Date: Aug 2011
Posts: 314
Received Thanks: 88
Quote:
Originally Posted by { Angelius } View Post
It would be an overkill but Imagine running the same test in C++ and on the GPU instead :P
Have never done anything similar, in fact, i'm quite new to C++, sure i could code it in C++ but after a quick research, doing that kind of test feels time consuming in my position, sound quite interesting though :P, also, its still just a concept, so i'd rather improve/finish the C# one.

Quote:
Originally Posted by Xio. View Post
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();
Just visual studio profiler, LINQ was not and shouldn't be the problem here, the quick test kinda proof that, and in the worst scenario, dictionaries and spatial hashes were tested with the same where call.

Interested about forcing the JIT, going to check that.

About benching with parallel, i remember doing something like that, time * amount of threads as one would expect, can't remember about the concurrent dictionary though, if i recover the interest, i will make sure to improve the thread.

writing that extra line for the stopwatch was annoying af., will start checking static methods from now lol.


U2_Caparzo is offline  
Old 05/05/2018, 16:56   #5
 
elite*gold: 0
Join Date: May 2006
Posts: 319
Received Thanks: 48
Interesting.

Well, maybe not exaclty for conquer entitys (on client side, of course), in a crowd place (market, guild war) entitys is about 100.

For server development should be applicable.
giacometti is offline  
Old 05/05/2018, 18:10   #6
 
elite*gold: 0
Join Date: Feb 2009
Posts: 235
Received Thanks: 147
you can make this with Blocks.. map size(Width, Height) / 18 and for indexs : x / 18 and y / 18 .. Like EO Source

Code:
  const int CELLS_PER_BLOCK = 18;
        private int GetWidthOfBlock() { return (Width - 1) / CELLS_PER_BLOCK + 1; }
        private int GetHeightOfBlock() { return (Height - 1) / CELLS_PER_BLOCK + 1; }

        public MapView(int _Width, int _Height)
        {
            Width = _Width;
            Height = _Height;

            m_setBlock = new BlockView[GetWidthOfBlock(), GetHeightOfBlock()];
            for (int x = 0; x < GetWidthOfBlock(); x++)
                for (int y = 0; y < GetHeightOfBlock(); y++)
                    m_setBlock[x, y] = new BlockView();
        }

        private int Block(int nPos)
        {
            return nPos / CELLS_PER_BLOCK;
        }
        private BlockView BlockSet(int nPosX, int nPosY) { return m_setBlock[Block(nPosX), Block(nPosY)]; }

        public bool MoveTo<T>(T obj, int nNewPosX, int nNewPosY)
            where T : IBaseRole
        {

            int nOldPosX = obj.X;
            int nOldPosY = obj.Y;
            if ((nOldPosX >= 0 && nOldPosX < Width) == false)
                return false;
            if ((nOldPosY >= 0 && nOldPosY < Height) == false)
                return false;
            if ((nNewPosX >= 0 && nNewPosX < Width) == false)
                return false;
            if ((nNewPosY >= 0 && nNewPosY < Height) == false)
                return false;

            //if (obj.GetType() == MapObjectType.Player)
              obj.IndexInScreen = CounterMovement.Next;

            if (Block(nOldPosX) == Block(nNewPosX) && Block(nOldPosY) == Block(nNewPosY))
                return false;

            BlockSet(nOldPosX, nOldPosY).RemoveObject<T>(obj);
            BlockSet(nNewPosX, nNewPosY).AddObject<T>(obj);



            return true;
        }

        public bool EnterMap<T>(T obj)
            where T : IBaseRole
        {
            if ((obj.X >= 0 && obj.X < Width) == false)
                return false;
            if ((obj.Y >= 0 && obj.Y < Height) == false)
                return false;

            BlockSet(obj.X, obj.Y).AddObject<T>(obj);

            if (obj.GetType() == MapObjectType.Player)
                obj.IndexInScreen = CounterMovement.Next;

            return true;
        }
        public bool LeaveMap<T>(T obj)
             where T : IBaseRole
        {
            if ((obj.X >= 0 && obj.X < Width) == false)
                return false;
            if ((obj.Y >= 0 && obj.Y < Height) == false)
                return false;

            return BlockSet(obj.X, obj.Y).RemoveObject<T>(obj);
        }
        public IEnumerable<IBaseRole> Roles(MapObjectType typ, int X, int Y, Predicate<IBaseRole> P = null)
        {

            for (int x = Math.Max(Block(X) - 1, 0); x <= Block(X) + 1 && x < GetWidthOfBlock(); x++)
                for (int y = Math.Max(Block(Y) - 1, 0); y <= Block(Y) + 1 && y < GetHeightOfBlock(); y++)
                {
                    var list = m_setBlock[x, y].GetObjects(typ);
                        for (int i = 0; i < list.Count; i++)
                        {
                            if (i >= list.Count)
                                break;
                            var element = list[i];
                            if (element != null)
                            {
                                if (P != null)
                                {
                                    if (P(element))
                                        yield return element;
                                }
                                else 
                                    yield return element;
                            }
                        }
                }
        }
..where BlockView is a list
teroareboss1 is offline  
Old 05/05/2018, 18:57   #7
 
elite*gold: 0
Join Date: Aug 2011
Posts: 314
Received Thanks: 88
Quote:
Originally Posted by teroareboss1 View Post
you can make this with Blocks.. map size(Width, Height) / 18 and for indexs : x / 18 and y / 18 .. Like EO Source
Pretty much what is called SpatialHash in the thread.
Have been refactoring code for a project, tonight will try to visit this (not a priority, also, 13:26 here) and test different implementations keeping the structure since my approach was faster than the SpatialHash, but still don't know the,exact reason and some research and testing would be need (i did almost everything quick because i had an exam later that day), thinking that it could be the LINQ calls, but avoiding them would mean that an extra iteration will be done


U2_Caparzo is offline  
Reply



« read/write play.dat | Multi Client »

Similar Threads
Dreamfancy//Near Auto Damage // Near Damage
01/02/2012 - Metin2 Hacks, Bots, Cheats, Exploits & Macros - 8 Replies
Der Hack schlägt automatisch die Monster ohne jegliche bewegung. Link:http://*******/4Um3H Quelle:Dreamfancy // Near Auto Damage // Yakindan Vurus // Yakindan Slot KeS // Near Damage - Metin2 Hileleri - MMORPG - Metin2 - Knight Online - Karahan Online - Silkroad Credits by Dreamfancy und meine türkischen Kentnisse :cool: Tutorial:Ihr müsst alle Daten in den Metin ordner einfügen und dann den Anti Torrent starten. Have Fun
Screening Procedure
06/09/2009 - Grand Chase Philippines - 90 Replies
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 5 approvals ng juryI-ppm ako ng jury pag "OK" kayo sa kanilaPag 4 na ang approval i-pm ako at isesend ko ang new engine w/ tut 5 Jury qwertybugoyangielic2626cute_sakurakirtbrixKamenRiderDelta
entities.cs problem
10/13/2008 - CO2 Programming - 2 Replies
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 error at line:217 error=System.NullReferenceException: Object reference not set to an instance of an object. line:218 is DataBase.Mobs = null; now you know where to look just above line:218 this is what i have: public static void SpawnAllMobs() { try {



All times are GMT +1. The time now is 20:03.


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.