Alternatives for getting near entities (screening)

[U2_Caparzo]

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

 Spoiler

public class RedundantSpatialHash
    {
        private int mapWidth;               // width of the map
        private int mapHeight;              // height of the map
        private int cameraWidth;            // width of the camera, 36 for CO
        private int cameraHeight;           // height of the camera, 36 for CO
        private int width;                  // the amount horizontal lists
        private int height;                 // the amount of vertical lists
        private List<MyPoint>[,] buckets;   // represents a cell with the size of four times the camera size

        public RedundantSpatialHash(int width, int height, int cameraWidth, int cameraHeight)
        {
            mapWidth = width;
            mapHeight = height;
            this.cameraWidth = cameraWidth;
            this.cameraHeight = cameraHeight;
            this.width = 2 * mapWidth / cameraWidth;
            this.height = 2 * mapHeight / cameraHeight;
            InitializeBuckets();
        }

        private void InitializeBuckets()
        {
            buckets = new List<MyPoint>[width, height];
            for(int y = 0; y < height; y++)
                for(int x = 0; x < width; x++)
                    buckets[x, y] = new List<MyPoint>();
        }

        public void Add(MyPoint p)
        {
            int left = p.X - cameraWidth / 2;
            int up = p.Y - cameraHeight / 2;
            int x = left / cameraWidth;
            int y = up / cameraHeight;
            buckets[x, y].Add(p);
            buckets[x + 1, y].Add(p);
            buckets[x, y + 1].Add(p);
            buckets[x + 1, y + 1].Add(p);
        }

        public void Remove(MyPoint p)
        {
            int left = p.X - cameraWidth / 2;
            int up = p.Y - cameraHeight / 2;
            int x = left / cameraWidth;
            int y = up / cameraHeight;
            buckets[x, y].Remove(p);
            buckets[x + 1, y].Remove(p);
            buckets[x, y + 1].Remove(p);
            buckets[x + 1, y + 1].Remove(p);
        }

        public IEnumerable<MyPoint> Search(int xCenter, int yCenter)
        {
            int left = xCenter - cameraWidth / 2;
            int up = yCenter - cameraHeight / 2;
            int x = left / cameraWidth;
            int y = up / cameraHeight;
            return buckets[x, y].Where(p => Math.Abs(xCenter - p.X) + Math.Abs(yCenter - p.Y) <= 18);
        }
    }

 Spoiler

public class SpatialHash
    {
        private int mapWidth;               // width of the map
        private int mapHeight;              // height of the map
        private int cameraWidth;            // width of the camera, 36 for CO
        private int cameraHeight;           // height of the camera, 36 for CO
        private int width;                  // the amount horizontal lists
        private int height;                 // the amount of vertical lists
        private List<MyPoint>[] buckets;    // represents a cell with the same size than the camera

        public SpatialHash(int width, int height, int cameraWidth, int cameraHeight)
        {
            mapWidth = width;
            mapHeight = height;
            this.cameraWidth = cameraWidth;
            this.cameraHeight = cameraHeight;
            this.width = mapWidth / cameraWidth + 1;
            this.height = mapHeight / cameraHeight + 1;
            InitializeBuckets();
        }

        private void InitializeBuckets()
        {
            buckets = new List<MyPoint>[width * height];
            for (int y = 0; y < buckets.Length; y++)
            {
                buckets[y] = new List<MyPoint>();
            }
        }

        public void Add(MyPoint p)
        {
            int x = p.X / cameraWidth;
            int y = p.Y / cameraHeight;
            buckets[x + y * width].Add(p);
        }

        public void Remove(MyPoint p)
        {
            int x = p.X / cameraWidth;
            int y = p.Y / cameraHeight;
            buckets[x + y * width].Remove(p);
        }

        public IEnumerable<MyPoint> Search(int xCenter, int yCenter)
        {
            int x = xCenter / cameraWidth;
            if (xCenter % cameraWidth <= cameraWidth / 2)
                x--;

            int y = yCenter / cameraHeight;
            if (yCenter % cameraHeight <= cameraHeight / 2)
                y--;

            Func<MyPoint, bool> select = p => Math.Abs(xCenter - p.X) + Math.Abs(yCenter - p.Y) <= 18;
            IEnumerable<MyPoint> ps = buckets[x + y * width].Where(select);
            if (x + 1 + y * width < buckets.Length)
                ps = ps.Union(buckets[x + 1 + y * width].Where(select));
            if (x + 1 + y * width < buckets.Length)
                ps = ps.Union(buckets[x + y * width + width].Where(select));
            if (x + 1 + y * width < buckets.Length)
                ps = ps.Union(buckets[x + 1 + y * width + width].Where(select));
            return ps;
        }
    }

MyPoint:

 Spoiler

    public class MyPoint
    {
        public int X { get; set; }
        public int Y { get; set; }
        public MyPoint(int x, int y)
        {
            this.X = x;
            this.Y = y;
        }
    }

