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