   How to check large maps (or not)
  Right now i''m programming a turn based strategy game, and i''m rather happy with it. However, i''m thinking about how you guys code more action-oriented games, so i had a question that basically boils down to how you do hit detection, only with more words :-)my TBS is a tile based game. So my world may be divided into ~100x100 discrete units. If i want to know what or who is in some tile, i do something like:map->GetContents(x,y);BUT, if i was programming a kind of action game it won''t work like that since the "map" is divided into however many units will fit into a LONG INT * 2 = ("a lot"). I''m imagining a game like one of those multiplayer internet "asteroids" types of game where you fly the ships around trying to blast each other. very simple concept. But if i''m at coords 3907x, 2056y, and i want to know if my next "step" is going to run into a wall, how do i know the wall is there? I can check for objects by running a for loop through a list of game object looking for collisions. That''s one way. I certainly can''t say map->GetContents() because the map structure would be too large since we are working in pixels now, not tiles. So what is the right way to "check the map" and look for collisions? Do you check the map or do you check object to each other? It seems like there might be a lot of checking either way. 
  In my current RPG, Golem, I subdivide the map into tiles, and further subdivide each tile into a 4x4 set of subtiles. Each subtile has single-bit flags for BLOCK_WALK, BLOCK_FLY, BLOCK_LIGHT, etc... By simply referencing a tile, then a particular subtile, and reading the bitflag for a particular property, I can quickly perform collision checks between an object and the terrain.Collision between game objects is a different matter. Each tile maintains a contents list. When an object needs to check for collisions, it merely iterates through the contents lists for all tiles the object intersects, and performs checks against each object in the list.There are, of course, many other methods, and the tile-based approach isn''t always appropriate. In the asteroids example you mentioned, you might have better luck with a different sort of space partitioning scheme such as a quadtree (for a 2D) or an octree (for 3D). Each object is resident to a leaf node in the tree, and it is easy and relatively fast to perform collision checks by tree-ing down through the structure, testing nodes at each level, discarding nodes which do not intersect with the object. This rapidly discards non-colliding space in large chunks, recursively fining down the search space until collisions are pinpointed.Of course, in the event that game objects are very limited in number (as occurs in many asteroids-type games) simple brute-force search through a list can be acceptable, and may even be better than something with the overhead of a quadtree. If an asteroids game I was playing had 30-100 objects at most, I''d probably just brute-force and use a single object list. Save overhead, and the computer in such a relatively simple game isn''t going to choke on a brute-force linear search of a 100 object list. Whereas, the overhead penalty of using a recursive tree structure might eat up any efficiency gains.   GolemBlender--The Gimp--Python--Lua--SDLNethack--Crawl--ADOM--Angband--Dungeondweller;  To simplify some of the above, you generally use a bounding check like a bounding sphere for example. In that you measure the distance between 2 objects and if it''s less than the size of the objects they are touching. Therefore you can check collision without a map.You do something similar on a map by checking the range to every tile but that would be silly. Most map based collision is as you desbribe but with a more mobile floating box around the object to test.MarkSound Effects For Game Developershttp://www.indiesfx.co.ukFlatspace is here: The ultimate space adventurehttp://www.lostinflatspace.com;quote:Original post by Mark Sheeky  To simplify some of the above, you generally use a bounding check like a bounding sphere for example. In that you measure the distance between 2 objects and if it''s less than the size of the objects they are touching. Therefore you can check collision without a map.The problem is knowing which objects to check. Let''s say i''m an object and i need to know if any of the 10,000 steaking bullets has just hit me. Do i check all 10,000? If not, the only other alternative i can see is to record there whereabout on the map structure somehow. If a bullet moves, it''s location would get recorded on the map as something like "in the 34, 98 area". Then i am in the 34,98 area and so i say:map->GetOccupants(34,98)and get a list of things in that area. Then check each one for collisions. Is that a good way? It has some overhead in recording positions with every movement though. That could get tedious.;  A little idea on this:I suppose you are using a tile map, and you want to know if an object collides with any tile.Divide the game world in "sectors", each one containing many tiles, how many depends on the map size. Then have each object keep a variable with the sector that object is in. When you move the object, you update that variable if it cross any sector's boundaries.Then, for collisions, look at that variable, and then loop through all the tiles of the sector the object is in, and do your usual collision-test for each one.If that is still slow, try using more sectors, or more complex structures, like quadtrees.   [edited by - Sante05 on February 19, 2004 12:15:02 PM];  It''s all about space partitioning, or organizing objects with some sort of relationship to the space in the world they occupy. Tile-based organization--in which each tile or group of tiles maintains a list of objects within that space--is one way of partitioning space along the lines of regular grid units. If the game world isn''t tile based graphic-wise, then you can still break it down into sectors or grid units. Each time an object (say, a bullet) moves, you pull it out of it''s current sector list, update it''s position, then put it back in.Then, when you need to check to see if a ship collides with a bullet, you just loop through all the objects only in the sector the ship occupies, testing for intersections. Rather than testing all objects in the game, this way only tests those objects in relatively close proximity to the ship.This method has a tendency to break down at the boundaries of sectors. If a ship occupies one sector, but its boundary slightly overlaps the boundary of the sector, then it is possible that a bullet in a neighboring sector will actually intersect the ship, but that since the bullet isn''t in the same sector, the collision will go unnoticed (except by the player who says "Hey, that should have killed me. WTF?!"). This can be fixed by checking collisions against objects in neighboring sectors as well, at the cost of slightly more work.Quadtrees are another way of partitioning a 2D space, though instead of going with regularly spaced grid units, the quad tree recursively subdivides the space, building a branching tree, where each node above the leaf level has 4 children. (Thus the name quadtree; an octree takes it further, with each node having 8 children, good for partitioning full 3D space). The root or parent node of the tree is the entire level. The four children of the root are the 4 quarters of the level, the whole thing split in half each direction. These quarters themselves are quartered into children, which are further quartered until you reach some arbitrary depth of nodes that do not have children (leaf nodes).You insert objects into the tree by starting with the root node and checking to see if the current node completely encloses the object. You recurse down the tree, trying to find the lowest level node which completely encloses the object, discarding from consideration any node that does not completely contain it. Once you find this lowest level node, you insert the object into a contents list owned by that node and move on to the next object.Now, if you need to check a ship for collisions, you tree down the quadtree structure, testing the ship''s bounding box for intersection against each node''s bounding box, starting with the root node, and discarding any nodes that do not intersect the ship. For each node that the ship intersects, you iterate through the node''s contents list and check each object in the list against the ship for collision.This recursive subdivision adds a little bit of overhead for the tree processing. Each object when it moves needs to remove itself from it''s current node and re-tree itself into a new node. Intersection tests start out on a very broad scale, but quickly scale down to testing only in areas very close to the ship. There is overhead, but in a world with a large number of objects it is much more efficient than a brute-force single-list approach.An octree works in a similar fashion but works with cube-shaped nodes rather than squares as the 2D version, and splits each cube node into 8 children. GolemBlender--The Gimp--Python--Lua--SDLNethack--Crawl--ADOM--Angband--Dungeondweller