modernuo / ModernUO

Ultima Online Server Emulator for the modern era!
https://www.modernuo.com
GNU General Public License v3.0
255 stars 154 forks source link

Make Tracking Skill closer to OSI #1629

Open kamronbatman opened 11 months ago

kamronbatman commented 11 months ago

Currently tracking uses the "RunUO" method which was constrained due to performance. We should make it work properly like OSI. Requirements:

Technical Implementation: A new GetMobilesInRange flag should be added called useConcentricSearch. This flag should fork the behavior to a new ref struct enumerable/enumerator. This new enumerator should enumerate sectors from the center sector of the given coordinates, radiating outward.

Example, let's say the range is 100, resulting in a depth of up to 7 sectors in all directions. Loop 1 -> sector at 0/0 Loop 2 -> sectors at -1/-1, -1/0, -1/+1, 0/-1, skip 0/0, 0/+1, +1/-1, +1/0, +1/+1 Loop 3 -> sectors at -2/-2, -2/-1, -2/0, -2/+1, -2/+2, -1/-2, skip the middle, then +1/+2, etc etc..

Here is an iterative approach, but will need to be converted to a recursive approach. Hopefully we can make assumptions and don't have to use a BFS.

          int x;
          int y;
          var incr = 2;

          y = -incr;
          for (var i = -incr; i <= incr; i++)
          {
              x = i;
              Console.WriteLine("Coordinates: {0}/{1}", x, y);
          }

          // Sides are incr * 2 - 2
          for (var i = -incr - 1; i < incr; i++)
          {
              y = i;
              x = -incr;

              Console.WriteLine("Coordinates: {0}/{1}", x, y);
              x = incr;
              Console.WriteLine("Coordinates: {0}/{1}", x, y);
          }

          y = incr;
          for (var i = -incr; i <= incr; i++)
          {
              x = i;
              Console.WriteLine("Coordinates: {0}/{1}", x, y);
          }

The idea of this enumerator is that we can end our search early if we already have 12 mobs and our next distance is the next multiple of 16 tiles (sector size). This is because all mobs at the next sector depth will necessarily always be too far away to qualify as the closest.

danielfcastro commented 2 weeks ago

A recursive approach would consume more memory. Why using it them?

kamronbatman commented 2 weeks ago

This method should consume no extra memory since we already have a ref struct enumerator. Just requires an algorithm that spirals, or scans left to right inside-out.