您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> J2ME

SLG 遊戲角色可移動區域搜尋與尋路演算法實作

編輯：J2ME

問題定義

回合制策略遊戲（SLG）中，選中單位後需高亮顯示其可移動範圍（受地形消耗、單位移動力限制），並支援點擊目標格自動尋路。本文提供遞歸 DFS 搜尋可移動區與贪心回溯尋路的輕量實作。

資料結構

byte[][] map：地形碼（草地=1、森林=2、山脈=3...）。
byte[][] moveMap：搜尋過程產生，記錄「到達該格剩餘移動力」，0 表示不可達。
int locomotivity：單位基礎移動力（如 5）。
int getCost(terrain, unitType)：地形消耗函數（騎兵平地 1、森林 2；步兵平地 1、森林 1）。

可移動區域搜尋：遞歸 DFS + 剪枝

/** 
 * @param map 地形圖
 * @param r, c 當前格座標
 * @param loco 到達此格後剩餘移動力
 * @param fromDir 來自方向（避免立即回頭）：1=上,2=下,4=左,8=右
 */
public void scanMovableArea(byte[][] map, int r, int c, int loco, int fromDir) {
    if (loco > moveMap[r][c]) {
        moveMap[r][c] = (byte) loco; // 更新最大剩餘移動力
    } else {
        return; // 無優勢，剪枝
    }

    // 四方向嘗試擴展
    // 向上
    if (fromDir != 2) {
        int cost = getTerrainCost(map, r, c-1);
        if (loco - cost >= 0)
            scanMovableArea(map, r, c-1, loco - cost, 1);
    }
    // 向下
    if (fromDir != 1) {
        int cost = getTerrainCost(map, r, c+1);
        if (loco - cost >= 0)
            scanMovableArea(map, r, c+1, loco - cost, 2);
    }
    // 向左
    if (fromDir != 8) {
        int cost = getTerrainCost(map, r-1, c);
        if (loco - cost >= 0)
            scanMovableArea(map, r-1, c, loco - cost, 4);
    }
    // 向右
    if (fromDir != 4) {
        int cost = getTerrainCost(map, r+1, c);
        if (loco - cost >= 0)
            scanMovableArea(map, r+1, c, loco - cost, 8);
    }
}

// 地形消耗查詢（含邊界檢查）
private int getTerrainCost(byte[][] map, int r, int c) {
    if (r < 0 || c < 0 || r >= map.length || c >= map[0].length)
        return 1000; // 超出邊界視為不可通行
    // 依單位類型與地形碼返回消耗
    switch (map[r][c]) {
        case GRASS: return (unitType == CAVALRY) ? 1 : 1;
        case FOREST: return (unitType == CAVALRY) ? 2 : 1;
        case MOUNTAIN: return 3;
        default: return 1;
    }
}

呼叫方式

// 初始化
moveMap = new byte[mapHeight][mapWidth];
scanMovableArea(map, unitRow, unitCol, unitLocomotivity, 0);

// 繪製高亮：moveMap[r][c] > 0 即可到達
for (int r=0; r 0) drawHighlight(c, r);

尋路：從目標貪心回溯至起點

利用 moveMap 中的「剩餘移動力」單調遞減特性：從目標格出發，尋找鄰格中 moveMap 最大者，必為最短路徑上的前一格。

public Vector findPath(int sr, int sc, int tr, int tc) {
    Vector path = new Vector();
    if (sr == tr && sc == tc) {
        path.addElement(new short[]{(short)tr, (short)tc});
        return path;
    }
    // 取四鄰格剩餘移動力
    byte up    = (tr > 0)     ? moveMap[tr-1][tc] : 0;
    byte down  = (tr < mapH-1) ? moveMap[tr+1][tc] : 0;
    byte left  = (tc > 0)     ? moveMap[tr][tc-1] : 0;
    byte right = (tc < mapW-1) ? moveMap[tr][tc+1] : 0;

    byte max = (byte) Math.max(Math.max(up, down), Math.max(left, right));
    int pr = tr, pc = tc;
    if (max == up)    { pr = tr-1; pc = tc; }
    else if (max == down) { pr = tr+1; pc = tc; }
    else if (max == left) { pr = tr; pc = tc-1; }
    else if (max == right){ pr = tr; pc = tc+1; }

    Vector sub = findPath(sr, sc, pr, pc);
    sub.addElement(new short[]{(short)tr, (short)tc});
    return sub; // 起點→終點順序
}