Questions tagged [space-partitioning]
The space-partitioning tag has no usage guidance.
28
questions
4
votes
0answers
101 views
How can I divide tile-based space into largest the possible squares?
I'm trying to find a way to take a tilemap like the top image and divide it into square spaces like the colored areas in the second image.
4
votes
0answers
140 views
How can I render geometry represented in a 64-bit floating point environment?
In this video about Star Citizen, right at the 12:30 mark on the timeline you can see the player zooming in on a space station who's location is clearly out of the limit of 32-bit floating point ...
12
votes
1answer
2k views
Algorithm for “healing” multiple rectangles into a smaller number of rectangles?
Say I have a grid of rectangles of different shapes and colors and I want to reduce (reasonably close to optimal is fine, optimal is not necessary) the number of rectangles to represent the same ...
1
vote
2answers
267 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 ...
1
vote
1answer
156 views
Intersecting rectangles in space
I need to intersect 1 million spatial polygons (specified using their Minimum Bounding Rectangles) with 4 completely disjoint MBR's (MBR1,MBR2,MBR3,MBR4) in space. MBR1, MBR2, MBR3 and MBR4 divide the ...
3
votes
2answers
1k views
understanding spatial hash function behaviour and Knuth for int64
I implemented open-indexing sparse 2D spatial HashMap, and I'm quite satisified with performance ( ~30-70 CPU cycles to get object at particular location for size ~16 Milion objects ).
However, I ...
4
votes
2answers
2k views
What are the disadvantages of R-Trees in collision detection?
I was poking around in SQLite and discovered R-trees. A little digging revealed that R-trees are really just fancy AABB-trees.
Then I realize that the state of the art in collision detection (often ...
0
votes
1answer
68 views
3D space indexing for nearest neighbor searching
I am developing a CAD-like application where the user can draw (digitize) new geometries (points, polylines & polygons). While digitizing, I want the user to be able to (optionally) snap the ...
1
vote
1answer
555 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:...
2
votes
2answers
901 views
Spatial Partitioning - Objects larger than cell?
I'm developing a top down 2D tile based game. Recently I started working on collision detection and have gone down the route of simply using spatial partitioning.
Each object belongs in a cell and ...
0
votes
1answer
233 views
Is spatial partitioning for collision detection an appropriate way for objects to “know” whats around them even if they are not colliding?
I've been puzzling over how to do spatial awareness for units and buildings. I've asked a few questions and the final conclusion was spatial partitioning in the same manner used for collision ...
1
vote
1answer
721 views
Collision, triggering, and range detection in an RTS. What are the optimal solutions for unit spatial awareness?
I've finally ran into the problem of multiple triggers and collisions within my 2D RTS. Up till now I've been using unities sphere colliders as a way of simulating spatial awareness. To trigger when ...
3
votes
1answer
149 views
Planar scene graph
Suppose there are many line segments on a plane (2D scene) and I would like to redraw only small portion ("window") of the whole scene. The scene is dynamic, meaning one can add/remove/transform lines....
3
votes
4answers
576 views
Is moving entities between sectors of a grid spatial partitioning inefficient?
I'm using a grid system for spacial partitioning. If I have moving entities, will I have to reassign every entity to its correct section every frame?
Surely this is inefficient. Have I got the wrong ...
11
votes
2answers
2k views
Axis Aligned Spatial Division : Divide space into random rectangles?
I need a method to divide 3d space into random axis aligned box shapes. For now
I am currently dividing the 2d space for testing purposes. The most immediate approach I came up with was to define a ...
4
votes
2answers
6k views
When would you use an octree in a voxel Engine?
I've been reading about Octrees, and I understand how they work (or at least I think I do). However, I can't figure out why you would use octrees instead of a simple multidimensional array.
In my ...
9
votes
2answers
481 views
World Bounds - (0, Size) or (-HalfSize, HalfSize)?
When creating a game space in which to move, draw and collide objects, is it better to have the (0,0) point, or the (0,0,0) point, be in the very center of your space, such that the bounds of the ...
3
votes
2answers
1k views
Working with chunks of terrain
Let's take for example that in our game, we divide our world (1000x1000 tiles) into chunks of 100x100 tiles. Each chunk contains its own npcs, traps, players, items, whatever. Now, there comes to my ...
4
votes
2answers
265 views
Spatial Partitioning - Language Independant
I understand the structure of Spatial Partitioning Trees - BSP, Quad and Octal. You just take a space and split it into however many parts specified by your tree - BSP:2, Quad:4, Octal:8. I've written ...
8
votes
2answers
2k views
Space partitioning when everything is moving
Background
Together with a friend I'm working on a 2D game that is set in space. To make it as immersive and interactive as possible we want there to be thousands of objects freely floating around, ...
3
votes
3answers
791 views
How to choose cell to put entity in in an uniform grid used for broad phase collision detection?
I'm trying to implement the broad phase of my collision detection algorithm. My game is an arcade game with lot of moving entities in an open space with relatively equivalent sizes.
Regarding the ...
2
votes
1answer
5k views
Would someone please explain Octree Collisions to me?
I've been reading everything I can find on the subject and I feel like the pieces are just about to fall into place, but I just can't quite get it.
I'm making a space game, where collisions will ...
1
vote
1answer
201 views
Dynamic quadrees
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 ...
12
votes
1answer
2k views
What is the kd tree intersection logic?
I'm trying to figure out how to implement a KD tree.
On page 322 of "Real time collision detection" by Ericson
The text section is included below in case Google book preview doesn't let you see it ...
2
votes
2answers
595 views
What are the possible options for AI path-finding etc when the world is “partitionned”?
If you anticipate a large persistent game world, and you don't want to end up with some game server crashing due to overload, then you have to design from the ground up a game world that is ...
10
votes
1answer
299 views
Efficient solution for multiplayer space partioning?
This question is a little tricky, but I will try to make it clear.
Lets say I am building an online game (not MMO-scale), but that supports as many players as possible, in a authoritative server ...
8
votes
1answer
433 views
Chunking/caching large levels in a singleplayer game
Does it make sense to try to offload a large nonlinear level into file-based chunks, and load those on demand? We've implemented level chunking to improve rendering performance, but still all level ...
75
votes
6answers
28k views
How can I optimise a Minecraft-esque voxel world?
I found Minecraft's marvelous large worlds extremely slow to navigate, even with a quad core and meaty graphics card.
I assume Minecraft's slowness comes from:
Java, as spatial partitioning and ...
