Coding challenge: convex shapes

[togFox]

At the start of the game I create a shape that has 8 segments and forms a perfect square:



Love2D requires this to be convex (Box2d):

Creates a new PolygonShape.
This shape can have 8 vertices at most, and must form a convex shape.

As the game proceeds and the player is rewarded, the shape grows by moving one 'point' "outwards", but it must do so without breaking the "convex" rule:





The shape can get quite large and quite complex as the player keeps winning and getting rewarded. Over time, the size of the shape starts to work against the player and that is one of the mechanics of the game.

Here is the challenge:

Assuming a 'point' is the end of one segment and the start of the next segment:

• Starting with the square, each time the player receives a reward, two segments (or one 'point') are moved so that the shape gets larger, i.e. the inside area increases.
• The shape must always be convex
• The 8 'points' of the convex can move according to whatever rules you invent (i.e. along axis or random or whatever)
• Any point can be moved according to described rules
• Assume moving a 'point' is by an arbitrary distance (unless it matters) but for simplicity, assume whole numbers of pixels
• You can assume that moving the end of one segment means moving the start of the segment it joins
• Bonus points if the shape formed is irregular i.e. not a perfect square or rectangle.

What algorithm can I use to move a point in a direction such that it remains convex?

[darkfrei]

What algorithm can I use to move a point in a direction such that it remains convex?

Just keep in the green, cyan or magenta areas.

2022-07-17T14_13_20-Window.png (9.58 KiB) Viewed 2984 times

[togFox]

Thanks.

How would I avoid choosing a corner at the very start and fail instantly? Should I try, fail, then choose another point at random and repeat? It's a 50/50 shot so not a terrible approach.

[Xugro]

Just a small nitpick:

Just keep in the green, cyan or magenta areas.

You cannot move point A into the magenta area, because this would decrease the overall area of the polygon which is against togFoxs first point:

• Starting with the square, each time the player receives a reward, two segments (or one 'point') are moved so that the shape gets larger, i.e. the inside area increases.

Edit:

How would I avoid choosing a corner at the very start and fail instantly? Should I try, fail, then choose another point at random and repeat? It's a 50/50 shot so not a terrible approach.

Should the point to move be chosen by the player or randomly?

[togFox]

Not the player. The algorithm needs to choose a point and then move that line 'outwards' without breaking the rules.

My first problem: deciding which points can legally be moved (the four corners can'tbe moved first)

Then: with a point that can be moved legally, know which direction is a legal move.

I suspect solving step 1 will solve step 2.

[Xugro]

You can just use brute force. This will work within a few attempts (most of the time). I attached a simple example.

[pgimeno]

There are some shapes for which no moves that extend the area and keep the shape convex are possible. What do you plan to do in that case?

[togFox]

You can just use brute force. This will work within a few attempts (most of the time). I attached a simple example.

Nice one. A lot of hypothesising on Discord but this addresses all the criteria. I notice not all segments 'move' - either a bug or your algorithm keeps moving the same three points because that reaches success the fastest?

Edit: I see you used a physics object to calculate mass. Very sneaky. I approve.

There are some shapes for which no moves that extend the area and keep the shape convex are possible. What do you plan to do in that case?

Is this possible? With 8 segments surely there will always be one option?

[pgimeno]

Is this possible? With 8 segments surely there will always be one option?

Well, the minimum shape where that is outright impossible that I can think of has 9 vertices, but I assumed the playfield to be limited, and then yes, it will eventually happen. Maybe that assumption was wrong, but you've been talking about integer coordinates which suggests that.

With 8 vertices there's a shape where you can move just 1 vertex, and once the corner of the playfield is reached, there are no moves. It's also pretty boring, as the game then consists of moving that vertex towards the corner as slowly as possible.

Edit: I was wrong, sorry.

[darkfrei]

Just a small nitpick:

Just keep in the green, cyan or magenta areas.

You cannot move point A into the magenta area, because this would decrease the overall area of the polygon which is against togFoxs first point:

You are right, green area makes area bigger, the magenta area makes is tinier, the line through the point A and parallel to the magenta line don't change the polygon area.

So you can take any random point from the triangle and it will be often near the this not drawn line.