Алгоритм А*, Поиск пути Опции

[cirus]

Алгоритм А*, 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 килобайт ) Кол-во скачиваний: 292

Описание алгоритма: 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 килобайт ) Кол-во скачиваний: 328

[cirus]

но для второй карты минута с лишним расчет.

Если на lua будет findcolor, скорее всего, все расчёты займут минимум времени. Можно функцию написать.

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

Это скорее в сторону графов. Алгоритм Дейкстры.
Если доработать можно и этим искать путь, только на пилотовском языке устанешь ждать.
Самая большая проблема - это создание карты, а не поиск пути.