Среда, 24 Апреля 2024, 06:51

Приветствую Вас Гость

[ Новые сообщения · Игроделы · Правила · Поиск ]
  • Страница 1 из 1
  • 1
Форум игроделов » Программирование » Общие обсуждения программистов » алгоритм обхода препятсвий (пример алгоритма для похода препятствий)
алгоритм обхода препятсвий
kr0n4ikДата: Воскресенье, 24 Сентября 2017, 21:37 | Сообщение # 1
был не раз
Сейчас нет на сайте
вообщем загорелся идей написать рпг с сервером. возникла проблема. как обходить препятствия.
SaiteiДата: Воскресенье, 24 Сентября 2017, 21:50 | Сообщение # 2
старожил
Сейчас нет на сайте
Почитай про алгоритм поиска пути А* (A star), например
drcrackДата: Воскресенье, 24 Сентября 2017, 21:57 | Сообщение # 3
старожил
Сейчас нет на сайте
Не читай про А*, лучше потрать свое время непосредственно на разработку
Есть готовые решения по поиску путей, не надо изобретать велосипед:
C++ https://github.com/recastnavigation/recastnavigation
C# https://github.com/Robmaister/SharpNav


Сообщение отредактировал drcrack - Воскресенье, 24 Сентября 2017, 21:58
SaiteiДата: Воскресенье, 24 Сентября 2017, 22:19 | Сообщение # 4
старожил
Сейчас нет на сайте
drcrack, прежде чем использовать, полезно бы узнать как это работает.
drcrackДата: Воскресенье, 24 Сентября 2017, 23:16 | Сообщение # 5
старожил
Сейчас нет на сайте
Не согласен)
Полезно родить прототип как можно быстрее, чтобы было с чем дальше работать
Теоретические знания алгоритмов поиска путей никак не ускорят появление прототипа, а даже замедлят, при этом никак не улучшив его качество

Какие-то архитектурные решения, направленные на ускорение разработки, в дальнейшем приведут к проблемам и потребуют много времени на рефакторинг
Но только не это
Ведь поиск путей это по сути простейший интерфейс с несколькими методами типа FindPath(Vector3 start, Vector3 end)
Вся логика инкапсулирована внутри реализации и никак не влияет на остальной код
Нет никаких проблем в будущем заменить ее на другую библиотеку или что-то свое
И соответственно нет никаких причин пытаться щаз во всем разобраться и сразу сделать идеально


Сообщение отредактировал drcrack - Воскресенье, 24 Сентября 2017, 23:25
OrdanДата: Понедельник, 25 Сентября 2017, 02:58 | Сообщение # 6
Главный зомби
Сейчас нет на сайте
kr0n4ik, с начало лучше уточнить какое именно рпг, поклеточное/свободное/псевдо свободное(мини клеточки)
И уточнить среду разработки или движок.


Цитата недели: Из-за леса, из-за гор, кишки, месиво, хардкор. (Берсерк ТВ-2)

Мои проекты ТЫК
Мои видяхи на ютубэ ТЫК

Если ты споришь с идиотом, вероятно тоже самое делает и он.
Animan2010Дата: Понедельник, 25 Сентября 2017, 04:24 | Сообщение # 7
постоянный участник
Сейчас нет на сайте
drcrack, этот алгоритм крайне прост и фундаментален, есть смысл изучить его хотя бы для того, чтобы понять как использовать и какие данные на вход подавать, а так же какой результат он может выдать. Использовать такие функции как отрисовка или воспроизведение звуков не зная реализации можно, но внедрять в логику игры функции, не зная как они работают - это потеря времени

Anima Games
Animan Publishing
drcrackДата: Понедельник, 25 Сентября 2017, 08:28 | Сообщение # 8
старожил
Сейчас нет на сайте
:D теперь я понимаю откуда беруца проекты которые спустя год разработки выглядят как будто кто-то вчера создал пустой юнити проект и перетащил на сцену террейн и fpscontroller — просто их авторы вместо того чтобы заниматься делом, разбираются в поиске путей
МорриартеДата: Понедельник, 25 Сентября 2017, 12:48 | Сообщение # 9
LINUX ФАНАТ
Сейчас нет на сайте
drcrack, зато на выходе у них получается тот FPS Controller и тот алгоритм, который их устраивает. Я думаю это стоит потерянного времени.
ShortKedrДата: Понедельник, 25 Сентября 2017, 13:41 | Сообщение # 10
Renword Studio
Сейчас нет на сайте
drcrack, те кто разбираются в деталях - делают на выходе шедевры. И у них точно нет стандартных FPSController'ов с чужим кодом. Алгоритм A* настолько прост и понятен, что его можно воспроизвести меньше чем за сутки. Не гоже разработчику не знать как устроен его проект

