Trying to understand the best way to avoid nested loops

In this example, I am trying to create targeting logic that would work well with tons of units.
The obvious example is to just double itterate everything but that will get worse and worse.

My best guess on how to solve this is to have a 2 stage job approach.
Job 1 goes through all the entities and assigns them a region based on where they are on the map
Job 2 then goes through each entity and looks for other entities in the neighboring regions only.

A couple questions arise.
1) If i stored in a native array all the entity ids for each region I would not have to double iterate at all. Instead I could pick a list of entities for my region and adjacent regions and just scan that instead of the whole entity list. However this feels like its doing memory lookups for each entity 1 by 1, which sounds like the "old way" and not taking advantage of the power of ECS
2) if only one thing can exist in each grid location, a job could have every unit pick its destination, but not actually move. When it comes time to moving however, all the translation adjustments would need to be done in such a way that they are cancelled if a once open location is now occupied

 

In standard Unity the physics engine has things that will help with this, e.g. SphereCast to find units in Range of the the searching Unit, combined with raycasts to check line of sight within the level.

As DOTS has a new Physics solution based on Havok it should include include these or similar features.
-> https://docs.unity3d.com/Packages/com.unity.physics@0.0/manual/collision_queries.html

 

What you've described is pretty much how the Boids demo works.

I've done a similar thing with a raycast algo. Divide world into regions, fill a NativeMultiHashMap with the key as the region ID and the value as the entity ID or whatever data you need.

Pass the hash map into your targeting job and you should be good to go.

As far as the 'old way', these sort of data access patterns tend to be random anyway.

 

@Arowx That could probably work, but I feel like in a grid based solution where you only need to look a few squares away from you, there is a much better option out there.

 

Probably don't want to link an outdated manual.

https://docs.unity3d.com/Packages/com.unity.physics@0.2/manual/collision_queries.html

 

There are quite a few space partitioning data structures https://en.wikipedia.org/wiki/Space_partitioning designed to reduce the search space in these types of problems. These are already built into and heavily optimised in most physics engines, even your board game space is still a space that could be represented by the physics engine.

Hint: Don't reinvent the wheel by making a Hexa/Octa Wheel.(Using unoptimised own code instead of professionally optimised code).

However, if your using a grid based approach you could try a lower resolution regional grid e.g. if your working on a 1m grid you could opt for a regional grid of 10m,100m,1000m this would just be a 'smaller' array of lists that contain everything in that region.

Benefits here are if you need to test for 50 m you would only need to scan 100*, 1**,1** (**worst case 4) regions instead of potentially thousands of tests if you test against units of 10,000 if your scanning 100x100 1m grid squares.

if you get the region size right for the viewing/targeting radius you can simply loop through a set of regional lists that have potential targets.
If you are going for a nearest target first you could spiral search outwards and stop on the first target you find. Massively reducing the workload.

Cons you need to ensure all movement on the high resolution grid is reflected in the low resolution grid.

* Hint you could reduce this further if you exclude regions outside of the radius.

 

Typically for these types of problems it is more efficient to bake out whatever data is needed to select a target into a NativeArray when building up the spatial data structures so that your evaluation of the entities nearby when trying to pick a target is actually just iterating through a subset of the array.