Page 1 of 1

### 2-D Phyisics engine on the X-Z plane

Posted: Tue Jan 16, 2018 13:49
Hello all,
Over the past few weeks I have seen several requests for rotating collision boxes and even a failed attempt to make a hacky substitute for it. As I was thinking, the idea for having a full 3-d physics engine came around, but it would be waay too CPU intensive. Then an idea struck me, why not do a 2-d engine n the XZ plane while keeping the Y-axis collisions in the code?
To my knowledge 2-d engines are much faster than 3d ones and might even open up possibilities for different collision boxes such as pentagons, triangles, etc.

### Re: 2-D Phyisics engine on the X-Z plane

Posted: Tue Jan 16, 2018 15:20
Rotating Collisionboxes are possible !
Here's my "plan" :
We can determine pointing-at, right ? That means, we can determine if a ray intersects with a non-rotated box.
This fact enables us to determine if a line intersects with a box.
Again :
- we can determine if a (3D)line intersects with a (3D)Box.
And thats the key !
But how to apply this process for a ROTATED box ?
Easy : instead of simulating a rotated box, we do it the other way round : We rotate the line instead of the box !
Now we can check rotated box - line intersection.
The same principle also works for point-rotated box intersection; rotate the point, not the box !
Whats missing ?
rotated box - rotated box intersection
And how can we describe this ?
Lets name the rotated boxes (a) and (b).
We check for EVERY edge of (a) if it intersects with box (b).
We check for EVERY edge of (b) if it intersects with box (a).
We check for EVERY corner point/vertex of (a) if it intersects with box (b).
We check for EVERY corner point/vertex of (b) if it intersects with box (a).
And thats not too much CPU-intensive, is it ?
But now - uh - implementing this...

### Re: 2-D Phyisics engine on the X-Z plane

Posted: Tue Jan 16, 2018 15:21
BTW, a circle-physics engine would be nice, and would not suffer of rotation problems(circles dont change if rotated)...

### Re: 2-D Phyisics engine on the X-Z plane

Posted: Tue Jan 16, 2018 18:13
I already brought up a perfectly viable algorithm for improved entity collision detection that merely doubles the number of calculations. Moreover, it does not involve any trigonometry functions, only basic arithmetic.

https://github.com/minetest/minetest/is ... -352839610

sorcerykid wrote:Another straightforward solution would be to divide the entity collision box into multiple vertical boxes that remain axis-aligned with the world. This would provide a much greater degree of precision, while being less CPU intensive.

For entities that are square, 2 concentric vertical boxes in a plus sign configuration should suffice. As the entity rotates about the Y-axis, the boxes would be dynamically resized along the X and Z axes (progressing from squares at 0 degrees to rectangles at 45 degrees) at the entity's center to maintain the relative proportions of the entity. Such yaw to size ratios could be precomputed into a cache to reduce the number of redundant calculations.

For entities that are rectangular, 2 non-concentric but equidistant vertical boxes would be more practical. As the entity rotates about the Y-axis, the boxes would be resized and repositioned (progressing from rectangles at 0 degrees to squares at 45 degrees) from the entity's center to maintain the relative proportions of the entity . The yaw to size and the yaw to offset ratios could both be precomputed into a cache, as suggested above.

It was quickly shot down by a certain core dev (we all know who), with the assertion that it is would be too inefficient. Ignore the fact that entity collisions with nodeboxes can already involve upwards of 2-3x the number of calculations, yet nobody is talking about removing nodeboxes even though they are also "inefficient". Sigh.

### Re: 2-D Phyisics engine on the X-Z plane

Posted: Tue Jan 16, 2018 22:09
I believe the attempt of MT is wrong : Simulation steps !
So :
- an entity has a velocity and a position
- every simulation step, the velocity is added to the position.
- but what must not occur is that the entity passes through or gets stuck in other entities
- so the entity has to be blocked before collision
We can achieve this if we calculate the cube from the vertices/edgepoints BEFORE and AFTER and determine WHERE the intersection occurs and WHERE it has to stop DURING this simulation step.
Drawing :

### Re: 2-D Phyisics engine on the X-Z plane

Posted: Wed Jan 17, 2018 07:34
sorcerykid wrote:I already brought up a perfectly viable algorithm for improved entity collision detection that merely doubles the number of calculations. Moreover, it does not involve any trigonometry functions, only basic arithmetic.

It was quickly shot down by a certain core dev (we all know who), with the assertion that it is would be too inefficient. Ignore the fact that entity collisions with nodeboxes can already involve upwards of 2-3x the number of calculations, yet nobody is talking about removing nodeboxes even though they are also "inefficient". Sigh.

Read the thread, i 'shot it down' by saying it was a good idea, but i questioned whether it is worth the doubling of collision checks, for me personally i don't think it is:
Paramat > "Good ideas, but still intensive and multiple collision boxes then need processing for collisions. The current simple box is not ideal obviously but performance is more important i feel."

I later pointed out what you stated above, that it will (obviously) double the amount of collision checks:
Paramat > "With 2 collisionboxes for an object you have already doubled the amount of collision processing done, that's significant, plus all the processing for resizing and moving the multiple collisionboxes."

We then talked about the collision issues of nodeboxes although you state "nobody is talking about removing nodeboxes":
Paramat > "Stairs are different as they're static nodes, and are not very large in number relative to other nodes, so don't make a significant difference. Also, they're worth it."

Note i never once used to words "too inefficient", i only questioned the balance of gain against extra processing.

Your post above contains untruths used together with language designed to try to stir up bad feeling against me, that is very unpleasant behaviour.
You did it because i questioned your idea and disagreed that it was worth it, other people are allowed to have opinions that differ from your own.
I have noticed your unpleasant posts that are irrationally and excessively negative about MT and MT devs, you seem to have a habit of 'baseless MT / MT dev bashing'. Your negativity and unpleasantness is your problem.

