0 / 0 / 0
Регистрация: 07.03.2017
Сообщений: 4
1

Навигация в пошаговой игре

07.03.2017, 21:06. Показов 1216. Ответов 7
Метки ии (Все метки)

Author24 — интернет-сервис помощи студентам
Навигация в пошаговой игре

Создаю пошаговую игру. Минимальная единица времени – тик. Персонаж может передвинуться на соседнюю клетку за 1 тик, но после этого он некоторое время должен бездействовать (время
бездействия зависит от направления движения (после передвижения по диагонали время бездействия больше)). Персонаж на данном изображении бездействует 9 тиков после движения на 1 клетку не по диагонали или 13 тиков после движения по диагонали. Таким образом на перемещение (вместе с бездействием) не по диагонали тратится 10 тиков, а по диагонали – 14. Персонаж управляется компьютером. Надо чтобы он пришел в определённую точку или подошёл вплотную к определённому объекту (в данном случае к синему кристаллу), минуя препятствия (в данном случае – деревянную стену рядом с персонажем) и после этого быть готовым к следующему действию (т. е. подождать, пока закончится вынужденная задержка после последнего перемещения) за максимально короткое время. При наличии одинаковых по времени прохождения маршрутов выбирается случайный из них.
Подскажите, пожалуйста, как это сделать, чтобы это не было слишком ресурсоёмко, т. к. таких персонажей будет много.


Навигация в пошаговой игре

У меня есть одна идея: на каждой клетке отмечается минимальное время движения из неё до цели (или до клетки рядом с целевым объектом). Делается это так: на целевой клетке или клетках отмечается 0, на соседних с них не по диагонали – 10, по диагонали – 14, затем для клеток с наименьшими метками, не окружённых помеченными клетками, все соседние с ней не по диагонали клетки помечаются числами на 10 больше, затем непомеченные клетки, соседствующие с ними по диагонали, помечаются числами на 14 больше. В результате эти клетки становятся окружёнными помеченными клетками. Затем снова находятся клетки с наименьшими метками, не окруженные помеченными клетками, и процесс повторяется до тех пор, пока персонаж не будет окружен помеченными клетками (пример на 2-й картинке (до конца рисовать лень)). Затем персонаж перемещается на клетку с наименьшей меткой (по возможности не по диагонали). Затем, если персонаж становится не окружён помеченными клетками, клетки продолжают помечаться по вышеописанному алгоритму, пока персонаж снова не будет окружён ими. Это повторяется, пока персонаж не придёт в точку назначения.
Укажите, пожалуйста на ошибки, если они есть и по возможности подскажите менее ресурсоёмкий вариант (тогда ошибки можно не указывать).
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.03.2017, 21:06
Ответы с готовыми решениями:

Игра на время в пошаговой онлайн игре. Как учесть пинг и пр.?
Всем привет! Ситуация такая: делаем онлайн игру. Для простоты будем считать что нарды. Процесс...

Сделать программу для навигация в игре
Добрый день, Играю в MMO RPG ArcheAge. Скриншот из игры: Хотел бы сделать небольшую...

Ошибка 0x000000101 , при игре 10 минутной игре в Dota 2, CS:GO
Имя события проблемы: BlueScreen Версия ОС: 6.1.7600.2.0.0.256.48 Код языка: 1049 ...

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

7
639 / 515 / 73
Регистрация: 20.09.2014
Сообщений: 3,336
08.03.2017, 06:28 2
Изучайте динамическое программирование. Основная идея заключается в том, что в подобного рода задачах бот должен "жить текущим моментом". То есть каждое свое текущее оптимальное действие выбирает таким образом, исходя из того, что предыдущие действия тоже были оптимальные.
Вроде то самое, что Вы изобрели. Только у Вас вроде небольшой недочет: в соседних клетках рядом с целевой должны быть не нули, а числа 10, 14.
1
Модератор
Эксперт функциональных языков программирования
3048 / 2190 / 459
Регистрация: 26.03.2015
Сообщений: 8,465
08.03.2017, 12:32 3
Лучший ответ Сообщение было отмечено SilvianDev как решение

Решение

