Questions tagged [space-partitioning]
The space-partitioning tag has no summary.
32 questions
19
votes
1
answer
2k
views
How to achieve the Steel Division 2 frontline? (Dividing area smoothly with curves using a few points)
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 ...
- 447
3
votes
1
answer
239
views
How to maximize enclosed area and minimize perimeter on a grid with obstacles?
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 ...
- 10.7k
2
votes
1
answer
277
views
Fill a non rectangular grid with rectangles
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 ...
- 21
3
votes
0
answers
196
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.
- 811
4
votes
0
answers
214
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 ...
- 729
18
votes
1
answer
5k
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 ...
- 484
2
votes
2
answers
680
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 ...
- 23
1
vote
1
answer
200
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 ...
- 11
4
votes
2
answers
2k
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 ...
- 193
4
votes
2
answers
4k
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 ...
- 740
0
votes
1
answer
126
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 ...
- 171
1
vote
1
answer
886
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:...
- 11
2
votes
2
answers
2k
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 ...
- 55
0
votes
1
answer
1k
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 ...
- 924
1
vote
1
answer
1k
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 ...
- 924