Minetest: Thoughts about a more accurate shaped selection/collision box?

[ExeterDad]

Currently collision/selection boxes are literally boxes. Is it possible to make entity meshes themselves selectable (is that even a word?) or a copy of the mesh scaled?

This would be useful for collision in the movement of odd shaped mobs, and make fighting them more true to life as you would have to actually aim well to harm them.

This is one of the first things I found odd about Minetest when I first played it. I would of expected only the mesh, or what appears as the mesh to be selected.

I'm hoping by putting this out there, that some able bodied dev might consider looking in to it during their copious amounts of free time. :)

[C1ffisme]

What about being able to outline the node by placing a copied and silhouetted version behind it?

This is my rough approximation.

[ExeterDad]

Nice visual, but not exactly what I'm talking about. Imagine selecting a sandmonster. And the selection being the shape of a sandmonster rather than a refrigerator.

[C1ffisme]

@ExeterDad That would be pretty nice. I know multiple boxes are allowed for nodes, but I don't think they are meant for entities since entities can rotate.

[paramat]

As far as i know collisionboxes do not rotate, to keep collision detection in a mostly cuboid world simple. So these need to be square when seen from above to act identically in X and Z directions. So currently the collsionbox always needs to be a designed custom shape because of this.

I don't know if multiple collisionboxes are possible with players and mobs, they are for stairs and nodeboxes. A simple cuboid for players and mobs is probably chosen to make collision detection more lightweight, also, since the world is mostly at node or half-node resolution a more hi-res collisionbox would not make much difference.

Collision detection and selectionbox selection is per-step and probably fairly intensive, so i can understand (and agree) that more complex shapes are not worth the extra complexity.

[C1ffisme]

Or... We could just remove the selection box altogether... [Link to that Pull Request goes here]

[sofar]

Well, collision boxes could just rotate, that isn't really that complex.

[ExeterDad]

I just want to let you guys know that I really do appreciate you discussing this and giving reasons why, or why not this is a good idea.
@sofar It's interesting to me that you are implying that it wouldn't be too complex to implement rotating collision boxes. That would really be a huge improvement as far as mobs are concerned. Odd shaped mobs (think T-rex) could turn without body parts going into blocks. I've engaged with devs in the past on that exact idea and it was quickly waved off. As movement in Minetest is not restricted to 90 degree turns, I think collision box rotation wouldn't break the feel of the cubic world any.

[MoNTE48]

I agree. These mobs are like a cow (technically it is a horizontal rectangle). Very strange, when it is set at 45 degrees, and passing through the blocks "stuck" in their head. Colissionbox should rotate too.

[NathanSalapat]

Rotating collision boxes would be a great addition, right now it's really hard to make any four legged mob, as they usually are longer than wide. As soon as they get larger than one node all sorts of silly things start happening.

[paramat]

A finely-rotated collisionbox would greatly increase complexity of collision detection, because you would be coping with angles and trigonometry. We could perhaps rotate a collisionbox by 90 degree increments, although that would still have problems with long objects.

[ExeterDad]

Even 90 degrees would be better than nothing honestly. I'm assuming if a mob was to turn and hit the 90 degree mark, it would push it away from walls and obstructions. Then if it turned beyond that point, the mob would appear clear of the wall or obstruction.

[Ferk]

Not the collision box. Maybe the selection box.

But I think that the point you want to make is that the visual appearance of the boxes when you select is strange and ugly. I'd rather simply not show them by default and leave the boxes geometry alone (there's already a new option for that).

Maybe an alternative for selection highlight would be to apply a filter to the texture of the entity selected or something like that. Easier to do and nicer than having a mesh of wireframes surrounding the entity selected (because that's what you'd get with what you asked unless you used shaders or an superimposed mesh like in node_highlighting=halo.. which would already sort of apply a filter in the texture anyway).

[ExeterDad]

