2

だから私は Bejeweled にメカニズムが似ているゲームに取り組んでいます - あなたは同じタイプのタイルのグループを一緒に一致させるためにグリッド内の隣接するタイルを交換するタイプを知っています. ここで私の質問です: タイルの MxM グリッドがあり、N 個の異なるタイル タイプがある場合、3 つの同じタイプのタイルのグループの数が最小化されるようにタイルの「ランダムな」配置を計算するにはどうすればよいですか?

現時点では、完全にランダムに配置していますが、これにより最初から多くのグループが作成され、ゲームからすべてのスキルが削除されます。これらの初期グループを最小化するためのアルゴリズムをどこから考え始めればよいかさえわかりません。それが助けになるか重要な場合は、現在、10x10 グリッドに具体的に 5 種類のタイルがあります。

4

2 に答える 2

0

私が考えることができる最も簡単なアプローチ：

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

そして、これを行うための最適化されていない方法は、水平方向と垂直方向の一致のみを想定しています (対角線ではありません): (疑似コード)

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]))

繰り返し生成を完全に回避する方法: (型が数値であると仮定)

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

上記の方法は、範囲 [0,A-1] および [A+1,B] の数値を生成するのと同様に機能し、範囲 [0,B-1] の数値を生成し、生成された数値が A 以上の場合、それを 1 増やします。

N少なくとも 3 である必要があります。そうでない場合は、次のようになります。

..A
..A
BB?

上記のアルゴリズムは無限ループに陥ります。

于 2013-10-12T22:55:43.550 に答える
0

2 つの観察:

  • タイルの数は非常に少ないため、アルゴリズムはそれほど効率的である必要はありません
  • 最初のシーケンスは「完全に」グループ化を解除する必要はないので、問題を解決する必要はありませんが、ベストエフォートでアプローチするだけです

これは、あなたにとって「十分に良い」かもしれない簡単なアルゴリズムにつながります。

  • 空のボードとすべてのタイルのリスト (配列など) から始めます
  • リストをシャッフルする
  • 簡単なルールに従って、ボード上にリスト要素を次々と配置します。
    • 現在のタイルのまだ可能な位置のリストを作成します。すべての位置は 1 ポイントから始まります
    • 同じ色の斜めに隣接するタイルごとに、位置ポイントに N を掛けます
    • 同じ色の直接隣接するタイルごとに、位置ポイントを M で乗算します (M>N)
    • 最低点で位置を見つける
    • これが一意でない場合は、中心からの距離が最も短い位置を使用します
    • それでも一意でない場合は、ランダムに選択します
于 2013-10-12T22:56:42.317 に答える