c++ - 宝石をちりばめたゲームのための改善された一致検索アルゴリズムを推奨しますか?

Question

行と列ごとに、3、4、または 5 の一致を見つける賢明な方法を決定しようとしています。プレーヤーはゲーム ボード内の領域 (行または列) を探し、同じ「宝石」が 2 つの隣接するピースを交換した後 (ターンごとに 1 つの交換)、3 ～ 5 の連続するスポットを繰り返します。

マッチメイキングの動きのシナリオの例を次に示します。

• プレイヤーが移動する前のボード (太字はスワップが必要) :

  ACBBC

  DDBAD

  DAACC

  AD BBA

  DCDAA

• プレイヤーの移動後のボード (太字は結果の一致) :

  ACBBC

  DDBAD _

  D AACC

  Dアバ

  DCDAA _

この例では、最初の行の後の最初の列に "D" の 4 つの一致があります。1.) ボードはゲームの開始時に作成され、ボードは即時の一致を排除するために何度もランダム化され、2.) プレーヤーが移動した後、そのような一致を見つける方法を見つけようとしています。正しく動作している場合、プログラム自体またはプレーヤーによって正しいスワップが行われた後、プログラムは一致を検出できます。

私が試みたすべてのアルゴリズムは、ループが範囲外になったり、スワップ後に結果として得られたすべての一致を不適切に見つけたりする原因となりました。これは、現在のスポットがどこにあるかに基づいて配列検索を「調整」する方法をプログラムに伝えることに失敗したため、プログラムが配列の外側を検索しようとする場合があることを意味します。実行時エラーが発生しない場合でも、不適切な結果が表示されます。たとえば、プレイヤーは、ボードに少なくとも 1 つの完全な一致が表示されていることがわかりますが、これは良くありません。

私が試みた2つの手順の説明は次のとおりです。

• 次のスペース。現在のスポットから、同じ行の 4 つのスペース (または、行に残っているスペースが 4 つ未満の場合はそれ以下) を先に確認します。最初に、現在のスポットを含む 5 つの一致を確認します。ない場合は、4 (スポットを引いたもの) をチェックします。ない場合は、3 つ (スポットを引いたもの) を確認します。ない場合は、一致が見つかりません。以下の列についても同じチェックを繰り返します。

• 先行スペース。 現在のスポットから、同じ行にある 4 つのスペース (または、行の最初のスポットと現在のスポットの間に 4 つ未満のスペースがある場合はそれ以下) を確認します。最初に、現在のスポットを含む 5 つの一致を確認します。ない場合は、4 (スポットを引いたもの) をチェックします。ない場合は、3 つ (スポットを引いたもの) を確認します。ない場合は、一致が見つかりません。上記の列についても同じチェックを繰り返します。

これは、そのような作業アルゴリズムが必要な主要な機能です。ここでの Gem クラスの使用 (現在は壊れています) は、要求にとって重要ではない可能性があるため、役に立たない限り追加しません。

bool Board::findMatches(bool scoringMove) // false if board is being setup before game
{
    bool matchesFound = false;

    // loops through entire board, where "size" is the width, not the number of spots
    for (int i = 0; i < size.getSize()*size.getSize(); i++)
    {
        // loops for each type of Gem, six total (_not identical to given example_)
        for (int k = 0; k < gems.getNumGems(); k++)
        {
            Gem traverseGems(k); // next Gem (in sequence)
            char nextGem = traverseGems.getGem(); // next Gem set to a char

            // ROWS check
            // default match search for 3-match
            if ((i < (size.getSize()*size.getSize())-4)
            && (board[i]->getGem() == nextGem)
            && (board[i+1]->getGem() == nextGem)
            && (board[i+2]->getGem() == nextGem))
            {
                // if the player is making a move
                if (!scoringMove)
                    return true;

                matchesFound = true;

                // just adds points to score; irrelevant to algorithm
                scoreMatches(3, 'R', i, 3);

                // no 4-match, but a 3-match
                if (board[i+3]->getGem() != nextGem)
                    scoreMatches(3, 'R', i, 3);
                else
                    scoreMatches(4, 'R', i, 4);

                // 5-match found
                if (board[i+3]->getGem() == nextGem && board[i+4]->getGem() == nextGem)
                    scoreMatches(5, 'R', i, 5);
            }

            // COLUMNS check (comments for rows check apply here as well)

            if ((i <= (size.getSize()-1))
            && (board[i]->getGem() == nextGem)
            && (board[i+size.getSize()]->getGem() == nextGem)
            && (board[i+(size.getSize()*2)]->getGem() == nextGem))
            {
                if (!scoringMove)
                    return true;

                matchesFound = true;

                scoreMatches(3, 'C', i, 3);

                if (board[i+(size*3)]->getGem() != nextGem)
                    scoreMatches(3, 'C', i, 3);
                else
                    scoreMatches(4, 'C', i, 4);
                if (board[i+(size*3)]->getGem() == nextGem && board[i+(size*4)]->getGem() == nextGem)
                    scoreMatches(5, 'C', i, 5);
            }
        }
    }

    return matchesFound;
}

ボード.h

#ifndef BOARD_H
#define BOARD_H

#include "Size.h"
#include "Score.h"
#include "Move.h"
#include "Gem.h"

#include <iostream>
#include <iomanip>
#include <ctime>

class Board
{
private:
    Size size;
    Score score;
    Gem **board;
    bool moreSwaps;

    void swapGems(Move);
    void swapGems(int, int);
    void setNewRandGem(int);
    void findMoreSwaps();
    void scoreMatches(int, char, int, int);
    bool findMatches(bool);

public:
    Board();
    Board(Size, Score&);
    ~Board();
    void displayBoard() const;
    bool isMatch(Move);
    bool moreMovesFound() const;
};

#endif

ボード コンストラクター

Board::Board(Size size, Score &score)
{
    srand((unsigned int)time(NULL)); // I can always move this to main()

    this->size = size;
    this->score = score;

    board = new Gem *[size.getSize()*size.getSize()];

    for (int i = 0; i < size.getSize()*size.getSize(); i++)
        board[i] = new Gem;

    //This is the "pre-game" block.
    //As long as the program finds a new match after performing its
    //own swaps, it'll randomize the entire board and start over again.
    //This is incredibly unefficient, but I will try to fix it later.
    do
    {
        for (int i = 0; i < size.getSize()*size.getSize(); i++)
            setNewRandGem(i);

    } while (findMatches(false));
}