Hard Light Productions Forums
Modding, Mission Design, and Coding => FS2 Open Coding - The Source Code Project (SCP) => Topic started by: fightermedic on August 15, 2011, 06:50:58 am
-
:pimp:
are we ever going to see more than 512 astroids in a field?
or, even better, more than one astroid field per mission?
another thing that would really have me freak out would be if local nebulae (just like the ones behind the knossos) would be possible, you know, just have them ristricted to a certain area like astroid fields
wouldn't that be just cool? flying into (and out again) of a nebula?
one can dream i guess...
any opinions?
-
soft particles
(No, legit. Some long-lived soft particles would do the job at approximating distinct clouds of nebula)
-
I once asked for the whole local nebula idea, and I wasn't anywhere near the first. AFAIK, it's not possible at this point, and may well not be for a while - though Kolgena makes an interesting point. Soft particles solve everything!
As for the asteroid thing, as soon as asteroid fields get a code rewrite, the limit at least shouldn't be a problem. The question is when and if that will happen.
-
Oh man... The nebula looks awful right now... Here's hoping a better method reveals itself... Than the ugly scaling and rotating 2d planes.
-
the whole soft particle thing is all greek to me, i leave that discussion for people smarter than me :D
:(
but changing the asteroid maximum to somthing like 5000 should only be a matter of changing one number in the code, yes?
now, who do i need to bribe to get that arrangend? :v-old:
-
the whole soft particle thing is all greek to me, i leave that discussion for people smarter than me :D
:(
but changing the asteroid maximum to somthing like 5000 should only be a matter of changing one number in the code, yes?
now, who do i need to bribe to get that arrangend? :v-old:
At least two numbers, actually. You'd also need to increase the total number of allowed objects. :)
-
And then you need a rather powerful PC that is able to handle all the collision detection required, and a rendering code rewrite that can handle that many objects without much of a slowdown....
Bottom line, these limits are there for a reason, that reason being "making the game playable".
-
And then you need a rather powerful PC that is able to handle all the collision detection required, and a rendering code rewrite that can handle that many objects without much of a slowdown....
Bottom line, these limits are there for a reason, that reason being "making the game playable".
To be fair, increasing the limits doesn't really slow anything down. You only get that problem when people actually make missions that fill up the expanded limits. :)
That said, a 5000 asteroid mission would probably be pretty unplayable. You're much better off faking it like BtRL did, using a bunch of "real" asteroids plus a lot of "fake" asteroids in the distance via skybox.
EDIT: Like this:
(http://3.bp.blogspot.com/_4Lk67pYMLoE/S8HNjSUnSrI/AAAAAAAAAV4/vhKfo65EEps/s1600/beyond-the-red-line_2.jpg)
-
Fredding a few asteroid belt based missions myself I've had some trouble with the limit of asteroids as well. There's a few methods to improve it such as aforementioned skybox but i'm not particularly happy with for instance asteroid ship-like objects that have no collision and thus also can't be blown up. I would love to see the limit improved, and the implementation of soft particles to make local nebulae's like in Freelancer would be very welcoming as well.
I'm hoping there will be some development on this very soon.
*Edit: Darius was kind enough to supply me, thanks again!
-
what about non-persistant objects. if the player is flying in an asteroid field. along side your standard set of asterids say have several smaller asteroids automatically spawned in your vicinity and then disappear as they go out of range, sorta like nebula poofs. there might only be 3 or 4 different models but it provides fill that makes the asteroid field feel denser than it actually is. if the models are small then i figure limiting their collision detecion to radius checks only would improve performance and wouldn't look too bad. likewise i wonder if localized nebulas can be done simply by replacing asteroid models with poofs. real issue with this kinda thing is the transitional effects.
using soft particles would slow down the game a lot especially if you drew an entire asteroid fields worth of them. so what if you only draw poofs on the surface of the field, eliminate anything more than a couple layers deep to increase speed. perhaps using fewer, larger distance poofs at range. i do kinda like the way btrl did their asteroids, with the rotating skybox elements. but heres the part i tell you that the cables are too thick and that asteroid fields are so dispursed that real asteroids appear to be faint blips off in the distance from each other.
-
And then you need a rather powerful PC that is able to handle all the collision detection required, and a rendering code rewrite that can handle that many objects without much of a slowdown....
Bottom line, these limits are there for a reason, that reason being "making the game playable".
To be fair, increasing the limits doesn't really slow anything down. You only get that problem when people actually make missions that fill up the expanded limits. :)
exactly, i say, give the fredder the choice ;) at least my pc can handle large amount of objects quite well, and it's 4 years old
ever made a 10000m³ asteroid field and filled it with 512 asteroids? thats like nothing at all!
so no massive battle in a asteroid field possible right now :(
a very cool solution would be to have asteroids respawn, once destroyed, or once they moved too far away from the original placement area
if you place one or two beam free captial ships with guards in an field, the asteroids will be gone in no time :(
wow a lot of people interested in this matter :lol:
that btrl screen looks awesome btw :)
-
The asteroid count was already bumped from 256 to 512 fairly recently. That is the practical limit until the collision code is improved. (And it wouldn't hurt to improve the asteroid code either.) It can't be bumped higher without incurring severe slowdowns; I've tested it.
Incidentally, there is absolutely no need for a 10km by 10km by 10km cube filled with asteroids. That is indicative of poor FREDding, the same as if you added a dozen capital ships with beam-free-all. Just find out how much volume the battle will take up, and create an asteroid field that's only a little bit larger than that.
-
You could make the asteroids work the collision by just doing radius checks right now. It is quite probable that the slight lack of precision in the resulting collisions would not be that annoying, at least in contrast with the huge benefits...
-
The asteroid count was already bumped from 256 to 512 fairly recently. That is the practical limit until the collision code is improved. (And it wouldn't hurt to improve the asteroid code either.) It can't be bumped higher without incurring severe slowdowns; I've tested it.
It's good to hear such a clear response on the subject, thanks Goober. Some experimentation helped on my end but I look forward to be able to work with a (slightly) larger limit for large vistas or approaching asteroid fields from 10k away.
I also like Nuke's suggestion of non-persistant objects. Motion debris can to mind for some reason as well, also like Freelancer.
-
I have suggested a method for variable density nebulae. There exists portions of the code that dictate the rendered distance between nebula poofs, as well as others that control how far away from the player that ships should become obscured by the fog. The later of these can be adjusted in objecttypes.tbl (I believe) on a per-ship basis, but there is currently no way to change this on a per-mission basis, let alone mid-mission. I would imagine however, that it would not be impossible to make said changes... though adding a FRED interface to make it part of the background editor might take a bit of work. It would need to use a global multiplier so one only needs to change a single number to proportionally increase or decrease the visibility distance for all classes... possibly in-mission if sexps are used.
-
You could make the asteroids work the collision by just doing radius checks right now. It is quite probable that the slight lack of precision in the resulting collisions would not be that annoying, at least in contrast with the huge benefits...
Luis, that would be a valid suggestion if the code didn't do that already.
-
I blame it on nuke, he fooled me!
-
The asteroid count was already bumped from 256 to 512 fairly recently. That is the practical limit until the collision code is improved. (And it wouldn't hurt to improve the asteroid code either.) It can't be bumped higher without incurring severe slowdowns; I've tested it.
Incidentally, there is absolutely no need for a 10km by 10km by 10km cube filled with asteroids. That is indicative of poor FREDding, the same as if you added a dozen capital ships with beam-free-all. Just find out how much volume the battle will take up, and create an asteroid field that's only a little bit larger than that.
i beg to differ sir, because adding 12 beam-free-all ships in an almost 10km³ field was exactly what i did, and it worked out quite well
apart from the fact that after a short time almost all the asteroids are gone, either flown away or destroyed, and that doesen't look like massive battle in dense asteroid field anymore :(
-
That sounds like a true BoE mission.
-
12 beam ships inside an asteroid field?
And people complained about Delenda Est! :lol:
-
Given the distances involved, I suppose it won't be that heavy.
-
You actually need 10km by 10km by 10km when you fly at like, 300-400 m/s.
it only takes like 30 seconds to fly from one end to the other, which is really fast and easy to do and then suddenly no more rocks... >.>
-
I blame it on nuke, he fooled me!
meh, i didnt realize the game only did radius checks by default.
-
Does the engine (in its current state) have any kind of support for Instancing? Because if we could instance asteroid objects (and perhaps fighters like Mara's and such that come in big waves) we could seriously reduce the rendering overheads. For anyone who doesn't know what instancing is, the most basic way I can describe instancing is taking 100 of the same object, and instead of rendering each and every one of those individually, you pass them through the rendering pipeline as 1 single object, drastically reducing the workload on the GPU. Basically...
I just think that if that can be implemented (and I don't imagine that it'd be TOO much to ask of this particular engine) than we could really start to see some improvements to the limitations of model-heavy scenes.
I'll let a coder call the ball on that one though.
-
How could you possibly 'instance' collision and lighting on multiple objects without it looking ridiculous.. or perhaps I don't really understand what instancing does...
-
How could you possibly 'instance' collision and lighting on multiple objects without it looking ridiculous.. or perhaps I don't really understand what instancing does...
It's a quite known feature since directx 10, and I think that the latest iterations from opengl accept this. Still it's not every graph card that does it.
-
That doesn't answer my question...
-
How could you possibly 'instance' collision and lighting on multiple objects without it looking ridiculous.. or perhaps I don't really understand what instancing does...
It's a quite known feature since directx 10, and I think that the latest iterations from opengl accept this. Still it's not every graph card that does it.
OpenGL 3.0 and beyond fully supports model / geometry instancing, so that won't be a problem. And so long as anyone playing FSOpen has a videocard made within the last 3 or 4 years, they should have no issues with support for that feature (and correct me if I'm wrong, but this is the target audience for FSOpen due to performance requirements of the mod and shaders etc). So I don't think it's a question of playerbase support, but rather the actual implementation of the feature and its feasibility.
Lighting & collision detection shouldn't be an issue either. I'm no coder but as far as I understand it, the lighting and/or collision mechanisms are handled at a different 'stage' within the rendering pipeline and therefore should pose no issues (you could almost look at it like post-processing in this situation). What we're talking about is just taking multiple copies of the same model and enabling the GPU to process them all as if they were the 1 individual object. Their size, texture, lighting, collision and so forth are all handled separately.
You can get the basic idea behind instancing here;
http://en.wikipedia.org/wiki/Geometry_instancing
Like I said, I'm no coder but I've hung around with enough folk working on instancing methods to understand that in theory this should be 'relatively' easy to implement and control, especially when using OpenGL as opposed to DirectX.
-
I think the question is: How does instancing help when the calculations for collisions of hundreds of entities is the real bottleneck in asteroid fields?
You said that collision and so forth are handled per-instance, which does nothing for cutting down collision calculations. I guess you do have a point for instancing ships and stuff though. Could reduce the load when there are multiple high stress ships (karunas) involved in a scene, and the GPU buckles before the CPU. However, I have no clue whether some form of instancing is already being used in the engine.
-
I think the question is: How does instancing help when the calculations for collisions of hundreds of entities is the real bottleneck in asteroid fields?
You said that collision and so forth are handled per-instance, which does nothing for cutting down collision calculations. I guess you do have a point for instancing ships and stuff though. Could reduce the load when there are multiple high stress ships (karunas) involved in a scene, and the GPU buckles before the CPU. However, I have no clue whether some form of instancing is already being used in the engine.
This was my next question.
-
I think the question is: How does instancing help when the calculations for collisions of hundreds of entities is the real bottleneck in asteroid fields?
You said that collision and so forth are handled per-instance, which does nothing for cutting down collision calculations. I guess you do have a point for instancing ships and stuff though. Could reduce the load when there are multiple high stress ships (karunas) involved in a scene, and the GPU buckles before the CPU. However, I have no clue whether some form of instancing is already being used in the engine.
I'm just harking on about instancing because from what I can gather the collision detection limitation is currently being worked on and won't be too big an issue before long. I think what we'll start to see is a relaxation in the collision detection overheads, but then we'll see a bottleneck in how many asteroids & ships that can be rendered simultaneously - that's where I'm looking to with this.
It's all well and good if we can solve the collision detection performance issues so the overhead is negligible on x many hundreds (or thousands? ;7 ) of objects, but if we just replace collision detection overheads for rendering limitation overheads, we're right back where we started. That's where I think instancing could help out dramatically.
:yes:
-
Well, I guess instancing is going on that long list of "be nice if we had it, but I don't want/know how to do it" things, assuming it isn't already implemented.
-
I would like to take a moment to help everyone appreciate what N^2 complexity means, when there are 256 asteroids, this means that there are 65536 potential collisions that must be checked against, now this isn't too bad, lets make a gross understatement and say that the collision detection of these objects will take one nanosecond to determine, this means that for this grossly simplified model of the problem the absolute maximum framerate that we could possibly get assuming we did nothing other than collision detection (i.e. no drawing) using some insanely efficient bounding spheres implementation would be about 15258 FPS. pretty good right, we only want 60 FPS so what is the big deal, ok, well lets double it and see what happens.
now we have 512 asteroids that yields 262144 pairs, that's 3814 FPS, wow, that's still crazy good... but if you are perceptive, you might have noticed something, we increased our objects by a factor of 2, our framerate and amazingly high as it is, is now 1/4th what is was before, but that's no matter we have tones of room to expand, we only need 60 FPS and we have almost 4000. lets double it again.
1024 asteroids, 1048576 pairs => 953 FPS. wow, it was almost 4000 last time, now it's not even 1000. but no matter we still have a lot of room, lets go one more
2048 asteroids, 4194304 pairs => 238 FPS. lets do it again
4096 asteroids, 16777216 pairs => 60 FPS. oh, wow, all we did was multiply the number of asteroids by 8, and our framerate went from over 15000 FPS, to just 60, if we go just one more step we hit 15 FPS, the one after that and its down to 4 FPS. keep in mind, this is doing nothing more than an impossibly fast collision test, in reality 1ns is about the speed it takes to perform one multiplication instruction, even just a simple sphere collide test is substantially more complex then this, these numbers give you an understanding of the performance characteristics of the overhead of the comparison, just simply touching them, it's how fast the nested loop would run if it did nothing. and this assumes we do nothing else, no graphics, no input, no game logic. now their might be a better way of running these tests, but it doesn't really matter because right now this isn't even the bottleneck. the bottleneck comes once we have exhausted all possible cheap routs and have to actually collide with a BSP poly-object.
now you might say to yourself, why are we using this horrendously complex structure? the answer is because it gives us logN complexity collision tests, this is effectively the opposite of what we have at the top level, testing for collisions on a model with 100 polies? that will take about 7 steps, more or less (actually it'll provably be more like 25 in the real world) want to collide with a poly object with a BILLION polygons? oh, that'll take about 30 steps (honestly it'd probably be more like 300, but who's counting?) without the BSP tree an object ten million times more complex would need a ten million times as much time to collide with, rather than 4 times more.
so you see we are already using an extremely efficient algorithm to do the model tests, and yet it is still slower than the extremely slow high level test we are using, and it doesn't even get used for asteroids.
-
The key is probably to unphysicalize a majority of asteroids when they're not doing much, but physicalize them on demand only when they are a certain distance to the player or inside the camera's fov. I'm not sure what would happen if you were to look at and physicalize two asteroids while they are floating within each other though.
Or do what WoD did and build a corridor of asteroids and hope the player is not going to leave it.
-
"to look at and physicalize two asteroids while they are floating within each other" -> That "looking" is actually the problem. Checking per-poly is O(log N) according to Bobboau.
Don't asteroids not collide with each other at all? (I mean, is a high-level check done between two asteroids)? If that were the case, adding a ship would be O(N^2) but adding an asteroid would be O(N). a mission with 1 fighter and 65535 asteroids should have 65535 collision pairs.
Like Kolgena said, FRED could have an option- a radius around the player, or the origin, or maybe just a box like asteroid fields already are- within which asteroids check collision, and outside of which they don't. The FREDder would just have to make sure that no ships or installations are outside of the collision box but still inside the field, or that asteroids passing through it wouldn't be noticed.
[EDIT] also, soft particles are the solution
-
The key is probably to unphysicalize a majority of asteroids when they're not doing much, but physicalize them on demand only when they are a certain distance to the player or inside the camera's fov. I'm not sure what would happen if you were to look at and physicalize two asteroids while they are floating within each other though.
I don't think that such a solution would actually help, since you'd still need to be checking all asteroids continuously to confirm whether or not they are at the criteria to be physiciszed. Besides, what about events occurring off-screen, like a capital ship you're escorting getting pummeled by rocks, or a dopey wingman flying into a 'roid?
Damnit, Shivan Hunter. Edged me out!
-
The key is probably to unphysicalize a majority of asteroids when they're not doing much, but physicalize them on demand only when they are a certain distance to the player or inside the camera's fov. I'm not sure what would happen if you were to look at and physicalize two asteroids while they are floating within each other though.
Or do what WoD did and build a corridor of asteroids and hope the player is not going to leave it.
thats kinda what i suggested before. right now asteroids are a derifitive of the object class, they have hitpoints physics data, etc, and they are persistant in the game all the time. if you find an asteroid shoot at it, and leave the area, you will be able to come back and the asteroid would still have all its data. they are persistant, and persistant objects are always being processed all the time (and that includes things like rendering and collision detection, the game checks to make sure 2 asteroids in a far cornerof the miccion collide, its really a waste of time). even if its 10 klicks away and at lod 6. now why does that behavior need to do that all the time. you have a one to ten meter asteroid, that is only visible if youre within say a klick of it. as soon as its out of sight, it simply ceases to existm, no further operations are being done on it. you would still be able to shoot the asteroids and youd still see them hit eachother, but they dont do it when your not looking (or rather when they are out ouf visual range, or rather non-existant at that point).
so what i would do is keep asteroid limits where they are. so you might have 256 good sized asteroids which are persistent at all times. but on top of that you have a another set of say 128 asteroids that only exist in the vicinity of the camera. it would pay heed to the cameras velocity so that asteroids are spawned as they are being "approached" (periodically an asteroid would be spawned a km or two in the direction of the velocity vector). as that happens your also gonna remove an asteroid that you have passed by a km or two, the furthest one away in the reverse direction. the game tries to keep a constant number of small asteroids (by varying spawn time based on the number of slots in the buffer), and they are deleted once they are out of range. so it may seem that there are millions of small asteroids, when in fact there are only ever a few of them. this is probibly something you could rig up in lua in a few minutes. doing this in the engine allows for other things to be done, like instancing for rendering performance. might not work to well in multiplayer since multiple players wouldnt see the same asteroids, maybe they would share asteroid data if their spawn areas ever intersected. or you would div up the buffer so each player could have some rocks and players could see eachothers rocks if they were close enough. thats a whole other can of worms.
of course coming back to btrl, it really shows you how to composite an awesome environment with several existing elements layered on top of eachother. i just say give modders a few more layers to play with. id really like to see improved environments in the game though. localized nebula and better asteroid fields, etc.
-
I think the question is: How does instancing help when the calculations for collisions of hundreds of entities is the real bottleneck in asteroid fields?
You said that collision and so forth are handled per-instance, which does nothing for cutting down collision calculations. I guess you do have a point for instancing ships and stuff though. Could reduce the load when there are multiple high stress ships (karunas) involved in a scene, and the GPU buckles before the CPU. However, I have no clue whether some form of instancing is already being used in the engine.
To be fair, Rendering multiple high-poly objects is a pretty big bottleneck too. The engine is far more inefficient than it should be when rendering lots of a high-poly object (like the mediavps asteroids). Revamping our rendering pipeline (using instancing, or something else) would certainly result in framereate improvements.
As far as bumping asteroid limits, I honestly think we could probably get away with it, but I'd rather focus on bumping weapon/object limits first. :) Diaspora won't be able to release until that happens.
-
so, if asteroid collisions are the problem, what about a checkbox for asteroid fields to have them static?
in this case only ships etc would need to check for collisions with aseroids as the asteroids themselfs would not move.
and ships, rocktes etc only need to check their immidiate surroundings every now and then
-
fightermedic, you do not understand the problem.
-
Jesus Christ, are we talking about revamping the collision and rendering code just so we can have 349587293458 asteroids?
-
Yeah, rock on! :lol:
-
Yeah, rock on! :lol:
lol
-
Jesus Christ, are we talking about revamping the collision and rendering code just so we can have 349587293458 asteroids?
More that we're talking about the engine limitations being what they are, and that we'd have to fix those segments of the engine to get around the limits. :)
Which, of course, we want to do, but not necessarily because of asteroids.
-
i dont think upping the limits in this case is a good idea in this case at all. id drop the limit back to where it was, but then add a second more dynamic set of asteroids which adaptively spawn around the player as they move providing forground fill and the illusion that there are more asteroids than there really are. between the first set of persistent asteroids and the second (probibly smaller) set of filler asteroids. it would look awesome. there will only be a handfull of these things in the game at any time, so they could be destroyed and have collisions.
-
Jesus Christ, are we talking about revamping the collision and rendering code just so we can have 349587293458 asteroids?
no, we are talking about revamping the collision and rendering code just so we can have more than 2000 objects of any sort, be they asteroids, ships, weapons.
-
Jesus Christ, are we talking about revamping the collision and rendering code just so we can have 349587293458 asteroids?
no, we are talking about revamping the collision and rendering code just so we can have more than 2000 objects of any sort, be they asteroids, ships, weapons.
Limit for weapons is only 700, IIRC. Very easy to reach, and Diaspora slammed against that ceiling hard quite a while ago.
-
More Dakka yes/yes?
-
So, I maybe way in over my head, but it seems like this is similar to basic event problems you get in FRED. Some event needs to happen as a response to either this or that or this or that or this or that eventuality. And we solve it in Fred using variables.
Couldn't it be possible to solve this problem too with something that looks like FRED variables?
Let's say you have 1000 asteroids, and these asteroids are flying around all over the place, and some of them are 6000m away from each other so there's no way they're going to collide. If you set up a "variable" for every 1500 meters of space, overlapping about 300 meters in each dimension, and you have the engine create "variables" up to a certain amount of space, like 100,000m3. Then you have the engine derive which variable each ship is in from its coordinates, so that the engine will know if there are any ships in them. Then "variables" which have been verified as having ships are checked for collisions with the normal method.
The number of collision checks should be reduced by a strong factor, but this is an abstract solution which may not work at all because of programming limitations. And larger ships would need to have special derivations. For instance, an Aeolus would probably need endpoint derivations. (Centerpoint +- (1/2)(ship length)) etc..... And the Colossus would need many derivations.
-
So, instead of checking each object against each other, you want to compartmentalize the game space into bubbles, then check the contents of each bubble for collisions.
This strikes me as simply adding overhead for no real benefit, and discounts the fact that we already mechanisms in place for dealing with collision pairs that aren't going to happen. In other words, thank you for your contribution, but it's not something that seems worthwhile (although Swifty, or someone who has spent more time with the collision stuff, may have a more substantiated opinion on this).
On a more general note, I would ask everyone to reign in your posting urges on this topic a bit. Yes, we do appreciate that you're just trying to help, but at this point, we can't really use the help of people who aren't knowledgable in these matters.
-
Just to be clear on what I meant, not all the bubbles would be checked. The bubbles exist theoretically but they wouldn't actually exist in the code until an object entered it because they would be derived from the object location. The bubbles would be defined by the derivation formulas. (I don't know enough about code to know if this is possible.) Then the collision code would be filtered through those bubbles which have come to exist.
The thing that gets cut down is the 2^N factor. Instead of 2^N possible collisions, it becomes 2^x/N + 2^y/N + 2^z/N etc, where x/N, y/N, and z/N are a percentage of N. But what is added is the bubble creation (and destruction?). At least it would be indeterminate whether there is a benefit or not.
But this will be the last I post on it, I promise; I just wanted to make sure there wasn't a mis-understanding of what I was trying to say.
-
I'll repeat what I said in the other collision detection thread. (Really, guys?)
What I'm currently working on is a way for Freespace to track and find collision pairs by not brute forcing through all object pairs. It's called sort and prune. The technical term is recursive dimensional culling. Instead of tracking all pairs and storing N^2 data elements corresponding to each pair, I sort all objects across the X, Y, and Z world axes using a fast sorting algorithm. In this case, quicksort.
I then sweep through all axes individually and prune out all objects that are not overlapping on an axes. The remaining objects are tested with the objects that are overlapped.
No more memory leaks from inserting/deleting elements in the collision linked list. No n^2 costs from deleting/inserting objects into the mission. No n^2 storage requirements. No n^2 bubbles corresponding with increased object numbers. Timing information is kept in log n stl::maps so retrieving timing information for a given pair is a non-issue.
The only problem right now is that it kills timings with ship-ship collisions. And I haven't even tested this with beam collisions but I'm confident they should be okay. Ship-weapon collisions (lasers and missiles versus ships) and weapon-weapon collisions work fine.
Once these issues are resolved, this'll be good to go.
So there you have it, a solution is being worked on. Can we please stop back seat coding?
-
Sorry, from what people were saying, it seemed like only optimizations on the old code were being tried. I'll make sure to do a lot more research in previous threads if I have something to suggest.
-
In this case, quicksort.
As opposed to mergesort? (Not playing algorithm wars, just curious.)
Timing information is kept in log n stl::maps so retrieving timing information for a given pair is a non-issue.
The only problem right now is that it kills timings with ship-ship collisions.
What is this timing issue you speak of? Sorry, I don't believe I've seen the previous thread.
-
What is this timing issue you speak of? Sorry, I don't believe I've seen the previous thread.
Timing as in the next check time for a pair in the obj_pair struct. Originally my code ignored the timings but it just thrashed ship-weapon checks really badly when a bolt or a missile was close to hitting an object for it to check to the BSP tree but not close enough to impact polygons. Freespace handles this by delaying the next check for a few seconds. I restored the timing info for pairs and stored them in an SCP_map to quickly retrieve them when the sort and prune algorithm returns this pair again to see if we need to check the pair in the current frame.
-
As opposed to mergesort?
this is a good question, quicksort turns n^2 when you give it presorted data, you should use an algorithm that takes advantage of the fact that most of the time the order of the objects will not have changed, oddly bubblesort works well in this sort of situation (it's order n*(number of items not in order)).
-
Insertion sort is actually O(n) with sorted or nearly sorted data.
That may be what you're thinking of; I think bubble sort is bad regardless. No, I just looked it up; both bubble sort and insertion sort are good on sorted lists, but insertion sort is better.
-
this is a good question, quicksort turns n^2 when you give it presorted data
Are you sure about that? I think this only happens if the implementation chooses pivots very badly, and IIRC most standard implementations choose a pivot either from the center or randomly precisely to avoid n^2 performance on an already-sorted list.
-
Pure quicksort is n^2 on sorted data. But many implementations are locally optimized for various scenarios. In fact, I think Java's quicksort actually switches to insertion sort when n <= 7.
-
the larger point was there are other sorting algorithms that could take advantage of the fact that the list was sorted last frame.