Automatically create hitboxes that are similar to the shape of the object (using a convex hull algorithm)

[tristanbob]

Description

Currently, the hitbox of a sprite matches the size of the image. This does not provide a great user experience, because the sprite may collide with a blank part of the image. To the user, it would appear like hitting an invisible barrier.

Users can manually edit a sprite hitbox into a convex polygon, but it requires time, effort, and skill.

Solution suggested

Provide a way to automatically generate a hitbox for a sprite. This can be done with a convex hull algorithm, like one of these:

Javascript:
https://www.nayuki.io/page/convex-hull-algorithm
https://github.com/aureooms/js-convex-hull-2d
https://github.com/andrewseidl/node-quick-hull-2d
https://github.com/mikolalysenko/monotone-convex-hull-2d

Python: (shows how to go from image to points of convex hull)
https://towardsdatascience.com/convex-hull-an-innovative-approach-to-gift-wrap-your-data-899992881efc

If this works well, it should become the new default hitbox for sprites.

Forum discussion:
https://forum.gdevelop-app.com/t/request-magic-wand/31411

[Silver-Streak]

If something like this were to be implemented, I think we'd want to make sure that it is implemented where the hitboxes are detected then made static before export.

My understanding is that while GMS2 has this option, instead of being created during development and then the shapes exported as static, it has the hitbox constantly be adjusted during gameplay rendering which is heavily performance impacting.

I will also mention that a better alternative to this may be allowing for multiple custom named hitboxes that can be targeted.

• This brings GD5 closer in line to something like Defold, and more closely matches how many modern games are built.
• Having one big polygon for a hitbox seems useful, but in most cases you want "damage" collision to be based off a torso hitbox, movement-impacting collision to only be based off the feet hitbox (ice, slime, etc).
  • These type of hitboxes can be seen in Celeste debug mode as well as Hollow Knight if you see some of their dev discussions, or with Hotline Miami (different head hitbox vs body) as a top down example.

These two ideas are mostly opposing, because having auto-detected convex hitboxes would basically make it so you have one sprite-sized hitbox, vs allowing for multiple specialized hitboxes.

I think we'd probably want @4ian to decide which makes more sense from the engine.

[tristanbob]

If something like this were to be implemented, I think we'd want to make sure that it is implemented where the hitboxes are detected then made static before export.

I agree; I don't see why we would want hitbox dimensions to be updated constantly (other than scale, rotation, and movement).

I will also mention that a better alternative to this may be allowing for multiple custom named hitboxes that can be targeted. ​
These two ideas are mostly opposing, because having auto-detected convex hitboxes would basically make it so you have one sprite-sized hitbox, vs allowing for multiple specialized hitboxes.

I see these two ideas as different use-cases. My idea improves the experience of first-time and beginner game-devs; which is the primary appeal of GDevelop. An automatic convex hull would be a good default hitbox, especially when compared to the size-based rectangular hitbox that is used today.

Your idea is a good one, but it serves a different use-case. Multiple hitboxes will help advanced users implement more complex game mechanics and game feel. It will allow users to keep using GDevelop as their skills improve, rather than hitting a wall and needing to change to Godot or similar.

I think it would be most effective to document your idea in a separate Github issue, to make sure it doesn't get lost.

Cheers!

Tristan

[tristanbob]

After looking into this more, I haven't found a way to go directly from an image to a convex hull (well, maybe this tool). Instead, this will likely need to be done in two steps:

1) Determine the outline of the image (described by non-transparent pixels)

Input:

• Image of sprite

Output:

• Set of points that represent the outline of the image

Potential software tools

• image-outline
  

2) Generate the convex hull

Input:

• Set of points that represent that outline of the image (generated from step 1)
• Desired number of points on convex hull

Output:

• Set of points that represent a convex polygon
• These points can be used as the collision mask for the sprite

Potential software tools

• See the list from the original post.

[willianholtz]

@Silver-Streak and @tristanbob

I don't know if this can help, but...
I was looking at the "magic wand" version of Tiled and found it works fine for this function in GD5

can be found here:
https://github.com/mapeditor/tiled/blob/master/src/tiled/magicwandtool.cpp
https://github.com/mapeditor/tiled/blob/master/src/tiled/magicwandtool.h

[tristanbob]

@willianholtz thanks for looking for solutions to this! From what I can see, the magic wand in Tiled is creating the AABB (smallest rectangle) around the image. That is neat, but I want it to follow the edges of the image while keeping the selection convex (required for fast collision detection).

However, you did give me the idea to start searching for other open source magic wands that might do this... let me know if you find any that do that! :)

[willianholtz]

@tristanbob I was already looking for something on the subject, and I came across these codes, I don't know if they help, but it seems to do as we want.

https://losingfight.com/blog/2007/08/28/how-to-implement-a-magic-wand-tool/
https://stackoverflow.com/questions/30699104/magic-wand-tool-through-javascript

This one caught my attention a lot.
http://jsfiddle.net/Tamersoul/dr7Dw/

[jjhesk]

This is really a good idea. Lets support non-convex physics. We should add this to the card.

[Midhil457]

Not sure if this is still relevent. But, I found an example that coverts image to convex hull with code attached. Though it is in python https://scikit-image.org/docs/stable/auto_examples/edges/plot_convex_hull.html