Oolite Bulletins

The main thing with the collision detection system is that it scales O(n^2) or thereabouts. Don't ask me how it could be made O(n) because I'll start to whimper.

Ahruman wrote:

Then again, this could possibly be reduced by putting asteroids in groups; first test colliders against the group’s bounding volume, then against individual asteroids if there’s a hit. Asteroid groups far from the player could be marked non-collidable. Other things could be grouped, too, like formations, or the entire TOGY.

Mmm. Trouble comes when NPC's interact at a distance from the player (say there's a rock-hermit mining that distant asteroid field). I'd still want those interactions to be 'real', so some collision detection has to be done.

winston wrote:

The main thing with the collision detection system is that it scales O(n^2) or thereabouts. Don't ask me how it could be made O(n) because I'll start to whimper.

The basic approach to reducing collision detection overhead is to divide space into regions, place each object in one or more of these regions (more than one for objects on a boundary) and then do collision detection within each region. If you have 100 entities in ten subregions, that’s on the order of 1,000 potential collisions rather than 10,000.

The basic algorithms to look into here are binary space partitioning and octtrees. For Oolite you’d have to take into account the essentially boundless nature of the space being played in; this should’t be too hard.

aegidian wrote:

Mmm. Trouble comes when NPC's interact at a distance from the player (say there's a rock-hermit mining that distant asteroid field). I'd still want those interactions to be 'real', so some collision detection has to be done.

Well, groups (or heirarchies) would still work. For the suggestion involving larger asteroid fields, making groups non-collidable if there are no ships nearby would potentially be helpful, although detecting that there are no ships nearby is obviously a collision-detection problem; this detection could possibly be done at a lower rate, say a few times per second.

Ahruman wrote:

On the other hand, a reasonably expensive fuel station with < 10% chance of showing up would be kinda cool.

I think that a fixed fuel station would alter game-play and make it too easy to refuel if you know the station is there. I would go along with some like being able to arrange a meeting with a fuel tanker, which would work something like this:

- At the station you arrange for a fuel tanker to meet you at a specific witch-point in a specific system at a specific time. You pay up front for this service. The cost would depend on the system and other factors. At the designated time the tanker would appear, you dock, buy the fuel (at a tidy markup) then the tanker moves/jumps off to its next stop.

However there would be a couple of curve balls:

0. You would not be able to arrange a fuel tanker meeting for some systems (too unsafe).

1. The fuel tanker might never show up, no indication why so you loose the money you paid and are stuck without a refuel stop and have to make a break to the station.

2. The fuel tanker might be delayed. You get a message with the new time. The question then becomes does the player wait for the new time and risk getting attacked or make a break for the station ?. Of course the tanker might be delayed again once the new time is reached...

3. The fuel tanker shows up, followed 30 seconds later by a pack of pirates. The fuel tanker being skittish and unarmed will be threatening to jump away if the player doesn't take care of the situation quickly or if it starts taking fire from the pirates.

4. There is no tanker. You are met by a pirate ambush. More common in less reputable systems.

I think this would add the option to refuel to the game, without making it too easy. It would also be at a cost and not be reliable and add an element of risk to the process.

It would also make passenger and cargo runs a lot more interesting as you could add bonuses for early delivery, and watch your bonus go up in smoke as the tanker you arranged for doesn't show or keeps getting delayed

If you put the refuel station in orbit of the sun and populate the WP-sun tradelane, gameplay would still be fun.

Properties:
Fuel extra cheap at solar station, but
no other commodities,
limited shipyard facilities.
Only at higher tech systems or large suns.
Same defence as a normal station or just several defensive turrets.

(+) Would be usefull to avoid the trader-convoys when doing a multi-jump route.
(-) Little activity in lane.
(+) make WP-Sun more populated.
(-) Why refuel at station if the sun is so close you could scoop it for free.

A very rare occasion of a tanker hanging around the WP could be fun, but should still be a random occurence. Maybe have it travel from Sun to WP, pause, wp-sun, scoop fuel/dock with fuel refinery.
Start at random point in route.

Would it make any difference to have the distant objects be stationary until the player ship gets within a certain range? Would this affect the gameplay any, or make any difference to collision detection?

