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) 這個就是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;
}
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);
}
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);
}
