We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [spatial-partitioning]

Spatial partitioning refers to dividing up some space (such as the game world) into regions with the intent to efficiently search or traverse those regions or the objects within those regions.

Filter by
Sorted by
Tagged with
0
votes
2answers
83 views

How to handle objects at the edges of spatial partition cells?

A lot of games store object positions as floats and have a closed ball for the game area (eg. a rectangle and objects are allowed to have position coordinates on all 4 edges). However, this becomes ...
0
votes
1answer
21 views

Does collision detection data structures require a manifold mesh

Is it possible to apply spatial split techniques (oct-trees bsp-trees, etc) when meshes are not necessary manifolds? The mesh in question represents the "map". This means that it is static so spatial ...
24
votes
4answers
6k views

How can I detect “rooms” in a 2D side scrolling game?

I'm looking to create a system that recognizes certain types of buildings and rooms you can create in game, like how Terraria detects "residences." In that game, a house can be constructed in a tile-...
4
votes
2answers
935 views

Performance problems with quadtree for dynamic objects

I´ve implemented a quadtree spatial partitioning to my game engine as I wanted to try it and see how it affects the performance checks. The results were great (instead of hundreds collision checks ...
3
votes
0answers
127 views

How often should I do a spatial partition over a top down MMO 2D game?

I am writing an top down 2D game like agario/diep.io and I am using spatial hashing for detecting on screen objects. However I find it is too expensive to do a spatial partition a few times a second. (...
0
votes
2answers
389 views

Looking for a 2D spatial partitioning method for my top down browser game

Hi I am currently using a modified version of spatial hashing algorithm written by Christer Bystrom. This algorithm is OK for collision detection. However when I use it for detecting entities in ...
0
votes
1answer
159 views

Should I check all the collisions in the game world?

I'm developing a 2D game engine and right now I'm designing the collision system. I've read about space partitioning and quad trees, and I understand that only the objects that are in the user's ...
3
votes
2answers
227 views

How do I efficiently choose the terrain chunks to render based on the player position?

Well, I have an array with all the terrains. How do I render them? I just add them to a List of terrains that are sent to the Renderer. There, every terrain of the list is rendered. The problem is ...
1
vote
0answers
107 views

How can I represent collection of distant but visit-able stars while using minimal resources?

I have recently started to plan a project in Unity that will be for Android. I have a database that consists of over 150,000 stars (may trim this down if I/O cripples the overhead). The game will ...
0
votes
1answer
748 views

How can I find the object closest to a given 2D point?

I have an array of objects. Their position is a Vector2. I want to select the closest object, given an X and Y coordinate that represents an user touch on screen. ...
0
votes
2answers
169 views

Quick algorithm to identify undrawn rectangles inside a map

I already have a working algorithm for this but it's home-made and there is some redundancy in the things it checks, so I'm looking for a fast algorithm (or the name of it) that would detect undrawn ...