Java撰寫單詞小游戲

介紹

公司最近有一個競技場專案，里面有一個單詞小游戲，

游戲大概就是隨機生成一個5*5的棋盤，上面有單詞的字母，通過滑動連出正確的單詞，

棋盤生成演算法

思路

首先隨機選個一個起點，從這個點開始鋪單詞，

分別選取上下左右四個方向作為下一個字母的擺放位置，不能觸邊也不能走重復路，直到平鋪完所有的單詞，

如果在棋盤能平鋪下單詞的情況下，找不到路徑，就從四個角作為起點，必能找到路徑，

代碼

import java.util.*;

/**
 * @author Wang Guolong
 * @version 1.0
 * @date 2020/7/31 5:50 下午
 */
public class GenerateWordBoard {

    private static char[][] board;

    public static void main(String[] args) {
        GenerateWordBoard g = new GenerateWordBoard();
        g.generateCharBoard("vocabulary", 5, 5);
    }

    private void generateCharBoard(String word, int m, int n) {
        // 單詞為空 直接回傳
        if (word.isEmpty()) {
            return;
        }
        // 單詞長度大于棋盤 鋪不下 直接回傳
        if (word.length() > m * n) {
            return;
        }
        // 初始化棋盤 全為*
        initBoard(m, n);

        char[] wordChar = word.toCharArray();
        // 隨機選取一個位置開始
        Random random = new Random();
        int randomX = random.nextInt(m);
        int randomY = random.nextInt(n);
        // 開始從隨機位置dfs鋪單詞 從index 0 開始
        boolean result = generateDfs(board, wordChar, randomX, randomY, 0);
        // 如果沒有找到路線 那么從四個角開始 必能找到一條路
        if (!result) {
            List<int[]> starts = Arrays.asList(new int[]{0, 0}, new int[]{0, n - 1}, new int[]{m - 1, 0},
                    new int[]{m - 1, n - 1});
            // 隨機四個角的一個
            Collections.shuffle(starts);
            // 初始化棋盤
            initBoard(m, n);
            // dfs鋪單詞
            generateDfs(board, wordChar, starts.get(0)[0], starts.get(0)[1], 0);
        }
        // 查看結果
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                System.out.print(board[i][j] + "  ");
            }
            System.out.println();
        }
    }

    private void initBoard(int m, int n) {
        // 初始化
        board = new char[m][n];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j] = '*';
            }
        }
    }

    /**
     * 回傳true則為找到一條路 回傳false為死路
     */
    private boolean generateDfs(char[][] board, char[] wordChar, int i, int j, int index) {
        // 碰到邊 或者碰到已經走過的位置 不能走了 死路
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] == '/') {
            return false;
        }

        // 擺放一個字母
        board[i][j] = wordChar[index];

        //如果已經達到單詞長度則直接回傳 找到一條路
        if (index == wordChar.length - 1) {
            return true;
        }

        // 記錄當前矩陣元素
        char tmp = board[i][j];
        // 修改為/ 表示已經訪問過
        board[i][j] = '/';

        // 向上下左右四個方向開啟遞回
        // 查看能走幾個方向 隨機選擇一個
        List<int[]> directions = Arrays.asList(new int[]{-1, 0}, new int[]{1, 0}, new int[]{0, -1}, new int[]{0, 1});
        Collections.shuffle(directions);

        boolean res = false;
        for (int k = 0; k < directions.size(); k++) {
            int di = i + directions.get(k)[0], dj = j + directions.get(k)[1];
            boolean partialRes = generateDfs(board, wordChar, di, dj, index + 1);
            if (k == 0) {
                res = partialRes;
            } else {
                res = res || partialRes;
            }
            // 如果res為true 說明找到一條路 就不再遍歷了 還原后回傳true
            if (res) {
                // 還原矩陣元素
                board[i][j] = tmp;
                return true;
            }
        }
        // 還原矩陣元素
        board[i][j] = '*';
        return false;
    }
}

運行結果