Improving an O(N^2) function (all entities iterating over all other entities)Problem of saturation of ram on XNA?ECS and life management of entitiesBouncing ball slowing down over timeCan you specify which VBO/EBO to use with glDrawElements?How to avoid cost comparison each and every frame?How do I manage monster tables and item databases in my Android game?How do I implement Pokemon-style moves?Are there recursive variants for trigonometric functions to potentially improve performance?Is there a “Least Terrible Method” for sharing Entities over Network?

What's an "add" chord?

Surfacing out of a sunken ship/submarine - Survival Tips

Polling on Impeachment

Calculations in shell Unix

Why are circuit results different from theorised?

Best angle to attack

Find constant that allows an integral to be finite

Is it possible to keep cat litter on balcony during winter (down to -10°C)

How do I resolve science-based problems in my worldbuilding?

'Nuke the sky' to make a rocket launch a tiny bit easier

Why do some papers have so many co-authors?

Is it sportsmanlike to waste opponents' time by giving check at the end of the game?

Is there any point in having more than 6 months' runway in savings?

Was there a clearly identifiable "first computer" to use or demonstrate the use of virtual memory?

Photographic Companions

Rashi's explanation of why we are told that Avram was 86 at the birth of Yishma'el

how to make a twisted wrapper

Is current (November 2019) polling about Democrats lead over Trump trustworthy?

What is the "opposite" of a random variable?

Do physicists understand why time slows down the faster the velocity of an object?

Is this a pure function?

Which fallacy: "If white privilege exists, why did Elizabeth Warren pretend to be an Indian?"

"Cобака на сене" - is this expression still in use or is it dated?

What is the lowest level at which a human can beat the 100m world record (or: the presumed human limit) without using magic?



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


Problem of saturation of ram on XNA?ECS and life management of entitiesBouncing ball slowing down over timeCan you specify which VBO/EBO to use with glDrawElements?How to avoid cost comparison each and every frame?How do I manage monster tables and item databases in my Android game?How do I implement Pokemon-style moves?Are there recursive variants for trigonometric functions to potentially improve performance?Is there a “Least Terrible Method” for sharing Entities over Network?






.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty
margin-bottom:0;









21














$begingroup$


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.



Example screenshot of the game



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!










share|improve this question












$endgroup$










  • 2




    $begingroup$
    Have you experimented with multiple threads on multiple CPU cores running simultaneously?
    $endgroup$
    – Ed Marty
    Jul 19 at 5:05







  • 6




    $begingroup$
    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.
    $endgroup$
    – Turms
    Jul 19 at 8:24






  • 4




    $begingroup$
    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.
    $endgroup$
    – Harabeck
    Jul 19 at 18:53










  • $begingroup$
    A naive suggestion: you could use a quadtree or related data structure instead of the O(N^2) way you're doing it now.
    $endgroup$
    – Seiyria
    Jul 19 at 21:21






  • 3




    $begingroup$
    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)
    $endgroup$
    – A C
    Jul 21 at 0:08


















21














$begingroup$


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.



Example screenshot of the game



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!










share|improve this question












$endgroup$










  • 2




    $begingroup$
    Have you experimented with multiple threads on multiple CPU cores running simultaneously?
    $endgroup$
    – Ed Marty
    Jul 19 at 5:05







  • 6




    $begingroup$
    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.
    $endgroup$
    – Turms
    Jul 19 at 8:24






  • 4




    $begingroup$
    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.
    $endgroup$
    – Harabeck
    Jul 19 at 18:53










  • $begingroup$
    A naive suggestion: you could use a quadtree or related data structure instead of the O(N^2) way you're doing it now.
    $endgroup$
    – Seiyria
    Jul 19 at 21:21






  • 3




    $begingroup$
    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)
    $endgroup$
    – A C
    Jul 21 at 0:08














21












21








21


5



$begingroup$


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.



Example screenshot of the game



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!










share|improve this question












$endgroup$




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.



Example screenshot of the game



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!







c++ performance entity-system






share|improve this question
















share|improve this question













share|improve this question




share|improve this question








edited Jul 23 at 9:18







Alexandre Rodrigues

















asked Jul 18 at 23:58









Alexandre RodriguesAlexandre Rodrigues

1081 silver badge6 bronze badges




