# Tagged Questions

The tag has no usage guidance.

38 views

### Drawbacks to an Octree and Quadtree hybrid?

I've implemented an octree to divide 3D space that contains several objects. I've noticed in certain octree nodes I could use more refinement in some axis, but splitting the node into 8 children is a ...
25 views

### Where should I store an object? - QuadTree

I'm designing a QuadTree to scene partitioning, I've read theory and seen some code examples. When a node has more than 4 objects, it will be splitted into 4 sub-nodes and its objects will be put ...
74 views

### Should I check all the collisions in the game world?? - 2D game

I'm developing a 2D game engine and right now I'm designing the collision system. I've read about space partitioning and QuadTree, and I understand that only the objects that are in the user's view ...
77 views

### QuadTree nice design for nodes

I'm using c++ and have some problems with the QuadTree design. I have some components which are not related to the QuadTree directly. These components are eg. RenderableMesh, PointLight, etc. Some of ...
54 views

A quadtree has limit on number of item in each nodes. Suppose a node has already has same number of item as the limit. If I add another item on same node the node should split and new item should be ...
76 views

### QuadTree Checking Collision With Different Levels of Nodes

I am making a QuadTree for a 2D Platformer. Researched on it and I managed to make a pretty good one where each node stores its 4 SubNode and there's a MAX_OBJECTS for each Node and MAX_LEVELS which ...
67 views

### How to handle (0,0) in 2D game quad tree?

I am not sure how to handle situation when out objects (player) is in center (0,0) point of game which is crossing of four quads. How to handle that case? This image shows problem: Red rectangle is ...
201 views

### Efficient container(s) for units in an 2D RTS game

As the title says, I'm toying around with developing a 2D space RTS game. All of my units are spaceships that basically just shoot at one another, but they have to do a variety of other things as well:...
254 views

### QuadTree-based pathfinding for a volume body

I want to make a game where a player follows a mouse pointer. The game is not tile-based. I use quadtree for a collision detection and everything works fine. But now I want to develop a player ...
216 views

### Should I use octree or quadtree for my spacial data structures? [closed]

I would like to know the advantages and disadvantages of using octree or quadtree for spacial data structures? In a 3d gaming setting would you ever need more than 4 children nodes? Does it take ...
331 views

### Using QuadTree for Procedural Generation

so I've been trying to start a new project that focuses on procedural room generation similar to what is seen in Binding of Isaac. I plan to have the code use a QuadTree to help determine where ...
2k views

### Fully dynamic KD-Tree vs. Quadtree?

Working on my game, I'm at the point where I need to track all of the units in the world so that I can do nearest-neighbor checks for combat. This is an RTS-like game, with potentially thousands of ...
550 views

### Quadtree vs multiple resolution grids for terrain rendering

I have been thinking about quad trees with regards to terrain rendering. From my understanding the basic functionality of quadtree terrain rendering is to frustum cull the terrain in such a manner: ...
97 views

### Pair collision detection on quadtree

I'm planning to use a quadtree for optimizing collision detection. But this quadtree can handle only one type of objects (so I used a base class for my objects). If I use double dispatch after two ...
154 views

### How do I construct the planes for my camera's frustum?

I'm trying to get a handle on frustum culling, but I'm not quite there yet. I have a camera in three-dimensional space Camera position (cx, cy, cz) rotation (tx, ty, tz) fieldofview ...
341 views

### How should I choose quadtree depth?

I'm using a quadtree to prune collision detection pairs in a 2d world. How should I choose to what depth said quadtree is calculated? The world is made mostly of moving objects1, so the cost of ...
81 views

### Optimal approach to build a quad-tree for elongated terrain?

I have got a polygonal terrain in 3D. For simplicity sake I have split it into multitude of unit squares (cells) alike tilemaps do. Now I need to pick a cell under a cursor. For that I'm casting a ray ...
396 views

I've recently discovered the power of Quadtrees and Octrees and their role in culling/LOD applications, however I've been pondering on the implementations for a Dynamic Quad/Oct Tree. Such tree would ...
367 views

### How do I simplify terrain with tunnels or overhangs?

I'm attempting to store vertex data in a quadtree with C++, such that far-away vertices can be combined to simplify the object and speed up rendering. This works well with a reasonably flat mesh, but ...
175 views

### Overlap detection, nearest neighbors

