its just to big!
Archives Forums/Blitz3D SDK Programming/its just to big!
| ||
| hi there. im new here so bear with me. lets say i have 1000 ship in the vastness of space! now i need to know whats each ship distance if from any other ship(for collsions, ai,ect...) now just doing a loop of 1000 ship looking for 1000 ship is not an option! thats one million iterations of a loop each "just" checking distance! thats more resources then the 1000 ship in my 3D engine! im trying to think of a way to relay shrink that! i been trying to do it for weeks with nothing effective to show... here is some of the ways i was thinking will help: splitting the space into virtual sectors or galaxies - dose save a lot but not enough and what happens on the borders of the sector? if someone is sitting on the edge of the next sector i cant see him? an organized list (by distance) i dont think it will save anything coz of the high operating cost of a list like that. so thats where i need help or if anyone knows how a big game handles it. |
| ||
| splitting the space into virtual sectors or galaxies - dose save a lot but not enough and what happens on the borders of the sector? if someone is sitting on the edge of the next sector i cant see him? You could check both your current sector and bordering sectors? Of course In 3D-space that still means checking 27 sectors (think rubics-cube shape), but faster than checking *everything*? |
| ||
| well thats the problem 27 sectors is still alot! and if i make the sectors smaller then the overhead is huge! |
| ||
| so it sounds crazy but it works for physics engines again and again... make these sectors much smaller so you may have 1000 of them 10x10x10 Then before doing any collisions loop through all of the ships and figure out what sector they are in by dividing by the width of the sector and casting to an int.. Now just check for collisions between all ships in the same squares and the ones directly surrounding them.. it actually gets more efficient the more sectors you have set up (to a certain degree of course). I went from 800 colliding balls to over 8,000 balls colliding in real time with this method... also if you arent already, use arrays to store your ships (a tenfold faster as well) |
| ||
| i posted this on gamedev look here they say allmost the same thing BUT i got me a new idea now! http://www.gamedev.net/community/forums/topic.asp?topic_id=544745 read! |
| ||
| ok people we got us a new algorithm to rip apart! nuke it and tell me what you think! so it iterates through every ship and adds it to a list of uh onion layer thingies??? It seems like this would be pretty inneficient... maybe if you have each ship loop through all other ships in its onion ring thing (hey that rhyms) every few seconds and add the ships close by to a list which it uses for collisions. If the ship goes warp speed then simply force the ship to re evaluate its surroundings... |
| ||
| i dose do one loop over all the ships BUT only ones a second and sorts them then everyone else use the same list to add to there list. |
   |