@Ferk You are exactly right. I did inquire about a selection box that fit the shape of the mob closer at the beginning of this discussion. My first reason was related to collision, and the pleasing shape came second. But however the collision/selection box not rotating is a factor I had forgotten about until reminded. Doesn't matter how tidy the mesh is if it only fits the model for one of the 360 degrees! I could live with a long low box for a snake if needed, just as long as that box is pointing the right way when he's coming at me and I have to try to kill it.
Now are the selection and collision boxes essentially the same thing? I know the differences from the view of the player, but are they the same thing on the coding end?

[DonBatman]

The collision box will make it so mobs do not go into nodes and selection box is what you see when pointing at a mob. Collision boxes imho are more important to have. Having a cow have it's nose sticking our one side of a node while the back side is on the other side is an issue to me.

[paramat]

Another idea for collisionbox is to create an axis-aligned cuboid that changes it's shape to always contian the object as it rotates. Bt then if a long object rotates to 45 degrees you end up with a huge square box far too big for the object.

[ExeterDad]

As I only hoped for a discussion and us get some ideas out there, this can be closed as I got what I asked for :)
I'm closing to cut down on the clutter.

[sorcerykid]

For most purposes, an entity collision box only needs to rotate around the Y-axis, correct? If the X and Z axes are still aligned, then perhaps an algorithm like that described on the following page might be possible:

http://www.euclideanspace.com/threed/games/examples/cars/collisions/index.htm

[sorcerykid]

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.

