Improving an O(N^2) function (all entities iterating over all other entities)

Question

A little bit of background, I'm coding an evolution game with a friend in C++, using ENTT for the entity system. Creatures walk around in a 2D map, eat greens or other creatures, reproduce and their traits mutate.

Additionally, performance is fine (60fps no problem) when the game is run in real time, but I want to be able to speed it up significantly to not have to wait 4h to see any significant changes. So I want to get it as fast as possible.

I'm struggling to find an efficient method for creatures to find their food. Each creature is supposed to look for the best food that is close enough to them.

If it wants to eat, the creature pictured in the center is supposed to look around itself in a 149.64 radius (its view distance) and judge which food it should pursue, which is based on nutrition, distance, and type (meat or plant).

The function responsible for finding every creature their food is eating up around 70% of the run-time. Simplifying how its written currently, it goes something like this:

for (creature : all_creatures)
{
  for (food : all_entities_with_food_value)
  {
    // if the food is within the creatures view and it's
    // the best food found yet, it becomes the best food
  }
  // set the best food as the target for creature
  // make the creature chase it (change its state)
}

This function is run every tick for every creature looking for food, until the creature finds food and changes state. It's also run every time new food spawns for creatures already chasing a certain food, to make sure everyone goes after the best food available to them.

I'm open to ideas on how to make this process more efficient. I'd love to reduce the complexity from \$O(N^2)\$, but I don't know if that's even possible.

One way I already improve it is by sorting the all_entities_with_food_value group so that when a creature iterates over food too big for it to eat, it stops there. Any other improvements are more than welcome!

EDIT: Thank you all for the replies! I implemented various things from various answers:

I firstly and simply made it so the guilty function only runs once every five ticks, this made the game around 4x faster, while not visibly changing anything about game.

After that I stored in the food searching system an array with the food spawned in the same tick it runs as. This way I only need to compare the food the creature is chasing with the new foods that appeared.

Lastly, after research into space partitioning and considering BVH and quadtree, I went with the latter, as I feel like it's much simpler and better suited to my case. I implement it pretty quickly and it greatly improved performance, the food search barely takes any time at all!

Now rendering is what's slowing my down, but that's a problem for another day. Thank you all!

Answer 1

I know you do not conceptualize this as collisions, however what you are doing is colliding a circle centered at the creature, with all food.

You really do not want to check food that you know is distant, only what is nearby. That is the general advice for collision optimization. I would like to encourage to search for techniques to optimize collisions, and do not limit yourself to C++ when searching.

---

Creature finding food

For your scenario, I would suggest to put the world on a grid. Make the cells at least the radius of the circles you want to collide. Then you can pick the one cell on which the creature is located and its up to eight neighbors and search only those up to nine cells.

Note: you could make smaller cells, which would mean that the circle you are searching would extend beyond the immidiate neighbors, requiring you to iterate there. However, if the problem is that there is too much food, smaller cells could mean iterating over less food entities in total, which at some point turns in your favor. If you suspect this is the case, test.

If food does not move, you can add the food entities to the grid on creation, so that you do not need to be searching what entities are in the cell. Instead you query the cell and it has the list.

If you make the size of the cells a power of two, you can find the cell on which the creature is located simply by truncating its coordinates.

You can work with squared distance (a.k.a. do not do sqrt) while comparing to find the closest one. Less sqrt operations means faster execution.

---

New food added

When new food is added, only nearby creatures need to be awaken. It is the same idea, except now you need to get the list of creatures in the cells instead.

Much more interestingly, if you annotate in the creature how far is it from the food it is chasing... you can directly check against that distance.

Another thing that will help you is to have the food aware of what creatures are chasing it. That will allow you to run the code for finding food for all the creatures that are chasing a piece of food that was just eaten.

In fact, start the simulation with no food and any creatures have an annotated distance of infinity. Then start adding food. Update the distances as the creatures move... When food is eaten, take the list of creatures were chasing it, and have then find a new target. Besides that case, all other updates are handled when food is added.