No.

As I said, there would indeed be the problem of increasing the complexity of the simulation...

However the question has to be asked about how accurate simulation of distant objects should be, since objects at a sufficient distance (about 2x scanner range) are essentially invisible to the player. Beyond that distance you could simply do away with collision detection and use pure event probability and random number generation instead.

This could potentially allow for many more ships to be simulated whilst decreasing the amount of collision detection simulation. At first this might sound like a really heavy change to the simulation code, but if memory serves (from a few hours looking at the code many months ago) the universe is all event driven, so it probably wouldn't be that tough to put in a pure probability-based simulation in place of the combined probability and collision-based.

Ahruman wrote:

The basic algorithms to look into here are binary space partitioning and octtrees. For Oolite you’d have to take into account the essentially boundless nature of the space being played in; this should’t be too hard.

My mind immediately asks "what happens on the borders?".

Although I could divide up space to reduce the amount of collision checks some entities near the partition borders would have to be classed as being in both partitions when checking if they collide with other entities.

I suppose an octree structure with fuzzy borders might be an answer... *noodles*

The usual work-around is to allow the objects to be in more than one subspace – up to eight in an octtree. The alternative would be to have border zones which are checked by all ajoining subspaces. These zones would need to be big enough for the largest allowable entity; special-casing planets and suns seems a good idea. (Or just special-casing everything bigger than some arbitrary limit; you don’t get that many Ixian Cruisers in system at once.)

So.

Each entity would keep track of the identifier(s) for the octree leaf(s) it currently occupies, updated when it crosses an octree leaf boundary.

On checking collisions each entity is only checked against entities it shares a leaf with.

That's still O(n^2) to make that check. How do I change that?

Checking everything against everything else is always going to be n². The trick is to make “everything” smaller.

As mentioned above, for 100 objects n² is 10,000. For 10 bins of 10 objects, you get 10 * 10² = 1,000 tests. With 20 bins of five objects, it’s 20 * 5² = 500 tests. For b evenly distributed bins, you’re getting b(n/b)² tests = bn²/b² = n²/b. Obviously there’s a point where managing the transitions between bins, and the effective increase in n due to objects appearing in multiple bins, becomes more expensive than it’s worth.

So, the number of partitions/groups/bins should be smaller than the number of entities?

The number of entities is usually somewhere between 20 and (say) 1000, and is typically about 50, spread across about 250 000 000 m of space.

Most of these will be in specific regions: in orbit about the planet and near the station (lots), on the route out to the witchpoint (many), on the route from the witchpoint to the sun (v.few), on the route from the station to the sun (few).

So, during the set-up of space we define a number of overlapping regions (say spheres) - a sphere about the planet and the station aegis, a sphere about the sun, a number of overlapping spheres along the route from witchpoint to the planet, and 'everywhere else' (outside of any other defined region).

Entities check which spheres they are within (or near the boundary of) as they move.

In checking for collisions we iterate once over each entity to determine the entities in each sphere. We then iterate over each sphere, testing all entities in each sphere against all other entities in that sphere.

Would this be a workable solution/a valid optimisation?

Am I getting this?

Yeah, that’s basically similar to the “group” idea I mentioned earlier. They could probably be combined – putting the TOGY in a group would probably be a win, for instance.

In an octtree or BSP approach, one would typically divide spaces that have too many objects in them (say, for arguments sake, more than ten), and merge ones that have too few objects to their immediate sibling and divide again if necessary. This’d probably end up as something like O(n log n), but I’m not going to prove that at this time of night. :-)

So: standard groups :
System - everything not inside another group
planet-sphere
(ps-route?)
sun-sphere
(sw-route?)
wp-sphere
special (script configurable)

these 3 spheres would overlap in the middle, or maybe smaller groups should be added in between on the routes.

Special should have location-variables similar to other placement methods, plus diameter.

Maybe AI-messages or flags that could be triggered upon entering a sphere. (for enhanced compass etc)

Would box/bar/tube like regions be possible for tradelanes?
A bar or tube region would need quaternion-type coordinatesystem to determine direction, origin, diameter and length.
That or a two coordinate method that places the tube between two points.

hah! blabla. I don't know anything about it. I should shutup.