[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.

[sorcerykid]

I could be mistaken, but how are two boxes significantly more intensive than one box? I was under the impression that stairs already involve multiple boxes for collision detection with entities, yet I haven't seen any arguments in favour of removing stairs and other node boxes since they can potentially degrade performance.

Perhaps it might be more reasonable to offer a global config setting, so that end-users can decide for themselves whether or not they want to enable or disable more precise collision detection based upon the capabilities of their device.

[benrob0329]

I just turn them off, collision/selection boxes are meant to be practical, not pretty. A node outline should be shown based on the model, not the selection box (which may be blocky and imprecise on purpose to make it easier to hit or not hit a node)

[MarkuBu]

The typical collision "box" in Unity is a capsule. But I don't think we need a capsule.

A cylinder on the other hand would be a good choice, at least for human like mobs. I had the problem that rotated mobs stuck in 1 node wide passages and I need to reduce the collision box size to 0.6 or less. That wouldn't happen with a cylinder

[benrob0329]

Collision boxes can be smaller/larger than the node/entity, selection boxes are separate and can better reflect the actual shape of it. Selection highlights should be completely separate and only be based on the shape of the model imho.

[MarkuBu]

It a collision box is much smaller than the entity you may have a problem if you try to shoot with an arrow. You can visually hit the entity, but you will miss because you don't hit the collision box.

I opened #6812 for the cylinder idea

[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.
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.

I think having a rectangular and rotatable single box is the better idea. A cylinder isn't much better for rectangular objects than what we already have.

[MarkuBu]

No offense, but how do other games handle collisions and are still playable? Unity3d can use capsules or even mesh collider. Capsules are much more complex than boxes

https://docs.unity3d.com/ScriptReference/Collider.html

And they can calculate much more complex and realistic physics.

[sorcerykid]

I think it is premature to make assessments about the processing overhead of two collision boxes vs one collision box without real-world performance testing. Shouldn't we first determine whether modern computing hardware is really burdened by simple vector arithmetic? After all, I find it hard believe that a Pentium Core i3 processor would struggle with calculations like x1 - x2 > 0.

Minetest engine already supports waving leaves, 3d clouds, and numerous other fancy and fun features, most of which are not even essential to gameplay. Why not move the processing overhead for waving leaves and 3d clouds to something that offers more utility like improved collision detection?

[sorcerykid]

I also suspect that the number of arithmetic operations required to detect collisions with a non-axis aligned (rotatable) single rectangular box would actually exceed that of two axis-aligned rectangles. According to all Websites that I've found on this subject, axis aligned rectangles are always the optimum method for collision detection in computer games, far outweighing every alternative approach.

[paramat]

I didn't say MT can't do it, i'm saying it is significant and is it worth it? Considering that MT is meant to be able to run on low power or old devices.

it is premature to make assessments about the processing overhead of two collision boxes vs one collision box without real-world performance testing

All i said was it will double collision processing, obviously, because collisions have to be checked for 2 object boxes instead of 1. So i mean 'relatively intensive' compared to currently, obviously MT can do it, but we have to consider if it's worth it.

Minetest engine already supports waving leaves, 3d clouds, and numerous other fancy and fun features, most of which are not even essential to gameplay. Why not move the processing overhead for waving leaves and 3d clouds to something that offers more utility like improved collision detection?

Because the fancy features are not essential for gameplay and can be turned off, basic collisions are and cannot be turned off.

axis aligned rectangles are always the optimum method for collision detection in computer games, far outweighing every alternative approach.

Yes very possibly.

[paramat]

I'll reopen as there is discussion.

[MarkuBu]

However, we should really fix #6807 before we add a new kind of collision box.

I literally had a headache because I wasn't able to find the reason for this weird behaviour in my code. Now I'm 100% sure that it is an engine issue.

[ThomasMonroe314]

I had this idea here:
https://forum.minetest.net/viewtopic.php?f=5&t=19428
@paramat I would like to get your thoughts on this.

[benrob0329]

MC gets away without rotation by making the boxes (selection and collision) work with the models (more square shaped rather than long). I believe we should make selection outlines completely separate (based on the model) from the selection box because the selection box isn't generally pretty. At that point a more accurate/rotating selection box is not needed as much because it, and any changes to it would be hidden (we can change collision in real time iirc, so 90 degree turns would be doable if you really needed a long model)

[paramat]

Selection boxes are just cuboids, their appearence isn't a problem, their prettiness isn't a reason to do something. Selectionboxes need to be simple or cuboids to simplify the code that checks if your shoot line intersects one.

[MarkuBu]

I would just disable the visual selection box by default.

And I think, the collision box in Minetest is much smaller and collision is done by steering behaviours or something similar. How else could dozens of mobs fit on a node?

[benrob0329]

I would just disable the visual selection box by default.

Problem is that people want to know what they are pointing at, so thus my request for a model-based highlight.

[ThomasMonroe314]

I would like to see how much of a performance drop(which I don't think it will be much) my idea would actually have.
If it isn't enough to completely bog down my 32-bit 1.5GB RAM 1.0GHz single-core computer, then I don't see it as a problem.

[sorcerykid]

I'm not sure I understand your idea. Collision detection in the XZ plane is already possible, and it is implemented in the engine. If you are proposing more complex shapes, then that would entail even more computations, in excess of those required by my solution above. Detecting collisions with triangles and rotating rectangles are not nearly as straightforward as axis aligned squares.

[ThomasMonroe314]

I am proposing moving the XZ collisions to an already highly optimized 2d physics engine such as Box2d and leave the Y collisions as they are right now.

[benrob0329]

That sounds neither easy nor practical for a 3D game engine.

[sorcerykid]

From what I understand (and perhaps I am just misunderstanding your proposition), that would entail two separate collision detection algorithms. Thinking outside the box (no pun intended) is good when it comes to problems like this, but I'm not sure if such added complexity would be justified or favorable particularly given the concerns already expressed above.

[Cazadorro]

if you guys just want better outlines why don't you just use the stencil buffer to outline? Also don't understand what is so hard about rotating collision, you can always axis align one box, and test against another one, and especially for simple shapes you can just use GJK algorithm to do collision test no matter alignment or rotation...

How does minetest even do collision? I thought it would just delegate to the underlying seperate engine it uses, but I guess it handles it in some custom way? Does it not sweep and prune, pair prune, then collide check? None of those are particularly hard for rigid rotateable entities, especially given the regular boxy shape. Generally you use a static octree for block collisions detection and a separate system of rotatable entities for minecraft style games maybe they tried to use a single system?

[paramat]

I'm no expert but my thoughts are:

I am proposing moving the XZ collisions to an already highly optimized 2d physics engine

Physics engines are for realistic behaviour, which is much more complex behaviour, so it would likely be much more intensive. We don't need super-realistic behaviour with momentum etc.
There's also the issue of involving another external engine and the work that generates.

[ThomasMonroe314]

Physics engines are for realistic behaviour

That's not exactly what I was going for, as I know that MT doesn't go by realistic physics. I was looking for a more modular approach

There's also the issue of involving another external engine and the work that generates.

good point.

While replying to this, I was pondering about the much dicussed rotating collision boxes.
I have seen people say it would be much more CPU extensive, but haven't shown exactly why.
I was thinking on how they would actually be accomplished, at first I agreed with them about how hard it would be to calculate the rotated planes and such. But then an idea struck me, what if we simplify the process, since there are no curved surfaces, the probability of a face-to-face collision on the XZ plane would be close to none (except for maybe items, but those can be rotated 45 degrees).

Here is an image for the explanation of the algorithm that is to follow:

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.

[sorcerykid]

Like I said, the solution I proposed above is as simple as the existing collision detection between entities which currently entails calculating box2.x_max + box2.x_delta > static_box1.x_min (it's a bit more involved iirc, but that's the gist of the code). However, it includes a second pair of axis-aligned boxes.

In contrast, what ThomasMonroe seems to be suggesting above is using points and lines and checking angles and distances all of which involves trigonometry, and that is going to be more processor intensive than the basic formula shown above.

It's important to remember that visualizing something in the mind or on paper is nearly always easier than implementing it in computer code.

[stujones11]

It seems to me there are two separate issues being discussed here, better looking item selection and more accurate collision detection :)

As others have noted, non axis-aligned collision need not be that computationally expensive, especially if we only consider the XZ plane and reduce it to a 2d problem. Were it gets a little more complicated with MT is when it comes to client-side prediction and server-side validation. I haven't really studied the collision code but I'd guess it could be improved.

A simpler idea that I actually find quite appealing is to allow cylindrical collision boxes. I think it is a nice compromise for realism and good performance. Related issue #6812

[ThomasMonroe314]

In contrast, what ThomasMonroe seems to be suggesting above is using points and lines and checking angles and distances all of which involves trigonometry, and that is going to be more processor intensive than the basic formula shown above.

maybe, maybe not. There are probably dozens of ways to calculate if a point is on one side or another, some might be more CPU extensive than others. If the trig was going to be used more than 4 times for each collision check, then I'd be worried. I mean rendering uses waaaaay more trig than this collision check ever would.

Like I said, the solution I proposed above is as simple as the existing collision detection between entities which currently entails calculating box2.x_max + box2.x_delta > static_box1.x_min (it's a bit more involved iirc, but that's the gist of the code). However, it includes a second pair of axis-aligned boxes.

but it would present more problems when alot of mobs are present, such as the boxes interlocking and maybe even glitching through eachother(due to overlapping boxes).

A simpler idea that I actually find quite appealing is to allow cylindrical collision boxes. I think it is a nice compromise for realism and good performance.

yes cylinder-cylinder is very simple, however cylinder-rectangle is not.

[stujones11]

Unless you are something special then I suggest not trying to re-invent the wheel, there are several well documented techniques, tried and tested over many years of game development. The trick is to find the one most suitable for your own particular game :)

[ThomasMonroe314]

The trick is to find the one most suitable for your own particular game :)
Touche :wink:

[stujones11]

yes cylinder-cylinder is very simple, however cylinder-rectangle is not.

It is simple enough if the axis-alignment is fixed, however, it would make rotating collision boxes even harder to implement. I guess it would have to be one or the other.

[ThomasMonroe314]

It is simple enough if the axis-alignment is fixed, however, it would make rotating collision boxes even harder to implement. I guess it would have to be one or the other.

true, I don't know why I was thinking too complicated

[ThomasMonroe314]

It is simple enough if the axis-alignment is fixed, however, it would make rotating collision boxes even harder to implement. I guess it would have to be one or the other.

true, I don't know why I was thinking too complicated

[paramat]

Author closed this a while back:

As I only hoped for a discussion and us get some ideas out there, this can be closed as I got what I asked for :)
I'm closing to cut down on the clutter.

Closing but feel free to continue discussion.