Game Development Stack Exchange is a question and answer site for professional and independent game developers. It only takes a minute to sign up.
Sign up to join this community
I want to draw an invisible path that the user must follow. I've stored that path as points. When a player draws a line, how can I test if it follows the path I've stored?
Here's an example for tracing the letter A.
if((traitSprite.getX()<=Invisible.X && traitSprite.getX()>=Invisible.X )){...}
(traitSprite is a sprite.)
Here's a vector-based solution. I haven't tried it, but it seems fine conceptually.
I gather you've stored the shape as line segments. Here's the letter A represented with three line segments.
I've assumed that paths in the user's drawing are stored as lists of points.
We can "inflate" those line segments to allow an error margin when checking for nearness: whether the user's drawn path is near the correct lines error margin.
However, that alone is not enough. We also have to check for coverage: whether the user's drawing "covers" a large fraction of the shape. These drawings are bad, because even though they fit within the error margin, they're missing some part of the letter:
If we check both of those things, we can approximate if the player's drawing is good.
Checking nearness just means for each user path point, finding the distance between that and every line making up the letter, taking the lowest and checking it's less than the error margin.
Checking coverage is more complicated, but you can get a very good approximation with vector math if for each line segment, you find the nearest user-drawn path (green) and project its parts (dark green) onto that line segment (black), then check for how well the projected vectors (blue) cover it:
To project a vector a onto another vector b, do
projection = dotProduct(a, b) / lengthSquared(b) * b
where dotProduct computes the dot product of the two vectors and lengthSquared is what it sounds like. Essentially, this finds the scalar value of how much a goes in b's direction and multiplies b by that to get a vector in the same direction. (Metanet Software's collision detection tutorial A has a nice visualisation of this in Appendix A § projection.)
The direction of the projected vector might not actually be important. If you just sum together the lengths of the projected vectors and compare them to the total length of the line segment, that will tell you what fraction of it is covered. (Except in odd cases—see §Limitations below).
In the above image, the path would cover about half of the segment. You could pick any tolerance value you want.
Line segments are sub-ideal: Many letters are curved! How do you represent a ‘P’ or an ‘O’?
You could use many line segments (maybe with a larger error margin).
You also could start using Bézier curves instead of lines for a closer fit, but note that finding the closest point on a Bézier is much more complex—as are many other measurement operations.
Overly relaxed tolerance margins for distance from the lines and coverage of the letter could have unintended consequences.
For example, the player might have been trying to draw an ‘H’ here.
Loops or overlaps in the player-drawn path could result in some parts of the drawing being counted twice when projecting them onto the nearest line segment.
This could be worked around by doing fancier processing on the projected vectors, perhaps storing exactly where the projected vector would be (store the direction of the projection too, and the closest point on the line segment to the point on the player-drawn line), then rejecting new ones that overlap it.
If the player drew a single path and it was processed starting at the end marked with the blue circle, the green parts of that path would be accepted and the red ones rejected, because their projection would overlap with some parts processed before.
The implementation has many technical subtleties that would probably belong in a different question.
A player might draw something weird that still passes.
Although you could call that a feature! :)
tl;dr I suggest making the players' brush paint a visible (or invisible) 2d plane. Diff the users' painted image with the origin (the desired silhouette or 2d model). If you want to increase accuracy then make the guiding lines and brush more narrow, to allow more room for error, make brush and design thicker.
Otherwise, you could measure the distance of each (x, y) the users click / touch on from the spline by calculating point to segment distance. Then you can average the distances to compose a measure of accuracy and efficiency. It will require more work to get a meaningful measure of completion and realize how effectively the user performed.
Consideration: I suggest not doing so (checking directly if a line follows a path). This is possibly a bad idea. It seems you want the user to fill a silhouette. The path itself is a (skeletal) spline representing the silhouette.
If you simply make the players' brush apply a pulpy monochrome mass of pixel to the 2d plane, you can run a process in the background that checks how many pixels are inside the silhouette and how many of them are outside. This can easily result in % of success, where how much % of the pattern is filled is one statistics of interest and another is how much % is outside the borders of the model. If you check for sub-segment distances it's not very clear of accurate the users' work is.
The best solution not use graphics at all, do it with math!
You can easy understand how much every point (user painted) far from segment https://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment
That you can calculate average error, so measure how much user is correct.
