|
Движение к точке в платформере
| |
| LunarPixel | Дата: Четверг, 16 Августа 2012, 15:30 | Сообщение # 1 |
старожил
Сейчас нет на сайте
| Приветствую всех. 
Сразу к делу: есть локация, состоящая из блоков. Есть герой, которому нужно самостоятельно добраться до указанной точки. Движение по прямой (через ямы и преграды) реализовывается элементарно, а вот если точка располагается на высоте, на отдельной платформе, то тут возникают проблемы. Например, нужно пробежать вперед, запрыгнуть на платформу, весящую в воздухе, с ней запрыгнуть на другую платформу и пробежать по ней в обратном направлении. Реализовал одним способом, но он больно уж медленно работает. Собственно, какие у вас есть решения данной задачи?
Может хоть раз получу ответ на свой вопрос по ГМ. 
Спасибо.
|
|
|
| |
| Нохчи | Дата: Четверг, 16 Августа 2012, 15:35 | Сообщение # 2 |
|
заслуженный участник
Сейчас нет на сайте
| Судя по описанию, самое разумное запрограммировать передвижение героя по чекпоинтам.
Многие вопросы по Windows отпадут, если посмотреть тут
Сообщение отредактировал Нохчи - Четверг, 16 Августа 2012, 15:36 |
|
|
| |
| LunarPixel | Дата: Четверг, 16 Августа 2012, 15:58 | Сообщение # 3 |
|
старожил
Сейчас нет на сайте
| Нохчи, от части так и сделано сейчас. Только вот точка, к которой нужно идти, не постоянная, однозначного пути не выстроить, потому чекпоинты расставлены во всех точках изменения направления движения, от чекпоинта к чекпоинту ведется расчет достижения точки, идет контроль направления по которому нужно двигаться, проверяется ближайший к герою чекпоинт в этом направлении, и в зависимости от обстановки происходит то или иное действие.
Загвоздка ещё в том, что не только точка-цель может меняться, но и сама локация не постоянная. Следовательно, сразу расставить все чекпоинты нельзя, сейчас у меня проверяется вся локация, после её загрузки и в нужных местах ставятся чекпоинты. В общем, все весьма трудоемко. Думаю вот над альтернативами.
Сообщение отредактировал LunarPixel - Четверг, 16 Августа 2012, 16:00 |
|
|
| |
| Нохчи | Дата: Четверг, 16 Августа 2012, 16:11 | Сообщение # 4 |
|
заслуженный участник
Сейчас нет на сайте
| Немного не понял, генерируем карту, любым алгоритмом поиска пути находим путь к точке, расставляем чекпоинты. Это не должно нести какой-либо существенной нагрузки, в чем загвоздка?
Многие вопросы по Windows отпадут, если посмотреть тут
Сообщение отредактировал Нохчи - Четверг, 16 Августа 2012, 16:12 |
|
|
| |
| LunarPixel | Дата: Четверг, 16 Августа 2012, 16:33 | Сообщение # 5 |
|
старожил
Сейчас нет на сайте
| Нохчи, проблема в том, что путь нужно найти исходя из правил платформера, т.е. по доступному для героя пути (учитывая высоту и длину, на которую он может прыгнуть). Сейчас чекпоинты расставляются не по найденному пути, а на всех возможных разветвлениях движения. Следовательно, если карта большая и разветвлений таких очень много, то... сам понимаешь )
Пока писал это сообщение, наткнулся на ещё одну мысли ) но все равно рассмотрю все предложенный варианты. Можно на словах сформулировать ваш принцип алгоритма поиска.
|
|
|
| |
| Archido | Дата: Четверг, 16 Августа 2012, 16:52 | Сообщение # 6 |
Сэнсэй
Сейчас нет на сайте
| А окружение полностью статическое? Т.е. платформы не двигаются?
Есть такая мысль автогенерации:
Вот на картинке есть синие клетки - клетки карты на которых можно стоять, им стоит присвоить уникальный ID. Персонаж, как я понимаю, умеет прыгать вправо\влево и просто двигаться аналогично, т.е. 4 варианта движения у него.
Так вот, можно перед стартом игры "эмулировать" действия этого перса, ставив его в каждую уникальную клетку карты и выполняя вышеприведенные действия (прыг влево, шажок вправо и т.д.). Таким образом можно определить с какой клетки можно попасть на какую-то другую и с помощью какого действия, при этом можно добавить сюда учет веса (чем больше клеток за "действие" можно преодолеть, тем больше вес для этого действия), чтобы наиболее короткий маршрут выбирать.
В итоге мы знаем как из одной клетки попасть в другую, нужно лишь связать все это вместе - и получится вообщем-то готовый граф, в котором можно выполнять "нахождение маршрута между вершинами" при любой стартовой и конечной позиции.
C++ - он особенный. С помощью него можно не только выстрелить себе в ногу, но и повеситься в пустой комнате:)
|
|
|
| |
| LunarPixel | Дата: Четверг, 16 Августа 2012, 17:00 | Сообщение # 7 |
|
старожил
Сейчас нет на сайте
| Archido, при большом количестве блоков, на большой локации, такой вариант, думаю, тоже будет весьма затратным. Сейчас сделана, по сути, похожая система, только проверяется не каждый блок, а установленный в определенных местах чекпоинты. И так же известно, каким действием с одного чекпоинта можно попасть на другой, и каким должен быть следующий чекпоинт, чтобы добраться до цели.
|
|
|
| |
| Нохчи | Дата: Четверг, 16 Августа 2012, 17:02 | Сообщение # 8 |
|
заслуженный участник
Сейчас нет на сайте
| Зачем эмулировать? Правила известны заранее, мы знаем на какие блоки можно попасть с любого другого. Далее описываем карту графом и применяем любой алгоритм поиска пути. Это всё стандартно и описано уже тыщу раз. Это надо делать всего один раз при генерации уровня.
Или я чего-то в упор не понимаю.
Многие вопросы по Windows отпадут, если посмотреть тут
Сообщение отредактировал Нохчи - Четверг, 16 Августа 2012, 17:03 |
|
|
| |
| Archido | Дата: Четверг, 16 Августа 2012, 17:04 | Сообщение # 9 |
|
Сэнсэй
Сейчас нет на сайте
| Quote (Нохчи) мы знаем на какие блоки можно попасть с любого другого
Откуда мы это знаем?
Quote (LunarPixel) при большом количестве блоков, на большой локации, такой вариант, думаю, тоже будет весьма затратным
При очень большой да, может задуматься  . Но зато 100% процесс автоматический.
Нет возможности делать его 1 раз после создания карты и сохранять в файл? После чего таскать его с собой и быстро загружать в игру.
И да, затраты только до начала игры - поиск по графу весьма быстр.
C++ - он особенный. С помощью него можно не только выстрелить себе в ногу, но и повеситься в пустой комнате:)
Сообщение отредактировал Archido - Четверг, 16 Августа 2012, 17:14 |
|
|
| |
| FirestorM | Дата: Четверг, 16 Августа 2012, 17:06 | Сообщение # 10 |
Блэк-программист
Сейчас нет на сайте
| Кхм. Карта генерируется сама случайным образом? Нет? Расставляй точки, где надо прыгать ручками.
Все твои игры говно, ты ничего не умеешь и тебе незачем жить, пока ты не доказал обратного.
|
|
|
| |
| ЭтоЧудоИзЧудес | Дата: Четверг, 16 Августа 2012, 17:08 | Сообщение # 11 |
заслуженный участник
Сейчас нет на сайте
| Quote (FirestorM) Кхм. Карта генерируется сама случайным образом? Нет? Расставляй точки, где надо прыгать ручками.
Quote (LunarPixel) Загвоздка ещё в том, что не только точка-цель может меняться, но и сама локация не постоянная.
Велосипед никто не купил. Зол. Скоро начну рвать и метать.
|
|
|
| |
| FirestorM | Дата: Четверг, 16 Августа 2012, 17:09 | Сообщение # 12 |
|
Блэк-программист
Сейчас нет на сайте
| Блжад. Чувствую себя кротом.
Все твои игры говно, ты ничего не умеешь и тебе незачем жить, пока ты не доказал обратного.
|
|
|
| |
| Нохчи | Дата: Четверг, 16 Августа 2012, 17:14 | Сообщение # 13 |
|
заслуженный участник
Сейчас нет на сайте
| Quote (Archido) Откуда мы это знаем?
Есть простые правила, которые регламентируют как должны распологаться блоки относительно друг-друга, чтобы можно было считать их смежными в графе. Есть какие-то трудности?
Многие вопросы по Windows отпадут, если посмотреть тут
|
|
|
| |
| LunarPixel | Дата: Четверг, 16 Августа 2012, 17:17 | Сообщение # 14 |
|
старожил
Сейчас нет на сайте
| Нохчи, да нет, ты все правильно понимаешь. По сути, у меня так и сделано (ибо это все описано уже тыщу раз), только алгоритм поиска импровизированный ) просто мне важна быстрая загрузка, а при большой локации загрузка притормаживает (в момент формирования вершин графа). Меня интересуют альтернативные варианты, если таковые есть )
Quote (Archido) Нет возможности делать его 1 раз после создания карты и сохранять в файл?
Вот это, кстати, вариант. Если ничего лучше не придумается, то, пожалуй, так и сделаю.
|
|
|
| |
| Archido | Дата: Четверг, 16 Августа 2012, 17:44 | Сообщение # 15 |
|
Сэнсэй
Сейчас нет на сайте
| Quote (Нохчи) Есть простые правила, которые регламентируют как должны распологаться блоки относительно друг-друга, чтобы можно было считать их смежными в графе. Есть какие-то трудности?
Мм, ну тогда весь вопрос алгоритма в том, как эти близжайшие блоки быстро определять. А как насчет такого маршрута? :
Quote (LunarPixel) Вот это, кстати, вариант. Если ничего лучше не придумается, то, пожалуй, так и сделаю
Так обычно и делается , в играх всегда навигационные данные единственный раз считают, а потом быстро загружают. Поэтому если само "передвижение" по этим данным не тормозит и ошибок не делает, то выбор очевиден
C++ - он особенный. С помощью него можно не только выстрелить себе в ногу, но и повеситься в пустой комнате:)
Сообщение отредактировал Archido - Четверг, 16 Августа 2012, 17:59 |
|
|
| |
| LunarPixel | Дата: Четверг, 16 Августа 2012, 18:19 | Сообщение # 16 |
|
старожил
Сейчас нет на сайте
| Quote (Archido) Мм, ну тогда весь вопрос алгоритма в том, как эти близжайшие блоки быстро определять.
Ну мы получаем граф из всех возможных доступных путей и по этим путям ищем кратчайший до цели. С этим все понятно, у меня по похожему принципу сейчас и работает.
Quote (Archido) Так обычно и делается , в играх всегда навигационные данные единственный раз считают, а потом быстро загружают. Поэтому если само "передвижение" по этим данным не тормозит и ошибок не делает, то выбор очевиден
Тут просто есть ещё один подводный камушек, связанный с самой системой, которую я делаю... Дополнительные сторонние файлы не очень желательны
У меня такого нет, но как быть, если локация изменяется случайным образом, динамически, непосредственно во время игрового процесса!?
|
|
|
| |
| Archido | Дата: Четверг, 16 Августа 2012, 18:51 | Сообщение # 17 |
|
Сэнсэй
Сейчас нет на сайте
| Quote (LunarPixel) Ну мы получаем граф из всех возможных доступных путей и по этим путям ищем кратчайший до цели
Не, это то понятно. Интересно как раз таки - как определять эти самые возможные доступные пути вообще и наиболее эффективно.
Вот как определить, что с одного блока можно запрыгнуть на другой? Или в определенном месте можно запрыгнуть на какой-то блок? Или, что можно спрыгнуть с блока на большой высоте - пролететь некоторое пространство и приземлиться на другой. Вот как на картинке в №15. Такое нормально отработает? Мне именно сам процесс построения "доступных путей" интересен
Quote (LunarPixel) Тут просто есть ещё один подводный камушек, связанный с самой системой, которую я делаю... Дополнительные сторонние файлы не очень желательны
Вообще, можно записать сначала в файл, а потом особым образом содержимое файла записать в ехе файл (или как файл ресурсов). Но скорее всего, в ГМ так нельзя делать . А с чем, если не секрет, связаны такие ограничения?
Quote (LunarPixel) У меня такого нет, но как быть, если локация изменяется случайным образом, динамически, непосредственно во время игрового процесса!?
. Но это, видимо, смотря как изменяется.
Если, что-то разрушается - то соответственные этому вершины графы удаляются и маршрут будет выбираться из других возможных.
Если это какие - нибудь движущиеся платформы, то в их движении обычно всегда присутствует цикличность, что дает возможность заранее это дело рассчитать.
А вот при добавлении чего либо и в следствиии появления новых возможных маршрутов - это уже сложный вопрос , но потенциально быстро кое-какие места пересчитать может и реально
C++ - он особенный. С помощью него можно не только выстрелить себе в ногу, но и повеситься в пустой комнате:)
Сообщение отредактировал Archido - Четверг, 16 Августа 2012, 18:52 |
|
|
| |
| LunarPixel | Дата: Четверг, 16 Августа 2012, 19:13 | Сообщение # 18 |
|
старожил
Сейчас нет на сайте
| Quote (Archido) А с чем, если не секрет, связаны такие ограничения?
Ну, скажем так, все это дело будет работать с сетью.
Quote (Archido) Но это, видимо, смотря как изменяется.
Ну изменяется, так сказать, по полной.. случайным образом и как попало.
С описанным алгоритмом все понятно, но вопрос открыт, есть ли альтернативные решения?!
|
|
|
| |
| Saladin | Дата: Четверг, 16 Августа 2012, 22:46 | Сообщение # 19 |
заслуженный участник
Сейчас нет на сайте
| Может я сейчас глупость скажу или кто-то уже это предлагал, мне кажется этот вариант идейно верным.
Берем встроенный в гм астар. Оставляем свободными для просчета на сетке только те ячейки, которые находятся выше блоков, чем ограничиваем путь "по земле".
Далее просто запускаем генерацию пути и двигаем персонажа по узлам пути. Если точка находится на одном уровне с персонажем - двигаемся прямо, если выше - запускаем скрипт прыжка. Это поиск пути рабоает довольно шустро и задержек быть не должно даже если считать путь не при старте комнаты а в любой игровой момент.
Анбаннэд. Хэлоу эгин =)
|
|
|
| |
| Нохчи | Дата: Четверг, 16 Августа 2012, 23:31 | Сообщение # 20 |
|
заслуженный участник
Сейчас нет на сайте
| Quote (Archido) Мм, ну тогда весь вопрос алгоритма в том, как эти близжайшие блоки быстро определять.
Так я же говорю
Quote (Нохчи) Это надо делать всего один раз при генерации уровня.
определять нужно лишь один раз, дальше можно хоть в файл сохранить, хоть еще куда-то. Весь разговор о том, что эмулировать движения перса не обязательно, если "правила" наши не меняются по ходу игры конечно.
Многие вопросы по Windows отпадут, если посмотреть тут
Сообщение отредактировал Нохчи - Четверг, 16 Августа 2012, 23:31 |
|
|
| |
|
