Skip to content

Instantly share code, notes, and snippets.

@pnlybubbles
Last active September 23, 2015 05:51
Show Gist options
  • Save pnlybubbles/cd3f73989f2feb101579 to your computer and use it in GitHub Desktop.
Save pnlybubbles/cd3f73989f2feb101579 to your computer and use it in GitHub Desktop.
ぷよクエの最適解探索を行うプログラム。ぷよクエのスクショから譜面を自動読み込みする機能も付けた。並列処理対応。まだ分岐を含む斜めの消し方(一度通ったぷよを再び通るなぞり方)には対応していない。
require 'highline'
require 'rmagick'
require 'parallel'
require 'pp'
class ImageAnalize
attr_reader :img
COLOR_MAP = [
nil,
0,
219,
112,
36,
275,
333
]
ERROR = 6
SYMBOL_COLOR_MAP = [
[0.0, 0.0, 60.0, 1.0],
[356.0, 246.0, 162.0, 1.0],
[213.0, 255.0, 162.0, 1.0],
[116.0, 146.0, 149.0, 1.0],
[53.0, 221.0, 147.0, 1.0],
[270.0, 255.0, 182.0, 1.0],
[298.0, 255.0, 187.0, 1.0]
]
def initialize(img_magick)
@img = []
img_magick.each_pixel do |p, x, y|
@img[y] ||= []
@img[y][x] = p
end
end
def size
return @img[0].size, @img.size
end
def to_board
img_size = size()
margins = []
test_max = 100
[0, 1].each { |rl|
margins[rl] = []
test_max.times { |i|
before_luminousity = nil
check_y = (img_size[1] * Rational(i + 1, test_max + 1)).round
(img_size[0] / 10).times { |j|
if rl == 0
check_x = j
elsif rl == 1
check_x = img_size[0] - j
end
current_luminousity = @img[check_y][j].to_hsla[2]
if before_luminousity && (before_luminousity - current_luminousity).abs >= 50
# p [j, before_luminousity, current_luminousity, (before_luminousity - current_luminousity).abs]
margins[rl] << j
break
end
before_luminousity = current_luminousity
}
}
}
margin = []
[0, 1].each { |rl|
margin_freq = {}
margins[rl].each { |v|
margin_freq[v] ||= 0
margin_freq[v] += 1
}
# p margin_freq
max = margin_freq.to_a.sort_by { |v| v[1] }.reverse[0]
if max[1] >= 30
margin[rl] = max[0]
else
margin[rl] = 0
end
}
board_size = [(img_size[0] - margin.inject(:+)), (img_size[0] - margin.inject(:+)) * Rational(719, 1024)]
board_base = [margin[0], img_size[1] - board_size[1]]
include_np_board_size = [(img_size[0] - margin.inject(:+)), (img_size[0] - margin.inject(:+)) * Rational(784, 1024)]
include_np_board_base = [margin[0], img_size[1] - include_np_board_size[1]]
cell_size = [board_size[0] * Rational(1, 8), board_size[1] * Rational(1, 6)]
cell_size_np = [board_size[0] * Rational(1, 8), include_np_board_size[1] - board_size[1]]
p ['img_size', img_size.map(&:to_f)]
p ['margin', margin.map(&:to_f)]
p ['board_size', board_size.map(&:to_f)]
p ['board_base', board_base.map(&:to_f)]
p ['include_np_board_size', include_np_board_size.map(&:to_f)]
p ['include_np_board_base', include_np_board_base.map(&:to_f)]
p ['cell_size', cell_size.map(&:to_f)]
check_relative = []
30.times { |x|
30.times { |y|
check_x = cell_size[0] * Rational(1, 4) + (cell_size[0] * Rational(1, 2)) * Rational((x + 1), 30)
check_y = cell_size[1] * Rational(1, 4) + (cell_size[1] * Rational(1, 2)) * Rational((y + 1), 30)
check_relative << [check_x, check_y]
}
}
check_relative_np = []
30.times { |x|
30.times { |y|
check_x = cell_size_np[0] * Rational(2, 5) + (cell_size_np[0] * Rational(1, 5)) * Rational((x + 1), 30)
check_y = cell_size_np[1] * Rational(3, 7) + (cell_size_np[1] * Rational(1, 2)) * Rational((y + 1), 30)
check_relative_np << [check_x, check_y]
}
}
board = []
8.times { |x|
7.times { |y|
rgb = []
if y == 0
check_relative_np.each_with_index { |r_coord, i__|
check_x = (include_np_board_base[0] + x * cell_size[0] + r_coord[0]).round
check_y = (include_np_board_base[1] + r_coord[1]).round
rgb << [@img[check_y][check_x].red, @img[check_y][check_x].green, @img[check_y][check_x].blue]
}
else
check_relative.each_with_index { |r_coord, i__|
check_x = (board_base[0] + x * cell_size[0] + r_coord[0]).round
check_y = (board_base[1] + (y - 1) * cell_size[1] + r_coord[1]).round
rgb << [@img[check_y][check_x].red, @img[check_y][check_x].green, @img[check_y][check_x].blue]
}
end
rgb_ave = rgb.transpose.map { |v|
v.inject(:+) / rgb.size
}
hsla = Magick::Pixel.new(*rgb_ave).to_hsla
# p [x, y]
# p hsla
index = nil
COLOR_MAP.each_with_index { |hue, i|
next if hue.nil?
ok = false
if hsla[2] > 100
if hue - ERROR < 0
ok = hsla[0] > (360 + hue - ERROR) || hsla[0] < hue + ERROR
else
ok = hsla[0] > hue - ERROR && hsla[0] < hue + ERROR
end
end
if ok
index = i
break
end
}
board[y] ||= []
board[y][x] = index || 0
# p rgb_ave
}
}
return board
end
def self.to_magick(img_da)
new_img = Magick::Image.new(img_da[0].length, img_da.length)
img_da.each_with_index do |y_p, y|
y_p.each_with_index do |pi, x|
pixel = Magick::Pixel.from_hsla(*pi)
# pixel = Magick::Pixel.new(*pi)
new_img.pixel_color(x, y, pixel)
end
end
return new_img
end
def self.board_to_img(path, board)
new_img = []
board.each_with_index { |row, y|
row.each_with_index { |cell, x|
40.times { |rx|
(y == 0 ? 20 : 40).times { |ry|
color = (ry == 0 || rx == 0) ? [0.0, 255.0, 255.0, 1.0] : SYMBOL_COLOR_MAP[cell]
new_img[(y >= 1 ? -20 : 0) + y * 40 + ry] ||= []
new_img[(y >= 1 ? -20 : 0) + y * 40 + ry][x * 40 + rx] = color
}
}
}
}
self.to_magick(new_img).write(path)
end
def self.hr_board_to_img(path, board_arr)
new_img = []
board_arr.each_with_index { |board, i|
board.each_with_index { |row, y|
row.each_with_index { |cell, x|
40.times { |rx|
(y == 0 ? 20 : 40).times { |ry|
color = (ry == 0 || rx == 0) ? [0.0, 255.0, 255.0, 1.0] : SYMBOL_COLOR_MAP[cell]
new_img[(y >= 1 ? -20 : 0) + y * 40 + ry] ||= []
new_img[(y >= 1 ? -20 : 0) + y * 40 + ry][i * 40 * 8 + i * 60 + x * 40 + rx] = color
}
}
}
}
if board_arr.size - 1 != i
60.times { |rx|
(20 + 40 * 6).times { |ry|
new_img[ry] ||= []
new_img[ry][(i + 1) * 40 * 8 + i * 60 + rx] = [0.0, 255.0, 255.0, 1.0]
}
}
end
}
self.to_magick(new_img).write(path)
end
end
class Board
attr_reader :board
PROXIMITY_VANISH = [6]
COLOR_NAME_MAP = [
:blank,
:red,
:blue,
:green,
:yellow,
:purple,
:pink
]
# blank : 0
# red : 1
# blue : 2
# green : 3
# yellow : 4
# purple : 5
# pink : 6
def initialize(board)
@board = Array.new(board.size) { |i| Array.new(board[i].size) { |j| board[i][j] } }
@h = HighLine.new
end
def filled?(color_index = nil)
@board.all? { |row|
row.all? { |cell|
if color_index.nil?
cell != 0
else
cell == color_index
end
}
}
end
def count(color_index)
count = 0
@board.each { |row|
row.each { |cell|
if cell == color_index
count += 1
end
}
}
return count
end
def print
board_colored = []
@board.each_with_index { |row, y|
row_colored = []
row.each_with_index { |cell, x|
row_colored << get_color(cell)
}
board_colored << row_colored
}
puts board_colored.map { |v| v.join(' ') }.join("\n")
puts
end
def delete(x, y)
@board[y][x] = 0
end
def exec(output = false)
all_vanished = []
vanished = {}
np_drop = false
loop {
drop_check(output, np_drop)
vanished = vanish_check(output)
if vanished.empty?
if np_drop
break
else
np_drop = true
end
else
all_vanished << vanished
end
}
return all_vanished
end
private
def drop_check(output = false, np_drop = false)
result_board = []
@board.transpose.each_with_index { |col, x|
result_col = []
move = 0
r_col = (np_drop ? col : col[1..-1]).reverse
# p r_col
r_col.size.times { |y|
result_cell = r_col[y + move]
if y + move >= r_col.size
result_cell = 0
elsif r_col[y + move] == 0
move += 1
redo
end
result_col << result_cell
}
result_col << col[0] unless np_drop
result_board << result_col.reverse
}
result_board = result_board.transpose
@board = result_board
print() if output
end
def vanish_check(output = false)
checked_board = Array.new(@board.size) { Array.new(@board[0].size) { 0 } }
all_vanished = {}
@board.each_with_index { |row, y|
# p row
next if y == 0
row.each_with_index { |cell, x|
if checked_board[y][x] == 1
next
end
vanish = false
normal_vanish_coords, proximity_vanish_coords = check_around(x, y)
if normal_vanish_coords.size >= 4
vanish = true
all_vanished[@board[normal_vanish_coords[0][1]][normal_vanish_coords[0][0]]] ||= []
all_vanished[@board[normal_vanish_coords[0][1]][normal_vanish_coords[0][0]]] << normal_vanish_coords.size
if proximity_vanish_coords.size != 0
all_vanished[@board[proximity_vanish_coords[0][1]][proximity_vanish_coords[0][0]]] ||= []
all_vanished[@board[proximity_vanish_coords[0][1]][proximity_vanish_coords[0][0]]] << normal_vanish_coords.size
end
end
# p ['normal_vanish_coords', normal_vanish_coords]
normal_vanish_coords.each { |coord|
# p ['coord', coord]
checked_board[coord[1]][coord[0]] = 1
if vanish
delete(*coord)
end
}
proximity_vanish_coords.each { |coord|
if vanish
delete(*coord)
end
}
}
}
print() if output
return all_vanished
end
def check_around(x, y, normal_vanish_coords = [], proximity_vanish_coords = [])
# puts "traced"
# p normal_vanish_coords
current_cell = @board[y][x]
if current_cell == 0
return normal_vanish_coords, proximity_vanish_coords
end
if PROXIMITY_VANISH.include?(current_cell)
proximity_vanish_coords << [x, y]
else
normal_vanish_coords << [x, y]
# p normal_vanish_coords
end
around = []
around << (y - 1 <= 7 - 1 && y - 1 >= 1 ? [x, y - 1] : nil)
around << (y + 1 <= 7 - 1 && y + 1 >= 1 ? [x, y + 1] : nil)
around << (x - 1 <= 8 - 1 && x - 1 >= 0 ? [x - 1, y] : nil)
around << (x + 1 <= 8 - 1 && x + 1 >= 0 ? [x + 1, y] : nil)
around.each { |coord|
if coord.nil? || normal_vanish_coords.include?(coord) || proximity_vanish_coords.include?(coord)
next
end
if @board[coord[1]][coord[0]] == current_cell
# puts "recursive"
normal_vanish_coords, proximity_vanish_coords = check_around(*coord, normal_vanish_coords, proximity_vanish_coords)
# p ['current', x, y]
# p normal_vanish_coords
elsif PROXIMITY_VANISH.include?(@board[coord[1]][coord[0]])
normal_vanish_coords, proximity_vanish_coords = check_around(*coord, normal_vanish_coords, proximity_vanish_coords)
end
}
# puts 'return'
# p normal_vanish_coords
return normal_vanish_coords, proximity_vanish_coords
end
def get_color(num)
color = [:black, :red, :blue, :green, :yellow, :cyan, :white]
return @h.color(num.to_s, color[num])
end
end
class PuyoSolver
def initialize(board)
@board = board.board
@want_vanish_color = nil
end
def solve(want_vanish_color = nil, delete_count = 5, inverse = false)
start_time = Time.now
@want_vanish_color = want_vanish_color ? [:blank, :red, :blue, :green, :yellow, :purple, :pink].index(want_vanish_color) : nil
scores = []
coords = []
@board.size.times { |y| # 6
next if y == 0
@board[y].size.times { |x| # 8
coords << [x, y]
}
}
Parallel.map(coords) { |coords_|
ret = []
delete_start(*coords_, [], delete_count) { |delete_arr|
verbose = false
# if delete_arr == [[3, 6], [4, 6]]
# verbose = true
# end
score, all_vanished = evaluate(delete_arr, verbose)
ret << {
:score => score,
:all_vanished => all_vanished,
:delete_arr => delete_arr
}
# p ret if verbose
# p ret if ret[:score] != 0
}
ret
}.each { |ret|
scores += ret
}
# pp scores
# p scores.size()
if inverse
sorted_score = scores.sort_by { |v| (v[:score][:opt].to_r / (v[:score][:attack] * 100 + 1)).to_f }.reverse
else
sorted_score = scores.sort_by { |v| (v[:score][:attack] * 1000 + v[:score][:opt]).to_f }.reverse
end
# Board.new(@board, @chance).print
# sorted_score[0..2].each_with_index { |v, i|
# puts i
# p v[:delete_arr]
# p v[:all_vanished]
# puts "score: #{v[:score]} sum: #{v[:all_vanished].values.inject(:+)}"
# test_board = Board.new(@board, @chance)
# v[:delete_arr].each { |coord|
# test_board.delete(*coord)
# }
# test_board.print
# test_board.exec()
# puts
# }
finish_time = Time.now
puts "elapsed time: #{finish_time - start_time}s"
return sorted_score[0]
end
private
def delete_start(x, y, circled = [], delete_count = 5, delete_arr = [], started_coord = nil)
return circled if @board[y][x] == 0
delete_arr = Array.new(delete_arr.size) { |i| Array.new(delete_arr[i]) { |j| delete_arr[i][j] } }
delete_arr << [x, y]
verbose = false
# if delete_arr == [[6, 2], [5, 3], [4, 4], [3, 5], [2, 6]]
# verbose = true
# p ['delete_arr', delete_arr]
# end
p ['current', x, y] if verbose
unless started_coord
started_coord = [x, y]
end
p ['delete_count', delete_count] if verbose
if delete_count == 1
if x <= started_coord[0] - 1 && y <= started_coord[1] - 1
return circled
end
end
around = []
around << (y - 1 <= 7 - 1 && y - 1 >= 1 ? [x, y - 1] : nil)
around << (y + 1 <= 7 - 1 && y + 1 >= 1 ? [x, y + 1] : nil)
around << (x - 1 <= 8 - 1 && x - 1 >= 0 ? [x - 1, y] : nil)
around << (x + 1 <= 8 - 1 && x + 1 >= 0 ? [x + 1, y] : nil)
around << (y - 1 <= 7 - 1 && y - 1 >= 1 && x - 1 <= 8 - 1 && x - 1 >= 0 ? [x - 1, y - 1] : nil)
around << (y + 1 <= 7 - 1 && y + 1 >= 1 && x - 1 <= 8 - 1 && x - 1 >= 0 ? [x - 1, y + 1] : nil)
around << (y - 1 <= 7 - 1 && y - 1 >= 1 && x + 1 <= 8 - 1 && x + 1 >= 0 ? [x + 1, y - 1] : nil)
around << (y + 1 <= 7 - 1 && y + 1 >= 1 && x + 1 <= 8 - 1 && x + 1 >= 0 ? [x + 1, y + 1] : nil)
before_circled = false
passed_circle = nil
available_around = []
around.each { |coord|
p coord if verbose
if coord.nil?
next
end
if @board[coord[1]][coord[0]] == 0
next
end
if delete_arr.include?(coord)
if delete_arr[-2] != coord
before_circled = true
if passed_circle.nil?
p ['circled size', circled.size] if verbose
circled.each { |arr|
next if arr.size != delete_arr.size
next if arr.last != delete_arr.last
if arr.all? { |v| delete_arr.include?(v) }
p ['existed', arr] if verbose
passed_circle = true
break
end
}
end
if passed_circle
break
end
end
next
end
available_around << coord
}
p [before_circled, passed_circle] if verbose
if passed_circle
return circled
end
if before_circled
circled << delete_arr
end
yield(delete_arr)
p delete_count if verbose
if delete_count >= 2
p ['available_around', available_around] if verbose
available_around.each { |coord|
circled = delete_start(*coord, circled, delete_count - 1, delete_arr, started_coord) { |delete_arr_|
yield(delete_arr_)
}
}
end
return circled
end
def evaluate(delete_arr, verbose = false)
test_board = Board.new(@board)
delete_arr.each { |coord|
test_board.delete(*coord)
}
all_vanished = test_board.exec(verbose)
attack_score = 0.to_r
opt_score = 0
all_vanished.each_with_index { |vanished , i|
chain_bonus = i + 1 <= 4 ? [1.0, 1.4, 1.7, 2.0][i].to_r : 2.0.to_r + 0.2.to_r * (i - 3)
sum_vanished_include_proximity = vanished.values.flatten.inject(:+)
sum_vanished = vanished.to_a.map { |v| Board::PROXIMITY_VANISH.include?(v[0]) ? [] : v[1] }.flatten.inject(:+)
if @want_vanish_color
if vanished.keys.include?(@want_vanish_color)
division = vanished[@want_vanish_color].size
attack_score += (1.to_r + 0.15.to_r * (sum_vanished - 4).to_r) * division.to_r * chain_bonus
end
end
opt_score += sum_vanished_include_proximity
}
if test_board.filled?(0)
opt_score += 100
end
if @want_vanish_color
opt_score += test_board.count(@want_vanish_color)
end
score = {
:attack => attack_score,
:opt => opt_score
}
return score, all_vanished
end
end
# 8 * 6
# temp_board = [
# [1, 1, 1, 2, 2, 1, 1, 1],
# [1, 1, 2, 5, 4, 2, 1, 1],
# [5, 5, 5, 4, 5, 4, 4, 4],
# [4, 4, 4, 5, 4, 5, 5, 5],
# [5, 5, 5, 4, 5, 4, 4, 4],
# [4, 4, 4, 1, 4, 5, 5, 5],
# [1, 1, 1, 3, 3, 4, 4, 4]
# ]
# temp_board = [
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 1, 0, 1, 1, 0, 1, 0],
# [0, 1, 1, 2, 2, 1, 1, 0]
# ]
# temp_board = [
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [1, 0, 1, 0, 0, 3, 0, 3],
# [1, 1, 2, 2, 2, 2, 3, 3]
# ]
# temp_board = [
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [1, 0, 1, 0, 0, 1, 0, 1],
# [1, 1, 2, 2, 2, 2, 1, 1]
# ]
puts "puyo solver started"
img_src = Magick::ImageList.new('./img.jpg')
puts "image imported"
img_analize = ImageAnalize.new(img_src)
puts "image initialized"
imported_board = img_analize.to_board
puts "image analized"
test = Board.new(imported_board)
# test = Board.new(temp_board)
puts "board initialized"
test.print
p test.filled?
solver = PuyoSolver.new(test)
puts "solver initialized"
puts "vanish priority: #{ARGV[0]}"
puts "vanish priority index: #{ARGV[0] ? Board::COLOR_NAME_MAP.index(ARGV[0].to_sym) : nil}"
result = solver.solve(ARGV[0] ? ARGV[0].to_sym : nil, 5, false)
puts "solver finished"
p result[:delete_arr]
p result[:all_vanished]
sum_all_vanished = {}
result[:all_vanished].each { |v|
v.each { |k, v_|
sum_all_vanished[k] ||= 0
sum_all_vanished[k] += v_.inject(:+)
}
}
puts "attack score: #{result[:score][:attack].to_f} opt score: #{result[:score][:opt]} sum: #{sum_all_vanished.values.inject(:+)}"
before_board = Board.new(test.board)
result[:delete_arr].each { |coord|
before_board.delete(*coord)
}
before_board.print()
after_board = Board.new(test.board)
result[:delete_arr].each { |coord|
after_board.delete(*coord)
}
after_board.exec()
after_board.print()
ImageAnalize.hr_board_to_img('./out.png', [test.board, before_board.board, after_board.board])
# test.delete(0, 3)
# test.delete(0, 4)
# test.delete(1, 4)
# test.delete(2, 4)
# test.delete(1, 5)
# test.print
# test.exec(true)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment