Что нового

[Автоматизация] Реализация карты и переходы по ней

Notum

Новичок
Сообщения
71
Репутация
0
Всем доброго времени суток!

Есть необходимость написать игрового бота для браузерной игрушки. Процесс остановился на реализации карты и перехода по ней. Постараюсь объяснить по подробнее:

Есть локация Поле, в ней есть переход на локации Замок и Луга, на локации Луга есть переход на локации Порт и Лес, в локации Лес, есть переходит на локации Тюрьма и Башня

Задача перейти из любой локации до любой. Функция определения текущего местоположения есть и назовём её GetCurrentMapLocation()

Буду благодарен советами и примерами.
 

zlo-kazan

Скриптер
Сообщения
374
Репутация
100
http://autoit-script.ru/index.php?topic=4375.0
 
Автор
N

Notum

Новичок
Сообщения
71
Репутация
0
zlo-kazan: спасибо за столь быстрый ответ, но вы точно читали то, что я написал? Речь идёт не о классической MMORPG, а о просто браузерной игре. Мне не нужно обходить препятствия, у меня нет непроходимых поверхностей, координатах и т.д.

Я всего лишь хотел узнать о концепции реализации карты по той логике, которую описал выше.
Определение локации, определении вариантов пути, определение куда пути ведут, ведут ли в нужную нам локации и всё.
 

edward_freedom

Осваивающий
Сообщения
200
Репутация
44
Насколько я понял,это игра типа Джагернаут или Двар.Я делал проверку на цвет и бегал по лакациям
 
Автор
N

Notum

Новичок
Сообщения
71
Репутация
0
edward_freedom
Да, что то на подобии этой игры.
Если вы реализовали переход, то как вы описали логику - в какую локацию идти, что бы дойти до нужного места?
 

zlo-kazan

Скриптер
Сообщения
374
Репутация
100
Хоть бы скрины прилепил... или ссылку...
 
Автор
N

Notum

Новичок
Сообщения
71
Репутация
0
Видимо, я как то заумно всё расписал и народ не понял, в чём конкретно я прошу помощи. Нужно помощь в построении логики карты и переходя по ней.

Как я это вижу:

Массив с локациями:
Loc[0] = Loc1
Loc[1] = Loc2
Loc[2] = Loc3 и т.д.

Обозначение перехода из локации в локацию:
Loc1 = Loc5, Loc6, Loc8
Loc2 = Loc3, Loc4, Loc10 и т.д.

Логика:
Определение текущего место положения
Определение какие переходы есть в этой локации
Выбор нужного нам перехода
Переход
Повтор.
 

Belfigor

Модератор
Локальный модератор
Сообщения
3 590
Репутация
938
Тут не подойдет стандартный массив, но подойдет структура ноды. Тоесть каждая ячейка массива у тебя будет нести информацию о том с какими ячейками еще она соприкасается. И обрабатывая эти ноды ты сможешь строить свой маршрут. Если одно поле длиннее другого тебе можно использовать алгоритм дийкстры или же упрощенные его гибрид с волновым алгоритмом - A*. Суть тут идет не о "стандартной ММО" а об алгоритме в целом, тот же волновой алгоритм у тебя сработает на ура для генерации маршрута через карты.
 
Автор
N

Notum

Новичок
Сообщения
71
Репутация
0
Скажу прямо, мало что понял из того, что ты написал, но есть желание разобраться.
Можешь скинуть ссылки на материалы по данным реализациям?
 

Belfigor

Модератор
Локальный модератор
Сообщения
3 590
Репутация
938
Карту мира скинь и я попробую объяснить как приделать туда волновой алгоритм.
 

Belfigor

Модератор
Локальный модератор
Сообщения
3 590
Репутация
938
http://pmg.org.ru/ai/stout.htm#listing1
http://www.mirgames.ru/articles/base/pathfind.html
http://articles.org.ru/cn/showdetail.php?cid=6973
http://filosof.historic.ru/books/item/f00/s00/z0000716/st000.shtml
http://www.loonies.narod.ru/pathfindr.htm
http://www.procoder.info/index.php/all/3/81-path-search
http://robot.paccbet.ru/docs/robot_path.php
http://gamesdevandmath.blogspot.com/2009/08/blog-post.html
http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%BF%D1%83%D1%82%D0%B8
http://www.ai-blog.net/archives/000152.html
http://ru.wikipedia.org/wiki/%D0%90%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B2%D1%8B%D0%B2%D0%BE%D0%B4
 

Belfigor

Модератор
Локальный модератор
Сообщения
3 590
Репутация
938
Что мы имеем:
1) Карта с кружками которую ты мне прислал. Исходный мир
2) Нарисованная мною карта содержащая 3 вариации твоего мира по сути своей каждый из которых является точной копией твоего мира.
3) Жестко заданное условие что если мы перемещаемся в локацию находящуюся дальше чем ближайшие соседствующие локации, мы прежде чем попасть в нужную, пройдем еще Nное количество локаций.

Что нам надо:
Найти путь из пункта А в пункт Б. Полученный путь должен содержать в себе все промежуточные вейпоинты которые встречаются на пути.

