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.)
Answer
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.
Curved letters
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.
Mismatches
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 and overlaps
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.
Unpredictably adventurous players
A player might draw something weird that still passes.
Although you could call that a feature! :)
No comments:
Post a Comment