The bloated and ugly Program.cs used for testing:

 Spoiler

    class Program
    {
        static RedundantSpatialHash rsh = new RedundantSpatialHash(1000, 1000, 36, 36); 
        static Dictionary<int, MyPoint> dict = new Dictionary<int, MyPoint>();
        static ConcurrentDictionary<int, MyPoint> cdict = new ConcurrentDictionary<int, MyPoint>();
        static int amount = 5;
        static int cycles = 100000;
        static SpatialHash sh = new SpatialHash(1000, 1000, 36, 36);
        static void Main(string[] args)
        {
            Random ran = new Random();
            for (int i = 0; i < amount; i++)
            {
                MyPoint k = new MyPoint(ran.Next(1000), ran.Next(1000));
                rsh.Add(k);
                dict.Add(i, k);
                sh.Add(k);
                cdict.TryAdd(i, k);
            }
            MyPoint p = dict[ran.Next(amount)];
            // maybe jit required?
            Test1(p);
            Test2(p);
            Test3(p);
            Test4(p);
            Console.WriteLine();
            Console.WriteLine();
            Console.WriteLine();
            Console.WriteLine();
            for(int n = 0; n <8; n++)
            {

                amount *= 2;
                rsh = new RedundantSpatialHash(1000, 1000, 36, 36);
                sh = new SpatialHash(1000, 1000, 36, 36);
                dict = new Dictionary<int, MyPoint>();
                cdict = new ConcurrentDictionary<int, MyPoint>();
                for (int i = 0; i < amount; i++)
                {
                    MyPoint k = new MyPoint(ran.Next(1000), ran.Next(1000));
                    rsh.Add(k);
                    dict.Add(i, k);
                    sh.Add(k);
                    cdict.TryAdd(i, k);
                }

                Console.WriteLine("Iterations: " + cycles + " -- amount of entities: " + amount);
                Test1(p);
                Test2(p);
                Test3(p);
                Test4(p);
                Console.WriteLine();
            }
            Console.ReadLine();
        }

        private static void Test1(MyPoint p)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            for(int i = 0; i < cycles; i++)
            {
                rsh.Remove(p);
                rsh.Add(p);
                foreach (var a in rsh.Search(p.X, p.Y))
                {
                    
                }
            }
            sw.Stop();
            Console.WriteLine("Redundant Spatial Hash:  " + sw.ElapsedMilliseconds + " ms   op/ms: " + cycles * amount / sw.ElapsedMilliseconds);
        }

        private static void Test3(MyPoint p)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < cycles; i++)
            {
                sh.Remove(p);
                sh.Add(p);
                foreach (var a in sh.Search(p.X, p.Y))
                {

                }
            }
            sw.Stop();

            Console.WriteLine("Spatial Hashing:         " + sw.ElapsedMilliseconds + " ms   op/ms: " + cycles * amount / sw.ElapsedMilliseconds);
        }


        private static void Test2(MyPoint p)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < cycles; i++)
            {
                foreach(var a in dict.Values.Where(p1 => Math.Abs(p1.X - p.X) + Math.Abs(p1.Y- p.Y) <= 18))
                {
                    
                }
            }

            sw.Stop();
            Console.WriteLine("Dictionary:              " + sw.ElapsedMilliseconds + " ms   op/ms: " + cycles * amount / sw.ElapsedMilliseconds);
        }

        private static void Test4(MyPoint p)
        {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            for (int i = 0; i < cycles; i++)
            {
                foreach (var a in cdict.Values.Where(p1 => Math.Abs(p1.X - p.X) + Math.Abs(p1.Y - p.Y) <= 18))
                {

                }
            }

            sw.Stop();
            Console.WriteLine("ConcurrentDictionary:    " +  sw.ElapsedMilliseconds + " ms   op/ms: " + cycles * amount / sw.ElapsedMilliseconds);
        }
    }

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

[{ Angelius }]

It would be an overkill but Imagine running the same test in C++ and on the GPU instead :P

[Xio.]

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.

 Spoiler

foreach (var type in Assembly.GetExecutingAssembly().GetTypes()) // or typeof(Program).GetTypes()
  {
    foreach (var method in type.GetMethods(BindingFlags.DeclaredOnly | 
                        BindingFlags.NonPublic | 
                        BindingFlags.Public | BindingFlags.Instance | 
                        BindingFlags.Static))
    {
      System.Runtime.CompilerServices.RuntimeHelpers.PrepareMethod(method.MethodHandle);
    }
  }

Oh and you could save a line with your stopwatch, not that it changes anything really

Stopwatch sw = Stopwatch.StartNew();

[U2_Caparzo]

Originally Posted by { Angelius }

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.

Originally Posted by Xio.

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.

 Spoiler

foreach (var type in Assembly.GetExecutingAssembly().GetTypes()) // or typeof(Program).GetTypes()
  {
    foreach (var method in type.GetMethods(BindingFlags.DeclaredOnly | 
                        BindingFlags.NonPublic | 
                        BindingFlags.Public | BindingFlags.Instance | 
                        BindingFlags.Static))
    {
      System.Runtime.CompilerServices.RuntimeHelpers.PrepareMethod(method.MethodHandle);
    }
  }

Oh and you could save a line with your stopwatch, not that it changes anything really

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.

[giacometti]

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.

[teroareboss1]

you can make this with Blocks.. map size(Width, Height) / 18 and for indexs : x / 18 and y / 18 .. Like EO Source

  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

[U2_Caparzo]

Originally Posted by teroareboss1

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