Skip to main content
Game Development

Questions tagged [space-partitioning]

Ask Question

The tag has no summary.

32 questions
Newest Active Bountied Unanswered
Filter by
Sorted by
Tagged with
19 votes
1 answer
2k views

The game Steel Division 2 has a very nice looking frontline system, where a smoothly curved line is drawn between friendly and enemy units, dividing the map into territorty owned by two teams. Does ...
DeeCeptor's user avatar
  • 447
3 votes
1 answer
239 views

Developing an RTS game, I have a tile-based terrain (grid) filled with obstacles. It looks like this (red shapes are obstacles): Now I need to plan an enclosed area on the terrain with some ...
Kromster's user avatar
  • 10.7k
2 votes
1 answer
277 views

I'm developing a city builder with a zoning system similar to Cities: Skylines. What I would need is an algorithm that would find all the way to fill this grid (in red) but with some constraints: In ...
Estelle's user avatar
  • 21
3 votes
0 answers
196 views

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.
IanLarson's user avatar
  • 811
4 votes
0 answers
214 views

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 ...
Allahjane's user avatar
  • 729
18 votes
1 answer
5k views

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 ...
xaxxon's user avatar
  • 484
2 votes
2 answers
680 views

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 ...
Beto's user avatar
  • 23
1 vote
1 answer
200 views

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 ...
Jannat arora's user avatar
  • 11
4 votes
2 answers
2k views

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 ...
Prokop Hapala's user avatar
  • 193
4 votes
2 answers
4k views

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 ...
Steven Lu's user avatar
  • 740
0 votes
1 answer
126 views

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 ...
kagelos's user avatar
  • 171
1 vote
1 answer
886 views

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:...
rawa's user avatar
  • 11
2 votes
2 answers
2k views

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 ...
Liam's user avatar
  • 55
0 votes
1 answer
1k views

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 ...
Douglas Gaskell's user avatar
  • 924
1 vote
1 answer
1k views

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 ...
Douglas Gaskell's user avatar
  • 924
3 votes
1 answer
215 views

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....
Ecir Hana's user avatar
  • 131
3 votes
4 answers
863 views

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 ...
GHroat's user avatar
  • 41
12 votes
2 answers
3k views

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 ...
AturSams's user avatar
  • 10.6k
6 votes
2 answers
11k views

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 ...
Afonso Lage's user avatar
  • 223
18 votes
1 answer
12k views

I'm making a 2d platformer with lots of objects at the same time. They're all AABB collision detected. I first tried a quadtree to decrease the number of of objects to check, tried a few different ...
Chris's user avatar
  • 283
9 votes
2 answers
526 views

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 ...
GarrickW's user avatar
  • 330
3 votes
2 answers
2k views

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 ...
Wolfrevo Kcats's user avatar
  • 676
4 votes
2 answers
395 views

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 ...
Peteyslatts's user avatar
  • 360
8 votes
2 answers
3k views

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, ...
Roy T.'s user avatar
  • 10.2k
3 votes
3 answers
1k views

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 ...
nathan's user avatar
  • 1,876
4 votes
1 answer
9k views

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 ...
A-Type's user avatar
  • 228
1 vote
1 answer
385 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 ...
paul424's user avatar
  • 41
12 votes
1 answer
3k views

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 ...
bobobobo's user avatar
  • 17.2k
2 votes
2 answers
791 views

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 ...
Sebastien Diot's user avatar
  • 631
10 votes
1 answer
439 views

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 ...
Grimshaw's user avatar
  • 3,131
8 votes
1 answer
610 views

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 ...
user802232's user avatar
  • 223
74 votes
6 answers
36k views

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 ...
SomeXnaChump's user avatar
  • 785