2-D Phyisics engine on the X-Z plane

User avatar
ThomasMonroe
Member
 
Posts: 278
Joined: Tue Apr 04, 2017 16:21
Location: Wherever I am at
GitHub: ThomasMonroe314
IRC: ThomasMonroe TMcSquared
In-game: ThomasMonroe TMcSquared

2-D Phyisics engine on the X-Z plane

by ThomasMonroe » 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.
Projects|:*sigh* school: :Qub³d: :Legends Of Survival: :making people think:
I don't make things messy, I just *cough* disturb the local entropy.
 

User avatar
LMD
Member
 
Posts: 228
Joined: Sat Apr 08, 2017 08:16
Location: Bonn, Germany
GitHub: appgurueu
In-game: LMD + PRO_LMD + Limo

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

by LMD » 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...
 

User avatar
LMD
Member
 
Posts: 228
Joined: Sat Apr 08, 2017 08:16
Location: Bonn, Germany
GitHub: appgurueu
In-game: LMD + PRO_LMD + Limo

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

by LMD » 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)...
 

User avatar
sorcerykid
Member
 
Posts: 737
Joined: Fri Aug 26, 2016 15:36
Location: Illinois, USA
In-game: Nemo

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

by sorcerykid » 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.
 

User avatar
LMD
Member
 
Posts: 228
Joined: Sat Apr 08, 2017 08:16
Location: Bonn, Germany
GitHub: appgurueu
In-game: LMD + PRO_LMD + Limo

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

by LMD » 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 :
Image
Attachments
explanation2.png
(9.05 KiB) Not downloaded yet
 

User avatar
paramat
Developer
 
Posts: 3090
Joined: Sun Oct 28, 2012 00:05
Location: UK
GitHub: paramat
IRC: paramat

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

by paramat » 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.
 

User avatar
burli
Member
 
Posts: 1605
Joined: Fri Apr 10, 2015 13:18

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

by burli » 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.
 

User avatar
ThomasMonroe
Member
 
Posts: 278
Joined: Tue Apr 04, 2017 16:21
Location: Wherever I am at
GitHub: ThomasMonroe314
IRC: ThomasMonroe TMcSquared
In-game: ThomasMonroe TMcSquared

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

by ThomasMonroe » 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?
Projects|:*sigh* school: :Qub³d: :Legends Of Survival: :making people think:
I don't make things messy, I just *cough* disturb the local entropy.
 

User avatar
ThomasMonroe
Member
 
Posts: 278
Joined: Tue Apr 04, 2017 16:21
Location: Wherever I am at
GitHub: ThomasMonroe314
IRC: ThomasMonroe TMcSquared
In-game: ThomasMonroe TMcSquared

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

by ThomasMonroe » 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:

Image

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.
Projects|:*sigh* school: :Qub³d: :Legends Of Survival: :making people think:
I don't make things messy, I just *cough* disturb the local entropy.
 

User avatar
LMD
Member
 
Posts: 228
Joined: Sat Apr 08, 2017 08:16
Location: Bonn, Germany
GitHub: appgurueu
In-game: LMD + PRO_LMD + Limo

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

by LMD » 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 !
Image
Attachments
explanied.png
(5.55 KiB) Not downloaded yet
 

User avatar
ThomasMonroe
Member
 
Posts: 278
Joined: Tue Apr 04, 2017 16:21
Location: Wherever I am at
GitHub: ThomasMonroe314
IRC: ThomasMonroe TMcSquared
In-game: ThomasMonroe TMcSquared

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

by ThomasMonroe » Fri Jan 19, 2018 12:51

the velocity check is a "minor" thing that can be added in to this algorithm.
Projects|:*sigh* school: :Qub³d: :Legends Of Survival: :making people think:
I don't make things messy, I just *cough* disturb the local entropy.
 

User avatar
LMD
Member
 
Posts: 228
Joined: Sat Apr 08, 2017 08:16
Location: Bonn, Germany
GitHub: appgurueu
In-game: LMD + PRO_LMD + Limo

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

by LMD » 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 :
Image
Attachments
emoij.jpg
(129.55 KiB) Not downloaded yet
 

User avatar
stu
Member
 
Posts: 882
Joined: Sat Feb 02, 2013 02:51
Location: United Kingdom
GitHub: stujones11

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

by stu » 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.
 

User avatar
ThomasMonroe
Member
 
Posts: 278
Joined: Tue Apr 04, 2017 16:21
Location: Wherever I am at
GitHub: ThomasMonroe314
IRC: ThomasMonroe TMcSquared
In-game: ThomasMonroe TMcSquared

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

by ThomasMonroe » Sat Jan 20, 2018 12:56

Sorry LMD, I meant that its not hard to add to the algorithm.
Projects|:*sigh* school: :Qub³d: :Legends Of Survival: :making people think:
I don't make things messy, I just *cough* disturb the local entropy.
 

User avatar
LMD
Member
 
Posts: 228
Joined: Sat Apr 08, 2017 08:16
Location: Bonn, Germany
GitHub: appgurueu
In-game: LMD + PRO_LMD + Limo

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

by LMD » Sun Jan 21, 2018 12:50

@ThomasMonroe : No clue what you are apologizing for, you didn't behave rude...
 

User avatar
ThomasMonroe
Member
 
Posts: 278
Joined: Tue Apr 04, 2017 16:21
Location: Wherever I am at
GitHub: ThomasMonroe314
IRC: ThomasMonroe TMcSquared
In-game: ThomasMonroe TMcSquared

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

by ThomasMonroe » Sun Jan 21, 2018 13:39

I was apologizing because I wasn't clear enough
Projects|:*sigh* school: :Qub³d: :Legends Of Survival: :making people think:
I don't make things messy, I just *cough* disturb the local entropy.
 


Return to Feature Discussion



Who is online

Users browsing this forum: No registered users and 1 guest