# How to find the ideal path done inside a given shape in LibGDX?

I'm trying to make an android/libgdx game in which for every level you have a different shape as a png, and you have to drag your finger inside the shape and try to be as close as the ideal path created after the shape. At the end of the level the game will show you in a percentage how close you were from the ideal path.

My question is how can I find the ideal way that the player has to follow? Is there any function that i can use to find out the array of points created after the shape?

My problem is that the shape width is different along the way, so I can't use the pixels path. I already have an algorithm which gives me the array of points from the path of the player so I have to compare it with the ideal one.

If you have any ideas of any algorithm or functions that can help please let me know. Any answer will be helpful. • By "ideal path" do you mean a curve running along the center of the shape, like a lane divider line running down a road? If not, can you define "ideal" specifically? – DMGregory Aug 17 '17 at 11:07
• @DMGregory yes, this is what i meant – cube888 Aug 17 '17 at 12:00
• Reconstructing this from an arbitrary raster is not exactly trivial. You can start by finding its topological skeleton, but you'll need additional processing steps to prune unimportant offshoots, and resolve intersections into a smooth path. If you're able to store the source vectors for each image you're likely to have an easier time. Or, you could skip vectorizing it and instead convert your image to a distance field, using that ramp to determine how close the touch is to the shape. – DMGregory Aug 17 '17 at 13:00

## 1 Answer

This is much harder than you think. It's extremely difficult. But before you render the shape, you can keep track of the shape that's being drawn in vertices. What I mean by this is, suppose the shape is a triangle. What would happen is you'd keep track of the three coordinate points needed to draw the triangle. Then just calculate the distance from the line at each point the user's finger is on the screen. This'll take some simple formulas and algorithms to calculate the distance from a point and a line. Here's an example of the distance formula.

At rendering time, draw lines from vertex to vertex with a thickness of some. I hope this made sense. because as I'm typing this, it sounds like it's not explaining too much.