Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Make Tracking Skill closer to OSI #1629

Open
kamronbatman opened this issue Dec 5, 2023 · 2 comments
Open

Make Tracking Skill closer to OSI #1629

kamronbatman opened this issue Dec 5, 2023 · 2 comments
Labels
bug Something isn't working enhancement New feature or request

Comments

@kamronbatman
Copy link
Contributor

kamronbatman commented Dec 5, 2023

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

  • Search up to 1 tile per skill point in all directions (100 tiles at 100% skill)
  • Do not search beyond an area's bounds. Example: Dungeon levels are next to each other on the map, but tracking shouldn't "cross" the void.

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.

@kamronbatman kamronbatman added bug Something isn't working enhancement New feature or request labels Dec 5, 2023
@kamronbatman kamronbatman changed the title Fix Tracking Skill Make Tracking Skill closer to OSI Dec 5, 2023
@danielfcastro
Copy link

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

@kamronbatman
Copy link
Contributor Author

kamronbatman commented Oct 22, 2024

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

2 participants