Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Thoughts about a more accurate shaped selection/collision box? #3996

Closed
ExeterDad opened this issue Apr 14, 2016 · 53 comments

Comments

Projects
None yet
@ExeterDad
Copy link

commented Apr 14, 2016

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

This comment has been minimized.

Copy link

commented Apr 14, 2016

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

screenshot_20160414_135659

This is my rough approximation.

@ExeterDad

This comment has been minimized.

Copy link
Author

commented Apr 14, 2016

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

This comment has been minimized.

Copy link

commented Apr 14, 2016

@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

This comment has been minimized.

Copy link
Member

commented Apr 15, 2016

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

This comment has been minimized.

Copy link

commented Apr 15, 2016

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

@sofar

This comment has been minimized.

Copy link
Member

commented Apr 15, 2016

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

@ExeterDad

This comment has been minimized.

Copy link
Author

commented Apr 16, 2016

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

This comment has been minimized.

Copy link
Contributor

commented Apr 16, 2016

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

This comment has been minimized.

Copy link
Contributor

commented Apr 16, 2016

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

This comment has been minimized.

Copy link
Member

commented Apr 17, 2016

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

This comment has been minimized.

Copy link
Author

commented Apr 17, 2016

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

This comment has been minimized.

Copy link
Contributor

commented Apr 20, 2016

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

This comment has been minimized.

Copy link
Author

commented Apr 21, 2016

@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

This comment has been minimized.

Copy link
Contributor

commented Apr 21, 2016

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

This comment has been minimized.

Copy link
Member

commented Apr 21, 2016

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

This comment has been minimized.

Copy link
Author

commented Aug 1, 2016

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.

@ExeterDad ExeterDad closed this Aug 1, 2016

@sorcerykid

This comment has been minimized.

Copy link

commented Dec 19, 2017

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

This comment has been minimized.

Copy link

commented Dec 19, 2017

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

This comment has been minimized.

Copy link
Member

commented Dec 20, 2017

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

This comment has been minimized.

Copy link

commented Dec 20, 2017

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

This comment has been minimized.

Copy link

commented Dec 20, 2017

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

This comment has been minimized.

Copy link
Contributor

commented Dec 20, 2017

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

This comment has been minimized.

Copy link

commented Dec 20, 2017

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

This comment has been minimized.

Copy link
Contributor

commented Dec 20, 2017

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

This comment has been minimized.

Copy link
Member

commented Dec 20, 2017

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

This comment has been minimized.

Copy link
Contributor

commented Dec 20, 2017

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

This comment has been minimized.

Copy link

commented Dec 20, 2017

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?

@ThomasMonroe314

This comment has been minimized.

Copy link
Contributor

commented Jan 16, 2018

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

This comment has been minimized.

Copy link

commented Jan 16, 2018

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

This comment has been minimized.

Copy link
Member

commented Jan 16, 2018

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

This comment has been minimized.

Copy link
Contributor

commented Jan 17, 2018

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

This comment has been minimized.

Copy link

commented Jan 17, 2018

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

This comment has been minimized.

Copy link
Contributor

commented Jan 17, 2018

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

This comment has been minimized.

Copy link

commented Jan 17, 2018

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

This comment has been minimized.

Copy link
Contributor

commented Jan 17, 2018

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

This comment has been minimized.

Copy link

commented Jan 17, 2018

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

@sorcerykid

This comment has been minimized.

Copy link

commented Jan 18, 2018

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

This comment has been minimized.

Copy link

commented Jan 18, 2018

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

This comment has been minimized.

Copy link
Member

commented Jan 18, 2018

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

This comment has been minimized.

Copy link
Contributor

commented Jan 18, 2018

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:

collisions

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

This comment has been minimized.

Copy link

commented Jan 19, 2018

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

This comment has been minimized.

Copy link
Contributor

commented Jan 19, 2018

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

This comment has been minimized.

Copy link
Contributor

commented Jan 19, 2018

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

This comment has been minimized.

Copy link
Contributor

commented Jan 19, 2018

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

This comment has been minimized.

Copy link
Contributor

commented Jan 19, 2018

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

@stujones11

This comment has been minimized.

Copy link
Contributor

commented Jan 19, 2018

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

This comment has been minimized.

Copy link
Contributor

commented Jan 20, 2018

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

1 similar comment
@ThomasMonroe314

This comment has been minimized.

Copy link
Contributor

commented Jan 20, 2018

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

This comment has been minimized.

Copy link
Member

commented May 4, 2018

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.