Calculations for a ship's centre of mass. Finding an efficient solution

[NeonSturm]

int[] x[(-4 to +4 step = 1 block resolution)] = {3 blocks, 5 blocks, ...}; // in real code: or use 0..8 with offset -4
// same for y and z
// update on block creation/deletion: x[block.x]++, -- or += number blocks
int left = 0;
int right = x.length;
int centre = right-left/2:

Initialize more realistic centre x:
int i = -4; // lower index; negative to positive index
int i2 = +4; // upper index; positive to negative index
while( i < i2){
. . if( left < right ) left+= x[i++];
. . . else right+= x[i2--];
}
centre = i // and i2 now both point as closest as possible to the centre.
/*
updates:
. to blocks left or right from the centre should update the counter-variables "left" or "right"
. compare diff(left, right)
. . to diff(( (left - x[centre-1]), (right + x[centre-1]) ))
. . and to diff(( (left + x[centre+1]), (right - x[centre+1]) ))
. take the centre with lowest difference and compare to a possible centre 1 index further in this direction.

Performance stats:

Permanent variables:

1 integer per x, y and z position
3 integers: left, right, centre​

calculations on block addition/loss (if changed in one step and with optimized calculations)

change 1 int for each different x, y, and z

currently 1 integer per block is updated anyway : block count​

update integers for left or right, above or below, inFront or behind

currently mass is updated.​

each second:

check if an updated left/right or above/below, inFront/behind causes a movement of the centre of mass.
. about 4 variable increments/decrements, 6 subtractions/additions, 2 comparison.
. and 2 increments/decrements, 3 subtractions/additions 1 comparison per block which the centre of mass moves.​

 

[ltmauve]

Okay, but do you know how to either a) efficiently translate the ship around the COM so the COM can be tracked instead of the core outside or b) efficiently translate and rotate the ship around the COM when rotating?

 

[Planr]

dangit i remembered how terrible i am at math by the fact i didnt understand anything in the op x.x

 

[ltmauve]

Erm, first, I don't think you would need to use x.length since the variables probably are based on the distances to the core.
Second, does this calculation need to be run again for each block being placed? Because I know a better algorithm for that.

Spoiler: Insert-friendly

First, make three sum variables, one for x, y, and z.
For all blocks, multiply the mass and the x-coordinate, and add it the x-variable. Repeat for y and z.
Now make three more variables, one for x, y, and z. Assign each the corresponding sum variable divided by the mass. These are the coordinates of the CoM.

To update, repeat the "for all blocks" step just for that block, then update the second set of variables.

 

[NeonSturm]

Just: addition takes 2 cpu cycles, multiplication 5+ and division 7 or 10+ (don't remember)

To translate a ship around the COM, you need to know the inertia resistance (= weight*distance of each block)
It gets updated each time the COM moves, or a block is lost/added.

You have the sum of blocks left and a separate for blocks right of com in x, y and z which is fine for everything but rotating the object...
At least it would be a lot better than using the core as com.

... now I see the issue in this. I haven't found thoughts on the concept behind efficient com-calculations in games except that more distant blocks need more velocity to turn at the same angular speed as general rule for objects :/

---

I know that you can do com blocks*0, (com+1) blocks *1...
But where do you start to multiply with 1 if you don't know the com or how long the ship will be? (as build mode can always add blocks to either side).

 

[NeonSturm]

When the ship has along x these blocks:
1 2 3 2 |1| 2 2 2 2
I did result=(result[i-1] default: 0)+x:
1, +2=3, +3=6, +2=8, +1=9
2, +2=4, +2=6 +2=8, +1=9
-> I had an index of 5 in:
1 3 6 8 |9| 8 6 4 2
used left & right = 9 and forgot that intermediate result, as it is not required any-more

I should also have done: result2=(result[i-1] default: 0) +result and use the second-step results to get the CoM, as it inherently multiplies by distance.
in: 1 3 6 8 |9| 8 6 4 2 of 0..9->0..5 and 9..0->9..5 I got 5.
in: 1, +3=4, +6=10, +8=18, +9=27 || 2, +4=6, +6=12, +8=20, +9=29 I would have got an index of about 5.1!
equals: 1 (*5.1) +2 (*4.1) +3 (*3.1) +2 (*1.1) +1*0.1 = 27.6

I wrote about finding the average, forgot to write about finding the centre with help from the results and then... was too much to hold it together in my head after 8 hours of thinking about different things

And now I have to find again a way to update this with efficient code :D

 

[Megacrafter127]

The general problem with rotating is that it is easy if you rotate around 0,0,0 , which is why I suppose the ship core's center is 0,0,0 for optimization.
However if you rotate around a point, that isn't 0,0,0 , you'll have to translate the whole grid to move that point to 0,0,0 , then do the rotating, and then translate it back. The translating itself isn't a big issue, because it's only addition. However all of this has to be executed whenever the ship is rendered, collision-checked, using weapons. There may be more times when this has to be done.

 

[der_scheme]

Okay, but do you know how to either a) efficiently translate the ship around the COM so the COM can be tracked instead of the core outside or b) efficiently translate and rotate the ship around the COM when rotating?

There is no need for that. I assume that the only reason why ships rotate around the core is because schema just wasn't motivated to implement CoM computations.

First, make three sum variables, one for x, y, and z.
For all blocks, multiply the mass and the x-coordinate, and add it the x-variable. Repeat for y and z.
Now make three more variables, one for x, y, and z. Assign each the corresponding sum variable divided by the mass. These are the coordinates of the CoM.

To update, repeat the "for all blocks" step just for that block, then update the second set of variables.

You are on the right track here. Updating the CoM is possible in O(m) (m being the number of updated blocks) complexity. (Note: In the source I'm going to link I wrote O(1). The reason is that this formula is only for one block, but updating m blocks is analogously.)

Anyway. We have an issue on the tracker on that topic. I'll have to confer with AndyP, see if we can push it into queue. There is no reason letting an important feature like this rot in Open status. :D

 

[NeonSturm]

The general problem with rotating is that it is easy if you rotate around 0,0,0 , which is why I suppose the ship core's center is 0,0,0 for optimization.
However if you rotate around a point, that isn't 0,0,0 , you'll have to translate the whole grid to move that point to 0,0,0 , then do the rotating, and then translate it back. The translating itself isn't a big issue, because it's only addition. However all of this has to be executed whenever the ship is rendered, collision-checked, using weapons. There may be more times when this has to be done.

That is why you have a copy of your coordinates (a matrix is 16 ints for position, orientation, scale, ...) + orientation always at 000 0 0.
Then you not translate/orientate your ship, but incoming projectiles and partners for collision checks.
Your ship is only rotated before it is rendered.