Здравствуйте, гость ( Вход | Регистрация )

2 страниц V  1 2 >  
Ответить в эту темуОткрыть новую тему
> Алгоритм А*, Поиск пути
cirus
сообщение 24.4.2017, 2:19
Сообщение #1


**********

Elder
Сообщений: 3.480
Регистрация: 18.8.2014
Группа: Пользователи
Наличность: 26540
Пользователь №: 16.971
Возраст: 29



Алгоритм А*, 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 килобайт ) Кол-во скачиваний: 279
Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Mirage
сообщение 24.4.2017, 20:17
Сообщение #2


*******

Группа: Пользователи
Наличность: 0
Из: Иваново
Пользователь №: 13.089
Возраст: 35



Жухала (IMG:style_emoticons/default/dry.gif)

(IMG:style_emoticons/default/biggrin.gif)
Адаптировать такое на какую нибудь рогрпг аля дьяблы что бы искал кротчайший путь по карте до выхода их подземелья. Все проходящие игру на скоростью сдохнут от зависти.


--------------------
Изображение
Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Cockney
сообщение 24.4.2017, 22:33
Сообщение #3


********

Master
Сообщений: 1.394
Регистрация: 22.6.2013
Группа: Пользователи
Наличность: 20893
Пользователь №: 16.156



Все конечно здорово, но для второй карты минута с лишним расчет. Встроить в пилот было бы замечательно. Да и предусмотреть бы возможность сохранения результата.
Пользователь в онлайне!Delete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
DarkMaster
сообщение 25.4.2017, 1:15
Сообщение #4


***********

Модератор UOPilot
Сообщений: 9.460
Регистрация: 2.12.2008
Группа: Супермодераторы
Наличность: 27708
Пользователь №: 11.279



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


--------------------
Скрипты UOPilot под заказ.
Консультации по UOpilot 15$/час.
Услуги Lua разработчика (не пилот, проекты, постоянка)
Disсоrd:
Kov____
Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
cirus
сообщение 25.4.2017, 2:43
Сообщение #5


**********

Elder
Сообщений: 3.480
Регистрация: 18.8.2014
Группа: Пользователи
Наличность: 26540
Пользователь №: 16.971
Возраст: 29



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

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

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


Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
DarkMaster
сообщение 25.4.2017, 5:54
Сообщение #6


***********

Модератор UOPilot
Сообщений: 9.460
Регистрация: 2.12.2008
Группа: Супермодераторы
Наличность: 27708
Пользователь №: 11.279



Цитата
Это скорее в сторону графов. Алгоритм Дейкстры.

Графов да, но Дейкстры ли? Вроде тоже а-старом решается... По крайней мере принципиальных отличий не вижу. Вообще в моем понимании подобных алгоритм должен возвращать массив с координатами точек пути, а передвижение между ними не более чем пользовательская функция.


--------------------
Скрипты UOPilot под заказ.
Консультации по UOpilot 15$/час.
Услуги Lua разработчика (не пилот, проекты, постоянка)
Disсоrd:
Kov____
Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
cirus
сообщение 25.4.2017, 11:13
Сообщение #7


**********

Elder
Сообщений: 3.480
Регистрация: 18.8.2014
Группа: Пользователи
Наличность: 26540
Пользователь №: 16.971
Возраст: 29



Цитата
Вообще в моем понимании подобных алгоритм должен возвращать массив с координатами точек пути, а передвижение между ними не более чем пользовательская функция.

Оно почти так и есть.
Массив %resultarray содержит индексы для массива с координатами (%coord) и направление движения.
Например, это массив %resultarray:
Код
2    2    5    
3    2    5    
3    3    3    
3    4    1    
2    4    

2 2 это начальная точка, 5 это направление движения (вниз).
2 4 конечная точка
Если используются клики, то:
left %coord [3 2] - первый ход
left %coord [3 3] - второй
left %coord [3 4] - третий
left %coord [2 4] - четвёртый

Сейчас скрипт останавливает поиск, если путь до конечной точки найден. Для нескольких точек нужно менять условие, или делать процедуру для поиска и искать сначала путь до одной точки, потом до другой.
Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
WKnight
сообщение 25.4.2017, 18:18
Сообщение #8


