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

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!

• Have you experimented with multiple threads on multiple CPU cores running simultaneously? Jul 19, 2019 at 5:05
• How many creatures do you have on average? It doesn't seem to be that high, judging from the snapshot. If that's always the case, space partitioning won't help much. Have you considered not running this function at every tick? You could run it every, say, 10 ticks. The results of the simulation shouldn't qualitatively change. Jul 19, 2019 at 8:24
• Have you done any detailed profiling to figure out the most costly part of the food evaluation? Instead of looking at the overall complexity, maybe you need to see if there some specific calculation or memory structure access that is choking you. Jul 19, 2019 at 18:53
• A naive suggestion: you could use a quadtree or related data structure instead of the O(N^2) way you're doing it now. Jul 19, 2019 at 21:21
• As @Harabeck suggested, I'd dig deeper to see where in the loop all that time is being spent. If it's square-root calculations for distance, for example, you might be able to first compare XY coords to pre-eliminate lots of candidates before having to do the expensive sqrt on the remaining ones. Adding if (food.x>creature.x+149.64 or food.x<creature.x-149.64) continue; should be easier than implementing a "complicated" storage structure IF it's performant enough. (Related: It might help us if you posted a little more of the code in your inner loop)
– A C
Jul 21, 2019 at 0:08

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.

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.

• "and search only there." and the cells immediate neighbours - meaning 9 cells in total. Why 9? Because what if the creature is right in the corner of a cell. Jul 19, 2019 at 10:03
• @UKMonkey "Make the cells at least the radius of the circles you want to collide", if the cell side is the radius and the creature is in the corner... well, I suppose you only need to search four in that case. However, sure, we can make the cells smaller, that could be useful if there is too much food and too few creatures. Edit: I'll clarify. Jul 19, 2019 at 10:06
• Sure - if you want to work out if you need to search in extra cells ... but given that most cells won't have food (from the given image); it'll be faster to just search 9 cells, than work out which 4 you need to search. Jul 19, 2019 at 10:49
• @UKMonkey which is why I did not mention that initially. Jul 19, 2019 at 10:49

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.

• That would indeed reduce the complexity to N log N, but it would also be costly to do the partitioning. Seeing as I'd need to do the partitioning every tick (since creatures move every tick) would it still be worth it? Are there solutions to help partition less often?
– Alex
Jul 19, 2019 at 2:02
• @AlexandreRodrigues you don't have to rebuild whole tree every tick, only update parts that move, and only when something goes outside of a particular AABB container. To further improve performance, you may want to fatten nodes (leaving some space between children) so you don't have to rebuild whole branch on a leaf update. Jul 19, 2019 at 2:13
• I think a BVH might be too complex here - a uniform grid implemented as a hash table is good enough. Jul 19, 2019 at 4:00
• @Steven by implementing BVH you can easily extend scale of the simulation in the future. And you don't really loose anything if you do it for a small scale simulation either. Jul 20, 2019 at 0:14

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.

• @Theraot we dont know how the drawing things are structured. But yes drawcalls will become bottlenecks once you get fast enough anyway Jul 21, 2019 at 6:34

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

• Welcome to GDSE & thanks for answering. How exactly would you apply this to OP's situation? The problem description says that an entity should consider all the food within its view distance & select the best one. A traditional Voronoi would exclude in range food that was closer to another entity. I'm not saying that a Voronoi wouldn't work, but it's not obvious from your description how OP should make use of one for the problem as described. Jul 20, 2019 at 23:27
• I like this idea, I would like to see it expanded. How do you do represent the voronoi diagram (as in memory data structure)? How do you query it? Jul 21, 2019 at 0:58
• @Theraot you dont need the voronoi diagram just tge same sweepline idea. Jul 21, 2019 at 6:47

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.