16

KD-trees are definitively not dynamic enough to be considered, honestly. Moving a few units can easily require you to rebuild the whole KD-Tree. Plus, a KD-tree is very efficient for queries, but not so much for neighbor searching. A quadtree is more flexible over time, as the modification are kept more locally. The disadvantage is that if you have many ...


11

Quadtrees typically store and retrieve rectangles. A point is a specific case where width and height are zero. The following logic is used to find home for new rectangles in the tree, starting with the root node: void Store(Rectangle rect) { if(I have children nodes) { bool storedInChild = false; foreach(Node childNode in nodes) ...


6

Lærne's suggestions are great, but I would also suggest a dynamic bounding volume tree of AABBs. Conceptually the dynamic bounding volume tree keeps a balanced tree of nodes which can be queried at any time for near elements by passing in an AABB and retrieving an overlapping pair. The tree is not rebuilt every frame. Instead each node's AABB is slightly ...


6

I'm not really good at fabricating N- statements, but the minimum search times for an object at child[0] of every child[0] should be close to the same +- a dimension. If the object falls at child[4] of every child[4] the calculation for the octtree could be as much as N^2(?) longer. Since you don't specify how/why the tree is being used, it's hard to give a ...


6

What would be a good approach to let my character move? Should I have a player system that updates the Player's position or velocity? Or should I let it set a state & let another system update the movements of entities based on their velocities and their current state? Leaving the option open that I could move a character by clicking somewhere? I would ...


5

You can read a more detailed answer here:Which is the best LOD method for planet rendering? I'm doing exactly something similar for my computer science degree thesis and attacked the same problem. The problem you have is jitter, and you will find another one more called z-fighting. Jitter: Most of today’s GPUs support only 32-bit floating-point values, ...


5

Usually you'll just have a single quad tree. Often times this would be better as the different layers of collisions can be quite complex and numerous. Also I don't think a bottleneck has ever been that too many potential pairs are culled by layering instead of being implicitly culled by separating data structures. It's hard to make something faster and ...


5

To do a basic spatial hash (slightly more complicated forms exist), you need to generate a broad discrete grid location for any game location. This might be as easy as converting float positions to ints or taking int positions and dividing them all by 64 or some other constant. The idea there is to create a single discrete location most nearby objects will ...


4

I don't understand why do you add the green ones? If you simply test in each step if the red overlaps with the child (simple test), it would look like this: Let's say your rectangle red is located in root and you want to retrieve the neighbours and put them into result child = root procedure populateResult if red collides with child add all ...


4

Just like with any software architecture question, the short answer is "It depends..." Where do I put that quadtree? Any auxiliary data structures needed by one system only should be part of that system. So if that quadtree is only used by the CollisionSystem, then you can make it part of the system. But if that quadtree is used by many different ...


4

Update I have wrote Theraot.ECS inspired by Fastest way to look up an entity with a set of components?. However this answer motivated me to allow to specify custom containers for particular types. It would be necesary to provide an adapter to the interface IIntKeyCollection<TValue> exposed in the project. Which would in theory allow the ECS to use a ...


3

It's a quad tree so when you split it into 4 parts any entities belonging to the parent get divided between the children based on position.


3

I'm doing research in autonomous navigation for robotics, and this is a familiar problem. The real world analogy is you have two vehicles (a robotic motorcycle and a robotic tank) that have to decide on going through a narrow alleyway or not. Dimensions and positions are known by whatever means (radar, LIDAR, maps, GPS, etc)--how do you program such a ...


3

As already stated in others comments I think you might be using the quadtree concept to solve the wrong problem. I spend most of my time managing massive amounts of data working with voxels and even I don't touch quad trees for anything related to generating my world data. The purpose of the quad tree is to help manage and work with your rendered world so ...


2

If you make separate binary trees for different objects, you will destroy the whole purpose of the tree: logarithmic complexity. Say you sort your objects into different trees. Each tree's contents and ordering will have no bearing on collisions with items in other trees. You will be back to testing each item from one tree against each item from another. ...


2

If you re-implement your quadtree to insert objects on borders into all siblings of that border, then the result you'll get is exactly the result you are trying to achieve (with an overhead of 2n per object where n is the number of borders the straddling object is in contact with.)


2

I'd go with some sort of notification/event system to keep the quadtree updated when an object moves. This would require telling the quadtree the previous location of the object (since that's where it was indexed) and the updated location, so the quadtree can check if the object should be reindexed.


2

I would add this as a comment in response to @Nathan Reed's answer, except it's too big to be a comment, and is perhaps in any case worthy of being a separate answer. We were doing precisely what was proposed in his answer, and in fact have comment in the source linking to this page. For the most part, it has worked extremely well, except that once every ...


2

It's not a full answer, but it's too long for a comment... From your question I presume you want to use a LOD system (geomipmap approach) and you're creating your mesh by cube subdivision, so why not to think about a LOD during both stages - mesh creation and rendering? You start from just a 6 planes, so it's really easy to tell which sides are connected. ...


2

Walk the quadtree recursively when saving: save_node(node n) { write_bbox(n.bbox) write_int(n.objects.length) for (object in n.objects) { write_object(object) } write_int(n.children.length) for (child in n.children) { save_node(child) } } save_node(quadtree.root) Read back the same way: read_node() { node n ...


2

Of course, if resources are scarce and speed critical, said depth should be determined through benchmarking, but here are some maths to help cornering it. Let us assume that we are dealing with n object for which we have to trace collisions, that their repartition in the world is uniform and they are small enough that no matter how fine the grid is, overlap ...


2

After reading a lot about this over the years, the advice that I see the most is to avoid doing it at all. It might not feel like good advice at first, but the arguments are that the performance gains you get for making this kind of structure is totally overshadowed by the potential performance gain you would get by simply chopping your model into cubes at ...


2

For performance reasons I never frustum cull on the CPU -- I just distance cull as part of the LOD determination so I'm rendering everything in front of and behind the camera (let the GPU do the culling for the frustum) so that when the player turns there is no potential lag while new terrain chunks are activated or (even worse) sent to the gpu. I also don't ...


2

It depends how you implement double dispatching how elegant it is. You are effectively trying to dispatch to a function that's able to handle collision between types X and Y and execute function for that type pair. This is basically a matrix lookup and you could implement it by registering collision functions to this matrix. Let say your type-ID is 0-based ...


2

There are multiple solutions to this problem. You can place the object in the smallest node which fully contains it. You can split its edges among multiple nodes and tag them with which object they belong to. Another solution is to use a "loose" quadtree. The idea with a loose quadtree is that the nodes are larger than in a normal quadtree, such that they ...


2

In this case you have to decide what to do. In most cases, this is done automatically for you because your sorting is based upon <=, >=, < or > where you definitely get an answer, either true or false, so it really depends which type of comparison you use. For example if(x < middle_of_this_quad) add_to_left_subtree else ...


2

GDX doesn't support it directly. A version for LibGDX https://github.com/alwex/QuadTree


2

Implementing LOD subdivision on terrain is quite complicated, I rather recommend to use a library or something. But if you prefer to learn the hard way here are the principal steps you need to do: First, unlike your assumption, you do not start with 6 meshes like the most zoomed out version, but you define your geometry at highest resolution (most zoomed in ...


2

The simple answer would be to add the object's pointer to both cells. As it exists in both cells, to not include it in both cells would be to circumvent the purpose of having the tree to begin with. The more complicated answer would be to reexamine the purpose for which you're using the spatial partitioning. If this is for graphics and culling, the answer ...


2

There are 2 ways to deal with boxes straddling a boundary. One is to keep the box in the vector of the node where it straddles the boundary and don't push it down. The other is to add the box to all subtrees it overlaps with. For the second option all you need to do is change first if in insert to: //Check if box overlaps boundary if (!mo_boundry.Overlaps(...


Only top voted, non community-wiki answers of a minimum length are eligible