1081 silver badge6 bronze badges










  • 2




    $begingroup$
    Have you experimented with multiple threads on multiple CPU cores running simultaneously?
    $endgroup$
    – Ed Marty
    Jul 19 at 5:05







  • 6




    $begingroup$
    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.
    $endgroup$
    – Turms
    Jul 19 at 8:24






  • 4




    $begingroup$
    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.
    $endgroup$
    – Harabeck
    Jul 19 at 18:53










  • $begingroup$
    A naive suggestion: you could use a quadtree or related data structure instead of the O(N^2) way you're doing it now.
    $endgroup$
    – Seiyria
    Jul 19 at 21:21






  • 3




    $begingroup$
    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)
    $endgroup$
    – A C
    Jul 21 at 0:08













  • 2




    $begingroup$
    Have you experimented with multiple threads on multiple CPU cores running simultaneously?
    $endgroup$
    – Ed Marty
    Jul 19 at 5:05







  • 6




    $begingroup$
    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.
    $endgroup$
    – Turms
    Jul 19 at 8:24






  • 4




    $begingroup$
    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.
    $endgroup$
    – Harabeck
    Jul 19 at 18:53










  • $begingroup$
    A naive suggestion: you could use a quadtree or related data structure instead of the O(N^2) way you're doing it now.
    $endgroup$
    – Seiyria
    Jul 19 at 21:21






  • 3




    $begingroup$
    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)
    $endgroup$
    – A C
    Jul 21 at 0:08








2




2




$begingroup$
Have you experimented with multiple threads on multiple CPU cores running simultaneously?
$endgroup$
– Ed Marty
Jul 19 at 5:05





$begingroup$
Have you experimented with multiple threads on multiple CPU cores running simultaneously?
$endgroup$
– Ed Marty
Jul 19 at 5:05





6




6




$begingroup$
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.
$endgroup$
– Turms
Jul 19 at 8:24




$begingroup$
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.
$endgroup$
– Turms
Jul 19 at 8:24




4




4




$begingroup$
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.
$endgroup$
– Harabeck
Jul 19 at 18:53




$begingroup$
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.
$endgroup$
– Harabeck
Jul 19 at 18:53












$begingroup$
A naive suggestion: you could use a quadtree or related data structure instead of the O(N^2) way you're doing it now.
$endgroup$
– Seiyria
Jul 19 at 21:21




$begingroup$
A naive suggestion: you could use a quadtree or related data structure instead of the O(N^2) way you're doing it now.
$endgroup$
– Seiyria
Jul 19 at 21:21




3




3




$begingroup$
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)
$endgroup$
– A C
Jul 21 at 0:08





$begingroup$
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)
$endgroup$
– A C
Jul 21 at 0:08











5 Answers
5






active

oldest

votes


















34
















$begingroup$

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.






share|improve this answer












$endgroup$










  • 1




    $begingroup$
    "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.
    $endgroup$
    – UKMonkey
    Jul 19 at 10:03






  • 1




    $begingroup$
    @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.
    $endgroup$
    – Theraot
    Jul 19 at 10:06







  • 2




    $begingroup$
    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.
    $endgroup$
    – UKMonkey
    Jul 19 at 10:49










  • $begingroup$
    @UKMonkey which is why I did not mention that initially.
    $endgroup$
    – Theraot
    Jul 19 at 10:49


















16
















$begingroup$

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.






share|improve this answer










$endgroup$










  • 1




    $begingroup$
    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?
    $endgroup$
    – Alexandre Rodrigues
    Jul 19 at 2:02






  • 3




    $begingroup$
    @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.
    $endgroup$
    – Ocelot
    Jul 19 at 2:13






  • 6




    $begingroup$
    I think a BVH might be too complex here - a uniform grid implemented as a hash table is good enough.
    $endgroup$
    – Steven
    Jul 19 at 4:00






  • 1




    $begingroup$
    @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.
    $endgroup$
    – Ocelot
    Jul 20 at 0:14


















2
















$begingroup$

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.






share|improve this answer












$endgroup$














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


















1
















$begingroup$

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






share|improve this answer










$endgroup$














  • $begingroup$
    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.
    $endgroup$
    – Pikalek
    Jul 20 at 23:27











  • $begingroup$
    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?
    $endgroup$
    – Theraot
    Jul 21 at 0:58











  • $begingroup$
    @Theraot you dont need the voronoi diagram just tge same sweepline idea.
    $endgroup$
    – joojaa
    Jul 21 at 6:47


















-2
















$begingroup$

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.





share|improve this answer










