Ищу любую инфу по алгоритму определения карты местности.

[Dremalka]

Здравствуйте!
Решил немного встряхнуть свои серые клеточки.
Хочу научить своего бота самому строить карту окружающей местности. Т.е. методом проб и ошибок выяснить расположение различных препятствий. И потом уже использовать эту карту при дальнейших передвижениях бота. Интересно послушать мысли и идеи подобных реализаций. Мое представление пока очень тупое и прямолинейное. Наверняка есть более изящные решения. Бот (хотя таковым я его не считаю) ингеймовский.
Собственно вопрос. Поделитесь, пожалуйста, ресурсами на которых обсуждают подобные вопросы. Желательно с расчетом, что обсуждения будут понятны среднему, в плане образования, человеку. :)

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

[Мегазадрот]

Такая задумка осуществима.
Я полтора года не играл и не копался в коде, поэтому могу что-то напутать. Так как я еще не искал адреса своих прежних находок для новой версии клиента игры, подкидываю идею как с помощью IDA быстро найти адрес функции с помощью, которой можно исследовать мир.
Как эту функцию отыскать:
1) Находишь обработчик нажатия левой кнопки мыши по миру. Я уже нашел ее адрес: 0x0047ECD0;
2) Смысл кода между 0x0047ECD0 и 0x0047ECD0 – преобразование координат мыши (x; y) в координаты векторов Location(x, y, z) и Direction(x, y, z). Location – это координаты «видеокамеры смотрящей на игровой мир», Direction – направление на точку куда сделан был клик.
3) Инструкция
0047EDD5 0A4 FF 12 call dword ptr [edx]
Вызывает сложную цепь событий в которой ищется точка пересечения найденного вектора с поверхностями трех видов: ландшафтом (земля, горы, вода), недвижимыми объектами (дома, стены), движимыми объектами (НИПы, чары, мобы). Где-то в этих недрах и находится функция с прототипом:
bool GetVectorCrosspoint( //Возвращает true, если есть пересечение, false если нет
__in__ CVector * Location, //Начало
__in__ CVector * Direction, //Направление (возможно единичный вектор)
__out__ CVector * CrossPoint, //Точка пересечения
__out__ CVector * CrossAnglePoint, //Угол к поверхности в точке пересечения (единичный вектор)
...) //Возможно есть еще какие-то параметры

С помощью IDA можно ее отыскать. Сам я этой функцией не пользуюсь, а искать снова велосипед неохота. У меня есть более мощная магия)))
Вот несколько примеров:

[Мегазадрот]

"Тыкаясь" этой функцией во все стороны можно получить информацию о препятствиях вокруг чара и построить сетку проходимости. Рекомендуется не двигаться во время «тыканья». Координаты Location должны быть в пределах видимости чара.

[Smertig]

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

[Dremalka]

Отлично!
Мой вопрос не был воспринят, как слишком извращенный. :)
Спасибо, Мегазадрот. Я даже не думал, что в игре есть подобная реализация. Некий аналог "зрения" у перса.
Я же исходил из того, что у бота есть только осязание и нет зрения. Но есть феноменальная память. Т.е. планировал его в "неизвестной" области двигать в различные стороны и анализировать изменение значений координат.

Если во время движения перс уткнулся в стену, то координаты не меняются, но точка назначения еще не достигнута.
Если достиг обрыва и свалился вниз, то зафиксировал резкий перепад по оси Z.

Таким образом, набивая шишки, перс будет анализировать и складывать в свою базу координаты с какой-либо информацией о соседних координатах. В дальнейшем, по сохраненным данным перс сможет строит путь от точки А, до точки Б. Это как минимум. Но ведь функционал можно нарастить. Во время исследований анализировать мобов и их характеристики. Накладывать на карту местности и строить путь с учетом левела, злобности и прочих характеристик мобов и уровня перса. Либо наоборот искать нужных мобов по какому-либо квесту.
Обязательно возьму этот способ на вооружение. Спасибо.