I'm trying to get something similar to the Nearest Neightbor Problem, except I only want neighbors with radius overlapping a radius, and all of them. I'll explain my problem before explaining what I ...
662 views

### Planet sized quadtree terrain precision

I've been working on a planet sized and shaped terrain lib for a while (In webgl and Unity) and have a couple of working implementations [Quadtree cubesphere and circular clipmaps]. But both of them ...
471 views

I have a quadtree which organize my terrain chunks (heightmap) and all the static objects of my 3D world. I use Axially Aligned Bounding Box as a volume for each node of the quadtree. Due to the ...
94 views

### Framebuffer Heightmap Performance Problems

I am using a framebuffer to procedurally create heightmaps with perlin noise in GLSL shaders. There are two main problems that I am experiencing with this. I have a quadtree for the terrain and in the ...
739 views

### How Do Shapes (Rectangles) Work in Quad Trees?

I've been told that a quad tree is the ideal data structure for my game, but I'm having trouble understanding how exactly shapes work within quad trees. I'm doing this in JavaScript, but I think ...
581 views

I've been experimenting with generating a quad sphere. This sphere subdivides into a quadtree structure. Eventually I'm going to be applying some simplex noise to the vertices of each face to create a ...
407 views

### Collision Detection: Simulation Inexplicably Slowing Down/How To Efficiently Calculate Extremes In Each Dimension

BACKGROUND: As discussed here: Fast 2D collision detection in an unbounded space I am working on a collision detection algorithm for a simulation. The catch that makes this case unique is that the ...
233 views

Let's say we have 100 objects of each of few types, that may have an effect if they collide with one other type, or they may not. Is it better to have quadtrees for each object type, and check ...
1k views

### How to deal with objects placed in the root nodes of a quad tree?

I've implemented a quad tree where points and axis aligned rectangles can be put. It works fine, except for one issue that I'll try to describe. When you put a rectangle in the tree and this rectangle ...
755 views

### Efficient collision detection using quadtrees

I recently started to learn Java and OpenGL with the LWJGL and I'm making some simple games to get started. At first, when I was going to implement collision detection I immediately thought there had ...
3k views

### C++ How to implement a spatial hash (for a 2d Game)

I feel kind of silly for asking this question, but are there examples or tutorials on how to implement a spatial hash (grid/cell-based partitioning), preferably in C++? I'm stuck and I have no idea ...
2k views

### Movement & Physics in an entity-component system

I'm currently playing around with entity-components systems and got started on the movement/collision/physics parts and would like to have some pointers! It's a basic 2D sidescrolling game, with the ...
329 views

I have been working on a level-of-detail program. Right now I have the rough structure down (splitting of quads without condensing of quads). But the problem is that when you try to split certain ...
661 views

### Sweep and Prune vs Quad Tree

I need some broad phase algorithm for my 2d game (shmup, bullet hell). Does one or another solution have any major advantages?
4k views

### Demystifying “chunked level of detail”

Just recently trying to make sense of implementing a chunked level of detail system in Unity. I'm going to be generating four mesh planes, each with a height map but I guess that isn't too important ...
498 views

Okay so i've spent a few days learning what a quadtree is and how to implement one. So far I have a quadtree that when I click inside a leaf it subdivides, I wondering how do I get the previous ...
294 views

### Level of detail algorithm not functioning correctly

I have been working on this problem for months; I have been creating Planet Generator of sorts, after more than 6 months of work I am no closer to finishing it then I was 4 months ago. My problem; The ...
402 views

I'm currently developing a 2D sidescrolling shooter game for PC (think metroidvania but with a lot more happening at once). Using XNA. I'm utilising quadtrees for my spatial partitioning system. All ...
187 views

Recently I started writing a Quadtree for creature culling in Opendungeons game. Thing is these are moving points and the bounding hierarchy will quickly get lost if the quadtree is not rebuild very ...
1k views

### QuadTree: store only points, or regions?

I am developing a quadtree to keep track of moving objects for collision detection. Each object has a bounding shape, let's say they are all circles. (It's a 2D top-down game) I am unsure whether to ...
920 views

### How would I create Dynamic LOD with Quad Trees

I would like to be able to create something like the following http://www.youtube.com/watch?v=LxZhWrSmrOY&feature=player_embedded how would I create something like it? I understand I will have to ...