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!