I'm not sure if this problem has been worked out yet, so I thought I'd better ask here first. Imagine if your position and your enemies position are points on a grid of potentially unlimited size. What I want to do is to take those points, compare them to a list of known shapes and find the closest match. I also want to know how close that match is. So imagine I have a 'Y' shape in my list and the board shows a much larger (or smaller) but perfect 'Y' shape. In that case I'd like it to tell me "This is 100% of a 'Y' shape." On the other hand if the board shows a 'Y' shape, but it has a slight flaw, I'd like it to tell me by how much it differs. So it would tell me something like "This is 75% of a 'Y' shape." Is this problem very difficult to solve? If it has been solved, can anyone point me to the solution?

If the points that form shapes are carefully selected to avoid such confusing patterns as 1 vs l, then rotation and scaling could map a stored set of points onto an observed set.

If the number of troops is known, and the known shapes is made using the same number of points, then it's as easy as comparing each troop to each node in each shape to determine the closest match, and multiplying the closeness ranks to compute an overall closeness rank for the shape. The highest rank is the closest shape.

This wouldn't scale well though, and you would need multiple sets of shapes if the number of troops is variable (which it will be).

I think neural networks are perfectly suited to this problem, I suggest reading a little about them and their pattern recognition abilities.

>I think neural networks are perfectly suited to this problem, I suggest reading a little about them and their pattern recognition abilities.

But can they give you the percentage match. Recognizing the shape is one thing, but I also need to know how close it is to the ideal.

There's been a lot of work on this subject in the fields of computer vision and object recognition. They reduce an object or image to some key feature points and possibly a graph or tree as a skeleton and then try to find a correspondence between the points or graphs. There are lots of ways to try to do this. Once the correspondence is established, rating the quality of the match is a simpler problem, but once again there are many ways this can be done.

Some keywords that might be useful: graph correspondence/matching, pattern matching, skeleton, shape matching/recognition, point correspondence, shock graphs.

It's a tough problem with research going in a lot of different directions.

Then again, you might be trying to do something a lot simpler than this, or a very rough algorithm might work if you only have simple cases to check for.

To check the pattern against the Y shape, you might try to find the optimal way to position the Y over the pattern to get it as close as possible and then measure how closely the pattern matches.

Hmmm... It sounds like a difficult problem. Thanks everyone.

Quote:

Original post by Davaris1 >I think neural networks are perfectly suited to this problem, I suggest reading a little about them and their pattern recognition abilities. But can they give you the percentage match. Recognizing the shape is one thing, but I also need to know how close it is to the ideal.

I think it does. I was talking to a classmate a while ago who was telling me he did digit recognition in a class. I remember him saying specifically that each option ( digits 1-9 ) had a change of being right, you just picked the one with the highest chance.

To help you in your search, this is a pattern matching problem, rather than a pattern recognition problem. Not everyone make the distinction, of course.

If you have no experience in pattern matching, I would strongly advise against trying neural network. Would be like walking into a bog.

Two straigtforward solutions to your problem.

1) As AngleWyrm suggested, scale the data to the model size (or vice-versa), align the principal axis of both shapes (in roation and translation) and then do a sum of square distance of each points to the model. You would be surprised on how well this simple scheme can work.

2) What you want can also be called a correlation. Similar to above, but using imaging techniques. Scale and align the images, perform a correlation (sum of differences).

There are more sophisticated methods, but I would begin by those.

Interesting. :)