Алгоритм Match3, Оптимизация и ускорение алгоритма Match3-игр Опции

[Denker]

Здравствуйте.
Давно вынашивал идею написать бота к онлайн игре Техномагия. Там бои проходят по системе Match3 (три в ряд). В конце концов написал скрипт на анализ игрового поля и поиск комбинаций простым перебором. Но этот метод слишком медленный -- на анализ поля 6х6 с 4-мя цветами уходит 10сек.
Как можно оптимизировать алгоритм поиска комбинаций, при этом учитывая приоритет по количеству камней в комбинации и цвету?

Вот мой скрипт:

Match3

Код

set linedelay 0
set #a findwindow (Техномагия)
set workwindow #a
showwindow #a
move 362 100
set #w windowfromcursor // игра флешевая, поэтому приходится делать привязку к окну внутри основного
set workwindow #w
set windowpos 388 342 1024 780 #a
set #h 54
:start
if_not 866, 189 4406769 // пока не появится боевое поле
 while 423, 12 196665 // востановление хитов
  wait 1000
 end_while
 set #z 0
 set #z findcolor (110, 46 880, 365 1 1 11352588 %cc 2) // поиск монстра
// set #z findimage (110, 46 880, 365 (c:\Program Files\uopilot\scripts\варан.bmp) %cc #w 20 1 5)
 if #z > 0
  set #z1 %cc[1 1] + 20
  set #z2 %cc[1 2] + 20
  left #z1 #z2
  wait 2000
  while 628, 391 158  // пока персонаж бежит, чтобы не отвлекался на других
  end_while
 end_if
end_if 
while 866, 189 4406769 // боевое поле
 while_not 300, 57 7796223 // ждём своего хода
  wait 1000
 end_while
set #x 686
set #y 392
set #i 0
set size (%s)
repeat 6
 repeat 6
//  if (300, 57 7796223) and ((362, 68 16702856) or (362, 68 2825721) or (362, 68 614415) or(362, 68 8351543)) // магия
//   left 300, 195
//  end_if
  set #i #i + 1
  set #x0 #x + #h
  set #x1 #x - #h
  set #x2 #x - 2 * #h
  set #x3 #x - 3 * #h
  set #x4 #x - 4 * #h
  set #x5 #x + 2 * #h
  set #y0 #y + #h
  set #y1 #y - #h
  set #y2 #y - 2 * #h
  set #y3 #y - 3 * #h
  set #y4 #y - 4 * #h
  set #y5 #y + 2 * #h

  get color #c #x #y
  
