drawing comparison algorithm

[Person]

Once for Christmas I received what, to this day, I believe to be one of the best DS games in history. Lost Magic.
http://en.wikipedia.org/wiki/LostMagic

The problem is that Lost Magic has limits, and I do not like limits! So I have decided to make a version of Lost Magic in Löve (I figured out how to make an umlat!)

I will be shamelessly stealing the game's rune drawing mechanic to create this clone but unfortunately, I have no idea how to make an algorithm that will compare two drawings (what the user draws and what the rune actually is) to find the closest match! Does anyone know of a place to look for such algorithms or even an algorithm itself?

[Tenoch]

It's unfortunately a quite complex problem. There are many ways to solve it. I remember reading a very good tutorial on GameDev, but the site is down. It was rather similar to http://www.gskinner.com/blog/assets/GRalgorithm.html.
However, the decision was made by using the cross product of the vector of coordinates with known patterns.
Some use neural networks.

PS: it appears GameDev is back. Article is there: http://www.gamedev.net/reference/articl ... le2039.asp

[Person]

Oh my....... do you hear that sound? That is the sound of my life being sucked into a complex project that will most likely never be finished.... it makes me happy inside

All joking aside, this is good stuff, I thought it was my googling skills that were off but it turns out I was just being very stupid with word choices.... I do think this will take a while to sort out but thanks to love.native I might not actually have to port this or anything!

[Tenoch]

Heh, I know the feeling. Fortunately, experimenting stuff is not time lost.

Be aware though that love.native is a C compiler. The example given was C++. But in this case, I'd try Lua anyway. Some of the stuff in the algorithm may be easier to write, and might run quite fast enough. And love.native is 0.6, and 0.6's ETA is "before the devs die", so you might not want to wait

[Person]

Having already consigned the rest of my life to this project I see no reason why not to port it to Lua. If anyone has input though, I have had an idea. If when drawing the symbol for comparison, the computer only draws a new point after a certain distance (maybe a small one so that no one notices), would that mean I wouldn't need to normalize the points?

[Jasoco]

This looks interesting, I have always wondered how recognition like this worked. Good luck!

Edit: This thread got me in the mood. I've started work on my own recognition code. So far I have a drawing program that only draws points if they're 20 pixels from the previous one, then finds the outer bounds of the shape and calculates the width and height of the shape.

Next I have to figure out how to scale it down or up to a fixed size.

Don't know how far I'll actually get, but it's fun to play around with.

Of course, if this ever gets finished, it'll probably be a gesture recognition system, not a handwriting system for recognizing letters. Just single line shapes. i.e. you draw the shape in one stroke without lifting the pen/mouse button, and as soon as it is lifted, it finishes. As opposed to handwriting which is more complex as letters have more lines to calculate, and most letters are done in more than one stroke. Like a T or an E or an A... lol.. TEA... anyway.. Gesture should be good for a game like that that. Draw a box, or a triangle, or a Z or something that uses one continuous line without backtracking.

[Jasoco]

Okay, I just spent all night on this for no reason at all except to prove that I could do it. And I almost have.



Everything is implemented except for the matching algorithm which I will write tomorrow...

First you draw a shape (In this case a Z) as perfectly as you can. (White line)

It then goes through the plot points and discards points that are close to straight (i.e. it finds straight lines and makes them straighter) while keeping sharp angles. (Purple line) And places these new points in a new Table.

Next it creates a grid. In my case I used a 5x5 grid. (Blue lines)

It then goes through the new (purple) path and A) straightens it even more, then B) finds grid squares with multiple points in them and removes all but one of the points.

By this point we have a pretty close to final shape. As you see in the picture the cyan grid squares are squares where there are points. Even though the matching algorithm isn't in place yet, you notice the Z shape (Cyan line) already matches up perfectly.

All I have to do is write a function that goes through the finalized path and makes sure the grid matches with the grid of a shape in the database.

[Tenoch]

Heh it's getting pretty cool! I see you restricted to rectilign shapes, it makes it easier (but works better too!)

I love geeky all-nighters, they're the best! Just had one too, but it wasn't LÖVE related. Good luck on the pattern matching!

[Jasoco]

Yeah, right now my pattern recognition engine will probably only work best on shapes with 90 or 45 degree angles. I know that LostMagic has patterns with rounds and swirls and stuff, but I'm just making what I can. I'll provide my code when I have a working thing and whoever wants it can have it for their game. If the OP wants it for his LostMagic game, by all means.

Now to get to work.

I guess the pattern matching will just be a matter of going down the list of remaining points and matching them in order to the points on the shapes in the database, and whatever shape has the most correct matches will most likely be the match. I dunno. Lots of testing to do with that.

[Robin]

Well, good luck with the pattern matching, because I expect it to be quite epic. If I were you, I'd check the source of some app or lib that implements Gestures, because I imagine the pattern matching function there to be similar to what you want to do.