looks like i need to speed up terrain collision checks in Caveman 3.0.

game description:

http://www.gamedev.net/blog/1730/entry-2258672-caveman-v30-general-desciption/

right now, it checks the world map to get the terrain type(s) present, then checks for collisions for the terrain type(s).

example:

i'm testing with a savegame. the terrain is non-tropical savanna with rocks and a creek.

movement collision checks test each entity vs a sparse matrix list of rocks, a sparse matrix list of trees, and a list of world objects (big stuff like shelters, lean-to's, bedding, fires, etc). each rock in turn is tested vs the creek and skipped if its in the creek, same with trees. trees are also tested vs world objects (no trees in huts!). needless to say, iterating through all these lists is SLOOOOW! <g>

so i'm thinking of using collision maps. due to the size of the game world, they would have to be generated on the fly as needed the way terrain chunks are. so collision maps would be generated on the fly as needed, and stored in a cache, with LRU discard.

the resolution defined for the map will determine the resolution of collision detection possible. in the game i use a scale of 1 d3d unit = 1 foot. so i figure i can get away with a collision map with a scale of 1 unit = 1 foot.

so then i choose a size for collision maps, say 300x300, the size i use for terrain chunks. when i need a map, i go through the world map data and add the rocks, trees, shelters, etc to the collision map. a zero indicates clear, a non zero value indicates some type of object, and the value tells you what kind or which object. testing for collisions is simply a matter of checking the collision map for non zero values in the squares of interest.

new collision maps would only need to be generated when entities and or the player moved far away (about 300 feet). caching of 20 or so maps would keep the number of regens to a minimum.

but how to handle edge cases when an object is at the edge of one map but its radius extends into the next map? just have to code for it?

all this seems a bit complex, but it seems to be the best solution. any alternatives come to mind?

a quick search of the literature online came down to basically subdivision or grids, and grids seemed faster.

timing tests have isolated terrain collision checks as the primary bottleneck in the new AI. the goal is to have 100+ entities active in a small area all mulling about. I'm currently using large herds of 40 or so hippidions (proto-horses) for the testing.

terrain collision checks right now are on the order of 2000+ ticks per moving entity. pretty much all the rest clocks in in the single or double digits for ticks.

any suggestions or advise would be appreciated. i figured out collision maps a while ago (except for edge cases with multiple tiled maps), but have never used them before in a game (at least that i recall - been doing this a long time...).

a quick check of the code reveals that in the test case above, a single entity is currently checked for collisions with 260 trees and 1300 rocks in an 800x800 sparse matrix "plant map".

movement collision checks test each entity vs a sparse matrix list of rocks, a sparse matrix list of trees, and a list of world objects

You could simplify this, and get rid of the tree-in-hut problem by using only one sparse matrix for all of your object types, instead of one matrix for each type. You can also represent objects that are allowed to overlap with other objects (like grass around a tree) by using bitmasked-values in the matrix, instead of straight-forward object-type values.

a quick check of the code reveals that in the test case above, a single entity is currently checked for collisions with 260 trees and 1300 rocks in an 800x800 sparse matrix "plant map".

You should only check each entity against the matrix cells that contain the entity's position... that's the whole point of doing grid-based collision.

the game uses a single generic 800x800 "plant map" implemented as a sparse matrix to determine the location of trees in a map square. the 800x800 plant map is repeatedly tiled over the 26400x26400 map square. when a terrain chunk is generated, it uses the plant map to place trees in the chunk, excluding those that intersect with water and man made objects. same idea for rocks with a separate plantmap2. so there is no unique spare matrix for a given area. its derived from a generic rock map, a generic plant map, and intersections with water and world objects. there are actually 4 types of plant/rock/tree maps and a map square can have all 4 types overlayed over a single area. combining plant maps would result in too many combos (4 to the 5th power including "not used" cases), and you'd still need one for the special cases of intersections with water and man made objects. at 800x800, there are 1089 plant maps in a single map square, and there are 250,000 map squares in the world map. that works out to 272.25 million plant maps. obviously, with that many, they need to be procedurally generated, and cant all fit in ram at once. although i haven't tested it, i suspect a collision map (or terrain chunk for that matter) can be generated faster or as fast as paging off of disk.

You should only check each entity against the matrix cells that contain the entity's position... that's the whole point of doing grid-based collision.

that's the plan.

You can also represent objects that are allowed to overlap with other objects (like grass around a tree) by using bitmasked-values in the matrix, instead of straight-forward object-type values.

fortunately, the only things i have to deal with are trees, large rocks, fruit trees, and man made objects like shelters, so no "overlapping" obstacles that i must keep track of. since its only used for collisions with terrain, what i hit wont really matter. collision recovery will be the result in all cases.

to deal with edge cases, i'm thinking of making a routine that converts a world location (map_x, map_z, x,y,z) to a collision map location (map_x,map_z, cmap_x,cmap_z,x,z).

cmap_x,cmap_z would be the index of the collision map in the map square, and would range from 0,0 thru 32,32. then you check the squares around the entity, x-r thru x+r, and z-r thru z+r, where r is the bbox radius of the entity. these are first normalized to the range 0-499,0-499,0-26399,0-26399. anything totally off the world map returns immediately

as a collision. otherwise its converted to a location in a collision map, which is then generated if needed, and checked.

If your terrain is height map-based, you could just sample the interpolated height from the height map texture, and use that for the collision math - most of the time, all you have to do is clamp each object's position against the terrain's height.

For the water, if it's always at the same height, you can just check your objects against that height and the terrain height (the water bed), to see if the objects are in water... You'll always have to do this, so I don't see how a collision map helps.

Anyway, it does not seem like your problem is the amount of memory used, but the number of objects that you have to check against each-other? What I was trying to explain is that you shouldn't do collision checks of one object from one of your sparse maps against ALL objects from ALL other sparse maps:

a single entity is currently checked for collisions with 260 trees and 1300 rocks in an 800x800 sparse matrix

For example, if you have four sparse maps - one for each object type, you should only have to do four checks - one for each map, at the grid position of the object. And you also don't have to do this every frame - only when placing the objects from the sparse maps into the world and/or collision maps - and I'm assuming you'd only be doing this with collision checks for ALL objects only once, in a "world generation" step which takes place during game load anyway, so the speed should not matter that much. After the objects were already placed in the collision map, you only have to check the dynamic objects for collisions against each other, and against the static objects. The static objects were already checked for collision against each other during the world generation (or sparse map generation), and they are not going to move, so there's no point doing checks between them every frame. In fact, there's no point in adding them to the collision map in the first place - it will be a lot faster to just check each dynamic object directly with the static objects from the sparse maps, even if you still have to do the extra check for the object-in-water case for each static object. Also, if your sparse maps do not contain any overlapping objects to begin with (you could make sure there are no collisions when you generate the sparse maps, as a "loading" step), you won't have to check them for collisions with each other - you'd only have to check for dynamic object collisions with the static objects - and the only "special case" that remains to be checked every frame is the object-in-water case, and for the static objects, assuming that the water is also static, you could just cache this check, maybe by using a "objectInWater" flag in your collision map.

at 800x800, there are 1089 plant maps in a single map square, and there are 250,000 map squares in the world map. that works out to 272.25 million plant maps. obviously, with that many, they need to be procedurally generated

I thought you said the plant maps are tiled (i.e., the same plant map is tiled many times?). Do you mean to say that this tiling is implemented by memcopy-ing the same "plant map" over and over 250,000 times? Wouldn't you be better off just using the original map every time, and just displacing the position of the objects inside them by the current tile's position during collision checks? If this is not the case (if each tile is generated differently), then why do you need the sparse maps in the first place - couldn't you just use values from your RNG directly (every time for all static objects, and for the initial position of the dynamic objects) (assuming your RNG is seed based and always returns the same value for the same (x, y, seed) input)?

If your terrain is height map-based, you could just sample the interpolated height from the height map texture, and use that for the collision math - most of the time, all you have to do is clamp each object's position against the terrain's height.

the game does separate checks for steep rise or steep drop ahead in the ground mesh. this is collision checks with stand alone meshes and models that stick up out of the ground, like trees, large boulders, etc.

the game does not use traditional level maps that contain both ground mesh and object and perhaps entity data.

a world map specifies the heightmap used in a 5x5 mile map square (flat, hills, mountains, etc). tiled plant maps specify the locations of trees, large rocks, etc. the plant maps are sparse matrices (lists of 1300 objects in a 800x800 area).

For example, if you have four sparse maps - one for each object type, you should only have to do four checks - one for each map, at the grid position of the object.

yes, but remember, a sparse matrix is not a real 2d array, its a 1d array list of objects in a 2D area which is mostly empty. so you can't just get the value at plantmap[x][z], you have to loop through the list of 1300 plants and see if one is at or near x,z.

I thought you said the plant maps are tiled

they are. there's only one plant map for each of the 4 types of possibly overlapping coverage (rocks, trees, fruit tress, and berry bushes). but the plants in a given area are those listed in the plantmap, minus ones which intersect with water, man made objects, etc. so while the pattern of plants in an 800x800 area is always the same, the plants in any given 800x800 area varies depending on other things present such as water and man made objects. my point was that due to the large number of 800x800 areas in the game world, and the fact that they are not all the same, it would take a long time to create them in an editor, like skyrim does with their outdoor levels. so i generate them procedurally. by the same token, it would probably take a long time and a lot of disk space to generate them all at new game start. so i generate them on the fly as needed, and don't load or save them at all (at least for the moment).

collision maps are in and done, works great.

execute time for terrain_in_way() dropped from 2000+ ticks to 0-1 ticks.

i may just get the AI to run at 900x speed after all! <g>

yes, but remember, a sparse matrix is not a real 2d array, its a 1d array list of objects in a 2D area which is mostly empty. so you can't just get the value at plantmap[x][z], you have to loop through the list of 1300 plants and see if one is at or near x,z.

A map with a <x,y> pair type as the map keys would give you better results with just two extra (short) integers stored per map entry, but I'm assuming you have to store the x,y position of the objects somewhere anyway, so you could just move it into the map keys, then there's no extra data per map entry compared to your 1D list.

A map with a pair type as the map keys would give you better results with just two extra (short) integers stored per map entry, but I'm assuming you have to store the x,y position of the objects somewhere anyway, so you could just move it into the map keys, then there's no extra data per map entry compared to your 1D list.

ordering the list on x,z would allow faster searches, but a lookup of collision_map[x][z] is even faster - basically the fastest way it can be done.

time to generate a collision map is on the same order as that to do a brute force collision check, so fortunately, that's not an issue, otherwise, ordering the lists on x,z could be used to speedup collision map generation. one might even go so far as to create a 2d index for the plant map that returns -1 (nothing there), or the plant map index of the plant there. this would be even faster than searching a list ordered on x,z.

from playing around with these various data structures, i keep noticing that 2D indexes into a 1D list seems to rise to the top again and again as the method of preference. beaten only by direct 2D (or 1D or 3D or nD) grid lookup.

so it appears that bucket sort wins when it comes to sorting, and grid lookup wins when it comes to retrieving data.

adding items to a n-Dimensional index is a form of bucket sort. i use it when generating terrain chunks (ordered render-ables lists - 2D, indexed on tex & mesh), to "sort" the render queue (2D, indexed on tex & mesh), and for lists of caves (2D index), huts (2D index), player caves (1D index), rafts (1D index), etc.