36
votes
Accepted
How can I detect "rooms" in a 2D side scrolling game?
I'm not familiar with Terraria, but that can be easily done using a flood-fill algorithm.
Instead of pixel, you check the tiles, and for each tile checked, you evaluate if the algorithm can proceed ...
3
votes
How can I detect "rooms" in a 2D side scrolling game?
There are 2 hard problems in computer science. Naming things, cache invalidation and off-by-one errors.
This is a cache invalidation problem.
If you have a record of "is this inside", whenever a ...
- 371
3
votes
How can I detect "rooms" in a 2D side scrolling game?
Like @Ferreira da Selva said, try the flood fill algorithm. Though, you can use a few different criteria when running the algorithm to determine whether it is enclosed.
For example, for each tile you ...
- 31
3
votes
Performance for range of effect in city builder
Sounds like a use-case for influence maps.
For every kind of building effect you have, you create a two-dimensional array of integers with the size of your map. These are "influence maps" ...
- 122k
3
votes
Optimizing a quadtree for circles and circular queries
As explained in the answer by Romen, there aren't many applicable data structures which are not based on rectangles. But there are a couple other optimizations you can do for circle-circle collisions ...
- 122k
2
votes
Optimizing a quadtree for circles and circular queries
I can't recommend a structure that actually implements what you're asking for, but it definitely won't work like a quad tree. It may not be a tree at all and it might not even exist...
A quad tree has ...
- 406
2
votes
Using octrees as LOD system
As Kromster alludes, this apparent problem occurs because of the small scale of your example. Usually when we reach for sparse octrees, we have more than two levels of subdivision.
Here's your same 2D ...
- 136k
2
votes
How to handle objects at the edges of spatial partition cells?
The simple answer would be to add the object's pointer to both cells. As it exists in both cells, to not include it in both cells would be to circumvent the purpose of having the tree to begin with.
...
- 534
1
vote
Accepted
Does collision detection data structures require a manifold mesh
No game development police will come to arrest you if you try to store a non-manifold mesh in a spatial partition data structure for collision detection purposes. No law of physics will cause your ...
- 136k
1
vote
Performance problems with quadtree for dynamic objects
How deep are your quadtrees? How many elements do you tolerate in a leaf node before you subdivide?
How are your entities spread out through the world?
If it is extremely uneven, with just a few big ...
- 3,734
1
vote
Accepted
Looking for a 2D spatial partitioning method for my top down browser game
The library you're using should do what you want. I tried it — demo here, with the default power of two setting (5):
You have to specify the “area of interest” in the ...
- 6,076
1
vote
Looking for a 2D spatial partitioning method for my top down browser game
Generally with a spatial hash, you will have to grab stuff from more than one cell. This is because even if each cell is larger than a screen width, you could always be close to the edge of your ...
- 9,039
Only top scored, non community-wiki answers of a minimum length are eligible