2
\$\begingroup\$

I currently working on a small mobile game. Not a clone of TwoDots(!) but I need to recognize patterns like they do and I use the game as an example. How the game works? Players have to connect dots. Players can only connect a dot to its direct neighbor in the grid. So the next dot has to be left, right, above or below. Dots can only be added once to a sequence. Connecting a dot to one that is already part of the sequence closes the sequence.

See here http://youtu.be/8RDm6wQ9QbM?t=1m41s (just the next 20 seconds)

What I want to know is when a player connects dots, are there any enclosed dots?

Patterns

My idea was to store the players touch directions (next to the dots and their position in the grid). For the blue square this would mean {1,2,3,4} if you start from the bottom left and connect counterclockwise. Then I could simply check the number of directions in the array (=4). From my grid I know that the start-dot is [3|3] and the end-dot is also [3|3]. This means it has to be a square and there is nothing enclosed because it is the smallest possible rectangle/square.

The problem starts with bigger squares e.g. the purple one. Starting from the bottom left and connect counterclockwise again there would be the following sequence {1,1,1,2,2,2,3,3,3,4,4,4}. How do I know that this is a square/rectangle or some strange stuff and furthermore how do I know if there are any dots inside?

I can count all directions (3x1, 3x2, 3x3, 3x4) and see that all directions appear 3 times. It has 12 directions. 12 is divisible by 4 so it could be a square. But sadly 12 directions doesn't have to be a square nor a rectangle because [1,2,1,2,1,2,3,3,3,4,4,4] would also close the pattern with the the same amount for each direction.

Well... the green one really makes my brain hurt. Green is definitely not a rectangle nor a square. I know that there might be any dots enclosed because there are more than 4 directions stored in the array and the start- and end-dot are the same but how do I get the three question marks? Same goes for the blue dots which are enclosed by the purple square.

I am totally lost here and I think... or better I hope I am overthinking/missing something here.

Thanks for your help! proudcastle

Some Possible Squares:
4x OO |8x OOO |12x OOOO |16x OOOOO |20x... 24x... etc.
   OO |   O?O |    O??O |    O???O |
      |   OOO |    O??O |    O???O |
      |       |    OOOO |    O???O |
                        |    OOOOO |

Some Non-Square Rectangles:
6x OOO OO |8x OOO OOOO OO |10x OOOO OOOOO OO |12x OOOOO OOOOOO OO etc.
   OOO OO |   O?O OOOO OO |    O??O OOOOO OO |    O???O OOOOOO OO
       OO |   OOO      OO |    OOOO       OO |    OOOOO        OO
          |            OO |               OO |                 OO
                          |               OO |                 OO
                                             |                 OO

Some Strange Stuff
10x OOOOO   OOO  OOOO  OO   OOOO |12x  OOOOO  OOOO   ...
      O?O  OO?O  O?OO  OO   OOOO |     O??OO  O??OO  
      OOO  OOOO  OOO   OOO   OO  |     OOOO   OOOOO  
                       OOO       |              
\$\endgroup\$
  • 1
    \$\begingroup\$ Okay. Solved it. I just draw a polygon and check if the dots are inside that polygon. I knew there has to be an easy way. \$\endgroup\$ – Proudcastle Mar 11 '15 at 0:03
1
\$\begingroup\$

Here is an easy way to detect any figures that have intersections or are "closed":

  1. You know the list of dots that are used in the selection with their coordinates (from first selected dot to last) e.g.: (1,1) (2,1) (3,1), (3,2), (4,2) ...

  2. If your list has two identical coordinates - you obviously have intersection

  3. Profit!

This is usable for the kind of figures that are formed from two dots:

two dots intersections

\$\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.