RTS Collisions - Any tips/thoughts on methods
Blitz3D Forums/Blitz3D Programming/RTS Collisions - Any tips/thoughts on methods
| ||
| Hi I'm working on a RTS and I'm now looking at the collision system. To set the scene there is a 32 x 32 mesh terrain, 6 to 12 buildings, up to 800 trees and up to 3200 player and enemy units moving in blocks of between 24 and 100 units. I have 3 entity types - player units, enemy units and terrain/scenery. Switching on all the collisions is deadly and I was looking at the best way to handle a collision system. The two basic ways I've thought of is to record the grid position of each entity and then go through each grid position, switching on entities collisions contained in that grid position and moving them, next grid switch off all active collisions and switch on that grid's, etc; or looking at a proximity system and only switching on entities collisions that are in close proximity to the moving entity. Both have got their problems and I was just wondering if anybody had looked at anything like this and could give me any tips or thoughts. Cheers GrumpyOldMan |
| ||
| Think you better skip the standard collision commands completely. Think it's a good idea to use a grid, but be shure to have the fields overlapping. Use trigonometry math to calculate the distance between two units, if they are too close to each other, push them both away, unless of course one is a lot lighter than the other. Hope that'll work. |
| ||
| I would avoid eBusiness's idea of trig - No offense, but it would be too computationally heavy. You need to have your pathfinding algo(s) simply avoid any such collisions among units. |
| ||
| Grumpy, I assume you don't move 3,200 units every loop, but only check a few at a time. If thats the case, then when they move, update "the master map" This would be: Dim map(64,64) ;64 is just our grid size - you choose Now each unit merely needs to multiply it's own position by 64 X and Z to be placed neatly within the map. However, you will need to either offset the coordinates or world to begin with as usually in Blitz3D the world starts at 0,0 and goes minus and positive! so bear that in mind. Anyway... When each unit is moved, inform the master map any changes. For example, if the unit was in grid 16,32 and is now in 16,33 it has to first delete itsself from sector 16,32 and add itsself to 16,33. map(x,z) can hold a bank handle if you're curious about how to store a list of entities. Ideally the entity will store where it is in the map, and the map will store where the entity is in the world/64 - they mirror each other. Why? well for collision checking, we now know only to check those that lie in the same grid square as each other. A large saving. Also, the entity's type must know which grid square it is in so we can change the grid square without checking up. It's obvious you can't calculate all the AI for each unit at once. The problem gets smaller in proportion to how you handle your units. |
| ||
| Problem with the grid set-up is if a unit partialy crosses the boarder between grid cells...take a tank unit for example, it's pivot point or whatever may be in grid location 3,4...but part of the mesh may overlap into grid location 4,4 or 4,5, etc...if another unit is near enough to that location in the other grid cell it could cause problems as they won't be able to detect each other until they occupy the same grid cell (at which point they may have collided) You said that the units were in groups of 24 or more...this can work greatly to your advantage...if you also grouped the static entities (buildings and trees) into small "groups" basied on thier proximity to each other...then create a simple collision "box" around these groups that completely surrounds the every object within the group...then when the units are moveing do some quick checking to see if these "boxes" collide with each other...if they are collideing then turn on the collision routines for the individuals within both groups and test accordingly... |
| ||
| Hi Thanks for the replies. I've had a think about both methods. Rob. The grid method is fairly simple but with the problems mentioned by MSW this would mean that as well as the unit's grid location being activated, another 5 would have to be activated (which 5 would depend on the direction the unit was facing) to account for 'cross-border' collisions. In some crowded battles this could mean around 600 units being checked for collisions. The way around this would be to have much smaller grid sizes but then you could have problems in storage for a large grid. I will be playing around with this and seeing what I can do. MTW. I was sitting down and thinking of this actual approach last night and I may go with the uber-entity collision system, possibly using a combination with the grid system. Using uber-entities would cut down the initial collision testing down to 32-36 unit groups, 40-80 forest clumps and 6-12 buildings. Back to chewing on the pencil in front of the drawing board. Thanks again for the replies. Cheers GrumpyOldMan |
| ||
| Also...I'm assumeing that the buildings and trees do not move ... so a combination of something like an OcTree or binary space partion tree and the uber-group thing would likely be very efficent...use the octree to point to potential static collision entities (trees, buildings, etc..) and run the uber group against them to find a selection of potential collisions with the group...you can then start at this octree leaf with each unit to find the nearest set of static objects per each unit... Actualy, with some design considerations, you might be able to develop a runtime auto building octree/BSP like structure to show potential collisions between units (but more likely between uber-groups)... You can do a search for octrees to find out more...but they are quite simple, somewhat like the grid setup you described, but nothing cross over a "grid boarder" |
   |