### Re: 2-D Phyisics engine on the X-Z plane

Posted: Wed Jan 17, 2018 09:59
LMD wrote:BTW, a circle-physics engine would be nice, and would not suffer of rotation problems(circles dont change if rotated)...

I opened an issue for cylindrical collision"boxes" a while ago. But meanwhile I think, collision boxes are overrated. I think, a vertical line would be better to detect the ground. To avoide collisions something like steering behaviours could be used.

I think, Minecraft uses something similar. How else would it be possible to add dozens of mobs in one node or make something like a mob cannon.

Steering behaviours is nothing that is Minecraft specific. It is used in many games and works well.

### Re: 2-D Phyisics engine on the X-Z plane

Posted: Wed Jan 17, 2018 13:26
steering behaviours have to be implemented per mob, its not a engine issue.

@paramat, do you have any thoughts on my idea?

### Re: 2-D Phyisics engine on the X-Z plane

Posted: Thu Jan 18, 2018 14:05
I had this crazily good idea for an algorithm for checking rotating collision boxes, LMD, paramat, please give your input:

This checks the collision of B with A:
calculate the distance of the red point to the center of B,
find the line that is facing the center of B
calculate if the red point is behind the line, not hard to do:
the way this would happen is you would find the angle between green-red and red-blue as that would tell you whether or not you are behind the line, thus detecting a collision.

Now I know this is a little bit more complicated than normal, but that is expected. I don't think it would be much of a performance drop as it is only dealing with four points at maximum. however, finding those points may or may not be efficient at first but can definitely be optimized.

### Re: 2-D Phyisics engine on the X-Z plane

Posted: Thu Jan 18, 2018 15:30
Nice idea ! But it works MUCH easier.
A rotated collisionrectangle consists of 4 border points, right ?
When do we have a collision ?
BEFORE moving :
- a borderpoint is on -um- lets say - the left side of a rectangle edge
And AFTER moving :
- this borderpoint would be - exactly - on the OTHER side of this edge !
What happened ?
The border point went through the edge of the rect - which MUSTNT occur.
It COLLIDED.
However, new suggestion : 3 face accurate pointing at !
I just wanted to mention that a exact pointing at algorithm would be way easier to accomplish than accurate collisionboxes. We only have to (1)rotate pointing vector (2)check collision with box, and we can simulate an ROTATED selectionbox !

### Re: 2-D Phyisics engine on the X-Z plane

Posted: Fri Jan 19, 2018 12:51
the velocity check is a "minor" thing that can be added in to this algorithm.

### Re: 2-D Phyisics engine on the X-Z plane

Posted: Fri Jan 19, 2018 16:20
Its simply necessary. For example, think of an arrow - travelling at a speed of - umm, lets say - average - 50 kilometres per hour. So if the client has a FPS of - hmm - 25, this arrow will be able to simply conquer/pierce/go through/pass a block ! And the player can be hit inside his house where he meant to be safe.
ASCII-Art is nice to imagine the players face if he dies in-game due to this error :

### Re: 2-D Phyisics engine on the X-Z plane

Posted: Fri Jan 19, 2018 18:52
LMD wrote:ASCII-Art is nice to imagine the players face if he dies in-game due to this error :

LOL, oddly enough, arrows from the crossbow in my 'shooter' mod employ a similar technique to which you describe above, using very crude ray-casting and prediction based on velocity. It's far from perfect but it works reasonably well in most cases. Given enough lag, a player can even walk though solid nodes, this is the real problem when dealing with collisions in client-server based games.

### Re: 2-D Phyisics engine on the X-Z plane

Posted: Sat Jan 20, 2018 12:56
Sorry LMD, I meant that its not hard to add to the algorithm.

### Re: 2-D Phyisics engine on the X-Z plane

Posted: Sun Jan 21, 2018 12:50
@ThomasMonroe : No clue what you are apologizing for, you didn't behave rude...

### Re: 2-D Phyisics engine on the X-Z plane

Posted: Sun Jan 21, 2018 13:39
I was apologizing because I wasn't clear enough

### Re: 2-D Phyisics engine on the X-Z plane

Posted: Sun Aug 12, 2018 17:20
I am too a bit annoyed by the collision box issue. I didn't understand why collisions boxes of mobs mods were "poorly made" until I tried to fix them.

Basically we are bound to square collision boxes because they don't rotate. It seems to me that we are even restricted to 1x1 square base collision boxes because the path finding algorithms don't look they can really deal well with something more fancy (I might be wrong on this).

It's no big deal if some parts of the mob are entering a bit in walls and trees because the collision box is smaller than the model, but that's annoying when you have to hit them; an arrow might go through a mob without dealing damage and that's a bit frustrating (at bow distance the selection box typically does not appear). I acknowledge that this is more specific to survival games with hostile mobs and extra weapons.

I think cylinder boxes could do slightly better because they at least allow the mobs to "slide" on obstacles. So maybe one could introduce a distinction between collision boxes and hit boxes.
For mods that define only collision boxes, the hit box is the same as the collision boxes. But new mods could define a collision cylinder (yay less computations - I think) and the collision_box field would be the hit box.
So new mods could define a narrow collision cylinders for better movement, and wider hit boxes for fights.

### Re: 2-D Phyisics engine on the X-Z plane

Posted: Sun Aug 12, 2018 18:32
At least we should use GL Object Picking.

### Re: 2-D Phyisics engine on the X-Z plane

Posted: Wed Sep 05, 2018 22:49
LMD wrote:At least we should use GL Object Picking.

What do you mean by GL object picking? Something like this? http://www.opengl-tutorial.org/miscella ... engl-hack/