search

diasurgical / devilutionX

Diablo build for modern operating systems
Other
8.01k stars 786 forks source link

Speed up DeadItem #7215

Closed glebm closed 1 month ago

glebm commented 2 months ago

Previously, the same tiles were rechecked over and over again.

O(k^3) -> O(k^2)

While looking at this, I've noticed we have 3 different methods for checking where to drop an item, all slightly different:

  1. DeadItem: uses ItemSpaceOk.
  2. FindAdjacentPositionForItem: uses CanPut.
  3. GetSuperItemLoc: uses FindClosestValidPosition (which uses Crawl) + ItemSpaceOk.
ephphatha commented 2 months ago

Do we care about keeping the exact drop pattern as vanilla here? I was thinking FindClosestValidPosition would be close enough:

    std::optional<Point> dropPoint = FindClosestValidPosition(ItemSpaceOk, playerTile, 1, 50);
    if (dropPoint) {
        RespawnDeadItem(std ::move(item), *dropPoint);
    }
glebm commented 2 months ago

I'm not sure whether we care, so I went with an optimization that exactly preserves the current behaviour for now.

AJenbo commented 1 month ago

As long as we do not start dropping items on new tiles we don't care about the order here.

Consider this approved, I'm just not doing so in case you want to change it since that would cause it to auto merge :)

glebm commented 1 month ago

Opened https://github.com/diasurgical/devilutionX/pull/7318 instead