Algorithm for units to attack each other in strategy games [duplicate]

Question

I am creating a strategy game with many objects, in which the objects will be able to attack each other.

If an object is within attack range of another object, it will be attacked. But I only know one way is to loop through all objects to see if it is within the scope of this object's attack. Therefore the complexity of the algorithm is O (n ^ 2). Can someone give me a better algorithm or preferably a book about algorithms like this.

Thanks !

Answer 1

You can optimize this using spatial partitioning. The basic idea ist that you only compare those objects with each other which are within areas which are close enought to have a chance to collide.

1. Divide your game world into sections.
2. Store those sections in a data-structure optimized for directly accessing a section at a specific location. When your sections are a square grid, then you can use a 2-dimensional array. When your sections are irregular, then you might want to use something like a BSP tree.
3. Add a list of objects to each section which represents the units which currently occupy it.
4. When an object moves across a section boundary, remove it from the list of the old section and add it to the list of the new section. If your objects are large enough to overlap multiple areas, then it might make sense to allow it to be on the lists of multiple areas.
5. If you want to get all objects in a given attack area:
   1. Determine which sections are completely overlapped by the area. All objects on their lists are potential targets. Accurate collision detection for these objects is unnecessary. You already know that they are affected, because anything which touches this section is affected.
   2. Determine which sections are only partially overlapped. You have to do a proper collision detection with the objects on their lists to determine whether or not they are affected.
   3. Any sections not touched by the area can be ignored. This is where most of the performance savings come from.
6. If you allow objects to be in multiple sections at once, remove duplicate from the list of potential targets.

Answer 2

There are a few solutions to this:

1. limit the total number of attackable entities that can be active at any one time. This is one of the reasons why unit caps exist in RTS games.

2. create a spatial partition so you can ask of the map "in a 50m radius give me every entity that is possible in this area" and then you loop over the resulting set to eliminate the false positives.