// проверка комбинаций из пятёрок  
// если найдёт, то сразу её собирает
  if #x > 570
   if (#x, #y #c) and (#x1, #y #c) and (#x3, #y #c) and (#x4, #y #c) and (#x2, #y1 #c)
    left #x2 #y1
    wait 300 + random (300)
    left #x2 #y
    wait 5000    
    break 3
   end_if
   if (#x #y #c) and (#x1 #y #c) and (#x3 #y #c) and (#x4 #y #c) and (#x2 #y0 #c)
    left #x2 #y0
    wait 300 + random (300)
    left #x2 #y
    wait 5000    
    break 3    
   end_if
  end_if
  if #y > 280  
   if (#x #y #c) and (#x #y1 #c) and (#x #y3 #c) and (#x #y4 #c) and (#x1 #y2 #c)
    left #x1 #y2
    wait 300 + random (300)
    left #x #y2
    wait 5000    
    break 3
    end_if
   if (#x #y #c) and (#x #y1 #c) and (#x #y3 #c) and (#x #y4 #c) and (#x0 #y2 #c)
    left #x0 #y2
    wait 300 + random (300)
    left #x #y2
    wait 5000    
    break 3
    end_if
  end_if  

// проверка комбинаций из троек, а найденые сохраняем в массив
  if (#x #y #c) and (#x1 #y #c) and (#x3 #y #c)
   set %s[#i 1] 3
   set %s[#i 2] #c
   set %s[#i 3] #x3
   set %s[#i 4] #y
   set %s[#i 5] #x2
   set %s[#i 6] #y
  end_if
  if (#x #y #c) and (#x1 #y #c) and (#x2 #y1 #c)
   set %s[#i 1] 3
   set %s[#i 2] #c
   set %s[#i 3] #x2
   set %s[#i 4] #y1
   set %s[#i 5] #x2
   set %s[#i 6] #y
  end_if
  if (#x #y #c) and (#x1 #y #c) and (#x2 #y0 #c)
   set %s[#i 1] 3
   set %s[#i 2] #c
   set %s[#i 3] #x2
   set %s[#i 4] #y0
   set %s[#i 5] #x2
   set %s[#i 6] #y   
  end_if  
  if (#x #y #c) and (#x1 #y #c) and (#x5 #y #c)
   set %s[#i 1] 3
   set %s[#i 2] #c
   set %s[#i 3] #x5
   set %s[#i 4] #y
   set %s[#i 5] #x0
   set %s[#i 6] #y   
  end_if  
  if (#x #y #c) and (#x1 #y #c) and (#x0 #y1 #c)
   set %s[#i 1] 3
   set %s[#i 2] #c
   set %s[#i 3] #x0
   set %s[#i 4] #y1
   set %s[#i 5] #x0
   set %s[#i 6] #y
  end_if  
  if (#x #y #c) and (#x1 #y #c) and (#x0 #y0 #c)
   set %s[#i 1] 3
   set %s[#i 2] #c
   set %s[#i 3] #x0
   set %s[#i 4] #y0
   set %s[#i 5] #x0
   set %s[#i 6] #y   
  end_if  
  if (#x #y #c) and (#x2 #y #c) and (#x1 #y1 #c)
   set %s[#i 1] 3
   set %s[#i 2] #c
   set %s[#i 3] #x1
   set %s[#i 4] #y1
   set %s[#i 5] #x1
   set %s[#i 6] #y
  end_if  
  if (#x #y #c) and (#x2 #y #c) and (#x1 #y0 #c)
   set %s[#i 1] 3
   set %s[#i 2] #c
   set %s[#i 3] #x1
   set %s[#i 4] #y0
   set %s[#i 5] #x1
   set %s[#i 6] #y   
  end_if    
  if (#x #y #c) and (#x #y1 #c) and (#x #y3 #c)
   set %s[#i 1] 3
   set %s[#i 2] #c
   set %s[#i 3] #x
   set %s[#i 4] #y3
   set %s[#i 5] #x
   set %s[#i 6] #y2   
  end_if
  if (#x #y #c) and (#x #y1 #c) and (#x1 #y2 #c)
   set %s[#i 1] 3
   set %s[#i 2] #c
   set %s[#i 3] #x1
   set %s[#i 4] #y2
   set %s[#i 5] #x
   set %s[#i 6] #y2
  end_if
  if (#x #y #c) and (#x #y1 #c) and (#x0 #y2 #c)
   set %s[#i 1] 3
   set %s[#i 2] #c
   set %s[#i 3] #x0
   set %s[#i 4] #y2
   set %s[#i 5] #x
   set %s[#i 6] #y2   
  end_if  
  if (#x #y #c) and (#x #y1 #c) and (#x #y5 #c)
   set %s[#i 1] 3
   set %s[#i 2] #c
   set %s[#i 3] #x
   set %s[#i 4] #y5
   set %s[#i 5] #x
   set %s[#i 6] #y0   
  end_if  
  if (#x #y #c) and (#x #y1 #c) and (#x1 #y0 #c)
   set %s[#i 1] 3
   set %s[#i 2] #c
   set %s[#i 3] #x1
   set %s[#i 4] #y0
   set %s[#i 5] #x
   set %s[#i 6] #y0   
  end_if  
  if (#x #y #c) and (#x #y1 #c) and (#x0 #y0 #c)
   set %s[#i 1] 3
   set %s[#i 2] #c
   set %s[#i 3] #x0
   set %s[#i 4] #y0
   set %s[#i 5] #x
   set %s[#i 6] #y0
  end_if  
  if (#x #y #c) and (#x #y5 #c) and (#x1 #y0 #c)
   set %s[#i 1] 3
   set %s[#i 2] #c
   set %s[#i 3] #x1
   set %s[#i 4] #y0
   set %s[#i 5] #x
   set %s[#i 6] #y0   
  end_if  
  if (#x #y #c) and (#x #y5 #c) and (#x0 #y0 #c)
   set %s[#i 1] 3
   set %s[#i 2] #c
   set %s[#i 3] #x0
   set %s[#i 4] #y0
   set %s[#i 5] #x
   set %s[#i 6] #y0   
  end_if    

  
// проверка комбинаций из четвёрок  
  if (#x #y #c) and (#x1 #y #c) and (#x3 #y #c) and (#x2 #y1 #c)
   set %s[#i 1] 4
   set %s[#i 2] #c
   set %s[#i 3] #x2
   set %s[#i 4] #y1
   set %s[#i 5] #x2
   set %s[#i 6] #y
  end_if
  if (#x #y #c) and (#x1 #y #c) and (#x3 #y #c) and (#x2 #y0 #c)
   set %s[#i 1] 4
   set %s[#i 2] #c
   set %s[#i 3] #x2
   set %s[#i 4] #y0
   set %s[#i 5] #x2
   set %s[#i 6] #y
  end_if
  if (#x #y #c) and (#x1 #y #c) and (#x5 #y #c) and (#x0 #y1 #c)
   set %s[#i 1] 4
   set %s[#i 2] #c
   set %s[#i 3] #x0
   set %s[#i 4] #y1
   set %s[#i 5] #x0
   set %s[#i 6] #y
  end_if
  if (#x #y #c) and (#x1 #y #c) and (#x5 #y #c) and (#x0 #y0 #c)
   set %s[#i 1] 4
   set %s[#i 2] #c
   set %s[#i 3] #x0
   set %s[#i 4] #y0
   set %s[#i 5] #x0
   set %s[#i 6] #y
  end_if
  if (#x #y #c) and (#x #y1 #c) and (#x #y3 #c) and (#x1 #y2 #c)
   set %s[#i 1] 4
   set %s[#i 2] #c
   set %s[#i 3] #x1
   set %s[#i 4] #y2
   set %s[#i 5] #x
   set %s[#i 6] #y2
  end_if
  if (#x #y #c) and (#x #y1 #c) and (#x #y3 #c) and (#x0 #y2 #c)
   set %s[#i 1] 4
   set %s[#i 2] #c
   set %s[#i 3] #x0
   set %s[#i 4] #y2
   set %s[#i 5] #x
   set %s[#i 6] #y2
  end_if
  if (#x #y #c) and (#x #y1 #c) and (#x #y5 #c) and (#x1 #y0 #c)
   set %s[#i 1] 4
   set %s[#i 2] #c
   set %s[#i 3] #x1
   set %s[#i 4] #y0
   set %s[#i 5] #x
   set %s[#i 6] #y0
  end_if
  if (#x #y #c) and (#x #y1 #c) and (#x #y5 #c) and (#x0 #y0 #c)
   set %s[#i 1] 4
   set %s[#i 2] #c
   set %s[#i 3] #x0
   set %s[#i 4] #y0
   set %s[#i 5] #x
   set %s[#i 6] #y0
  end_if
  set #x #x - 54
 end_repeat 
 set #x 686
 set #y #y - 54
end_repeat 

  
for #n 1 36 1
 if (%s[#n 1] = 4) and (%s[#n 2] = 8351543) // приоритет на срабатывание комбинации из 4-х черепов
  left %s[#n 3] %s[#n 4]
  wait 300 + random (300)
  left %s[#n 5] %s[#n 6]
  wait 5000
  break 2
 end_if 
end_for 

for #n 1 36 1  // приоритет на срабатывание комбинации из 4-х любого цвета
 if %s[#n 1] = 4
  left %s[#n 3] %s[#n 4]
  wait 300 + random (300)
  left %s[#n 5] %s[#n 6]
  wait 5000
  break 2
 end_if 
end_for 

 if 301, 157 4750079 // магия
  left 298, 157
  wait 300 + random (300)
  left 578, 279 
 end_if
 
for #n 1 36 1
 if (%s[#n 1] = 3) and (%s[#n 2] = 8351543) // приоритет на срабатывание комбинации из 3-х черепов
  left %s[#n 3] %s[#n 4]
  wait 300 + random (300)
  left %s[#n 5] %s[#n 6]
  wait 5000
  break 2
 end_if 
end_for 

//left 301, 232 
//left 296, 193

for #n 1 36 1
 if %s[#n 1] = 3 // приоритет на срабатывание комбинации из 3-х любого цвета
  left %s[#n 3] %s[#n 4]
  wait 300 + random (300)
  left %s[#n 5] %s[#n 6]
  wait 5000
  break 2
 end_if 
end_for 


end_while
if 484, 272 9165051 // кнопка победы или поражения
 left 484, 272 
end_if
goto start

размер 54х54, шаг 27

синий 16702856
красный 2825721
зелёный 614415
череп 8351543 

скрин

(IMG:http://img848.imageshack.us/img848/9369/88353642.png)

[esqado]

Простите за дурацкий вопрос: А сценарий рабочий?
Если не ошибаюсь переменная #а числовая.
Зы. А в массив %s[#i #x] записывается только последнее значение?
#i, по ходу, меняется только в начале и задаётся странным образом.
Не смог найти, где задаётся переменная #с. Пилот не ругается?
%s[#i 4] и %s[#i 6] - одно и то же?

[EL-GReeN]

Можно еще короче, цикл for.
Пересмотреть задержки, возможно их можно или убрать или вынести действия с ними в отдельный скрипт.
Заново проанализировать всю логику возможно что то лишнее и можно сделать проще.

[Denker]

Простите за дурацкий вопрос: А сценарий рабочий?

Да, скрипт полностью рабочий.

Если не ошибаюсь переменная #а числовая.

Переменная #a -- это хендл основного окна.

А в массив %s[#i #x] записывается только последнее значение?

В массив %s записываются координаты камней, кот. нужно поменять местами. Если на два камня комбинаций несколько, то записывается последняя из них.

Не смог найти, где задаётся переменная #с. Пилот не ругается?

Переменная #c: get color #c #x #y

%s[#i 4] и %s[#i 6] - одно и то же?

Нет, (%s[#i 3],%s[#i 4]) и (%s[#i 5],%s[#i 6]) -- координаты камней, кот. нужно менять местами.

Можно еще короче, цикл for.
Заново проанализировать всю логику возможно что то лишнее и можно сделать проще.

Выслушаю любые ваши предложения. Собственно в этои и заключается мой вопрос.

Пересмотреть задержки, возможно их можно или убрать или вынести действия с ними в отдельный скрипт.

Тут мы ждём пока упадут камни, сработают цепочки комбинаций и исчезнут надписи поверх игрового поля, кот. появляются после каждого хода.