神魔之塔的演算法研究...

Ref : http://35around.blogspot.tw/2014/07/ui-test-script-for-android-puzzle-and_14.html


接下來是最重要的演算法的部分, 如何設計一個好的演算法來求得傷害最高的路徑, 說真的, 我覺得要想到一個很好的演算法頗困難的, 還好目前的電腦cpu都還蠻強的, 加上其實盤面並不會很大, 只有6*5的大小, 所以在這邊我直接使用BFS方式來求解。實作的方式為: 針對盤面上的每一個珠子, 計算它可以往外前進的八個方向, 每走一步之後就計算目前盤面可以消除區域, 並計算落下之後是否造成下次的消除, 再代入上述的公式, 並且設定一個珠子最多可以走幾步, 最後就我們就可以得到每一個起始珠子走過的路徑的Combo數及攻擊力的權重表格, 透過這個表格我們就可以取到一個攻擊力最高的路徑了, 下面為pseudocode:

for row=1, 5 
    for col=1, 6
        solutions.add(new Solution(cursor(row, col));
while not solutions.isEmpty()
    solution = solutions.pop()
    if solution.depth >= MAX_DEPTH
        continue
    for move=1, 8
        newSolution = moveOrbs(solution, move)
        calculateWeight(newSolution) 

        solutions.add(newSolution) 


這個就是BFS 的演算法.......   這邊有提到是  Ref

https://github.com/kennytm/pndopt

接下來就是  code 的 study



row ->  y
col  ->  x


function evolve_solutions(solutions, weights, dir_step) {
    var new_solutions = [];
    solutions.forEach(function(s) {
        if (s.is_done) {
            return;
        }
        for (var dir = 0; dir < 8; dir += dir_step) {
            if (!can_move_orb_in_solution(s, dir)) {
                continue;
            }
            var solution = copy_solution(s);
            in_place_swap_orb_in_solution(solution, dir);
            in_place_evaluate_solution(solution, weights);
            new_solutions.push(solution);
        }
        s.is_done = true;
    });
    solutions = solutions.concat(new_solutions);
    solutions.sort(function(a, b) { return b.weight - a.weight; });
    return solutions.slice(0, MAX_SOLUTIONS_COUNT);
}

然後   can_move_orb_in_solution 

function can_move_orb_in_solution(solution, dir) {
    // Don't allow going back directly. It's pointless.  把直接退後的solution remove
    if (solution.path[solution.path.length-1] == (dir + 4) % 8) {
        return false;
    }
    return can_move_orb(solution.cursor, dir);
}

然後  can_move_orb() 的定義如下 :

function can_move_orb(rc, dir) {
    switch (dir) {
        case 0: return                    rc.col < COLS-1;
        case 1: return rc.row < ROWS-1 && rc.col < COLS-1;
        case 2: return rc.row < ROWS-1;
        case 3: return rc.row < ROWS-1 && rc.col > 0;
        case 4: return                    rc.col > 0;
        case 5: return rc.row > 0      && rc.col > 0;
        case 6: return rc.row > 0;
        case 7: return rc.row > 0      && rc.col < COLS-1;
    }
    return false;
}

col ->  y
row -> x

0  -> top ,  1 -> right and top ,  2 -> right,  3 -> right and down,  4 -> down
5  ->  left and down,   6 -> left ,     7  ->
           
 7    0    1
 6    p    2
 5    4    3

再來看   in_place_swap_orb_in_solution()

function in_place_swap_orb_in_solution(solution, dir) {
    var res = in_place_swap_orb(solution.board, solution.cursor, dir);
    solution.cursor = res.rc;
    solution.path.push(dir);
}

再來看     in_place_swap_orb()

function in_place_swap_orb(board, rc, dir) {
    var old_rc = copy_rc(rc);
    in_place_move_rc(rc, dir);
    var orig_type = board[old_rc.row][old_rc.col];
    board[old_rc.row][old_rc.col] = board[rc.row][rc.col];
    board[rc.row][rc.col] = orig_type;
    return {board: board, rc: rc};
}
 

function find_matches(board) {
    var match_board = create_empty_board();

    // 1. filter all 3+ consecutives.
    //  (a) horizontals
    for (var i = 0; i < ROWS; ++ i) {
        var prev_1_orb = 'X';
        var prev_2_orb = 'X';
        for (var j = 0; j < COLS; ++ j) {
            var cur_orb = board[i][j];
            if (prev_1_orb == prev_2_orb && prev_2_orb == cur_orb && cur_orb != 'X') {
                match_board[i][j] = cur_orb;
                match_board[i][j-1] = cur_orb;
                match_board[i][j-2] = cur_orb;
            }
            prev_1_orb = prev_2_orb;
            prev_2_orb = cur_orb;
        }
    }
    //  (b) verticals
    for (var j = 0; j < COLS; ++ j) {
        var prev_1_orb = 'X';
        var prev_2_orb = 'X';
        for (var i = 0; i < ROWS; ++ i) {
            var cur_orb = board[i][j];
            if (prev_1_orb == prev_2_orb && prev_2_orb == cur_orb && cur_orb != 'X') {
                match_board[i][j] = cur_orb;
                match_board[i-1][j] = cur_orb;
                match_board[i-2][j] = cur_orb;
            }
            prev_1_orb = prev_2_orb;
            prev_2_orb = cur_orb;
        }
    }

    var scratch_board = copy_board(match_board);

    // 2. enumerate the matches by flood-fill.
    var matches = [];
    for (var i = 0; i < ROWS; ++ i) {
        for (var j = 0; j < COLS; ++ j) {
            var cur_orb = scratch_board[i][j];
            if (typeof(cur_orb) == 'undefined') { continue; }
            var stack = [make_rc(i, j)];
            var count = 0;
            while (stack.length) {
                var n = stack.pop();
                if (scratch_board[n.row][n.col] != cur_orb) { continue; }
                ++ count;
                scratch_board[n.row][n.col] = undefined;
                if (n.row > 0) { stack.push(make_rc(n.row-1, n.col)); }
                if (n.row < ROWS-1) { stack.push(make_rc(n.row+1, n.col)); }
                if (n.col > 0) { stack.push(make_rc(n.row, n.col-1)); }
                if (n.col < COLS-1) { stack.push(make_rc(n.row, n.col+1)); }
            }
            matches.push(make_match(cur_orb, count));
        }
    }

    return {matches: matches, board: match_board};
}

function make_rc(row, col) {
    return {row: row, col: col};
}


function in_place_evaluate_solution(solution, weights) {
    var current_board = copy_board(solution.board);
    var all_matches = [];
    while (true) {
        var matches = find_matches(current_board);
        if (matches.matches.length == 0) {
            break;
        }
        in_place_remove_matches(current_board, matches.board);
        in_place_drop_empty_spaces(current_board);
        all_matches = all_matches.concat(matches.matches);
    }
    solution.weight = compute_weight(all_matches, weights);
    solution.matches = all_matches;
    return current_board;
}


//    rc ->  代表目前的   (x,y)   ,  dir -> 要移動的方向....  這個function 計算出下個點的col,row
function in_place_move_rc(rc, dir) {
    switch (dir) {
        case 0:              rc.col += 1; break;
        case 1: rc.row += 1; rc.col += 1; break;
        case 2: rc.row += 1;              break;
        case 3: rc.row += 1; rc.col -= 1; break;
        case 4:              rc.col -= 1; break;
        case 5: rc.row -= 1; rc.col -= 1; break;
        case 6: rc.row -= 1;              break;
        case 7: rc.row -= 1; rc.col += 1; break;
    }
}


//   update  掉下來的 code
function in_place_drop_empty_spaces(board) {
    for (var j = 0; j < COLS; ++ j) {
        var dest_i = ROWS-1;
        for (var src_i = ROWS-1; src_i >= 0; -- src_i) {
            if (board[src_i][j] != 'X') {
                board[dest_i][j] = board[src_i][j];
                -- dest_i;
            }
        }
        for (; dest_i >= 0; -- dest_i) {
            board[dest_i][j] = 'X';
        }
    }
    return board;
}


舉例  

src       -dest
0 O2
1 O1
2 O0      O2
3 X        O1
4 X        O0

src 從 4 開始  (row-1)
一開始  board[3][0]  為  X,      if (board[src_i][j] != 'X') 不成立

src 變 3
            board[3][0]  為  X,        if (board[src_i][j] != 'X') 不成立

src 變 2
            board[2][0]  為  O0,        if (board[src_i][j] != 'X') 成立

  dest 為 row            
board[dest-i][0] = O0  

依序下去....  就會造成消去的現象


function in_place_remove_matches(board, match_board) {
    for (var i = 0; i < ROWS; ++ i) {
        for (var j = 0; j < COLS; ++ j) {
            if (typeof(match_board[i][j]) != 'undefined') {
                board[i][j] = 'X';  ///  代表可以消去的
            }
        }
    }
    return board;
}

function compute_weight(matches, weights) {

    var total_weight = 0;

    matches.forEach(function(m) {

        var base_weight = weights[m.type][m.count >= 5 ? 'mass' : 'normal'];

        var multi_orb_bonus = (m.count - 3) * MULTI_ORB_BONUS + 1;

        total_weight += multi_orb_bonus * base_weight;

    });

    var combo_bonus = (matches.length - 1) * COMBO_BONUS + 1;

    return total_weight * combo_bonus;

}

 Normal (3+)
 Mass (5+)


當按下  rand 的 button

$('#randomize').click(function() {
        var types = $('#randomization-type').val().split(/,/);
        $('#grid > div').each(function() {
            var index = Math.floor(Math.random() * types.length); //
            show_element_type($(this), types[index]);
        });
        clear_canvas();
    });

 舉例來說....  當你選擇    5 + Heal  ,  randomization-type ->  "0,1,2,3,4,5"  ....

types.length ->  6

<select id="randomization-type">
        <option value="0,1,2">3-color</option>
        <option value="0,1,2,5">3 + Heal</option>
        <option value="0,1,2,3,4">5-color</option>
        <option value="0,1,2,3,4,5" selected="selected">5 + Heal</option>
        <option value="0,1,2,3,4,5,6">All</option>
    </select>

當按下  clear 的按鈕.... 把每個方格填入  'X'  ->  也就是問號....
 
 $('#clear').click(function() {
        $('#grid > div').each(function() { show_element_type($(this), 'X'); });
        clear_canvas();
    });

當按下   drop  按鈕 ....
$('#drop').click(function() {
        var solution = global_solutions[global_index];
        if (!solution) {
            return;
        }
        var board = in_place_evaluate_solution(solution, get_weights());
        show_board(board);
        clear_canvas();
    });


從   global_solution  抓出 solution......  


當按下   solve ...

 $('#solve').click(function() {
        var solver_button = this;
        var board = get_board();
        global_board = board;
        solver_button.disabled = true;
        solve_board(board, function(p, max_p) {
            $('#status').text('Solving (' + p + '/' + max_p + ')...');
        }, function(solutions) {
            var html_array = [];
            solutions = simplify_solutions(solutions);
            global_solutions = solutions;
            solutions.forEach(function(solution) {
                add_solution_as_li(html_array, solution, board);
            });
            $('#solutions > ol').html(html_array.join(''));
            solver_button.disabled = false;
        });
    });


//   給定新的dir...  然後和原本的互換....
function in_place_swap_orb(board, rc, dir) {
    var old_rc = copy_rc(rc);
    in_place_move_rc(rc, dir);
    var orig_type = board[old_rc.row][old_rc.col];
    board[old_rc.row][old_rc.col] = board[rc.row][rc.col];
    board[rc.row][rc.col] = orig_type;
    return {board: board, rc: rc};
}

//    呼叫剛剛   in_place_swap_orb   ...  然後把  dir push 到  path queue裡面....

function in_place_swap_orb_in_solution(solution, dir) {

    var res = in_place_swap_orb(solution.board, solution.cursor, dir);

    solution.cursor = res.rc;

    solution.path.push(dir);

}

function in_place_evaluate_solution(solution, weights) {
    var current_board = copy_board(solution.board);
    var all_matches = [];
    while (true) {
        var matches = find_matches(current_board);
        if (matches.matches.length == 0) {
            break;
        }
        in_place_remove_matches(current_board, matches.board);
        in_place_drop_empty_spaces(current_board);
        all_matches = all_matches.concat(matches.matches);
    }
    solution.weight = compute_weight(all_matches, weights);
    solution.matches = all_matches;
    return current_board;
}


//   遞迴....自己 call 自己
function solve_board_step(solve_state) {
    if (solve_state.p >= solve_state.max_length) {   //  結束條件
        solve_state.finish_callback(solve_state.solutions);
        return;
    }

    ++ solve_state.p;
    solve_state.solutions = evolve_solutions(solve_state.solutions,
                                             solve_state.weights,
                                             solve_state.dir_step);
    solve_state.step_callback(solve_state.p, solve_state.max_length);

    setTimeout(function() { solve_board_step(solve_state); }, 0);
}


//   感覺就是8各方向都去計算出來 score.....然後利用排序找出最佳的方向...
//   然後只留下那個方向....

function evolve_solutions(solutions, weights, dir_step) {
    var new_solutions = [];
    solutions.forEach(function(s) {
        if (s.is_done) {
            return;
        }
        for (var dir = 0; dir < 8; dir += dir_step) {
            if (!can_move_orb_in_solution(s, dir)) {
                continue;
            }
            var solution = copy_solution(s);
            in_place_swap_orb_in_solution(solution, dir);
            in_place_evaluate_solution(solution, weights);
            new_solutions.push(solution);
        }
        s.is_done = true;
    });
    solutions = solutions.concat(new_solutions);
    solutions.sort(function(a, b) { return b.weight - a.weight; });
    return solutions.slice(0, MAX_SOLUTIONS_COUNT);
}