Разметка поля (индексирование). В зависимости от того как мы построим нашу логику текущего алгоритма, мы можем индексировать клетки возрастающими числами или уменьшающимися. Если мы индексируем от меньшего к большему то в полученный результат нам придется "переворачивать" ибо в конце мы получим путь не от старта к финишу а от финиша к старту, или же нам придется стартом обозначать пункт куда мы хотим прийти а финишем путь откудова мы начинаем путь.
Или мы используем индексацию от большего числа (старта) к меньшему (финиш) в таком случае пройдя от старта до финишам нам просто надо будет составить путь переходя в ближайшую ячейку хранящую наименьшее значение.

В связи с тем что у нас очень маленький мир я выбрал индексацию с 1000 к 0, тоесть наш бот сможет составить путь длинной не более в 1000 шагов.
Итак, помня как работает волновой алгоритм из этой темы: http://autoit-script.ru/index.php?topic=4375.0
Мы знаем что он идет вширь и просматривает все считаемые возможными для прохождения ячейки до тех пор пока не найдет финиш. Внеся небольшие изменения в код предложенный в вышеуказанной теме, мы сможем индексировать "ключевые вейпоинты" на пути нашего бота.
Итак, нам надо попасть из пункта 1 в пункт 5.
Поиск идет из пункта 1 в пункт 5.
У ячейки 1 будет индекс 1000
1) Алгоритм идет в ширь, видит проходимую клетку но не являющуюся вейпоинтом, индексирует ее числом равным числу той клетки из которой пришел поиск -1 (в нашем случае 1000-1=999)
2 )Идет дальше видит клетку 2 являющуюся проходимой и одновременно вейпоинтом но не целевой точкой. Индексируем эту клетку при этом оставляя метку вейпоинта. (поиск пришел из клетки с индексом 999 => индекс текущей клетки будет равен 998
3) Идем дальше видим 2 проходимых клетки не являющиеся вейпоинтами, индексируем их (Не упускаем из внимание что независимо от того сколько проходимых клеток поиск нашел рядом с той откудова пришел, индекс каждой новой найденной клетки = индекс предыдущей -1, то есть клетка выше 2 так же как и клетка правее 2 будет иметь индекс 998-1=997
4) Идем дальше, видим снова 2 клетки 3 и 6, обе являются вейпоинтами но не являются финишем, индексируем их и оставляем метки вейпоинта. (клетка 3 будет иметь индекс 996, клетка 6 будет так же иметь индекс 996)
Вейпоинт 3 оказался тупиковым, поиск продолжается с вейпоинта 6
5) Идем дальше, видим 3 клетки, все проходимые и ни одна не является вейпоинтом, индексируем (клетка выше 6 будет иметь индекс 995, так же как и клетка правее и ниже клетки 6)
6) Идем дальше, видим 3 клетки, все вейпоинты, ни одна не финишь, делаем тоже что и раньше. (индексы клетки 4 = 8 = 7 = 994
Вейпоинты 7 и 8 оказались тупиковыми, продолжаем поиск с 4-й.
7) видим проходимую клетку не вейпоинт, индексируем (993)
8) Видим клетку, она является вейпоинтом и при этом финишем.

Скрипт проиндексировал путь от старта до финиша. Теперь стартом поиска пути становится клетка 5.
Алгоритм заносит в сферическую переменную "Путь" имя локации: "5"
старт: Ищет среди прилегающих ячеек ячейку с наибольшим индексом (в нашем случае 993) переходим в нее и ищем дальше
993: видим ячейку 994, переходим в нее, т.к. она еще и вейпоинт в переменную "Путь" добавляем им локации "4", ищем дальше
994: видим ячейку с индексом 995, переходим в нее, она не вейпоинт, ищем дальше
995: находим ячейку с индексом 996, переходим, видим что вейпоинт, добавляем в переменную "Путь" имя локации "6", продолжаем осматривать ближайшие ячейки.
996: Мы видим что вокруг ячейки 6 есть 4 ячейки куда можно пойти, но мы помним что нам надо идти в ячейку с наибольшим значением, ячейка выше 6 = 995, ячейка справа 6 = 995, ячейка снизу 6 = 995, ячейка слева 6 = 997. Вот туда то нам и надо, переходим
...
видим ячейку 2 с индексом 998, заносим в переменную "путь" имя текущей локации "2"
...
видим ячейку 1, она является стартом, заносим в переменную "путь" имя текущей локации "1", возвращаем переменную "путь" со значением найденного пути = 12645

Как то так, я не программист, понятнее объяснить не могу

Описанные выше шаги будут справедливы для всех миров A B и С, единственное отличие C от A и B в том что в C будет проделано между вейпоинтами больше промежуточных шагов.
P.S. жду мегатонну репы, я в место того чтобы ходить за пивом рисовал эту карту
 

Belfigor

Модератор
Локальный модератор
Сообщения
3 590
Репутация
938
Ахда, я нету ячейку закрасил в мире A => пошаговая развертка алгоритма описанная выше справедлива только для мира A и не справедливо для миров B и C. Но этот алгоритм спокойно подходит для мира B и прекрасно масштабируется для мира C. Считайте условия миров B и C как уроки на самоподготовку.
 
Верх