Алгоритм А*, 2.0
Код
// Алгоритм A*
load_array %map C:\Users\abc\Desktop\map1.txt // массив карта
load_array %coord C:\Users\abc\Desktop\coord1.txt // координаты точек
set $start A // обозначение точки A в массиве
set $ending B // обозначение точки B в массиве
// 0 - ходы только по вертикали и горизонтали, 1 - по диагонали тоже
set #angle 0
set #logmap 1 // выводить в лог карту
set #readmap 1 // выводить ходы в лог
set #skipstep 0 // 0 - не пропускать ходы, 1 - пропускать. Нужно, если ширина препятствия меньше ширины клетки, на которую можно сделать ход.
set #click 1 // делать ходы, клик по координатам точек.
set #send 0 // делать ходы, нажатия клавииш Up, Down, Left, Right
set #hint 1 // показывать количество проверенных точек
set #showpoint 0 // показывать проверенные точки (клик по ним)
set #wait 30 // пауза между нажатиями клавиш Up, Down, Left, Right
// остальное менять не нужно
// направление движения
init_arr %vector (1) -1 -1 0 1 1 1 0 -1 // x
init_arr %vector (2) 0 1 1 1 0 -1 -1 -1 // y
set #handle workwindow
if workwindow = 0
Log Не сделана привязка
Log Скрипт остановлен
stop_script
end_if
if size(%map) = 0
Log Массив с картой не найден.
Log Скрипт остановлен
stop_script
end_if
if size(%coord) = 0
Log Массив с координатами не найден.
Log Скрипт остановлен
stop_script
end_if
log clear
log mode compact
set size(%tmp)
set size(%open)
set size(%close)
set size(%curr)
set size(%resultarray)
set #width size(%map[])
set #height size(%map)
set %sizemap indexof (%map (0))
set #sizemap size(%sizemap) + 1
// Позиция конечной точки на карте
set %ending indexof (%map ($ending))
// Позиция начальной точки на карте
set %start indexof (%map ($start))
// если точка A или B не найдены
if size(%ending) = 0 or size(%start) = 0
if size(%start) = 0
log Точка A не найдена
else
log Точка B не найдена
end_if
log Скрипт остановлен
end_script
end_if
// F, G, H, Направление_движения, Текущая клетка(X Y), Текущая клетка(X:Y), Родительская клетка (X Y)
init_arr %open (1) 0 0 0 0 %start [1 1] %start [1 2] %start [1 1]:%start [1 2] %start [1 1] %start [1 2]
while 1 = 1
sort_array %open // сортировка по наименьшему F
set #sizeclose size(%close) + 1
init_arr %curr (1) %open [1 1] %open [1 2] %open [1 3] %open [1 4] %open [1 5] %open [1 6] %open [1 7] %open [1 8] %open [1 9] // текущая клетка
init_arr %close (#sizeclose) %open [1 1] %open [1 2] %open [1 3] %open [1 4] %open [1 5] %open [1 6] %open [1 7] %open [1 8] %open [1 9] // добавить в закрытый список
if #showpoint = 1
left %coord[%curr[1 5] %curr[1 6]]
wait 1
end_if
delete_array %open -1 // удалить с открытого списка
// для каждой из 8 клеток просчёт хода
for #i 1 8
if #angle = 1 or mod(#i 2) = 1 // если ходы по диагонали допустимы или проверяется ход не по диагонали
set #x %curr [1 5] + %vector [1 #i]
set #y %curr [1 6] + %vector [2 #i]
init_arr %tmp (1) #x : #y
// поиск клетки в закрытом списке
set %resultclose indexof (%close (%tmp[1]))
if #x > 0 and #y > 0 and #x <= #height and #y <= #width // проверка не вышли ли за пределы массива
if (%map [#x #y] = 0 or %map [#x #y] = $ending) and size(%resultclose) = 0 // (если на клетку возможен ход или она является конечной) и не находится в закрытом списке
set %resultopen indexof (%open (%tmp[1])) // Если клетка еще не в открытом списке, то добавляем ее туда.
if size( %resultopen) = 0
set #sizeopen size(%open) + 1
if mod(#i 2) = 1
set #g %curr [1 2] + 10 // стоимость G
else
set #g %curr [1 2] + 14
end_if
set #h (abs(eval(#x - %ending [1 1])) + abs(eval(#y - %ending [1 2]))) * 10 // стоимость H
set #f #g + #h // стоимость F
init_arr %open (#sizeopen) #f #g #h #i #x #y %tmp[1] %curr [1 5] %curr [1 6]
else
// если клетка уже в открытом списке
set #tmp %resultopen [1 1] // позиция клетки в открытом списке
set #g1 %open[#tmp 2] // стоимость G клетки находящейся в открытом списке
if mod(#i 2) = 1
set #g %curr [1 2] + 10 // стоимость G текущей клетки + стоимость хода на клетку находящуюся в открытом списке
else
set #g %curr [1 2] + 14
end_if
if #g < #g1 // если стоимость хода дешевле
// меняем стоимость хода клетки находящейся в открытом списке
// меняем родителя клетки на текущую
set #h (abs(eval(#x - %ending [1 1])) + abs(eval(#y - %ending [1 2]))) * 10
set #f #g + #h
init_arr %open (#tmp) #f #g #h #i #x #y %tmp[1] %curr [1 5] %curr [1 6]
end_if
end_if
end_if
end_if
end_if
end_for
// если конечная клетка добавлена в закрытый список или все точки проверены
if (%curr [1 5] = %ending [1 1] and %curr [1 6] = %ending [1 2]) or size(%open) = 0
if %curr [1 5] != %ending [1 1] and %curr [1 6] != %ending [1 2]
log Вариантов хода нет
end_script
end_if
// проходим весь путь от точки B до точки A и записываем путь в массив
set size(%tmp)
init_arr %tmp (1) %close [size(%close) 8] %close [size(%close) 9]
while %tmp [size(%tmp) 1] != %start [1 1] or %tmp [size(%tmp) 2] != %start [1 2]
set %pathAB indexof (%close (%tmp [size(%tmp) 1]:%tmp [size(%tmp) 2]))
set #zz size(%tmp) + 1
init_arr %tmp (#zz) %close [%pathAB [1 1] 8] %close [%pathAB [1 1] 9] %close [%pathAB [1 1] 4]
end_while
set #z 0
set delimiter ' '
for #i size(%tmp) 1 -1
set #z #z + 1
init_arr %resultarray (#z) %tmp [#i]
end_for
set delimiter
// save_array %open C:\Users\abc\Desktop\open.txt // открытый список
// save_array %close C:\Users\abc\Desktop\close.txt // закрытый список
// save_array %resultarray C:\Users\abc\Desktop\resultarray.txt // массив с индексами нужных точек находящихся в массиве %map
log На поиск хода затрачено: timer мсек
// Вывод карты
if #logmap = 1
gosub logmap
end_if
// Вывод в лог ходов
if #readmap = 1
gosub readmap
end_if
// Сделать ход
if #click = 1
gosub hod
end_if
end_script
end_if
if #hint = 1
hint Проверено size(%close) из #sizemap точек.
end_if
end_while
end_script
:logmap
for #i 1 size(%map)
log %map [#i]
end_for
return
:readmap
set workwindow #handle
wait 500
showwindow #handle
wait 500
set #tmpi size(%resultarray) - 1
for #i 1 size(%resultarray)
if (#skipstep = 0) or (mod (#i 2) = 0 or #tmpi = #i)
switch %resultarray [#i 3]
case 1: log Вверх
if #send = 1
send {Up}
wait #wait
end_if
break
case 2: log Вверх-Вправо
if #send = 1
send {Up}
wait #wait
send {Right}
wait #wait
end_if
break
case 3: log Вправо
if #send = 1
send {Right}
wait #wait
end_if
break
case 4: log Вниз-Вправо
if #send = 1
send {Down}
wait #wait
send {Right}
wait #wait
end_if
break
case 5: log Вниз
if #send = 1
send {Down}
wait #wait
end_if
break
case 6: log Вниз-Влево
if #send = 1
send {Down}
wait #wait
send {Left}
wait #wait
end_if
break
case 7: log Влево
if #send = 1
send {Left}
wait #wait
end_if
break
case 8: log Вверх-Влево
if #send = 1
send {Up}
wait #wait
send {Left}
wait #wait
end_if
break
end_switch
end_if
end_for
return
:hod
if #showpoint = 1
alarm
set showscriptprocessing 1
log Путь найден. Скрипт на паузе.
log Для вывода пути снять скрипт с паузы.
pause_script
set showscriptprocessing 0
end_if
showwindow #handle
wait 500
if #skipstep = 0
for #i 2 size(%resultarray) // делать все ходы
kleft %coord[%resultarray [#i 1] %resultarray [#i 2]]
// log %coord[%resultarray [#i 1] %resultarray [#i 2]]
wait 1
end_for
else
for #i 3 size(%resultarray) 2 // пропускать не нужные ходы
kleft %coord[%resultarray [#i 1] %resultarray [#i 2]]
// log %coord[%resultarray [#i 1] %resultarray [#i 2]]
wait 1
end_for
end_if
return
Уменьшен код почти на 200 строк. Работает чуть медленнее первой версии.
Алгоритм А*, 1.0
АлгоритмA__версия1.zip ( 3,1 килобайт )
Кол-во скачиваний: 253 Описание алгоритма:
http://masters.donntu.org/2013/fknt/buga/library/AStar.htmСкрипт просчитывает самый короткий путь от точки A до точки B.
Для его работы нужен массив-карта, содержащий:
0 - точки, по которым можно перемещаться
1 - препятствия
A - точка A (англ.)
B - точка B (англ.)
Если для ходов используются клики, то ещё нужен массив с координатами всех точек.
Пример работы скрипта:
https://youtu.be/dC-bBCIYuwEВ архиве картинки 2 лабиринтов и массив-карта к ним.
A.zip ( 38,2 килобайт )
Кол-во скачиваний: 280