Добавлено (25 сентября 2017, 13:41)
---------------------------------------------
kr0n4ik, алгоритм A* отлично подойдёт для обхода препятствий. Небольшой пример отличной реализации:https://www.youtube.com/playlist?list=PLFt_AvWsXl0cq5Umv3pMC9SPnKjfp9eGW

VuvkДата: Понедельник, 25 Сентября 2017, 13:44 | Сообщение # 11
заслуженный участник
Сейчас нет на сайте
А мне вот для статичного мира понравился алгоритм Флойда — Уоршелла тем, что все возможные пути просчитываются единожды и хранятся в виде простых матриц.

drcrack, ну знаешь, не все любят доверять чужому коду, если не понимают, что в нём творится.
ShortKedrДата: Понедельник, 25 Сентября 2017, 13:51 | Сообщение # 12
Renword Studio
Сейчас нет на сайте
Vuvk, просчёт статики во время загрузок, запусков и тп - правильное решение. Но всё равно без оптимизированных решений для реалтайма не обойтись в большинстве случаев
drcrackДата: Понедельник, 25 Сентября 2017, 13:52 | Сообщение # 13
старожил
Сейчас нет на сайте
Цитата
Алгоритм A* настолько прост и понятен, что его можно воспроизвести меньше чем за сутки.

Это если у тебя навмеш волшебным образом на сервере генерируется сам
Но ведь по твоей теории в этой теме тоже надо разбираться самому и писать с нуля
А потом оптимизировать, чтобы дотянуть производительность до готовых решений
И вот получится что 2 недели прошло, а игра готова на 0%

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


Сообщение отредактировал drcrack - Понедельник, 25 Сентября 2017, 13:53
HerrPotapovДата: Понедельник, 25 Сентября 2017, 16:10 | Сообщение # 14
заслуженный участник
Сейчас нет на сайте
ShortKedr, в моих проектах обычно десятки сторонних библиотек. Какой смысл мне писать, дебажить, а потом поддерживать мой A*-велосипед (или любой другой), если можно взять готовое решение?
Я согласен с тем что разработчик должен иметь представление об используемых алгоритмах, но очень не согласен с предложением делать все с нуля


Discord: alpotapov#1741

Интервью с разработчиком WarCastle - Читаем и вникаем!
ShortKedrДата: Понедельник, 25 Сентября 2017, 16:59 | Сообщение # 15
Renword Studio
Сейчас нет на сайте
Цитата drcrack ()
Серьезно, в прототипе боты могут бегать просто по прямой через препятствия, зачем время тратить на это вообще
Если уж хочется погрузиться в теорию, лучше озадачиться сетью и синхронизацией, вот это уже реально нужная тема, и выбранный протокол потом заменить будет не так просто.

Хорошее замечание. Но это, как я считаю, вопрос организации последовательности разработки. Нужно начинать всегда с основы, с ядра. Поиск пути это тоже часть этого ядра, но не его центр, начало

Добавлено (25 сентября 2017, 16:51)
---------------------------------------------

Цитата HerrPotapov ()
Я согласен с тем что разработчик должен иметь представление об используемых алгоритмах, но очень не согласен с предложением делать все с нуля

Не обязательно с нуля. Если время не позволяет, или лень делать то, что делал миллион раз, то можно/нужно готовое решение взять, даже своё. Я очень люблю подсистемы своих проектов выделять в отдельные библиотеки, потом очень удобно использовать в проектах

Добавлено (25 сентября 2017, 16:59)
---------------------------------------------

Цитата drcrack ()
Это если у тебя навмеш волшебным образом на сервере генерируется сам
Но ведь по твоей теории в этой теме тоже надо разбираться самому и писать с нуля
А потом оптимизировать, чтобы дотянуть производительность до готовых решений
И вот получится что 2 недели прошло, а игра готова на 0%

Если исполнить всё в соответствии с алгоритмом A*, то и оптимизация почти не нужна будет. Ну а свои заморочки оптимизировать - это другой вопрос уже. Навмеш может быть запечёным в клиенте, а перемещения ботов, других игроков - дело сети. Не вижу проблем в этом. Первый раз всё равно нужно разбираться, если не знаешь, как это работает, что бы потом проблем не возникло
ByurrerДата: Понедельник, 25 Сентября 2017, 17:16 | Сообщение # 16
почетный гость
Сейчас нет на сайте
A* хорошо, сам использую, чрезвычайно прост, эвристика методом Манхеттена вполне сойдет. Многоэтажность поддерживается. Еще можно глянуть алгоритм Дейкстры, тоже интересный подход, в теории с ним знаком, на практике не использовал. Гугли "A* для новичков", первая ссылка.