$endgroup$
















    Your Answer






    StackExchange.ifUsing("editor", function ()
    StackExchange.using("externalEditor", function ()
    StackExchange.using("snippets", function ()
    StackExchange.snippets.init();
    );
    );
    , "code-snippets");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "53"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: false,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    imageUploader:
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    ,
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );














    draft saved

    draft discarded
















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fgamedev.stackexchange.com%2fquestions%2f173890%2fimproving-an-on2-function-all-entities-iterating-over-all-other-entities%23new-answer', 'question_page');

    );

    Post as a guest















    Required, but never shown


























    5 Answers
    5






    active

    oldest

    votes








    5 Answers
    5






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    34
















    $begingroup$

    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.






    share|improve this answer












    $endgroup$










    • 1




      $begingroup$
      "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.
      $endgroup$
      – UKMonkey
      Jul 19 at 10:03






    • 1




      $begingroup$
      @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.
      $endgroup$
      – Theraot
      Jul 19 at 10:06







    • 2




      $begingroup$
      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.
      $endgroup$
      – UKMonkey
      Jul 19 at 10:49










    • $begingroup$
      @UKMonkey which is why I did not mention that initially.
      $endgroup$
      – Theraot
      Jul 19 at 10:49















    34
















    $begingroup$

    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.






    share|improve this answer












    $endgroup$










    • 1




      $begingroup$
      "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.
      $endgroup$
      – UKMonkey
      Jul 19 at 10:03






    • 1




      $begingroup$
      @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.
      $endgroup$
      – Theraot
      Jul 19 at 10:06







    • 2




      $begingroup$
      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.
      $endgroup$
      – UKMonkey
      Jul 19 at 10:49










    • $begingroup$
      @UKMonkey which is why I did not mention that initially.
      $endgroup$
      – Theraot
      Jul 19 at 10:49













    34














    34










    34







    $begingroup$

    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.






    share|improve this answer












    $endgroup$



    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.







    share|improve this answer















    share|improve this answer




    share|improve this answer








    edited Jul 19 at 10:23

























    answered Jul 19 at 1:00









    TheraotTheraot

    8,9623 gold badges24 silver badges33 bronze badges




    8,9623 gold badges24 silver badges33 bronze badges










    • 1




      $begingroup$
      "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.
      $endgroup$
      – UKMonkey
      Jul 19 at 10:03






    • 1




      $begingroup$
      @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.
      $endgroup$
      – Theraot
      Jul 19 at 10:06







    • 2




      $begingroup$
      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.
      $endgroup$
      – UKMonkey
      Jul 19 at 10:49










    • $begingroup$
      @UKMonkey which is why I did not mention that initially.
      $endgroup$
      – Theraot
      Jul 19 at 10:49












    • 1




      $begingroup$
      "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.
      $endgroup$
      – UKMonkey
      Jul 19 at 10:03






    • 1




      $begingroup$
      @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.
      $endgroup$
      – Theraot
      Jul 19 at 10:06







    • 2




      $begingroup$
      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.
      $endgroup$
      – UKMonkey
      Jul 19 at 10:49










    • $begingroup$
      @UKMonkey which is why I did not mention that initially.
      $endgroup$
      – Theraot
      Jul 19 at 10:49







    1




    1




    $begingroup$
    "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.
    $endgroup$
    – UKMonkey
    Jul 19 at 10:03




    $begingroup$
    "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.
    $endgroup$
    – UKMonkey
    Jul 19 at 10:03




    1




    1




    $begingroup$
    @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.
    $endgroup$
    – Theraot
    Jul 19 at 10:06





    $begingroup$
    @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.
    $endgroup$
    – Theraot
    Jul 19 at 10:06





    2




    2




    $begingroup$
    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.
    $endgroup$
    – UKMonkey
    Jul 19 at 10:49




    $begingroup$
    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.
    $endgroup$
    – UKMonkey
    Jul 19 at 10:49












    $begingroup$
    @UKMonkey which is why I did not mention that initially.
    $endgroup$
    – Theraot
    Jul 19 at 10:49




    $begingroup$
    @UKMonkey which is why I did not mention that initially.
    $endgroup$
    – Theraot
    Jul 19 at 10:49













    16
















    $begingroup$

    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.






    share|improve this answer










    $endgroup$










    • 1




      $begingroup$
      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?
      $endgroup$
      – Alexandre Rodrigues
      Jul 19 at 2:02






    • 3




      $begingroup$
      @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.
      $endgroup$
      – Ocelot
      Jul 19 at 2:13






    • 6




      $begingroup$
      I think a BVH might be too complex here - a uniform grid implemented as a hash table is good enough.
      $endgroup$
      – Steven
      Jul 19 at 4:00






    • 1




      $begingroup$
      @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.
      $endgroup$
      – Ocelot
      Jul 20 at 0:14















    16
















    $begingroup$

    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.






    share|improve this answer










    $endgroup$










    • 1




      $begingroup$
      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?
      $endgroup$
      – Alexandre Rodrigues
      Jul 19 at 2:02






    • 3




      $begingroup$
      @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.
      $endgroup$
      – Ocelot
      Jul 19 at 2:13






    • 6




      $begingroup$
      I think a BVH might be too complex here - a uniform grid implemented as a hash table is good enough.
      $endgroup$
      – Steven
      Jul 19 at 4:00






    • 1




      $begingroup$
      @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.
      $endgroup$
      – Ocelot
      Jul 20 at 0:14













    16














    16










    16







    $begingroup$

    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.






    share|improve this answer










    $endgroup$



    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.







    share|improve this answer













    share|improve this answer




    share|improve this answer










    answered Jul 19 at 0:25









    OcelotOcelot

    1,1849 silver badges19 bronze badges




    1,1849 silver badges19 bronze badges










    • 1




      $begingroup$
      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?
      $endgroup$
      – Alexandre Rodrigues
      Jul 19 at 2:02






    • 3




      $begingroup$
      @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.
      $endgroup$
      – Ocelot
      Jul 19 at 2:13






    • 6




      $begingroup$
      I think a BVH might be too complex here - a uniform grid implemented as a hash table is good enough.
      $endgroup$
      – Steven
      Jul 19 at 4:00






    • 1




      $begingroup$
      @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.
      $endgroup$
      – Ocelot
      Jul 20 at 0:14












    • 1




      $begingroup$
      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?
      $endgroup$
      – Alexandre Rodrigues
      Jul 19 at 2:02






    • 3




      $begingroup$
      @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.
      $endgroup$
      – Ocelot
      Jul 19 at 2:13






    • 6




      $begingroup$
      I think a BVH might be too complex here - a uniform grid implemented as a hash table is good enough.
      $endgroup$
      – Steven
      Jul 19 at 4:00






    • 1




      $begingroup$
      @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.
      $endgroup$
      – Ocelot
      Jul 20 at 0:14







    1




    1




    $begingroup$
    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?
    $endgroup$
    – Alexandre Rodrigues
    Jul 19 at 2:02




    $begingroup$
    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?
    $endgroup$
    – Alexandre Rodrigues
    Jul 19 at 2:02




    3




    3




    $begingroup$
    @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.
    $endgroup$
    – Ocelot
    Jul 19 at 2:13




    $begingroup$
    @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.
    $endgroup$
    – Ocelot
    Jul 19 at 2:13




    6




    6




    $begingroup$
    I think a BVH might be too complex here - a uniform grid implemented as a hash table is good enough.
    $endgroup$
    – Steven
    Jul 19 at 4:00




    $begingroup$
    I think a BVH might be too complex here - a uniform grid implemented as a hash table is good enough.
    $endgroup$
    – Steven
    Jul 19 at 4:00




    1




    1




    $begingroup$
    @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.
    $endgroup$
    – Ocelot
    Jul 20 at 0:14




    $begingroup$
    @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.
    $endgroup$
    – Ocelot
    Jul 20 at 0:14











    2
















    $begingroup$

    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.






    share|improve this answer












    $endgroup$














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















    2
















    $begingroup$

    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.






    share|improve this answer












    $endgroup$














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













    2














    2










    2







    $begingroup$

    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.






    share|improve this answer












    $endgroup$



    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.







    share|improve this answer















    share|improve this answer




    share|improve this answer








    edited Jul 21 at 7:36

























    answered Jul 20 at 20:47









    joojaajoojaa

    2261 silver badge7 bronze badges




    2261 silver badge7 bronze badges














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
















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















    $begingroup$
    @Theraot we dont know how the drawing things are structured. But yes drawcalls will become bottlenecks once you get fast enough anyway
    $endgroup$
    – joojaa
    Jul 21 at 6:34




    $begingroup$
    @Theraot we dont know how the drawing things are structured. But yes drawcalls will become bottlenecks once you get fast enough anyway
    $endgroup$
    – joojaa
    Jul 21 at 6:34











    1
















    $begingroup$

    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






    share|improve this answer










    $endgroup$














    • $begingroup$
      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.
      $endgroup$
      – Pikalek
      Jul 20 at 23:27











    • $begingroup$
      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?
      $endgroup$
      – Theraot
      Jul 21 at 0:58











    • $begingroup$
      @Theraot you dont need the voronoi diagram just tge same sweepline idea.
      $endgroup$
      – joojaa
      Jul 21 at 6:47















    1
















    $begingroup$

    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






    share|improve this answer










    $endgroup$














    • $begingroup$
      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.
      $endgroup$
      – Pikalek
      Jul 20 at 23:27











    • $begingroup$
      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?
      $endgroup$
      – Theraot
      Jul 21 at 0:58











    • $begingroup$
      @Theraot you dont need the voronoi diagram just tge same sweepline idea.
      $endgroup$
      – joojaa
      Jul 21 at 6:47













    1














    1










    1







    $begingroup$

    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






    share|improve this answer










    $endgroup$



    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







    share|improve this answer













    share|improve this answer




    share|improve this answer










    answered Jul 20 at 21:09









    nablanabla

    1111 bronze badge




    1111 bronze badge














    • $begingroup$
      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.
      $endgroup$
      – Pikalek
      Jul 20 at 23:27











    • $begingroup$
      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?
      $endgroup$
      – Theraot
      Jul 21 at 0:58











    • $begingroup$
      @Theraot you dont need the voronoi diagram just tge same sweepline idea.
      $endgroup$
      – joojaa
      Jul 21 at 6:47
















    • $begingroup$
      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.
      $endgroup$
      – Pikalek
      Jul 20 at 23:27











    • $begingroup$
      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?
      $endgroup$
      – Theraot
      Jul 21 at 0:58











    • $begingroup$
      @Theraot you dont need the voronoi diagram just tge same sweepline idea.
      $endgroup$
      – joojaa
      Jul 21 at 6:47















    $begingroup$
    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.
    $endgroup$
    – Pikalek
    Jul 20 at 23:27





    $begingroup$
    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.
    $endgroup$
    – Pikalek
    Jul 20 at 23:27













    $begingroup$
    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?
    $endgroup$
    – Theraot
    Jul 21 at 0:58





    $begingroup$
    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?
    $endgroup$
    – Theraot
    Jul 21 at 0:58













    $begingroup$
    @Theraot you dont need the voronoi diagram just tge same sweepline idea.
    $endgroup$
    – joojaa
    Jul 21 at 6:47




    $begingroup$
    @Theraot you dont need the voronoi diagram just tge same sweepline idea.
    $endgroup$
    – joojaa
    Jul 21 at 6:47











    -2
















    $begingroup$

    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.





    share|improve this answer










    $endgroup$



















      -2
















      $begingroup$

      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.





      share|improve this answer










      $endgroup$

















        -2














        -2










        -2







        $begingroup$

        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.





        share|improve this answer










        $endgroup$



        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.






        share|improve this answer













        share|improve this answer




        share|improve this answer










        answered Jul 23 at 4:45









        José Franco CamposJosé Franco Campos

        1




        1































            draft saved

            draft discarded















































            Thanks for contributing an answer to Game Development Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid


            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.

            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fgamedev.stackexchange.com%2fquestions%2f173890%2fimproving-an-on2-function-all-entities-iterating-over-all-other-entities%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown









            Popular posts from this blog

            Tamil (spriik) Luke uk diar | Nawigatjuun

            Align equal signs while including text over equalitiesAMS align: left aligned text/math plus multicolumn alignmentMultiple alignmentsAligning equations in multiple placesNumbering and aligning an equation with multiple columnsHow to align one equation with another multline equationUsing \ in environments inside the begintabularxNumber equations and preserving alignment of equal signsHow can I align equations to the left and to the right?Double equation alignment problem within align enviromentAligned within align: Why are they right-aligned?

            Training a classifier when some of the features are unknownWhy does Gradient Boosting regression predict negative values when there are no negative y-values in my training set?How to improve an existing (trained) classifier?What is effect when I set up some self defined predisctor variables?Why Matlab neural network classification returns decimal values on prediction dataset?Fitting and transforming text data in training, testing, and validation setsHow to quantify the performance of the classifier (multi-class SVM) using the test data?How do I control for some patients providing multiple samples in my training data?Training and Test setTraining a convolutional neural network for image denoising in MatlabShouldn't an autoencoder with #(neurons in hidden layer) = #(neurons in input layer) be “perfect”?