Smertig, я предполагал, что карта высот уже давно найдена и используется. Если бы я писал бота с целью фарма, сбора статистики по котам и прочее, то конечно же не занимался подобной фигней, что хочу реализовать сейчас. :) А хочется именно малость ненормальное. Попробовать создать бота, который не имея изначальных данных сам их добудет и в дальнейшем сможет использовать.

[Smertig]

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

То есть бот будет вручную создавать карту высот, а смысл? Только время терять

Цитата: Я даже не думал, что в игре есть подобная реализация. Некий аналог "зрения" у перса.

Конечно, есть. Игра написана на движке Angelica 3D, а в каждом графическом игровом движке есть основные функции, в том числе и та, которую описал Мегазадрот

[Dremalka]

Цитата: Сообщение от Smertig То есть бот будет вручную создавать карту высот, а смысл? Только время терять

На счет потери времени, то наверно соглашусь. Практического выхлопа из затеи никакого.
Захотелось чего-то необычного. Решил написать Скайнет.

[Мегазадрот]

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

На счет «большой памяти». Надо на весь мир от (-3072; -4608; 0) до (3072; 4608; 780) создать огромный массив ячеек проходимости. Каждая ячейка проходимости – кубик пространства размером 1*1*1. Ячейка может принимать значения "проходимая", если внутри только пустота и "непроходимая", если внутри что-то есть. Дальше облететь весь мир, исследуя его сегментами по 64*64*64 ячейки. Core 2 Duo 8400 исследует сегмент 64*64*64 в реальном времени, 128*128*128 – 50 секунд. Результаты сохранять в файл.

Оббегать пешочком местность – идея, которая должна сразу вызывать скепсис. Данные о мобах лучше всего скачивать и парсить напрямую с pwdatabase.

Кстати, где-нибудь есть в ТЕКСТОВОМ ВИДЕ база данных о скиллах и бафах (что бы удобно было загонять в массив). Что бы не только название и ID, но и характеристики скилла/бафа, времена подготовки, применения, перезарядки и инфа о накладываемых бафах/дебафах.

Было бы круто что бы для «Укуса» и т.п. также что-то говорилось о значении вызываемой агрессии.

Добавлено через 20 минут
Кстати, в игре появился новый автопуть. Сколько нового за полтора года... Буду сейчас проверять его надежность.

Добавлено через 24 минуты
А что за карта высот, дайте ссылку пожалуйста.

[Smertig]

Цитата: А что за карта высот, дайте ссылку пожалуйста.

[Ссылки могут видеть только зарегистрированные пользователи. ]
Очень полезная тема. Пост #7 про карту высот

[Мегазадрот]

Мда... новый автопуть сильно пошатнул продвинутость моей магии... И как быстро он работает по земле на большие расстояния!!!! Молодцы, китайцы! Одно утешение: он пока не так совершенен:

1) Стоя у южной стены в городе драконов, если кликнуть автопуть за стену, то получитя удивительная траектория...

2) Обход препятствий во время полета/плавания не реализован.... Хотя это в 100500 раз проще, чем прокладывать путь по земле....

3) Прыжки не реализованы... Запрыгивание/перепрыгивание длинных стен пока невозможно....

Теперь, я думаю, дру и мисты в таком большом колличестве не летают...

[Dremalka]

Цитата: Сообщение от Мегазадрот На счет «большой памяти». Надо на весь мир от (-3072; -4608; 0) до (3072; 4608; 780) создать огромный массив ячеек проходимости....... Оббегать пешочком местность – идея, которая должна сразу вызывать скепсис........

Да, согласен. И ее изучение займет приличное время. Вся карта будет занимать большой объем. Но, почему бы не сделать по аналогии с людьми? Если среднестатистический человек не будет за всю свою жизнь в Антарктиде, то и незачем ему знать подробную карту материка. Он лучше всего будет знать ближайшие районы своего города. А если все же попадет на Антарктиду, то тогда потратит некоторое время на изучение карты, т.к. это стало для него намного важнее, чем в прошлом.
Такой вариант имеет право на существование? :)