********

Разработчик UO Pilot'а
Сообщений: 1.639
Регистрация: 9.1.2006
Группа: Пользователи
Наличность: 0
Пользователь №: 4.688



Красавчик.

Свитч полностью дублируется. Так имхо чуть короче.
Код
    for #i 1 size(%resultarray)
        //  #skipstep = 0                  // показывать все ходы
        //  mod (#i 2) = 0 or #tmpi = #i   // пропускать не нужные ходы
        if  (#skipstep = 0) or (mod (#i 2) = 0 or #tmpi = #i)
                switch %resultarray [#i 3]
                  ...
                end_switch            
        end_if
    end_for


Сообщение отредактировал WKnight - 25.4.2017, 18:19
Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
cirus
сообщение 26.4.2017, 2:52
Сообщение #9


**********

Elder
Сообщений: 3.480
Регистрация: 18.8.2014
Группа: Пользователи
Наличность: 26540
Пользователь №: 16.971
Возраст: 29



Цитата
Свитч полностью дублируется. Так имхо чуть короче

Спасибо. Подправил.
Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Aimed
сообщение 26.4.2017, 17:45
Сообщение #10


*********

Grandmaster
Сообщений: 2.250
Регистрация: 29.12.2012
Группа: Пользователи
Наличность: 8846
Пользователь №: 15.607



Вы же понимаете что вам для нормальной работы этого алгоритма в пилоте нужно так-же правила передвижения от ноде к ноде знать.

Мож для какого-нибудь 2Д лабиринта где только стенка и не стенка есть и сойдет, а все остальное... я не вижу как можно обобщить это и вшить в пилот. Тут для каждой игры свои правила будут.
Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
DarkMaster
сообщение 27.4.2017, 18:31
Сообщение #11


***********

Модератор UOPilot
Сообщений: 9.460
Регистрация: 2.12.2008
Группа: Супермодераторы
Наличность: 27708
Пользователь №: 11.279



Цитата
Мож для какого-нибудь 2Д лабиринта где только стенка и не стенка есть и сойдет, а все остальное... я не вижу как можно обобщить это и вшить в пилот. Тут для каждой игры свои правила будут.

Ну вейпоинты не такая большая проблема на самом деле. У меня был (да и сейчас где-то валяется) алгоритм перемещения из коодинат x1, y1 в x2, y2 для вов. Игровые координаты дернуть не так сложно, как могло бы показаться.


--------------------
Скрипты UOPilot под заказ.
Консультации по UOpilot 15$/час.
Услуги Lua разработчика (не пилот, проекты, постоянка)
Disсоrd:
Kov____
Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
cirus
сообщение 28.4.2017, 3:16
Сообщение #12


**********

Elder
Сообщений: 3.480
Регистрация: 18.8.2014
Группа: Пользователи
Наличность: 26540
Пользователь №: 16.971
Возраст: 29



Цитата
Т.е. есть некоторый набор точек с указанием к каким точкам из них можно добраться.

Возьмём тот же лабиринт, на котором есть 5 точек (A - начальная точка, остальные - B, C, D, E).
Нужно добраться из точки A до указанных, например, C и D.
Найти путь A-C-D, найти путь A-D-C. Выбрать тот, который короче. Так должно быть?
Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
DarkMaster
сообщение 28.4.2017, 5:53
Сообщение #13


***********

Модератор UOPilot
Сообщений: 9.460
Регистрация: 2.12.2008
Группа: Супермодераторы
Наличность: 27708
Пользователь №: 11.279



Цитата
Найти путь A-C-D, найти путь A-D-C. Выбрать тот, который короче. Так должно быть?

Давай на более понятных тебе величинах (IMG:style_emoticons/default/smile.gif)
Дано: орен, дарк елвен, глудин, глудио, дион, гиран, гиран харбор.
Из каждого города мы можем переместиться только в соседний(ходим пешком).
Нужно найти кротчайший путь из орена в глудин.


--------------------
Скрипты UOPilot под заказ.
Консультации по UOpilot 15$/час.
Услуги Lua разработчика (не пилот, проекты, постоянка)
Disсоrd:
Kov____
Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
DarkMaster
сообщение 28.4.2017, 6:15
Сообщение #14


***********

Модератор UOPilot
Сообщений: 9.460
Регистрация: 2.12.2008
Группа: Супермодераторы
Наличность: 27708
Пользователь №: 11.279



Черные линии некоторая координатная сетка. Задача добраться из синего в красный. Предполагается, что цена пути помимо значения расстояния может дополнительны иметь модификатор (на некоторых локациях невозможно использовать ездовых животных, например), либо задан константой (частные случаи).


Эскизы прикрепленных изображений
Прикрепленное изображение

--------------------
Скрипты UOPilot под заказ.
Консультации по UOpilot 15$/час.
Услуги Lua разработчика (не пилот, проекты, постоянка)
Disсоrd:
Kov____
Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
Aimed
сообщение 28.4.2017, 16:32
Сообщение #15


*********

Grandmaster
Сообщений: 2.250
Регистрация: 29.12.2012
Группа: Пользователи
Наличность: 8846
Пользователь №: 15.607



Цитата(DarkMaster @ 27.4.2017, 17:31) *

Ну вейпоинты не такая большая проблема на самом деле. У меня был (да и сейчас где-то валяется) алгоритм перемещения из коодинат x1, y1 в x2, y2 для вов. Игровые координаты дернуть не так сложно, как могло бы показаться.


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

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


Пробежка по вей пойнтам х это тоже самое что запуск А* х раз. Зачем вам это как отдельная фича?
Имхо в ней есть смысл только в том случае, если у вас есть пачка вей пойнтов и все они не упорядочены.
Тоесть нужно получить общий кратчайший путь через все вей пойнты. Но в каком случае можно встретить такой сценарий, где у вас куча разных точек, разбросанных по карте и вам нужно по ним создать кратчайший маршрут?
Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
DarkMaster
сообщение 28.4.2017, 16:51
Сообщение #16


***********

Модератор UOPilot
Сообщений: 9.460
Регистрация: 2.12.2008
Группа: Супермодераторы
Наличность: 27708
Пользователь №: 11.279



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

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

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

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

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


--------------------
Скрипты UOPilot под заказ.
Консультации по UOpilot 15$/час.
Услуги Lua разработчика (не пилот, проекты, постоянка)
Disсоrd:
Kov____
Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
pager
сообщение 28.4.2017, 17:21
Сообщение #17


****

Apprentice
Сообщений: 147
Регистрация: 10.1.2006
Группа: Пользователи
Наличность: 0
Из: --
Пользователь №: 4.699
Возраст: --



Цитата(Aimed @ 28.4.2017, 19:32) *

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

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


На мой взгляд
Не думаю что в поиске пути правильно было бы учитывать динамические препятствия , получатель маршрута должен сам оценивать динамические препятствия и максимум что можно было бы сделать это системе поиска маршрута посылать уведомления что проложенный маршрут не подходит для использования и система его не учитывала в новом положении маршрута.
Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
DarkMaster
сообщение 28.4.2017, 17:29
Сообщение #18


***********

Модератор UOPilot
Сообщений: 9.460
Регистрация: 2.12.2008
Группа: Супермодераторы
Наличность: 27708
Пользователь №: 11.279



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

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


--------------------
Скрипты UOPilot под заказ.
Консультации по UOpilot 15$/час.
Услуги Lua разработчика (не пилот, проекты, постоянка)
Disсоrd:
Kov____
Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
pager
сообщение 28.4.2017, 18:17
Сообщение #19


****

Apprentice
Сообщений: 147
Регистрация: 10.1.2006
Группа: Пользователи
Наличность: 0
Из: --
Пользователь №: 4.699
Возраст: --



Цитата(DarkMaster @ 28.4.2017, 20:29) *

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

А я и не говорил о составление карты я под динамическими объектами имел в веду мобов тех же самых паутин и временных препятствий.Просто если система проложения маршрута начала бы делать проверки на тех же самых мобов то производительность системы вразы бы была меньше чем если бы эти проверки делал бы получатель маршрута
Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
cirus
сообщение 29.4.2017, 21:38
Сообщение #20


**********

Elder
Сообщений: 3.480
Регистрация: 18.8.2014
Группа: Пользователи
Наличность: 26540
Пользователь №: 16.971
Возраст: 29



Пока черновой вариант. Путь считается только по расстоянию.
код
Код
// Алгоритм A*
load_array %map C:\Users\abc\Desktop\map.txt        // массив карта
load_array %coord C:\Users\abc\Desktop\coord.txt    // координаты точек

set $start 4   // начальная точка
set $ending 1  // конечная

set #click 0       // делать ходы, клик по координатам точек. Нужна привязка в paint.

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)

// Позиция конечной точки на карте
for #i 1 size(%map)
    if  %map[#i 1] =  $ending
        set %ending [1 1] $ending
        break
    end_if
end_for

// Позиция начальной точки на карте
set %start [1 1] 7
for #i 1 size(%map)
    if  %map[#i 1] =  $start
        set %start [1 1] $start
        break
    end_if
end_for

// F,  G,  H, Текущая клетка, Родительская клетка, Текущая клетка:Родительская клетка
init_arr %open (1) 0 0 0 %start [1 1] %start [1 1] %start [1 1]:%start [1 1]

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] // текущая клетка
    init_arr %close (#sizeclose) %open [1 1] %open [1 2] %open [1 3] %open [1 4] %open [1 5] %open [1 6]  // добавить в закрытый список
    delete_array %open -1     // удалить с открытого списка
    for #t 2 size(%map[1])    // проверяем все точки, в которые можно дойти из текущей
        set #tmp %map [%curr[1 4] #t]
        if  #tmp  != 0
            set #x %map [%curr[1 4] #t]      // текущая точка  // %curr[1 4] - родитель
            init_arr %tmp (1) #x : %curr [1 4]
            set #sizeopen size(%open) + 1
            set #g %curr [1 2] + round(point_distance(%coord[%curr [1 4] 1]  %coord[#x 1]))             // стоимость G
            set #h round(point_distance(%coord[$ending 1]  %coord[#x 1]))     // стоимость H
            set #f #g + #h          // стоимость F
            init_arr %tmp (1) #x : %curr [1 4]
            init_arr %open (#sizeopen) #f #g #h #x %curr [1 4] %tmp [1]
        else
            break
        end_if
    end_for

    if  size(%open) = 0 or %curr [1 4] = %ending [1 1]     // если открытый список пуст или конечная точка найдена
        set size(%tmp)
        set #tmp %curr [1 4]
        if  %curr [1 4] = %ending [1 1]                    // если конечная точка найдена
            set #z #z + 1
            set %tmp [#z] #tmp
            // идём от конечной точки к начальной
            while #tmp != $start
                for #i 1 size(%close)
                    if  %close [#i 4] = #tmp
                        set #zz #zz + 1
                        set #tmp %close[#i 5]
                        set #z #z + 1
                        set %tmp [#z] #tmp
                        break
                    end_if
                end_for
            end_while
            // переворачиваем путь
            set #z 0
            for #i size(%tmp) 1 -1
                set #z #z + 1
                set %resultarray [#z] %tmp[#i 1]
            end_for

            // вывод в лог пути
            for #i 1 size(%resultarray)
                log %resultarray [#i]      %coord[%resultarray [#i]]
                if  #click = 1
                    kleft %coord[%resultarray [#i]]
                end_if
            end_for
        else
            log Ходов нет
        end_if
        end_script
    end_if
end_while
end_script

В массиве %map содержатся все точки в виде:
<точка1> [до каких точек можно добраться из точки1]
<точка2> [до каких точек можно добраться из точки2]
В массиве %coord содержатся координаты всех точек. Координаты взяты с картинки открытой в Paint.
В архиве 2 тхт файла (%map и %coord) и картинка. Прикрепленный файл  Astar2.zip ( 7,66 килобайт ) Кол-во скачиваний: 192



Прикрепленные файлы
Прикрепленный файл  map.bmp ( 265,59 килобайт ) Кол-во скачиваний: 198
Пользователь в офлайнеDelete PostОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения

2 страниц V  1 2 >
Ответить в эту темуОткрыть новую тему
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 

- Текстовая версия | Версия для КПК Сейчас: 28.3.2024, 12:19
Designed by Nickostyle