18

さて、私はそれを解決する方法を教えている多くのサイトを見てきましたが、それを作成する方法を考えていました. コーディングの側面にはあまり興味がありませんが、その背後にあるアルゴリズムについてもっと知りたいと思っていました。たとえば、グリッドが 10 個程度の地雷で生成された場合、任意のランダム関数を使用してグリッド全体に分散させますが、それに関連付けられた数値を設定して、どのボックスを開くかを決定するにはどうすればよいでしょうか? どうやってそれを行うかについて、一般的なアルゴリズムを組み立てることができませんでした。

4

3 に答える 3

16

おそらく次の行の何か:

grid = [n,m]   // initialize all cells to 0
for k = 1 to number_of_mines
   get random mine_x and mine_y where grid(mine_x, mine_y) is not a mine
   for x = -1 to 1
      for y = -1 to 1
         if x = 0 and y = 0 then
            grid[mine_x, mine_y] = -number_of_mines  // negative value = mine
         else 
            increment grid[mine_x + x, mine_y + y] by 1

それはかなりそれです...

**編集**

このアルゴリズムは、いくつかの地雷がグループ化されすぎたり、さらに悪いことに非常に分散したボードを作成する可能mine_x性があるため (したがって、解決するのは退屈です)、生成およびmine_y番号付け時に追加の検証を追加できます。たとえば、少なくとも 3 つの隣接するセルが地雷でないことを確認するため、または互いに離れすぎている地雷の数を制限することを好む場合などです。

**更新**

自由に JS bin を少し試してみたところ、機能的なマインスイーパ ゲームのデモができました。これは、この回答で説明されているアルゴリズムを示すためのものです。生成された地雷の位置のランダム性を最適化していないため、一部のゲームは不可能または簡単すぎる可能性があります。また、グリッドにいくつの地雷があるかについての検証がないため、実際には 1000 個の地雷で 2 x 2 のグリッドを作成できます....しかし、それは無限ループにつながるだけです :) お楽しみください!

于 2010-08-26T18:55:42.243 に答える
5

地雷に種をまくだけで、その後、すべてのセルをトラバースし、隣接する地雷を数えます。

または、すべてのカウンターを 0 に設定し、シードされた地雷ごとに、すべての隣接セル カウンターをインクリメントします。

于 2010-08-26T18:52:03.090 に答える
3

m地雷を正方形に配置したい場合N、乱数発生器にアクセスできる場合は、残りの正方形を調べて、各正方形について (残りの地雷数)/(残りの正方形数) を計算し、乱数が次の場合に地雷を配置します。その値以下です。

ここで、隣接する地雷の数ですべての正方形にラベルを付けたい場合は、直接それを行うことができます:

count(x,y) = sum(
  for i = -1 to 1
    for j = -1 to 1
      1 if (x+i,y+j) contains a mine
      0 otherwise
)

または、必要に応じて、ゼロの配列から始めて、中央に地雷がある 3x3 の正方形でそれぞれを 1 ずつ増やします。(地雷のあるマスに番号を付けても問題ありません。)

これにより、純粋にランダムで正しく注釈が付けられたマインスイーパ ゲームが生成されます。ただし、一部のランダム ゲームは楽しいゲームではない場合があります。ランダムだが楽しいゲームを選択することは、はるかに困難な作業です。

于 2010-08-26T19:16:49.680 に答える