Добавлено (25 сентября 2017, 17:16)
---------------------------------------------
Если интересует вопрос как поделить пространство и понять где можно ходить, а где нет, тогда посмотри в сторону NavMesh или AI regular grid (сам использую это).


Мой блог - ссылка
Мои проекты:
SkyXEngine - графический 3D движок с real-time рендером
s4g - скриптовый язык программирования
kr0n4ikДата: Понедельник, 25 Сентября 2017, 22:09 | Сообщение # 17
был не раз
Сейчас нет на сайте
Вообще даже не знал, что такие активные пользователи. Очень удивлен.
Смысл такой пишу клиент на js (three.js).
Задумка, есть мир где там объекты (дом, деревья) я их обернул в кубы и персонаж это куб. При столкновении использовал AABB модель, но в место огибания по черной линии, объект прилипает к грани и движется по красной линии
Код

if (
    (
    (this.root.position.x < obj.position.x + 200) &&
    (this.root.position.x > obj.position.x - 200) &&
    (this.root.position.z < obj.position.z + 200) &&
    (this.root.position.z > obj.position.z - 200) )
     ) {
     if (this.root.position.x < obj.position.x + 198 && this.root.position.x > obj.position.x + 180) {
      this.root.position.z += Math.cos(this.root.rotation.y) * 800 * delta;
     }
     if (this.root.position.z > obj.position.z - 198 && this.root.position.z < obj.position.z - 180) {
      this.root.position.x += Math.sin(this.root.rotation.y) * 800 * delta;
     }
     if (this.root.position.x > obj.position.x - 198 && this.root.position.x < obj.position.x - 180) {
      this.root.position.z += Math.cos(this.root.rotation.y) * 800 * delta;
     }
     if (this.root.position.z < obj.position.z + 198 && this.root.position.z > obj.position.z + 180) {
      this.root.position.x += Math.sin(this.root.rotation.y) * 800 * delta;
     }
    } else {
     this.root.position.x += Math.sin(this.root.rotation.y) * 800 * delta;
     this.root.position.z += Math.cos(this.root.rotation.y) * 800 * delta;
    }

Залил на ucoz
My WebPage


Сообщение отредактировал kr0n4ik - Понедельник, 25 Сентября 2017, 22:50
drcrackДата: Вторник, 26 Сентября 2017, 15:04 | Сообщение # 18
старожил
Сейчас нет на сайте
Цитата
то и оптимизация почти не нужна будет.

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

Цитата
Еще можно глянуть алгоритм Дейкстры, тоже интересный подход,

а* находит путь между двумя конкретными вершинами, дейкстра находит пути с одной вершины до всех остальных
иногда это то что нужно, но в большинстве случаев напрасная трата времени

Цитата
Задумка, есть мир где там объекты (дом, деревья) я их обернул в кубы и персонаж это куб. При столкновении использовал AABB модель, но в место огибания по черной линии, объект прилипает к грани и движется по красной линии

не проще ли просто заменить квадраты на круги?

Добавлено (26 сентября 2017, 15:04)
---------------------------------------------
посмотрел код
не вижу никаких попыток как-то учитывать вращение обьектов
все проверки выполняются исходя из предположения что кубы никогда не поворачиваются а только двигаются влево-вправо и вверх-вниз
соответственно, если они поворачиваются, то код перестает работать

как и с поиском путей, советую не изобретать матан с нуля, а взять готовые библиотеки и для линейной алгебры и для столкновений


Сообщение отредактировал drcrack - Вторник, 26 Сентября 2017, 22:23
kr0n4ikДата: Вторник, 26 Сентября 2017, 22:03 | Сообщение # 19
был не раз
Сейчас нет на сайте
ну может подскажите готовую библиотеку или алгоритм
drcrackДата: Вторник, 26 Сентября 2017, 22:39 | Сообщение # 20
старожил
Сейчас нет на сайте
я как-то недельку ковырял babylon.js, там вроде встроенная физика была, а может и нет
кароче, не подскажу, нету опыта с браузерками)
Форум игроделов » Программирование » Общие обсуждения программистов » алгоритм обхода препятсвий (пример алгоритма для похода препятствий)
  • Страница 1 из 1
  • 1
Поиск:

Все права сохранены. GcUp.ru © 2008-2024 Рейтинг