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;

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!

edited Jul 23 at 9:18

asked Jul 18 at 23:58

Alexandre Rodrigues

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

|
show 3 more comments

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

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)

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.

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.

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

edited Jul 23 at 9:18

asked Jul 18 at 23:58

Alexandre Rodrigues

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

|
show 3 more comments

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

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)

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.

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.

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

edited Jul 23 at 9:18

asked Jul 18 at 23:58

Alexandre Rodrigues

1081 silver badge6 bronze badges

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

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)

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.

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.

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

c++ performance entity-system

edited Jul 23 at 9:18

asked Jul 18 at 23:58

Alexandre Rodrigues

1081 silver badge6 bronze badges

edited Jul 23 at 9:18

asked Jul 18 at 23:58

Alexandre Rodrigues

1081 silver badge6 bronze badges

edited Jul 23 at 9:18

asked Jul 18 at 23:58

Alexandre Rodrigues

1081 silver badge6 bronze badges

asked Jul 18 at 23:58

Alexandre Rodrigues

1081 silver badge6 bronze badges

asked Jul 18 at 23:58

Alexandre Rodrigues

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

|
show 3 more comments

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

Have you experimented with multiple threads on multiple CPU cores running simultaneously?

– Ed Marty
Jul 19 at 5:05

How many creatures do you have on average? It doesn't seem to be that high, judging from the snapshot. If that's always the case, space partitioning won't help much. Have you considered not running this function at every tick? You could run it every, say, 10 ticks. The results of the simulation shouldn't qualitatively change.

– Turms
Jul 19 at 8:24

Have you done any detailed profiling to figure out the most costly part of the food evaluation? Instead of looking at the overall complexity, maybe you need to see if there some specific calculation or memory structure access that is choking you.

– Harabeck
Jul 19 at 18:53

A naive suggestion: you could use a quadtree or related data structure instead of the O(N^2) way you're doing it now.

– Seiyria
Jul 19 at 21:21

As @Harabeck suggested, I'd dig deeper to see where in the loop all that time is being spent. If it's square-root calculations for distance, for example, you might be able to first compare XY coords to pre-eliminate lots of candidates before having to do the expensive sqrt on the remaining ones. Adding if (food.x>creature.x+149.64 or food.x<creature.x-149.64) continue; should be easier than implementing a "complicated" storage structure IF it's performant enough. (Related: It might help us if you posted a little more of the code in your inner loop)

– A C
Jul 21 at 0:08

|
show 3 more comments

5 Answers
5

active

oldest

votes

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.

edited Jul 19 at 10:23

answered Jul 19 at 1:00

Theraot

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

add a comment
|

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.

answered Jul 19 at 0:25

Ocelot

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

add a comment
|

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.

edited Jul 21 at 7:36

answered Jul 20 at 20:47

joojaa

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

add a comment
|

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

answered Jul 20 at 21:09

nabla

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

add a comment
|

-2

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.

answered Jul 23 at 4:45

José Franco Campos

add a comment
|

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

Name

Required, but never shown

5 Answers
5

active

oldest

votes

5 Answers
5

active

oldest

votes

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.

Creature finding food

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.

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.

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

edited Jul 19 at 10:23

answered Jul 19 at 1:00

Theraot

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

add a comment
|

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.

Creature finding food

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.

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.

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

edited Jul 19 at 10:23

answered Jul 19 at 1:00

Theraot

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

add a comment
|

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.

Creature finding food

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.

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.

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

edited Jul 19 at 10:23

answered Jul 19 at 1:00

Theraot

8,9623 gold badges24 silver badges33 bronze badges

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.

Creature finding food

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.

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.

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

edited Jul 19 at 10:23

answered Jul 19 at 1:00

Theraot

8,9623 gold badges24 silver badges33 bronze badges

edited Jul 19 at 10:23

answered Jul 19 at 1:00

Theraot

8,9623 gold badges24 silver badges33 bronze badges

answered Jul 19 at 1:00

Theraot

8,9623 gold badges24 silver badges33 bronze badges

answered Jul 19 at 1:00

Theraot

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

add a comment
|

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

"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.

– UKMonkey
Jul 19 at 10:03

@UKMonkey "Make the cells at least the radius of the circles you want to collide", if the cell side is the radius and the creature is in the corner... well, I suppose you only need to search four in that case. However, sure, we can make the cells smaller, that could be useful if there is too much food and too few creatures. Edit: I'll clarify.

– Theraot
Jul 19 at 10:06

