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

[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

[DarkMaster]

Не, я о другом. Я об обобщении и вшивании его в пилот как функции для поиска пути.
Проблема в том что есть слишком много разных факторов которые зависят от контекста.
Допустим возьмем УО.
Если на пути стоят персонажи, их все обходить или смотреть что по стамине и проходить через персонажа?
Если ты находишься на крыше у которой нет бортиков и с неё можно спрыгнуть?
Если на пути находится паутина, в которой ты застрянешь, но сама она непроходимой не является?

И так с каждой игрой.
Тут надо очень хорошо все нюансы игры знать, что-бы делать правильные расчеты кратчайшего пути через А*.
Например в той-же РанУО, при патфайндинге у мобов ( там тоже А* используется), между каждый тайлом используется весь алгоритм с проверками на шаг, а это довольно много кода, ибо нюансов вагон и тележка.

Для этого должен быть разработан формат карты который будет учитывать данные детали. Т.е. в моем понимании это xyz координаты, модификатор стоимость пути, задание фиксированной стоимости. Карта должна создаваться непосредственно пользователем. Алгоритм же поиска не должен каждый раз вымучиваться на движке пилота.

Пробежка по вей пойнтам х это тоже самое что запуск А* х раз.

Каким это образом? Это будет запуск 1 раз, просто логика должна понимать различную ценность маршрута и ограничения связей.

Зачем вам это как отдельная фича?
Имхо в ней есть смысл только в том случае, если у вас есть пачка вей пойнтов и все они не упорядочены.
Тоесть нужно получить общий кратчайший путь через все вей пойнты. Но в каком случае можно встретить такой сценарий, где у вас куча разных точек, разбросанных по карте и вам нужно по ним создать кратчайший маршрут?

Навигация в любом полноценном 3д приложении.