Что нового

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

Notum

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

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

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

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

Буду благодарен советами и примерами.
 
Автор
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,600
Репутация
940
Тут не подойдет стандартный массив, но подойдет структура ноды. Тоесть каждая ячейка массива у тебя будет нести информацию о том с какими ячейками еще она соприкасается. И обрабатывая эти ноды ты сможешь строить свой маршрут. Если одно поле длиннее другого тебе можно использовать алгоритм дийкстры или же упрощенные его гибрид с волновым алгоритмом - A*. Суть тут идет не о "стандартной ММО" а об алгоритме в целом, тот же волновой алгоритм у тебя сработает на ура для генерации маршрута через карты.
 
Автор
N

Notum

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

Belfigor

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

Belfigor

Модератор
Локальный модератор
Сообщения
3,600
Репутация
940
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,600
Репутация
940
Что мы имеем:
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,600
Репутация
940
Ахда, я нету ячейку закрасил в мире A => пошаговая развертка алгоритма описанная выше справедлива только для мира A и не справедливо для миров B и C. Но этот алгоритм спокойно подходит для мира B и прекрасно масштабируется для мира C. Считайте условия миров B и C как уроки на самоподготовку.
 
Верх