   Hierachical Spatial Grids implementation.
  I modified an existing primitive 3D raycasting engine to support multi-level storey buildings using a uniform tile grid to support a tile-based city simulator in the likes of Gametek's Quarantine long time ago in AS3/Flash. (Copy and paste link to see screenshot) http://glidias.freehostia.com/assets/files/kido.jpgI've left this project in the back-burner every since, but i'd would be cool to relook into it. I'm thinking of including a whole array of entity objects which are collidable (currently it isn't) to populate the world (cars, pedestrans, towers, non orthogonal, misc structures, etc. with varied settings). with the addition of using different grid resolution sizes to facilitate varied tile-raycast skips, allowing higher resolution (64x64 tile spaces for smaller skips) for enclosed areas such as alleyways versus large open areas of (1024x1024) spaces for larger-scaled skips. This allows you to scale the world in such a way where every small-space could be made enterable with greater details, kinda like a GTA-4 experience of seamlessly travelling in/out of buildings and enclosures. This could help support entering indoors seamlesssly in the future, but for now i'm just aiming for smaller spaces (ie. narrower alleyways) for people to hide in and provide zones with greater resolution details (64x64 tiles could allow for placing axis-aligned crates that are raycastable).Obviously, the city needs to be divided into a grid to support broad-phase collision detection via spatial hashing and nearest neighbour searches, etc. This also helps provide for a crowd control mechanism of charging through crowds as a man on foot (that react/repel to/from you) during rude chase moments. However, objects are vastly of different sizes from a pedestrian, a car, a non-axis aligned tower/structure, to perhaps some king kong monster , should be supported. As such,  there needs to be  a way to dynamically assign a hierarchical spatial grids only when it's needed over the "hot" areas of the map.I read a student article on this subject, http://www10.informatik.uni-erlangen.de/Publications/Theses/2009/Schornbaum_SA09.pdf . I like the implementation so far which I think might work for the game but there are some things I can't seem to wrap my head around to. (just can't get it, perhaps, due to pre-conceived notions). The questions/issues are:1) With regards to "infinite grid" in Section 2.5 (page 5), I can't seem to visualise the concept fully, and Fig 8 didn't really help either. I obviously know of ways to use modulus operations (bitwise operators) to aggregate a proper 1-dimensional array index for a cell in a uniform grid. I think in my 2d top-down map case, I won't be dealing with negative coordinate space, which makes the process much simpler. However, I'm reading this under the impression that a uniform grid is still being used (based on the first sentence in Section 2.4 Grid Hierarchies pg.7). It's just that within each cell in the uniform grid, there's also the possibility of upgrading that cell in the uniform grid to a hierarchical grid that supports varying cell sizes, and also possibly upgrading the cell size resolution if the threshold for minimum ratio of no. of cells vs no. of objects found in cell is being exceeded (Section 3.3, 3.4). This allows empty areas (like oceans, fields) to have no hierarchical grids assigned to them, only in populated areas. Which means the engine already has a uniform grid of tiles (where no hierarchical resolution-based grids are assigned yet to the tiles), and the engine would only automatically generate such hierarchical grids if the tiles happen to be concentrated with populated items. However, I think what I described may be different from what the article is saying, partly because I'm looking at this from a geo-perspective.2) I liked how he set up the neighboring cell-offsets pointer within each inner cell in the hierarchical grid in Section 3.1 Figure 11, pg 18. The thing is, you'd still need to allocate memory for the bordering cells (to the left,top,right,bottom) to contain unique array offsets to neighboring cells on it's resolution level. Fine, but this leads me to the following question: How does one reference a neighboring grid at the border edge of the current hierachical grid if the hierahical grid isn't the current one (obviously since it's a border cell). Throughout the article, I see no implemenation for referencing "the other hierachical grid"  at the other side (across the border), (if available). Again, I might be under the mistakened impression that there are also possibly other adjacient hierachical grids along the spatial space based on point 1) i mentioned. The thing is, with the given offsets, it looks like the simulation is only processing the cell on the other side of the same hierchical grid, and not a truly adjacient "other grid" across the border.3) Furthermore, because the list of hierarchical grids is implemented as a list and not a dense array, (Section 3.3 pg.27, Figure 16), how does one elegantly detect neighbouring cells across the border in the Detection Step( Section 3.6, pg 31, Algorithm 4) within the specific adjacient level H across another hierachical grid? There's no mentioned way to identify matching levels for adjacient grids at higher levels,  since for the adjacient grid, you'd need to detect whether the adjacent grid in the other hierarchical grid's list has that level to begin with. If the array was a dense array, I could simply check if the value in the current level slot is null or out of bounds. Albeit, you'd have to store extra unused slots in between levels.In short, for points 2 and 3, a) For detecting the neighbors of a bordering cell with a unique offset array, how does the programmer elegantly find the adjacent grid  belonging to the current level (if available), to  retrieve that neighbouring cell across the border?b) How does one know, from what is written in the offset array, that the particular offset value points to another adjacent grid across the border and not the current grid?I see how it's so easy to find neighboring cells with the shared offset array for all inner cells of a grid specific to a grid level. But I'm not satisfied with the solution proposed for the bordering cells, or perhaps I don't understand it fully in the context the author is describing it in to see how a unique offset array for bordering cells would allow me to look-up and find the actual cell that doesn't belong to the same grid, but another adjacent one.4) I also don't understand why in the ((Detection Step - Section 3.6, pg 31, Algorithm 4)) you'd only need to test for HALF of the set of adjacent tiles. It seems the other half would also be tested based on Figure 17 in the algorithm, but where? I can't seem to find it. (Okay, after tinkering stuff out, i figured out the reason due to pairwise interactions, ultimately, i'm going to check all occupied cells across all grids, so doing half it is going to prevent duplicate collision entries.).If only I had the email contact of the student that wrote this, perhaps I could clarify on doubts 2) and 3). I might have misunderstood the whole article completely with regards to the concept of "infinite grids", which leads to the snow-balling of points 2) onwards.[Edited by - Glidias on June 7, 2010 3:45:42 AM]