Блог

Главная - Вопросы по программированию - Алгоритм подсчета шашек с несколькими переходами

Алгоритм подсчета шашек с несколькими переходами

#c #algorithm #logic

#c #алгоритм #Логические

Вопрос:

Я делаю свой первый проект на C в SFML — Checkers. К сожалению, я застрял на изобретении рекурсивной функции, которая позволила бы мне проверять все возможные комбинации прыжков и которая вернула бы мне координаты.

Как я могу это сделать? Я просмотрел множество веб-страниц, не нашел ответа, поэтому я предполагаю, что это проще, чем я думаю.

ПРАВКА # 1:

 if (player2.isSelected(pos_x   blockSize, pos_y   blockSize))
    if (isBoardBlockEmpty(pos_x   2 * blockSize, pos_y   2 * blockSize))
        return true;
if (player2.isSelected(pos_x - blockSize, pos_y   blockSize))
    if (isBoardBlockEmpty(pos_x - 2 * blockSize, pos_y   2 * blockSize))
        return true;
if (player2.isSelected(pos_x   blockSize, pos_y - blockSize))
    if (isBoardBlockEmpty(pos_x   2 * blockSize, pos_y - 2 * blockSize))
        return true;
if (player2.isSelected(pos_x - blockSize, pos_y - blockSize))
    if (isBoardBlockEmpty(pos_x - 2 * blockSize, pos_y - 2 * blockSize))
        return true;

Комментарии:

1. У вас уже есть код для одного перехода?

2. @NicoSchertler Конечно, он проверяет, равна ли позиция выбранной пешки 1 блок пешке противника и свободна ли позиция пешки 2 (одинаковый код для каждого направления). (Я отредактирую основной пост и вставлю его туда)

3. Одним из способов продолжения было бы добавить состояние доски в качестве аргумента к этой функции. Затем измените состояние на основе исследуемого вами прыжка (удалите противника, измените положение собственной фигуры) и повторите рекурсивную проверку с целевой позиции.

Ответ №1:

Это пример задачи поиска по дереву, где узлами являются доски, а ребрами между ними — конкретная пешка, выполняющая по одному прыжку за раз.

Для данной доски board и пешки на позиции pos вы определяете, какие прыжки она может совершать:

  • Если переходы невозможны, последовательность с несколькими переходами заканчивается. Если текущий список переходов не был пустым, сообщите об этом в виде последовательности.
  • Если возможны прыжки, исследуйте каждый из них рекурсивно, совершая прыжок (удаляя перепрыгнувшую пешку с доски) и проверяя, сможете ли вы совершить больше прыжков с этой позиции.

На псевдо-C это выглядело бы следующим образом. Обратите внимание, что это написано в образовательных целях, без учета производительности. 

 // Assuming types pos and board were defined earlier.
using jump_list = std::vector<pos>;

// List of moves from a given starting position and board
std::vector<pos> possible_jumps(pos start, const boardamp; board);

// Apply a move (remove the pawn from the board, move the jumping pawn)
board apply_move(const boardamp; board, pos start, pos move);

// I'm bundling the multi-jump calculation in a struct to easily store
// the resulting jump list.
struct multi_jump {
    std::vector<jump_list> jumps;
    multi_jump(pos start, board board) {
        explore({}, start, board);
    }

    void explore(jump_list so_far, pos start, board board) {
        auto moves = possible_jumps(start, board);
        if (moves.empty()) {
            if (!so_far.empty()) {
                jumps.push_back(so_far);
            }
        } else {
            for (const auto move : moves) {
                board new_board = apply_move(board, start, move);
                jump_list new_so_far = so_far;
                new_so_far.push_back(move);
                explore(new_so_far, move, new_board);
            }
        }
    }
};

Наконец, вы можете получить список прыжков из начальной позиции и доски следующим образом:

 jump_list jumps = multi_jump(start, board).jumps;