Algorithm for 'Pogo Painter' minigame

Question

I am working on a minigame called 'Pogo Painter', and I need some mathematical solutions. Below is an image (made with Paint) to illustrate a bit what it's all about.

Four players, each of different color, must claim squares to gain points. The minigame will be similar to this: http://www.youtube.com/watch?v=rKCQfAlaRrc, but slightly different. The players will be allowed to run around the playground and claim any of the squares, and points are gathered when a pattern is closed. For example, claiming blue square on A3 will create a closed blue pattern.

enter image description here

What kind of variables should I declare and how do I check if the pattern is closed?

Please answer if you have a solution :)

Too generic question! What's the code language? How have you built the basic structure? You have to build classes, you cannot have an answer in this way — Alessandro, Jun 25 '13 at 13:30
It's actually a scripting language http://en.wikipedia.org/wiki/Pawn_(scripting_language), and it does not have classes nor constructors. — Stybos, Jun 25 '13 at 13:34
I have declared squares in arrays like so: square[9][9], is there a better way? — Stybos, Jun 25 '13 at 13:36
@Stybos: What would make this problem difficult is if you wanted to exclude patterns that don't surround tiles, for example, those listed at the end of both aec's and Rom's answers (e.g. 4 tiles tiles that form a square). So, do you want to include, or exclude these patterns?? — tom10, Jul 01 '13 at 16:39
@tom10 Currently they're included. I have considered different possible occasions how cycles could be formed, and having them excluded would make it too complicated for me. I've made it simple; the more tiles you have in your cycle, the bigger is the multiplier. — Stybos, Jul 01 '13 at 21:57

score 2 · Answer 1 · edited May 23 '17 at 12:07

Here’s another (Discrete Optimization) way to model your problem.

Notation

View your grid as a ‘graph’ with n^2 nodes, and edges of length 1 (Edges connect two neighboring nodes.) Let the nodes be numbered 1:n^2. (For ease of notation, you can use a double array (x,y) to denote each node if you prefer.)

Decision Variables

There are k colors, one for each player (1 through 4). 0 is an unclaimed cell (white)

X_ik = 1 if player k has claimed node i.  0 otherwise.

To start out

X_i0 = 1 for all nodes i.

All nodes start out as white (0).

Neighboring sets: Two nodes i and j are ‘neighbors’ if they are adjacent to each other. (Any given node i can have at most 4 neighbors: Up down right and left.)

Edge variables: We can now define a new set of edge variables Y_ijk that connect two adjacent nodes (i and j) with a common color k.

Y_ijk = 1 if neighboring nodes i and j are both of color k. 0 Otherwise.
(That is, X_ik = X_jk) for non-zero k.

We now have an undirected graph. Checking for ‘closed patterns’ is the same as detecting cycles.

Detecting Cycles:

A simple DFS search will do, since we have undirected cycles. Start with each colored node i, and check for cycles. If a path leads you back to a visited node, cycles exist. You can award points accordingly.

Finally, one suggestion as you design the game. You can reward points according to the “longest cycle” you detect. The shortest cycle gets 4 points, one point for each edge (or one point for each node in the cycle) whichever works best for you.

1 1
1 1    scores 4 points

1 1 1
1 1 1 scores 6 points

1 1 1
1 1 1
1 1    scores 8 points

Hope that helps.

Thank you very much, especially for the 'A simple DFS' link :) Helped me out a lot, as I'm still in process of adding features and fixing minor bugs. — Stybos, Jun 26 '13 at 09:49
+1: for identifying this as a standard "closed cycle" detection problem (at least pending further clarification from the OP). — tom10, Jul 01 '13 at 16:42

score 0 · Accepted Answer · edited Jun 25 '13 at 16:07

Okay,
This is plenty of text, but it's simple.

An N-by-N square will satisfy as the game-board.

Each time a player claims a square,
- If the square is not attached to any square of that player, then you must give that square a unique ID.
- If the square is attached,
  - Count how many neighbours of each ID it has. ( See the demos I put below, to see what this means)
  - For each group
    - patterns_count += group_size - 1
  - If the number of groups is more than 1
    - Change the ID of that group as well as every other square connected to it so they all share the same ID

You must remember which IDs belong to which players.

This is what you have in your example

1 1 1 0 0 0 0 2 2
1 0 0 0 1 3 3 0 0
1 1 0 0 3 3 0 0 0
0 1 0 0 4 5 0 0 0
0 0 0 6 4 0 0 0 0
7 7 0 0 0 0 8 8 8 
0 7 7 0 9 8 8 0 8
A A 7 0 9 8 0 0 8
A 0 7 0 0 0 8 8 8

And this is what it would turn out like after blue grabs A-3

1 1 1 0 0 0 0 2 2
1 0 0 0 1 3 3 0 0
1 1 0 0 3 3 0 0 0
0 1 0 0 4 5 0 0 0
0 0 0 6 4 0 0 0 0
7 7 0 0 0 0 8 8 8 
0 7 7 0 9 8 8 0 8
A A 7 0 9 8 0 0 8
A 0 7 0 0 8 8 8 8

More examples of the algorithm in use

1 1 1 0
1 0 1 0 
1 1   0
0 0 0 0
  2 neighbours. 2x'1'
  1x closed pattern.
1 1 1 0 
1 0 1 0
1 1 1 0
0 0 0 0

--

1 1 1 0 0
1 0 1 0 0
1 1   0 0
1 0 1 0 0
1 1 1 0 0
  3 neighbours: 3x'1'
  2x closed patterns
1 1 1 0 0
1 0 1 0 0
1 1 1 0 0
1 0 1 0 0
1 1 1 0 0

--

1 1 1 0 0
1 0 1 0 0
1 1   2 2
0 0 2 0 2
0 0 2 2 2
  4 neighbours: 2x'1', 2x'2'
  2 Closed patterns
1 1 1 0 0
1 0 1 0 0
1 1 1 1 1
0 0 1 0 1
0 0 1 1 1

But I also consider these a closed pattern. You haven't given any description as to what should be considered one and what shouldn't be.

Thanks for all your time, friend :) In fact, I had a very similar algorithm on my mind, but every time I tried make something out of it, I ended up having to start all over again. This has really helped me out! To comment on the ending part of your post: That's a small puzzle I yet have to figure. — Stybos, Jun 25 '13 at 17:00
@Stybos well, accept it then, so people don't see it popping up in their 'unanswered' list. — , Jun 25 '13 at 17:05
@Stybos The next big thing since **Angry Birds** already in the making huh? I'm glad you got it working. You're welcome, and have fun, mate. — , Jun 25 '13 at 20:26

Algorithm for 'Pogo Painter' minigame

2 Answers2