0
\$\begingroup\$

How can I check if a player has traced a closed vector shape from an arbitrary starting point all the way around to the beginning?

The path vector points A through E and the starting point P1.

Setup

Given are the vector points A through E, which form a closed path. The created shape can be convex or concave and even have sharp elongated corners. P1 is the point where the player decides to start tracing. The point can be anywhere on the path and will be set as soon as the mouse or touch is first close to the path.

Requirements

The player starts moving along a visual representation and traces the entire shape until he reaches P1 again. If his mouse path differs too greatly, misses a point or goes outside of a given margin, I want to start over. The player may either have to trace around in the direction from which he first starts without backtracking or just have to fill the entire path even if going back and forth on the path.

How can I approach this problem? Ideally, I would like to implement a vector-math solution. I don't have any pixel data to sample from and it would be rather cumbersome in my real world implementation to generate a suitable image and map world space coordinates to it.

My Attempt

  • Consider each corner a waypoint with a collision area.
  • Track each entered collider and when all were hit, solve.
  • While valid colliders are pending, project mouse position onto the closest point on the path.
  • If the distance between projected point and mouse is too great, abort.

This approach however doesn't give me perfect results. Firstly, it's not entirely what I want, since in my ideal case the user "draws" or traces the path with the mouse, not just hits the corners. Also, when moving around a sharp corner, the project point will snap from one line segment to the next, giving me ugly visuals, when showing progress.

Possibly Better Solution

  • As soon as player comes close to path start sampling points from mouse.
  • Build up a user drawn vector path every time step or distance step.
  • Check if the draw vectors are similar to the given path.
  • Problem: user drawn path needs some sort of processing or more complex algorithm until it is comparable to given path.

Thank you for any suggestions! I will post some of my own code as soon as my implementation gives me good results.

\$\endgroup\$
  • \$\begingroup\$ You should get the mouse's position every x milliseconds, create a path out of them, simplify it (e.g. if the difference between the angles of lines next to each other is less than 5 degrees, you merge them), then loop through the points of the original path, find the closest point in the new path each time, and if it' too far away, then the paths don't match up. \$\endgroup\$ – Bálint Jan 7 '17 at 0:50
1
\$\begingroup\$

Maybe something like the p$ algorithm for gesture recognition would serve your purpose? Just remove the normalizing from the gesture comparison so it cares what size your gesture is. http://depts.washington.edu/madlab/proj/dollar/pdollar.html

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.