[Swifty]

Jesus Christ, are we talking about revamping the collision and rendering code just so we can have 349587293458 asteroids?

[Luis Dias]

Yeah, rock on!

[Rodo]

Yeah, rock on!

lol

[Sushi]

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.

[Nuke]

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.

[Bobboau]

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.

[Sushi]

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.

[Droid803]

More Dakka yes/yes?

[Cyborg17]

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.

[The E]

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.

[Cyborg17]

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.

[Swifty]

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?

[Cyborg17]

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.

[Goober5000]

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.

[Swifty]

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.

[Bobboau]

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)).

[Goober5000]

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.

[Sushi]

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.

[Goober5000]

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.

[Bobboau]

the larger point was there are other sorting algorithms that could take advantage of the fact that the list was sorted last frame.