-1
\$\begingroup\$

In my game there are space ships and each of these space ships tracks which other ships are in range of it. I need to perform certain logic when a target ship comes in range of another ship, and certain logic when the target ship leaves the range of the ship.

I am looking for advice on the most performant way to manage the collection of targets. Not so much looking for advice on the range comparisons as I'm already making optimizations there (square distance and spatial partitioning).

I have a way to do this using two hashsets (code below), but I just want to confirm if this is the fastest way. I feel like there might be a better way, but I can't for the life of me think of one.

        public HashSet<Ship> TrackedShips = new HashSet<Ship>();
        public HashSet<Ship> FoundShips = new HashSet<Ship>();

        public void FindShipsInRange(Ship source, List<Ship> possibleTargets)
        {
            FoundShips = new HashSet<Ship>();

            foreach (var possibleTarget in possibleTargets)
            {
                if (InRange(source, possibleTarget))
                {
                    FoundShips.Add(possibleTarget);
                    TrackedShips.Remove(possibleTarget);
                    // Do the adding/revealing logic
                }
            }

            foreach (var oldTrackedShip in TrackedShips)
            {
                // Do the removal logic
            }

            TrackedShips = FoundShips;
        }

Would very much appreciate any suggestions! Very curious if there is a better way I am not thinking of.

EDIT: To clarify, I'm mainly asking if this is the best approach to tracking when a ship leaves the range. The collections can get quite large, i.e. 1000 ships each having 1000 possible targets each time the method runs. I want to ensure I am not iterating more than I need to be, and removing the ships from the tracked ships hashset and then looping over the remaining ships was the best I could come up with. Curious if anyone has a better idea!

\$\endgroup\$
5
  • \$\begingroup\$ Welcome to CodeReview! How frequently are you executing the FindShipsInRange method? Do you perform the same calculation for each and every Ship? \$\endgroup\$ Jan 26, 2022 at 8:25
  • 1
    \$\begingroup\$ You probably want a data structure that's set up to make the FindShipsInRange() performant - probably an octree or similar. But this sounds more like advice for code not yet written, not for a review of your code. \$\endgroup\$ Jan 26, 2022 at 8:59
  • \$\begingroup\$ Hello, thank you! Yes, this runs for each ship, and each ship can have its own "sensor range". The frequency is 60 times a second (once per frame) currently, but I do have plans to run it less frequently which of course is a huge optimization. I do have a grid implementation (game is in 2d) that helps cut down on the number of possible ships considered. All that said, I still want to make sure this logic is as optimal as possible. When I do profiling with 1000 ships, the main bottleneck I see is the management of these two hashsets with all the Adds and Removes \$\endgroup\$ Jan 26, 2022 at 15:15
  • \$\begingroup\$ @wilderness26 If all ship have the same weapons then if ship A is in a shooting range for ship B then the other direction is true as well (ship B is in a shooting range for ship A). If you can take advantage of this commutative property then you can half the computation need. \$\endgroup\$ Jan 27, 2022 at 7:51
  • \$\begingroup\$ @wilderness26 Or consider to store the state of the galaxy/universe/whatever you call the playground. If the current state can tell which ship is in shooting range for which other ships, then you don't need to calculate all the possibilities all the time. Rather you just need to perform some calculation based on the moves. If shipA was in a shooting range for shipB then after the move is it still there? Did it move to others' shooting range? \$\endgroup\$ Jan 27, 2022 at 7:55

1 Answer 1

0
\$\begingroup\$

I think it has room to improve, but really performance depends upon how List<Ship> possibleTargets is composed for each ship, and you do not show that code.

For the code you present, I would suggest NOT removing from TrackedShips. No need to perform temporary pruning when you completely replace the hash set later.

Alternate SECTION of code:

foreach (var possibleTarget in possibleTargets)
{
    if (InRange(source, possibleTarget))
    {
        FoundShips.Add(possibleTarget);
        // Do the adding/revealing logic
    }
}

foreach (var ship in FoundShips)
{
    if (!TrackedShips.Contains(ship))
    {
        // Do the removal logic
    }
}

TrackedShips = FoundShips;
\$\endgroup\$
1
  • \$\begingroup\$ Thanks for the suggestion! This suggestion definitely makes sense to me. My only question is if this scales better than my solution as the number of FoundShips increases since this solution likely iterates more. I guess the question comes down to how many enumerations is a HashSet.Remove() worth \$\endgroup\$ Jan 29, 2022 at 3:27

Not the answer you're looking for? Browse other questions tagged or ask your own question.