Используйте A*
1
Эксперт .NET
11991 / 8317 / 1266
Регистрация: 21.01.2016
Сообщений: 31,319
08.03.2017, 12:38 4
SilvianDev, давным давно, когда деревья были большими, а пиво не одавало помоями (не так сильно как сейчас), я писал одну стратегическую игрушку в жанре RTS и тоже озадачивался с алгоритмами поиска пути. Открытием для меня тогда оказался алгоритм волновой трассировки. Он хоть и не шибко производительный и память ему нравится кушать, но маршруты он находил безошибочно и самые короткие.
1
0 / 0 / 0
Регистрация: 07.03.2017
Сообщений: 4
08.03.2017, 16:38  [ТС] 5
Mikhaylo, тут нет ошибки, т. к. целевые клетки - это не кристалл (туда пройти нельзя), а клетки рядом с ним
0
Модератор
Эксперт функциональных языков программирования
3048 / 2190 / 459
Регистрация: 26.03.2015
Сообщений: 8,465
08.03.2017, 17:24 6
Если клеток с препятствиями существенно меньше, чем свободных, и сами препятствия "ровные", то возможна дополнительная оптимизация:
Вычислить "узловые" точки - напротив выпуклых углов фигур-препятствий. (Если квадратик под человечком на рисунке не мешает ему пойти по диагонали направо-вниз, то на каждый угол препятствия будет две узловые точки.) Искать путь не по клеткам поля, а по узловым точкам.
Это имеет смысл, если узловых точек существенно меньше, чем клеток на поле.

Добавлено через 3 минуты
На рисунке будет 6 узловых точек. Маршрут человечка будет состоять из трёх отрезков (через две узловые точки). Вычисляться будет быстрее, чем маршрут по клеткам. Такой подход особенно выгоден, когда положение человечка задаётся с точностью до пикселя (то есть, каждый пиксель является клеткой).
0
0 / 0 / 0
Регистрация: 07.03.2017
Сообщений: 4
08.03.2017, 19:52  [ТС] 7
Shamil1, а чтобы определить выпуклые углы препятствия надо действовать по принципу "Если рядом с блоком(не по диагонали) находится 0 блоков, 1 блок или 2 блока не с противоположных сторон, то это выпуклый угол"?

Добавлено через 3 минуты
Ещё, если стену можно сломать, то можно сделать так: узловые точки отмечаются на всех клетках рядом со стенами, время прохождения между ними будет = время на уничтожение стены + время на прохождение, или тогда лучше прокладывать по клеткам?

Добавлено через 25 минут
Shamil1, в случае с узловыми точками h(x) = расстояние по прямой?
0
Модератор
Эксперт функциональных языков программирования
3048 / 2190 / 459
Регистрация: 26.03.2015
Сообщений: 8,465
08.03.2017, 23:48 8
Лучший ответ Сообщение было отмечено SilvianDev как решение

Решение

Цитата Сообщение от SilvianDev Посмотреть сообщение
в случае с узловыми точками h(x) = расстояние по прямой?
h(x) вычисляется точно также - как расстояние при отсутствии препятствий:
(dx - dy) + 1.4 * dy, где dx и dy - это разница между координатами точек, и dx > dy

Цитата Сообщение от SilvianDev Посмотреть сообщение
или тогда лучше прокладывать по клеткам?
вероятно, так
иначе, каждая точка рядом с препятствием становится узловой
но надо оценить, исходя из того, какие бывают конфигурации поля
Если считать по клеткам, то все клетки будут узлами графа, который Вы обходите. Если по узловым точкам, то все узловые точки + точки отправления и назначения. Узловых точек будет меньше, но нужно ещё вычислить рёбра (в Вашем случае это может быть очень сложно... сходу не могу сказать, насколько корректно будет просто проверять прямую видимость). Поэтому вариант с узловыми точкам стоит рассматривать только, если их существенно меньше.

Цитата Сообщение от SilvianDev Посмотреть сообщение
а чтобы определить выпуклые углы препятствия надо действовать по принципу "Если рядом с блоком(не по диагонали) находится 0 блоков, 1 блок или 2 блока не с противоположных сторон, то это выпуклый угол"?
Да. И все пустые клетки рядом с этим блоком будут узловыми точками.

Добавлено через 7 минут
Я тут подумал, что, возможно, в Вашем случае два "минуса" могут компенсировать друг друга. При подходе с узловыми точками не нужно вычислять рёбра, а просто удлинять путь в соответствии с количеством блоков, через которые проходит прямой путь между ними.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.03.2017, 23:48
Помогаю со студенческими работами здесь

Алгоритм пошаговой игры
Добрый вечер) Возник вопрос по реализации какого-либо пошагового поединка в игре, например 2х2 или...

Окошко пошаговой отладки
Окошко, в котором при пошаговой отладке выводятся значения переменных и т.п. куда-то исчезло, а вот...

IAR проблемы пошаговой отладки
Версия 6.70.2 Оптимизация для всего проекта = none// не заходит в некоторые процедуры в...

начал разбираться в пошаговой отладке. и ?
Вообщем после пятого шага вылетает на это окно дальше если продолжаю жать f11 меняется только...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru