We are about to switch to a new forum software. Until then we have removed the registration on this forum.
Guys and gals,
I've been searching for a solution to my question in the forums – because I'm pretty sure I'm not the first person to ask this – but obviously I'm not using the right keywords, because I've not yet found any answers.
This is my hypothetical setup: Let's say I have a few thousand white ellipses scattered randomly on the screen and I want to turn every object fill-color within a 100px radius of the mouse to red. The working and obvious solution is to loop through EVERY object in play and use dist() to determine it's distance to the mouse and then act accordingly. Which does work fine, but slows down considerably the more objects are on the screen and the more complex the behaviours of these objects become.
Now I'm thinking that it ought to be possible to limit the actual calculations to just a fraction of the total objects, create sort of a "preselection" I you want, and thus forego the dist()-check on all object. But that's where I'm stuck. I know there are optimisation processes in programming to prevent ALL calculations happening at ALL time (like chunks in Minecraft) but I can't find the right terms to start reading into this topic. I've thought about creating quadrants, then checking which object is in which quadrant and then just apply calculations to the objects in the same quadrant as the mouse currently is. But my code always turns out to at some point require the same calculations across all objects. I'm stumped and would be grateful, not for a code solution, but on pointers on where I could read about this topic/which keywords I should be searching for. (Given the facts, that what I'm imagining is in fact a thing).
Also, I'm not specifically only trying to turn white ellipses red, that's just a simple example. I'd like to know how to set up a system which does the selection of a subset of objects, no matter what the actual operations then might be.
Thanks!
Answers
Sounds like a job for a quadtree.
Or you could try a grid system. Picture a Mario game: the game doesn't have to perform collision checks on every object in the game, it just figures out which grid cells Mario is in and checks the object in those cells.
Or you could try a square hitbox instead of a circular hitbox. The less-than / greater-than comparisons a square hitbox requires would probably be faster than the distance function a circular hitbox requires. Then you can do the circular distance check only between object whose square hitboxes collide.
Whoa, thanks for the swift reply.
I actually edited my initial post to explicitly not look for the solution for a turn-white-to-red-using-dist()-problem, but a more general approach for selecting only a subset of objects to operate on. In fact, my actual problem doesn't use stationary ellipses at all, but ones moving around the screen at varying velocities. Therefore assigning objects to a specific quadrant would be moot the very next cycle when all positions have shifted. Or rather, the quadrant-reassigning process would happen as often as a direct dist()-check and so not reduce the amount of cpu-power needed.
I've actually bumped into quadtree on a couple occasions in the past, and while I understand how they can become in handy, I have zero clue where to start utilising them for my kind of problem. Will definitely have to dig into that topic.
Thanks for the suggestions!
As well as searching for quadtree you could also try space partitioning which would probably be easier to implement.
I have a Processing example using quadtree that I created a while ago which you could have, uses PS2 and G4P but I could easily update it if you are using PS3. My AI library uses space partitioning.
All of the solutions I posted are general.
I disagree. You're going off what you think is true instead of doing any actual profiling. The whole goal is to reduce the number of distance checks you have to do. That's exactly what a quadtree does. The point is that inserting into a quadtree is cheaper than the collision check, so even though you still have to do that for every object, you're still saving time.
Start by googling "Java quadtree" or "Processing quadtree" for a ton of examples. The wikipedia link I gave you contains examples of pseudocode.
Yet another option would be to use a physics engine like Box2D, but that might be overkill for your actual goal.
...aaaand now I have egg on my face. You're completely right, I have no idea how quadtree works, so I shouldn't assume.
And you're right, I've already found a plethora of promising tutorials... time to learn!
@quark
If you'd let me look into the source, yeah, that'd be great! Also, I'll look into your AI library as well. Thanks!
The quadtree source code example is not secret, but it uses the G4P library so you can modify the quadtree parameters to see what happens. Changes made in moving PS2 to PS3 means each have a different version of G4P. So I need to know whether you are using PS2 or 3.
Let me know are I will provide a link to download the code.
I mentioned the AI library because it proves that space partitioning is a viable alternative to quadtrees. I would not recommend looking at the source code to see cell-partitioning in action. The library uses some very complex data structures to enable a limitless game space game and would probably make little sense except to very experienced programmers.
Ah, yeah, makes sense.
I'm currently using PS3 beta... so right in the middle. But I'll be updating to PS3 soon, now that it's launched officially.
You can download the demo sketch from here. Unzip the sketch and put it into your sketch folder. The sketch includes the G4P library jar file so it should run from PS3b7 and PS3 without further installs.
When you run it you will get 2 windows as shown below. The left window is the control panel and the black square shows the current simulation parameters. To create a new simulation change them in the bottom panel and click New Simulation
The centre panel shows the number of balls at each level of the quadtree and the current simulation has 5 levels and the quad partition is half the size of the partition above. You can increase the number of levels but be careful if the quad partition gets too small then the balls are never completely within them and you can see this in the centre panel, when that happens it becomes less efficient.
Anyway have a play with it and if you have any questions post them here.
There's a more modest approach w/ Comparable + sort():
The point is to implement a compareTo() method inside the class which represents the ellipse().
We then compare the x coordinate against the other x from another ellipse().
This way, when we invoke sort(), the container will be sorted by the order of the x coordinate.
Then when checking an area for a mousePressed(), we can skip all those x coordinates outside mouseX's range.
That'll boost a lot the double loop check, since we can skip a whole ellipse() when it's far away from mouseX!
Here's an upgraded version sketch from a very old thread for Processing 2 & 3 now.
So you can have some idea how it works: O:-)
http://forum.Processing.org/one/topic/interaction-among-objects-in-an-array.html
The crucial point is inside nearestNeighbors() function, which actually acts an inner loop for the outer loop within draw():
When it detects @
if (dx > range) return;
that the x distance between 2 Point objects are outside range, it abruptly quits the whole function, since there's no point going on if they're far away to each other already! *-:)In your case, you'd check against mouseX range.
If it's outside, quit the whole thing prematurely. :P
@GoToLoop although your solution is interesting it is still of the same order as a brute force approach i.e. N^2
For large N a quadtree or space-partitioning would give better performance.
For a generic what-is-in-the-neighbourhood type situation I believe the best approach would be to use space partitioning. The AI_CityPatrol example in my AI library would not run if it didn't use space-partitioning and attempted to use a N^2 algorithm.
@GoToLoop: Please post a profiling of your "approach" compared to other approaches. I'm going to be very skeptical until I see real numbers. How is your approach better than simply using a square hitbox to test which circles should be then checked based on distance?
I found a simple quadtree implementation here: http://www.java-gaming.org/index.php?action=pastebin&hex=4af3b227b3d1a
And I mixed it with the CircleCollision example sketch that comes with the Processing IDE (go to File > Examples > Topics > Motion > CircleCollision).
I created a sketch that consisted of 800 circles that all bounce off each other. If I use the brute force approach, I get 40 FPS. If I use a quadtree, I get 55 FPS.
Note that I have done absolutely no optimizations for either approach. This was just a quick proof that using a quadtree can save you time, even if you're rebuilding it every frame. This is because you're avoiding checking every other circle for each circle! You're doing N amount of work (technically nlgn) to build the tree so you can avoid doing N^2 amount of work.
Think about it this way: with the brute force approach, I have to loop through my N circles and then, for each of those circles, I have to loop through the N circles again. But with the quadtree approach, I build my quadtree before any looping. This is NlgN amount of work (inserting into the quadtree takes lgN time, and I have to do it N times). Then I still have to loop through my N circles, but now I only have to loop over the circles that might be near each of those N circles! Now my loop is only N*x, where x is the number of close neighbors. NlgN + N*x is less than N^2 when your N is large, which is why a quadtree saves you time.
This code is just thrown together, but if you feel like playing with it, here it is: