Hi,
I want to optimize my game for collisions and neightboor detections.
I have a map and many unities on it. How can i access quickly to neightboor and distance from other entities ?
I try to find a solution to organize the position of my units in a adapted data structures.
I think that a delaunay triangulation is a good solution, but i have no ideas to make this solution works.
How is it made in game with many units ?
Can anybody helps me ?
PS : sorry for my english...
Organize entities for optimization : Delaunay structure
-
kalvinorama
- Posts: 10
- Joined: Sat Jul 19, 2008 12:27 pm
Organize entities for optimization : Delaunay structure
Last edited by kalvinorama on Mon Nov 08, 2010 9:44 pm, edited 1 time in total.
The slowest version is simply to check for each element the distance to each other element. The trick to optimizing is figuring out ways so you don't have check against all of the other elements anymore. There are a lot of algorithms for that and it depends also on your map-layout which is optimal and on how often and when you have to update elements. The ones I've used so far in games are grids, quadtrees and octrees.
Quadtrees and octrees are rather similar. Quadtree if you only care about 2 dimensions (which is often the case for 3D games) and octrees if you need all 3 dimensions. But both are slow on updates, so they are usually used for static geometry and not for dynamic objects.
For dynamic objects I've had some good experiences with simply using a grid - which has also the advantage that it's somewhat easier to code. Your grid can have any resolution (just experiment) and each grid-field contains a list of objects which touch this grid-field (+ any other information which you find useful). And whenever you move an object it has to update it's grid entries also. And on collision you only have to check against elements within the grids which are touched by the object which is of interest. There are certainly also variations on how to code that, p.E. you might only enter each element in a single grid-field if you know a maximum radius for your elements.
Quadtrees and octrees are rather similar. Quadtree if you only care about 2 dimensions (which is often the case for 3D games) and octrees if you need all 3 dimensions. But both are slow on updates, so they are usually used for static geometry and not for dynamic objects.
For dynamic objects I've had some good experiences with simply using a grid - which has also the advantage that it's somewhat easier to code. Your grid can have any resolution (just experiment) and each grid-field contains a list of objects which touch this grid-field (+ any other information which you find useful). And whenever you move an object it has to update it's grid entries also. And on collision you only have to check against elements within the grids which are touched by the object which is of interest. There are certainly also variations on how to code that, p.E. you might only enter each element in a single grid-field if you know a maximum radius for your elements.
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm