Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>You're not talking about a lot of objects in this case. Honestly, you could probably brute force it and probably be fine for your application, even in mobile game development. With that in mind, I'd recommend you <em>keep it simple</em> but throw a bit of optimization on top for gravy. Spatial hashing with a reasonable cell size is the way I'd go here -- relatively reasonable memory use, decent speedup, and not that bad as far as complexity of implementation goes. More on that in a moment!</p> <p>You haven't said what the representation of your objects is, but in any case you're likely going to end up with a typical "broad phase" and "narrow phase" (like a physics engine) -- the "broad phase" consisting of a false-positives "what could be intersecting?" query and the "narrow phase" brute forcing out the resulting potential intersections. Unless you're using things like binary space partitioning trees for polygonal shapes, you're not going to end up with a one-phase solution.</p> <p>As mentioned above, for the broad phase I'd use spatial hashing. Basically, you establish a grid and mark down what's in touch with each grid. (It doesn't have to be perfect -- it could be what axis-aligned bounding boxes are in each grid, even.) Then, later you go through the relevant cells of the grid and check if everything in each relevant cell is actually intersecting with anything else in the cell.</p> <p>Trick is, instead of having an array, either have a hash table for every cell grid. That way you're only taking up space for grids that actually have something in them. (This is <strong>not</strong> a substitution for badly sized grids -- you want your grid to be coarse enough to not have an object in a ridiculous amount of cells because that takes memory, but you want it to be fine enough to not have all objects in a few cells because that doesn't save much time.) Chances are by visual inspection, you'll be able to figure out what a good grid size is.</p> <p>One additional step to spatial hashing... if you want to save memory, throw away the indices that you'd normally verify in a hash table. False positives only cost CPU time, and if you're hashing correctly, it's not going to turn out to be much, but it can save you a lot of memory.</p> <p>So: When you update objects, update which grids they're probably in. (Again, it's good enough to just use a bounding box -- e.g. a square or rectangle around the object.) Add the object to the hash table for each cell it's in. (E.g. If you're in cell 5,4, that hashes to the 17th entry of the hash table. Add it to that entry of the hash table and throw away the 5,4 data.) Then, to test collisions, go through the relevant cells in the hash table (e.g. the entire screen's worth of cells if that's what you're interested in) and see what objects inside of each cell collide with other objects inside of each cell.</p> <p>Compared to the solutions above:</p> <ul> <li>Note brute forcing, takes less time.</li> <li>This has some commonality with the "2D array" method mentioned because, after all, we're imposing a "grid" (or 2D array) over the represented space, however we're doing it in a way less prone to accuracy errors (since it's only used for a broad-phase that is conservative). Additionally, the memory requirements are lessened by the zealous data reduction in hash tables.</li> <li>kd, sphere, X, BSP, R, and other "TLA"-trees are almost always quite nontrivial to implement correctly and test and, even after all that effort, can end up being much slower that you'd expect. You don't need that sort of complexity for a few hundreds of objects <em>normally</em>.</li> </ul> <p>Implementation note: Each node in the spatial hash table will ultimately be a linked list. I recommend writing your own linked list with careful allocations. Each node need take up more than 8 bytes (if you're using C/C++) and should a pooled allocation scheme so you're almost never allocating or freeing memory. Relying on the built-in allocator will likely cripple performance. </p>
    singulars
    1. This table or related slice is empty.
    1. POProper Data Structure Choice for Collision System
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USKaganar
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POProper Data Structure Choice for Collision System
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COIt may become more complex in the future, but as of now the plan is to keep object's represented as axis-aligned rectangles of relatively small size (1 sq unit max in a loaded grid between 100x100 and 400x400 or so). One thing though is that the spacial density of objects will be fairly high. This would likely require a fairly fine hashtable that would have items in as much as 50% of the grids. Also I am using C# and XNA.
      singulars
      1. PO
      1. USGodric Seer
    2. COCool. Sounds like this is a perfect case for spatial hashing seeing as it doesn't handle variate object sizes gracefully with respect to memory use. (You may be hinting at something I'm not catching?) Empty space of any configuration gets handled very gracefully. Anything listed in the same cell will still need an overlapping rectangle check with all of its cell mates. As such, the grid shouldn't be super-fine -- it's just trying to eliminate most of the comparisons you'd need to do in brute force, not all of them. Grid sizes too small and then you're romping through too many cells.
      singulars
      1. PO
      1. USKaganar
    3. COI guess the conceptual issue I am having is trying to find a way that some grid cells will be empty. for instance, if the loaded map is 200x200, making a 200x200 grid for the hash table would likely be too fine. But if I make each grid cell represent a 3x3 area of map tiles, I would more than likely end up with at least 2-3 objects in every grid cell. At that point, doesn't the hashtable just turn into a giant array of linked lists, for all intents and purposes? Or now that I think of it, maybe I would end up with more empty space than I expect, I may just have to play with it.
      singulars
      1. PO
      1. USGodric Seer
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload