My attempt at Hit Detection... is it Efficient?

[dizzykiwi3]

So I've been messing around with love for about a year now and I'm loving it! I use the forums all the time but this is my first post.

Anyway, I was playing around with methods of hit detection, and my current model goes something like this-

Because, if a person is moving at say 100 pixels per frame and their own width is only 20 pixels, then there's an eighty pixel range wherein they can miss detecting something.

So to combat this I've made a box that is a hexagon that stretches from the corner of one to the other taking into account the change in horizontal and vertical velocity. It's probably most simply explained with a picture so here's what it looks like



The red corner is where the person will be next based on their h and v velocity, the green corner is their current location, and the white lines connect the two, as the inside corners are unnecessary.

So I test for contact with any of those lines and if something is inside it. In this case the thing hitting it in question would be a line over the blue thing coming out of the gray character. So I take the line and cycle it through every entity (mobs, breakable objects, the other player) to see if it should do something to it.

My basic question is: is this efficient? Right now with just two entities in play the detection could be super inefficient and I wouldn't know it. Is there some thing that every game dev knows to implement hit detection super easily that would save me the trouble now of learning it later?

I've heard people mention ray hit detection? But I don't know what that is.

[Reenen]

There are already collision libraries available for Love... Tip 1 is just that the term is "collision" more than Hit Detection.

My first google search got https://github.com/vrld/HardonCollider, but you're welcome to search for others. No idea how optimized that one is.

Also.. viewtopic.php?f=5&t=79223.

[ivan]

My basic question is: is this efficient? Right now with just two entities in play the detection could be super inefficient and I wouldn't know it. Is there some thing that every game dev knows to implement hit detection super easily that would save me the trouble now of learning it later?

I think you are referring to "continuous" collision detection.
It's generally slower, more complicated and often unnecessary compared to non-continuous collision detection.
The easiest approach is:
1. move shape A based on its velocity
2. find all other shapes that intersect with shape A
3. adjust shape A's position so that it's no longer intersecting with these shapes

I've heard people mention ray hit detection? But I don't know what that is.

Ray casting could be used to check the collision of small and fast moving objects (like bullets).
It's often unnecessary since objects in 2d games don't move that fast.
100 pixels per frame means: the object will move across the entire screen in 10-11 frames or 0.176 seconds (assuming your resolution is 1024x768).
Even if you have fast-moving objects you can just update the simulation with a smaller time step.

[dizzykiwi3]

The easiest approach is:
1. move shape A based on its velocity
2. find all other shapes that intersect with shape A
3. adjust shape A's position so that it's no longer intersecting with these shapes

Doesn't that still require checking through the same number of elements (each shape) every update? Or am I missing something?

[kikito]

I've heard people mention ray hit detection? But I don't know what that is.

You can do things a bit easier for yourself (and also faster) with rays, yes. The key thing to know is a mathematical operation called Minkowski Difference.

Imagine two boxes, A & B. A is moving. The minkowsky difference is a transformation you do to A and B.

• A gets smaller and smaller until it collapses to a point
• B gets bigger - his width and height is (old A + old B)
• The boxes are now moved so that A (now a point) is in {0,0}

So now we have a point (in {0,0}) and a box (B'). B' is the Minkowsky difference. It has very nice properties.

For example, if B' contains the point {0,0}, then the two original boxes (A & B) where colliding.

Also, remember that A was moving. A point which moves is a segment. The nice thing is, intersecting a segment with a box is easy and efficient. I used an algorithm called Liang-Barsky for that.

If you intersect the segment with B', you will get two values, t1 & t2 (or none, if the two initial boxes don't intersect). If the intersection happened, both t1 and t2 will be numbers between 0 and 1 - that's the distance along the path A will travel right until it collides with B.

[s-ol]

The easiest approach is:
1. move shape A based on its velocity
2. find all other shapes that intersect with shape A
3. adjust shape A's position so that it's no longer intersecting with these shapes

Doesn't that still require checking through the same number of elements (each shape) every update? Or am I missing something?

Another trick is dividing the world into squares and only checking entities that "both touch at least one the same"... That is awful English... Go look at kikito's bump.lua, it will either be a library you could perfectly use or be a good reference for your code.

[ivan]

Good description by Kikito.
To sum it up, if you have two moving shapes A and B:
1.Continuous collision detection: you want to find the time of impact (like in Kikito's bump)
2.Non-continuous collision detection: you check if the shapes intersect and find the shortest separation vector (like in FizzX)

Regarding the "number of collision checks" then this is another problem altogether called "broadphase collision".
As S0lll0s mentioned, broadphase collision is usually handled with "partitioning".
Some techniques include:
1.Spatial hashing (like in bump and Hardon collider): fast, designed to handle objects with a similar size
2.Quadtree (like in FizzX): slower, handles objects of varying sizes
3.Sweep and prune (example by Roland Yonaba): limits collision checks based on sorting
Generally, partitioning is ONLY useful if you have a lot of moving shapes that should collide with each other.
Most games don't need partitioning at all.
One alternative is to "filter" or only check for sensible collisions pairs:
-player vs bullet
-wall vs bullet
And ignore things like:
-bullet vs bullet