---

Skipping simulation

Knowing the speed of a creature, you know how much it is until it reaches its target. If all creatures have the same speed, the one that will reach first is the one with smallest annotated distance.

If you also know the time until you add more food... And hopefully you have similar predictability for reproduction and death, then you know the time to next event (either added food or a creature eating).

Skip to that moment. You do not need to simulate creatures moving around.

Answer 2

You should adopt a space partitioning algorithm like BVH to reduce complexity. To be specific to your case, you need to make a tree that consists of axis-aligned bounding boxes that contain food pieces.

To create a hierarchy, put food pieces close to each other in AABBs, then put those AABBs in bigger AABBs, again, by distance between them. Do this until you have a root node.

To make use of the tree, first perform a circle-AABB intersection test against a root node, then if collision happens, test against children of the each consecutive node. In the end you should have a group of food pieces.

You can also make use of AABB.cc library.

Answer 3

While the space partition methods described indeed can reduce the time your main problem is not just the lookup. Its the sheer volume of lookups you make that makes your task slow. So your optimizing the inner loop, but you can also optimize the outer loop.

Your problem is that you keep polling data. Its a bit like having kids in the back seat asking for a thousandth time "are we there yet", theres no need to do that the driver will inform when you are there.

Instead you should strive, if possible, to solve each action to its completion put it into a queue and let those bubble events out, this may make changes to the queue but that is ok. This is called discrete event simulation. If you can implement your simulation this way then you are looking fora sizable speedup that far outweighs the speedup you can get from the better space partition lookup.

To underline the point in a previous career i made factory simulators. We simulated weeks of big factories/airports entire material flow at each item level with this method in less than a hour. While the timestep based simulation could only simulate 4-5 times faster than real time.

Also as a really low hanging fruit consider decoupling your drawing routines from your simulation. Even though your simulation is simple there is still some overhead of drawing things. Worse the display driver may be limitting you to x updates per second while in reality your processors could do things 100's of times faster. This uderlines the need for profiling.

Answer 4

You can use a sweep-line algorithm to reduce the complexity to Nlog(N). The theory is that of Voronoi diagrams, which makes a partitioning of the area surrounding a creature into regions consisting of all points closer to to that creature than any other.

The so-called Fortune's algorithm does that for you in Nlog(N), and the wiki page on that contains pseudo code to implement it. I am sure that there are library implementations out there as well. https://en.wikipedia.org/wiki/Fortune%27s_algorithm

Answer 5

The easiest solution would be integrating a physics engine and using only the collision detection algorithm. Just build a circle/sphere around each entity, and let the physics engine compute the collisions. For 2D i would suggest Box2D or Chipmunk, and Bullet for 3D.

If you feel that integrating a whole physics engine is too much, I would suggest looking into the specific collision algorithms. Most collision detection libraries work in two steps:

• Broad phase detection: the goal of this stage is to get the list of candidate pairs of objects that may collide, as fast as possible. Two common options are:
  • Sweep and prune: sort the bounding boxes along the X axis, and mark those pair of objects that intersect. Repeat for every other axis. If a candidate pair passes all the tests, it goes to the next stage. This algorithm is very good at exploiting temporal coherence: you can keep the lists of sorted entities and update them every frame, but as they are almost sorted, it will be very fast. It also exploits spatial coherence: because entities are sorted in ascending spatial order, when you are checking for collisions, you can stop as soon as an entity doesn't collide, because all the next ones will be further away.
  • Spatial partitioning data structures, like quadtrees, octrees, and grids. Grids are easy to implement, but can be very wasteful if the entity density is low, and very difficult to implement for unbounded space. Static spatial trees are easy to implement too, but difficult to balance or update in place, so you would have to rebuild it each frame.
• Narrow phase: candidate pairs found on the broad phase are further tested with more precise algorithms.