Optimising use of large quantities of objects
BlitzMax Forums/BlitzMax Programming/Optimising use of large quantities of objects
| ||
| Hi All, I was wondering if you guys had any ideas regarding this: I have a large number of objects, upwards of say 20,000. Currently they are in a list. The list has to be checked sometimes 10 times a logic loop. I need a way to optimise this: My objects are in 3D space and can have any coordinate in 3D space. What I would like to do is find a way to itterate only blocks near the camera, so that if there are only 30 on screen then only 30 objects get checked without having to go through the 20,000 objects. Im also concerned that Lists are too slow for this use. Are there any alternative methods and techniques to do this efficiently? One way I have thought of is to do one check of each item in the list, and create a secondary list at this point containing only objects on screen, and then operate on this. Any thoughts on this appreciated! |
| ||
| Whenever I need to go through a list again, I try to find any way possible to carry out whatever operation it is while going through the list at the same time as the list is being checked elsewhere, it makes for messy code, but I'd rather my code was functional than readable If you really HAVE to check the list 10 times per loop, the secondary list suggestion would seem the way to go to me If it helps, I beleive checking Arrays is quicker, simply for the fact that you dont have to run through everything every time, and I have also had some success using Maps |
| ||
| Before I had finished reading the whole post, I had come to the same anwser that you had , (that is a second list), this doent mean that we are right. Just that if its wrong we would both be doing it. Possibly it would be better to make the second tlist an array, (But thats just academic) If you could order them when you go thru the first Tlist, it might make a difference. Maybe |
| ||
| i can cut down on the 10 per loop but it will always happen a number of times. I would like to do it all in one itteration but the system can't work that way :( I'll try my secondary list idea later. Arrays would take alot of work to convert to, but I will look into the speed difference later :) Thanks. |
| ||
| H&K, I would do it all as an array if I could. What I think im going to do is change all code that currently uses the large list to use a once-per-loop "Active" list, and see how that fares. Thanks :) [edit] Yup, thinking about it, i can render all objects but only have the maths go on around blocks within a certain distance of *the point the camera is looking at* or *the point the mouse is over*. this should reduce the math from 20,000 checks per list use to no more than say, 1000. (selections can contain many objects) Not a bad idea, and now im quite excited to implement it :) And next? Well, after the CPU requirement of 20,000 blocks drops, i have to sort out the GPU requirement haha. |
| ||
| I would do it all as an array if I could Dont forget that an array is only better is you are not manipulating the array itself. The reason I sudgested an array for the second Tlist, was your implication that it would be Recreated each time, and, (and this is important), I dont mean an array of the objects, I mean an array of the Tlinks to the objects in the main list. (Or a Tlist of Tlinks to the first list) |
| ||
| I dont mean an array of the objects, I mean an array of the Tlinks to the objects in the main list hmm! an interesting idea there H&K. Thanks for the thought! |
| ||
| Yup, thinking about it, i can render all objects but only have the maths go on around blocks within a certain distance of *the point the camera is looking at* or *the point the mouse is over*. this should reduce the math from 20,000 checks per list use to no more than say, 1000. (selections can contain many objects) not sure how your objects are setup but another way to cut out checks is visibility. Shoot a ray (or a few rays) from you're camera's position to each object inside that 'smaller' list that you already cut out. any object that doesn't have a clear line of sight you could ignore for this iteration, further cutting down on any computation you need to do. |
| ||
| good tip Alex, but the visibility changes over a frame so this wont work- useful for others though! i just got home, going to start on the list programming. |
| ||
| first off, your object that you store should also have a TLink field that you use for reference. with that you can traverse the list however you want. here is a small extension to TList that allows you to start and any TLink and continue for a number or until the end. http://www.blitzbasic.com/codearcs/codearcs.php?code=1807 |
| ||
| hmm, interesting Dmaz. Our objects could appear anywhere in the list though as they are all dynamically placed by the user. Thanks for all your comments :) |
| ||
| Ok, just an update on this, The "create a localised list once a frame and work from that" idea worked wonderfully resulting in a 600-800% increase in speed :)) |
| ||
| *cough* |
| ||
| Eh yes, Pert! I saw this a while back. I'll look into it :) |
| ||
| I'd look into using octrees to partition your 3D space into workable chunks. I don't know a lot about them myself or else this post would be more insightful :), but it seems like they'd be the tool for the job. |
| ||
| that could help with the FPS walkthrough mode, again, its something i can look into. |
   |