алгоритм обхода препятсвий
| |
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 |
старожил
Сейчас нет на сайте
| теперь я понимаю откуда беруца проекты которые спустя год разработки выглядят как будто кто-то вчера создал пустой юнити проект и перетащил на сцену террейн и 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, там вроде встроенная физика была, а может и нет кароче, не подскажу, нету опыта с браузерками)
|
|
| |
|