Русское сообщество по скриптингу

Алгоритм выбора оптимального пути по WayPoint для бота

Статьи или фрагменты кода для новичков и уже опытных скриптеров по AMXX.

Модератор: Chuvi

Правила форума
1. Запрещено материться и оскорблять других участников форума.
2. Запрещен флуд, оффтоп, дабл постинг во всех разделах форума, кроме раздела "Болтовня".
3. Запрещено взламывать сайт/форум или наносить любой вред проекту.
4. Запрещено рекламировать другие ресурсы.
5. Запрещено создавать темы без информативного названия. Название темы должно отображать ее смысл.

В данном разделе форума разрешено создавать темы, касающие только обучающему материалу по AMX Mod X.

Алгоритм выбора оптимального пути по WayPoint для бота

Сообщение trololost » 14 фев 2014, 02:50

Привет!

Очень грустно, но мне надоел скриптинг. А хотелось блин заниматься разработкой магазина для JailBreak. И чтобы мои труды не остались лишь в планах, решил выложить часть своей работы по разработке Саймон-Бота для JailBreak. Идея была в том, что будет некий Бот, который будет командовать(заранее сделанные записи) и проверять реакцию игроков на данные команды. В общем позволит держать ваш сервер в Тонусе, когда достойных Ведущих нету.

В процессе разработки сталкивался с разного рода задачами, но самым интересным и запоминающимся на мой взгляд стала разработка алгоритма выборки оптимального пути по точкам WayPoint.

[align=center]
Point.png
[/align]

Сначала на карте задавались "ключевые точки" - это повороты и точки, через которые постоянно ходят игроки. По скрину видно, что все точки взаимосвязаны друг с другом, а значит нужно будет задавать массив связи точек друг с другом(далее массив Сети).

Потом необходимо будет создать массив, который будет хранить значения минимального количества шагов от точки старта (пр. на скрине точка 1) до точки финиша(пр. точка 59) Этот массив назовем "массивом цены".

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


[pawn]
  1. public Cmd_Search(id){

  2.         new s_Value[2],s_Value2[2], PointStart, PointFinish

  3.         read_argv(1,s_Value,sizeof(s_Value))

  4.  
[/pawn]
Получаем из консоли стартовую точку для поиска
[pawn]
  1.  

  2.         PointStart=str_to_num(s_Value)

  3.         read_argv(2,s_Value2,sizeof(s_Value2))

  4.  
[/pawn]
;Получаем конечную точку для поиска
[pawn]
  1.  

  2.         PointFinish=str_to_num(s_Value2)

  3.         new i

  4.         for(i=1; i<=511; i++) {g_ArrayCost[i]=0;g_CompletePatch[i]=0;}

  5.  
[/pawn]
; Обнуляем массив цены и массив готового пути
[pawn]
  1.         g_MaxSearch1=0

  2. ;Переменная, в которой хранится число запусков функции 1го этапа поиска

  3.         g_MaxSearch2=0

  4. ;Тоже самое, но для второго этапа поиска

  5.  
[/pawn]
[pawn]
  1.  

  2.         g_ArrayCost[PointStart]=-1

  3. ;Помечаем стартовую точку значением -1, чтобы не дергать эту точку вновь.

  4.         g_FlagEndSearch = 1

  5. ; Переменная принимает Значение 0, когда поиск закончен.

  6.         function_search(PointStart, 1, PointStart)

  7. ;Запускаем первую функцию поиска

  8.         function_search2(PointStart, 0, PointStart, PointFinish )

  9.  ;Запускаем вторую функцию поиска

  10. }
[/pawn]

g_MaxSearch1 и g_MaxSearch1 были необходимы по большей части для отладки задачи и проверки сложности алгоритма.

[pawn]
  1. g_ArrayCost[PointStart]=-1
[/pawn] - необходимо было пометить стартовую точку, чтобы при обходе всего графа(сети Вейпоинт точек) можно было пропустить эту точку.

Далее идет запуск 1й функции поиска. Он необходим для того, чтобы найти минимальное количество шагов от 1й точки до последней. Принимает 3 аргумента:
1й: номер текущей рассматриваемой точки
2й: номер шага
3й: Что является "родителем" для текущей рассматриваемой точки(грубо говоря какая точка была предыдущей, чтобы ее не рассматривать более).
[pawn]
  1. function_search(PointStart, 1, PointStart)
[/pawn]

Вот так выглядит сама функция заполнения массива цены значениями:
[pawn]
  1. public function_search(point, step, header){

  2.  g_MaxSearch1+=1 ;Увеличим число входов в эту функцию

  3.  new i

  4.  for(i=1; i<=5; i++){  ;У меня был максимум в 5 ветвей у одного WayPointa

  5.    if(g_PointNet[point][i]==-1 || g_PointNet[point][i]==header ||g_PointNet[point][i]==0) continue; #УСЛОВИЕ1

  6.  

  7.     if(g_ArrayCost[g_PointNet[point][i]]==0 || g_ArrayCost[g_PointNet[point][i]]>step) {

  8.        g_ArrayCost[g_PointNet[point][i]]=step ; #УСЛОВИЕ2

  9.        function_search(g_PointNet[point][i], step+1, point)

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

  11.                 }

  12.         }

  13. }
[/pawn]
#Условие 1:
Проверяем несколько значений. 1-Является ли точка рассматриваемая ветви "точкой старта". 2-Является ли она "родителем". 3-Вообще существует ли такая ветвь у данной точки?
#Условие 2: Ну здесь думаю все понятно, проверка: Если точка рассматриваемой ветви еще не посещалась или значение в ней больше текущей "цены", то мы должны обновить это значение

