2-D Phyisics engine on the X-Z plane

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

2-D Phyisics engine on the X-Z plane

by ThomasMonroe » Post

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.
I don't make messes, I just, er...disturb the local entropy!

User avatar
LMD
Member
Posts: 1386
Joined: Sat Apr 08, 2017 08:16
GitHub: appgurueu
IRC: appguru[eu]
In-game: LMD
Location: Germany
Contact:

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

by LMD » Post

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...
My stuff: Projects - Mods - Website

User avatar
LMD
Member
Posts: 1386
Joined: Sat Apr 08, 2017 08:16
GitHub: appgurueu
IRC: appguru[eu]
In-game: LMD
Location: Germany
Contact:

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

by LMD » Post

BTW, a circle-physics engine would be nice, and would not suffer of rotation problems(circles dont change if rotated)...
My stuff: Projects - Mods - Website

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

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

by sorcerykid » Post

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: 1386
Joined: Sat Apr 08, 2017 08:16
GitHub: appgurueu
IRC: appguru[eu]
In-game: LMD
Location: Germany
Contact:

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

by LMD » Post

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
explanation2.png (9.05 KiB) Viewed 827 times
My stuff: Projects - Mods - Website

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

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

by paramat » Post

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: 1643
Joined: Fri Apr 10, 2015 13:18

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

by burli » Post

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: 286
Joined: Tue Apr 04, 2017 16:21
GitHub: ThomasMonroe314
IRC: ThomasMonroe TMcSquared
In-game: ThomasMonroe TMcSquared
Location: Wherever I am at

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

by ThomasMonroe » Post

steering behaviours have to be implemented per mob, its not a engine issue.

@paramat, do you have any thoughts on my idea?
I don't make messes, I just, er...disturb the local entropy!

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

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

by ThomasMonroe » Post

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.
I don't make messes, I just, er...disturb the local entropy!

User avatar
LMD
Member
Posts: 1386
Joined: Sat Apr 08, 2017 08:16
GitHub: appgurueu
IRC: appguru[eu]
In-game: LMD
Location: Germany
Contact:

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

by LMD » Post

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
explanied.png (5.55 KiB) Viewed 827 times
My stuff: Projects - Mods - Website

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

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

by ThomasMonroe » Post

the velocity check is a "minor" thing that can be added in to this algorithm.
I don't make messes, I just, er...disturb the local entropy!

User avatar
LMD
Member
Posts: 1386
Joined: Sat Apr 08, 2017 08:16
GitHub: appgurueu
IRC: appguru[eu]
In-game: LMD
Location: Germany
Contact:

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

by LMD » Post

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
emoij.jpg (129.55 KiB) Viewed 827 times
My stuff: Projects - Mods - Website

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

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

by stu » Post

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: 286
Joined: Tue Apr 04, 2017 16:21
GitHub: ThomasMonroe314
IRC: ThomasMonroe TMcSquared
In-game: ThomasMonroe TMcSquared
Location: Wherever I am at

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

by ThomasMonroe » Post

Sorry LMD, I meant that its not hard to add to the algorithm.
I don't make messes, I just, er...disturb the local entropy!

User avatar
LMD
Member
Posts: 1386
Joined: Sat Apr 08, 2017 08:16
GitHub: appgurueu
IRC: appguru[eu]
In-game: LMD
Location: Germany
Contact:

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

by LMD » Post

@ThomasMonroe : No clue what you are apologizing for, you didn't behave rude...
My stuff: Projects - Mods - Website

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

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

by ThomasMonroe » Post

I was apologizing because I wasn't clear enough
I don't make messes, I just, er...disturb the local entropy!

Astrobe
Member
Posts: 570
Joined: Sun Apr 01, 2018 10:46

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

by Astrobe » Post

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.

User avatar
LMD
Member
Posts: 1386
Joined: Sat Apr 08, 2017 08:16
GitHub: appgurueu
IRC: appguru[eu]
In-game: LMD
Location: Germany
Contact:

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

by LMD » Post

At least we should use GL Object Picking.
My stuff: Projects - Mods - Website

Byakuren
Member
Posts: 818
Joined: Tue Apr 14, 2015 01:59
GitHub: raymoo
IRC: Hijiri
In-game: Raymoo + Clownpiece

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

by Byakuren » Post

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/
Every time a mod API is left undocumented, a koala dies.

Post Reply

Who is online

Users browsing this forum: No registered users and 2 guests