Sure - if you want to work out if you need to search in extra cells ... but given that most cells won't have food (from the given image); it'll be faster to just search 9 cells, than work out which 4 you need to search.

– UKMonkey
Jul 19 at 10:49

@UKMonkey which is why I did not mention that initially.

– Theraot
Jul 19 at 10:49

add a comment
|

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.

You can also make use of AABB.cc library.

answered Jul 19 at 0:25

Ocelot

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

add a comment
|

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.

You can also make use of AABB.cc library.

answered Jul 19 at 0:25

Ocelot

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

add a comment
|

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.

You can also make use of AABB.cc library.

answered Jul 19 at 0:25

Ocelot

1,1849 silver badges19 bronze badges

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.

You can also make use of AABB.cc library.

answered Jul 19 at 0:25

Ocelot

1,1849 silver badges19 bronze badges

answered Jul 19 at 0:25

Ocelot

1,1849 silver badges19 bronze badges

answered Jul 19 at 0:25

Ocelot

1,1849 silver badges19 bronze badges

answered Jul 19 at 0:25

Ocelot

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

add a comment
|

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

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?

– Alexandre Rodrigues
Jul 19 at 2:02

@AlexandreRodrigues you don't have to rebuild whole tree every tick, only update parts that move, and only when something goes outside of a particular AABB container. To further improve performance, you may want to fatten nodes (leaving some space between children) so you don't have to rebuild whole branch on a leaf update.

– Ocelot
Jul 19 at 2:13

I think a BVH might be too complex here - a uniform grid implemented as a hash table is good enough.

– Steven
Jul 19 at 4:00

@Steven by implementing BVH you can easily extend scale of the simulation in the future. And you don't really loose anything if you do it for a small scale simulation either.

– Ocelot
Jul 20 at 0:14

add a comment
|

edited Jul 21 at 7:36

answered Jul 20 at 20:47

joojaa

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

add a comment
|

edited Jul 21 at 7:36

answered Jul 20 at 20:47

joojaa

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

add a comment
|

edited Jul 21 at 7:36

answered Jul 20 at 20:47

joojaa

2261 silver badge7 bronze badges

edited Jul 21 at 7:36

answered Jul 20 at 20:47

joojaa

2261 silver badge7 bronze badges

edited Jul 21 at 7:36

answered Jul 20 at 20:47

joojaa

2261 silver badge7 bronze badges

answered Jul 20 at 20:47

joojaa

2261 silver badge7 bronze badges

answered Jul 20 at 20:47

joojaa

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

add a comment
|

$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

@Theraot we dont know how the drawing things are structured. But yes drawcalls will become bottlenecks once you get fast enough anyway

– joojaa
Jul 21 at 6:34

add a comment
|

answered Jul 20 at 21:09

nabla

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

add a comment
|

answered Jul 20 at 21:09

nabla

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

add a comment
|

answered Jul 20 at 21:09

nabla

1111 bronze badge

answered Jul 20 at 21:09

nabla

1111 bronze badge

answered Jul 20 at 21:09

nabla

1111 bronze badge

answered Jul 20 at 21:09

nabla

1111 bronze badge

answered Jul 20 at 21:09

nabla

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

add a comment
|

$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

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.

– Pikalek
Jul 20 at 23:27

I like this idea, I would like to see it expanded. How do you do represent the voronoi diagram (as in memory data structure)? How do you query it?

– Theraot
Jul 21 at 0:58

@Theraot you dont need the voronoi diagram just tge same sweepline idea.

– joojaa
Jul 21 at 6:47

add a comment
|

-2

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.

answered Jul 23 at 4:45

José Franco Campos

add a comment
|

-2

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.

answered Jul 23 at 4:45

José Franco Campos

add a comment
|

-2

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.

answered Jul 23 at 4:45

José Franco Campos

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.

answered Jul 23 at 4:45

José Franco Campos

answered Jul 23 at 4:45

José Franco Campos

answered Jul 23 at 4:45

José Franco Campos

answered Jul 23 at 4:45

José Franco Campos

add a comment
|

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

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Bsrgvty

5 Answers
5

Your Answer

Post as a guest

5 Answers
5

5 Answers
5

Post as a guest

Popular posts from this blog

Tamil (spriik) Luke uk diar | Nawigatjuun

5 Answers 5

Your Answer

Sign up or log in

Post as a guest

Post as a guest

5 Answers 5

5 Answers 5

Sign up or log in

Post as a guest

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Popular posts from this blog

Tamil (spriik) Luke uk diar | Nawigatjuun

5 Answers
5

5 Answers
5

5 Answers
5