Все это хорошо, вот мы нашли цену шагов от точки старта до точки финиша, но путь то у нас не построен. Теперь необходимо найти этот самый путь. Что мы делаем?
У нас есть в g_ArrayCost[PointFinish] Минимальное число ходов, за которое можно добраться из точки старта до точки финиша. Поэтому мы должны вновь пройтись из стартовой точки по сети точек до финишной , но так, чтобы получилось это сделать за известное количество шагов.

[pawn]
  1. public function_search2(point, step, header, PointFinish){

  2.  g_MaxSearch2+=1 ; Число входов для функции поиска №2

  3.  new i

  4.  for(i=1; i<=5; i++){ ;тоже самое, обходим все 5 ветвей

  5.     if(point==PointFinish && step==g_ArrayCost[PointFinish]) {g_FlagEndSearch=0; break;}  ; #УСЛОВИЕ1

  6.     if(point!=PointFinish && step==g_ArrayCost[PointFinish])  break ; #УСЛОВИЕ2

  7.     if(g_PointNet[point][i]==-1 || g_PointNet[point][i]==header || g_PointNet[point][i]==0) continue ; #УСЛОВИЕ3

  8.  

  9.     if(g_ArrayCost[g_PointNet[point][i]]<=step) continue

  10.         ;Если мы уже смотрели этот элемент, то пропустим его

  11.     if(g_FlagEndSearch==0) return

  12.         ;Если вдруг значение уже было найдено, а функция не завершена, то закончим ее

  13.     g_CompletePatch[step+1]=g_PointNet[point][i]

  14.         ;Ну и наконец помечаем, что этот элемент на текущий момент является наиболее подходящим для нас                         

  15.     function_search2(g_PointNet[point][i], step+1, point, PointFinish)

  16. ;Продолжаем поиск

  17.                 }

  18. }
[/pawn]
#Условие 1: Если текущая точка является конечной и число шагов = минимальному найденному, то ставим флаг окончания поиска и завершаем текущий цикл
#Условие 2: Если текущая точка НЕ равна конечной, но число шагов исчерпано, то завершаем цикл
#Условие 3:  Если рассматриваемая ветвь является стартовой точкой или родительной или ее не существует, то пропустим

И наконец результат можно посмотреть с помощью вот такой функции:

[pawn]
  1. public function_result(PointFinish){

  2.         new i

  3.         for(i=1; i<=g_ArrayCost[PointFinish]; i++)

  4.                 client_print(0, print_chat, "g_CompletePatch[%d]=%d, coord[0]=%d", i, g_CompletePatch[i], g_PointOrigin[g_CompletePatch[i]][0]  )

  5.                 for(i=1; i<=g_ArrayCost[PointFinish]; i++)  server_print("g_CompletePatch[%d]=%d", i, g_CompletePatch[i])

  6.                 for(i=1; i<=512; i++)  if(g_ArrayCost[i]!=0) server_print("g_ARRAYCOST[%d]=%d", i, g_ArrayCost[i])

  7.                 server_print("====================")

  8.                 server_print("g_MaxSearch1=%d, g_MaxSearch2=%d", g_MaxSearch1, g_MaxSearch2)

  9. }
[/pawn]

Ее комментировать я не буду, ибо считаю тут должно быть все понятно.
Убедился что на сайте очень сложно понять весь код из-за узкой ширины поста, копируйте в исходник, понять суть на самом деле не очень сложно.
[Не принимаю заказы]
Аватара пользователя
trololost
 
Сообщения: 923
Зарегистрирован: 05 ноя 2011, 02:25
Благодарил (а): 104 раз.
Поблагодарили: 358 раз.

Re: Алгоритм выбора оптимального пути по WayPoint для бота

Сообщение straus » 14 фев 2014, 08:12

Ку а платно обучением не маешься?
могу помочь в скриптинге.
п.с.
кто бы мне помог))
Аватара пользователя
straus
 
Сообщения: 62
Зарегистрирован: 13 фев 2014, 10:38
Забанен
Благодарил (а): 17 раз.
Поблагодарили: 15 раз.
Опыт программирования: Около 3 месяцев
Языки программирования: Counter-Strike 1.6

Re: Алгоритм выбора оптимального пути по WayPoint для бота

Сообщение trololost » 15 фев 2014, 02:53

straus писал(а):Ку а платно обучением не маешься?


Нет. Уже нет.
[Не принимаю заказы]
Аватара пользователя
trololost
 
Сообщения: 923
Зарегистрирован: 05 ноя 2011, 02:25
Благодарил (а): 104 раз.
Поблагодарили: 358 раз.

Re: Алгоритм выбора оптимального пути по WayPoint для бота

Сообщение crash94 » 15 фев 2014, 11:23

Я нихрена не понял :-D
Но статья зачет
Аватара пользователя
crash94
 
Сообщения: 683
Зарегистрирован: 25 фев 2010, 16:34
Забанен
Благодарил (а): 80 раз.
Поблагодарили: 317 раз.

Re: Алгоритм выбора оптимального пути по WayPoint для бота

Сообщение quckly » 13 янв 2015, 18:52

Может проще было использовать более удобный язык для представления графов (например с++), и использовать готовый алгоритм нахождения кратчайшего пути в графе?
Аватара пользователя
quckly
Скриптер
 
Сообщения: 403
Зарегистрирован: 20 ноя 2009, 10:03
Благодарил (а): 41 раз.
Поблагодарили: 243 раз.
Опыт программирования: Около 6 месяцев
Языки программирования: Counter-Strike 1.6


Вернуться в Статьи / фрагменты кода

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 8