Очень грустно, но мне надоел скриптинг. А хотелось блин заниматься разработкой магазина для JailBreak. И чтобы мои труды не остались лишь в планах, решил выложить часть своей работы по разработке Саймон-Бота для JailBreak. Идея была в том, что будет некий Бот, который будет командовать(заранее сделанные записи) и проверять реакцию игроков на данные команды. В общем позволит держать ваш сервер в Тонусе, когда достойных Ведущих нету.
В процессе разработки сталкивался с разного рода задачами, но самым интересным и запоминающимся на мой взгляд стала разработка алгоритма выборки оптимального пути по точкам WayPoint.
[align=center] [/align]
Сначала на карте задавались "ключевые точки" - это повороты и точки, через которые постоянно ходят игроки. По скрину видно, что все точки взаимосвязаны друг с другом, а значит нужно будет задавать массив связи точек друг с другом(далее массив Сети).
Потом необходимо будет создать массив, который будет хранить значения минимального количества шагов от точки старта (пр. на скрине точка 1) до точки финиша(пр. точка 59) Этот массив назовем "массивом цены".
Последний массив, который нам понадобится - массив пути, именно туда мы запишем имена Вейпоинтов, которые нужно будет преодолеть для того чтобы дойти до нужной точки.
[pawn]
- public Cmd_Search(id){
- new s_Value[2],s_Value2[2], PointStart, PointFinish
- read_argv(1,s_Value,sizeof(s_Value))
Получаем из консоли стартовую точку для поиска
[pawn]
- PointStart=str_to_num(s_Value)
- read_argv(2,s_Value2,sizeof(s_Value2))
;Получаем конечную точку для поиска
[pawn]
- PointFinish=str_to_num(s_Value2)
- new i
- for(i=1; i<=511; i++) {g_ArrayCost[i]=0;g_CompletePatch[i]=0;}
; Обнуляем массив цены и массив готового пути
[pawn]
- g_MaxSearch1=0
- ;Переменная, в которой хранится число запусков функции 1го этапа поиска
- g_MaxSearch2=0
- ;Тоже самое, но для второго этапа поиска
[pawn]
- g_ArrayCost[PointStart]=-1
- ;Помечаем стартовую точку значением -1, чтобы не дергать эту точку вновь.
- g_FlagEndSearch = 1
- ; Переменная принимает Значение 0, когда поиск закончен.
- function_search(PointStart, 1, PointStart)
- ;Запускаем первую функцию поиска
- function_search2(PointStart, 0, PointStart, PointFinish )
- ;Запускаем вторую функцию поиска
- }
g_MaxSearch1 и g_MaxSearch1 были необходимы по большей части для отладки задачи и проверки сложности алгоритма.
[pawn]
- g_ArrayCost[PointStart]=-1
Далее идет запуск 1й функции поиска. Он необходим для того, чтобы найти минимальное количество шагов от 1й точки до последней. Принимает 3 аргумента:
1й: номер текущей рассматриваемой точки
2й: номер шага
3й: Что является "родителем" для текущей рассматриваемой точки(грубо говоря какая точка была предыдущей, чтобы ее не рассматривать более).
[pawn]
- function_search(PointStart, 1, PointStart)
Вот так выглядит сама функция заполнения массива цены значениями:
[pawn]
- public function_search(point, step, header){
- g_MaxSearch1+=1 ;Увеличим число входов в эту функцию
- new i
- for(i=1; i<=5; i++){ ;У меня был максимум в 5 ветвей у одного WayPointa
- if(g_PointNet[point][i]==-1 || g_PointNet[point][i]==header ||g_PointNet[point][i]==0) continue; #УСЛОВИЕ1
- if(g_ArrayCost[g_PointNet[point][i]]==0 || g_ArrayCost[g_PointNet[point][i]]>step) {
- g_ArrayCost[g_PointNet[point][i]]=step ; #УСЛОВИЕ2
- function_search(g_PointNet[point][i], step+1, point)
- ;и если мы это сделали, значит нужно вновь попробовать пройтись через эту точку для поиска минимальной цены точек ее окружающих
- }
- }
- }
#Условие 1:
Проверяем несколько значений. 1-Является ли точка рассматриваемая ветви "точкой старта". 2-Является ли она "родителем". 3-Вообще существует ли такая ветвь у данной точки?
#Условие 2: Ну здесь думаю все понятно, проверка: Если точка рассматриваемой ветви еще не посещалась или значение в ней больше текущей "цены", то мы должны обновить это значение
Все это хорошо, вот мы нашли цену шагов от точки старта до точки финиша, но путь то у нас не построен. Теперь необходимо найти этот самый путь. Что мы делаем?
У нас есть в g_ArrayCost[PointFinish] Минимальное число ходов, за которое можно добраться из точки старта до точки финиша. Поэтому мы должны вновь пройтись из стартовой точки по сети точек до финишной , но так, чтобы получилось это сделать за известное количество шагов.
[pawn]
- public function_search2(point, step, header, PointFinish){
- g_MaxSearch2+=1 ; Число входов для функции поиска №2
- new i
- for(i=1; i<=5; i++){ ;тоже самое, обходим все 5 ветвей
- if(point==PointFinish && step==g_ArrayCost[PointFinish]) {g_FlagEndSearch=0; break;} ; #УСЛОВИЕ1
- if(point!=PointFinish && step==g_ArrayCost[PointFinish]) break ; #УСЛОВИЕ2
- if(g_PointNet[point][i]==-1 || g_PointNet[point][i]==header || g_PointNet[point][i]==0) continue ; #УСЛОВИЕ3
- if(g_ArrayCost[g_PointNet[point][i]]<=step) continue
- ;Если мы уже смотрели этот элемент, то пропустим его
- if(g_FlagEndSearch==0) return
- ;Если вдруг значение уже было найдено, а функция не завершена, то закончим ее
- g_CompletePatch[step+1]=g_PointNet[point][i]
- ;Ну и наконец помечаем, что этот элемент на текущий момент является наиболее подходящим для нас
- function_search2(g_PointNet[point][i], step+1, point, PointFinish)
- ;Продолжаем поиск
- }
- }
#Условие 1: Если текущая точка является конечной и число шагов = минимальному найденному, то ставим флаг окончания поиска и завершаем текущий цикл
#Условие 2: Если текущая точка НЕ равна конечной, но число шагов исчерпано, то завершаем цикл
#Условие 3: Если рассматриваемая ветвь является стартовой точкой или родительной или ее не существует, то пропустим
И наконец результат можно посмотреть с помощью вот такой функции:
[pawn]
- public function_result(PointFinish){
- new i
- for(i=1; i<=g_ArrayCost[PointFinish]; i++)
- client_print(0, print_chat, "g_CompletePatch[%d]=%d, coord[0]=%d", i, g_CompletePatch[i], g_PointOrigin[g_CompletePatch[i]][0] )
- for(i=1; i<=g_ArrayCost[PointFinish]; i++) server_print("g_CompletePatch[%d]=%d", i, g_CompletePatch[i])
- for(i=1; i<=512; i++) if(g_ArrayCost[i]!=0) server_print("g_ARRAYCOST[%d]=%d", i, g_ArrayCost[i])
- server_print("====================")
- server_print("g_MaxSearch1=%d, g_MaxSearch2=%d", g_MaxSearch1, g_MaxSearch2)
- }
Ее комментировать я не буду, ибо считаю тут должно быть все понятно.
Убедился что на сайте очень сложно понять весь код из-за узкой ширины поста, копируйте в исходник, понять суть на самом деле не очень сложно.