Algorithm for Block-Matching Game Placement

Question

So I'm working on a game that's similar in mechanics to Bejeweled--you know the type, where you swap adjacent tiles in a grid to match groups of same-type tiles together. So here's my question: if I have an MxM grid of tiles, and there are N different tile types, how do I calculate a "random" placement of tiles such that the number of groups of 3 same-type tiles starts out minimized?

At the moment, I'm just completely randomly placing them, but this results in many groupings from the start, which removes all skill from the game. I don't even know where to begin coming up with an algorithm to minimize those initial groups. If it helps or matters, right now there are specifically 5 tile types in a 10x10 grid.

Answer 1

The simplest approach I can think of:

for each tile
  based on the surrounding already generated tiles,
    generate a random type among those which won't result in 3-in-a-row

And an unoptimized way to do this, assuming just horizontal and vertical matches (not diagonal): (pseudo-code)

for x = 1 to M
for y = 1 to M
  do
    board[x][y] = randomType()
  while ((x >= 3 && board[x-1][y] == board[x-2][y] && board[x-1][y] == board[x][y]) ||
         (y >= 3 && board[x][y-1] == board[x][y-2] && board[x][y-1] == board[x][y]))

A way to avoid the repeated generation completely: (assuming types are numbers)

for x = 1 to M
for y = 1 to M
  limit = N
  horizontal = (x >= 3 && board[x-1][y] == board[x-2][y] && board[x-1][y] == board[x][y])
  vertical   = (y >= 3 && board[x][y-1] == board[x][y-2] && board[x][y-1] == board[x][y])
  if horizontal
    limit--
  if vertical
    limit--
  board[x][y] = randomType(limit)
  offset = 0
  if (vertical && board[x][y] >= board[x][y-1])
    offset++
  if (horizontal && board[x][y] >= board[x-1][y])
    offset++

  board[x][y] += offset

The above method works similar to generating numbers in the ranges [0,A-1] and [A+1,B] by generating numbers in the range [0,B-1] and then, if the generated number is A or greater, we increase it by 1.

N needs to be at least 3, otherwise you may get something like:

..A
..A
BB?

For which the above algorithm will run into an infinite loop.

Answer 2

Two observations:

• The number of tiles is very small, so our algorithm needn't be very efficient
• Initial sequence need not be "perfectly" ungrouped, so we needn't solve the problem, but just best-effort approach it

This leads to a trivial algorithm, that could be "good enough" for you:

• Start with an empty board and a list (e.g. array) of all tiles
• Shuffle the list
• Place one list element after the other on the board, following simple rules:
• • Make a list for the still possible positions for the current tile, every position starts with 1 point
• • For every diagonally neighbouring tile of the same color multiply position points by N
• • for every directly neighbouring tile of same color multiply position points by M (M>N)
• • Find position with lowest points
• • If this is not unique use the position with the lowest distance from the center
• • If this is still not unique, chose randomly