7 ms·
Gamedev! One of the best parts of being in gamedev was that the problem space forces you to work this stuff out. People won’t wait 30 minutes for a frame to ren
by sillysaurusx 6y ago
Gamedev! One of the best parts of being in gamedev was that the problem space forces you to work this stuff out. People won’t wait 30 minutes for a frame to render.
A few ways to solve this pop to mind. As Aeolun mentions in a parallel comment, you can just divide coordinates if your grid is regular. But it often isn’t.
In that case, you can attack it in a few ways. One time Feynman was giving a lecture and said “This triangle looks a little cockeyed. Obtuse! That’s the word! I know about the triangles but not their names.” And I’m not Feynman, but I did forget the name of this: you build a tree of squares. First one is your whole grid; split it into four smaller squares, those are the children; repeat till your resolution is sufficient. Then you can attach whatever you want to the child nodes (in this case, grid squares). Since it bisects space into halves, you can do a search in O(log n).
But what if you want to go faster? What if it’s absolutely crucial for speed, like a physics engine, to be able to ask “which objects occupy this region of space?”
My favorite algorithm is absolutely delightful: a radix sort on floats. http://www.codercorner.com/RadixSortRevisited.htm http://www.codercorner.com/RadixSortRevisited.htm
You end up getting O(k*N) time, just like radix sort normally gives you. But the real magic is that it works with bounding boxes. There’s an article from the same author which I can no longer find, detailing it. But the idea is, you sort all your objects in one spatial dimension first, say along the X axis, and then you don’t need to do anything to search quickly. No trees. Suppose you want to ask “does this region of the X-axis have any objects?” You just... do something, ha. I forgot the next step, so I don’t want to say a mistaken answer and tarnish poor Pierre’s idea, which is quite nice. But he’s been working on this problem for basically decades, so here’s one of his N papers on the topic (of spatial partitioning, not applying radix sort to solve it): http://www.codercorner.com/ZeroByteBVH.pdf http://www.codercorner.com/ZeroByteBVH.pdf
I could work it out if I sat down with it for a bit, but, I leave it to one of you younger devs can take up the torch. It’s a fun puzzle.
- sp332 6y agoThat's a quadtree, or an octree in 3D.
- sdbrown 6y agoA k-D tree?
- contravariant 6y agoThat's a binary tree where each node divides the space along a single axis. A quad-, oct-, 2^n-tree divides along all axes for every node.
- geophile 6y agoNo. Quad and octtrees divide the space. K-d trees divide the data.
- snovv_crash 6y agokD-tree doesn't necessarily split at the midpoint like a quad or oct-tree do.
- Cthulhu_ 6y agoI've learned a few simple tricks about things like random numbers, rounding, simple physics (acceleration, inertia, gravity), etc just from following some tutorials in the pico-8 fantasy console. And some people have taken that to extremes, building 3d rendering engines and tech demos in what is a very constrained environment.
- wang_li 6y agoBinary Space Partitioning tree.
- dharmon 6y agoThe second algorithm you are thinking of is probably what is known as "sort-and-sweep". Basically each object takes up an interval along each axis, so a necessary condition for collisions between two objects is that the intersection of the intervals along each axis are non-empty. (which means if there is no overlap of intervals along any axis, you can guarantee they are not colliding). You compute the bounds along each axis in linear time. The sorting of these bounds can be done in linear time, then you take a pass over each axis looking at the marked intervals, which is also linear.
- jansan 6y agoI agree, that sounds a lot like "sort-and-sweep" or "sweep-and-prune" (I prefer the first name). This is an awesome algorithm and really simple. I once reimplemented an algorithm with sort and sweep to improve performance of a certain test case that took 45 seconds to compute. With sort-and-sweep it only needed about 100ms.
- CyberDildonics 6y agoIf you sort bounding boxes in only one dimension by their min values you still have to brute force test their max values and their other dimensions unless you make a secondary space partition or acceleration structure.
- jansan 6y agoNo, it works because you keep an array of "active" elements during the sweep. Let's say you sweep from left to right over the elements sorted by their left bounds. For each element you encounter you check if it collides with any of the active elements. While doing so, you check if the active element's right bounds is left of the current sweep line. If so, it cannot collide with any of the remaining elements, so you can remove it from the active elements. This way the number of active elements usually stays small and you have to check each element only against few other elements.
- CyberDildonics 6y agoWhat you described is what I said. A spatial acceleration structure is meant to skip as many comparisons as possible. What you are talking about is trading less sorting and more comparisons during the queries.
- jansan 6y agoSorry, I misunderstood the "brute force" part of your comment. You are right, for the active elements the standard implementation uses a brute force on the active elements. I had to implement sort-and-sweep to handle one specific performance problem that took 45 seconds to compute. With the simple sort-and-sweep this went down to 100ms. I also tried sorting the active elements along the secondary axis, but at least in our case this did not yield in any further performance improvements. This probably depends a lot on how many elements there are in the active list.
- djmips 6y agoAnd I would point out that some of the best Game Devs who make frighteningly fast code don't have CS degrees and are sometimes fixing up after people that do.