Патчфинд 3.0 - Страница 2 - Форум администраторов игровых серверов
Форум администраторов игровых серверов StormWall - Защита от DDos атак
Регистрация Мнения Справка Пользователи Календарь Все разделы прочитаны
Вернуться   Форум администраторов игровых серверов > MMO > Lineage II > Работа с геодатой

Работа с геодатой Разработка и правка Геодаты для ява серверов.
Описание темы:Зис дистанс, зис дисолюшен

Ответ
Опции темы
Непрочитано 24.12.2013, 20:36   #11
Аватар для rage
Герой

По умолчанию Re: Патчфинд 3.0

Цитата:
Сообщение от Pointer*Rage Посмотреть сообщение
Зачем это делать, если можно использовать за основу эвристику? Ее реализацию я описал в начале топика: использование событийной архитектуры.
Боюсь по затратам памяти и проца это будет не выгодно. К тому же при построении пути нету инфы о наличии двери в конкретной клетке. Это плюсом еще оверхед на хранение этой инфы.
К тому же это не "эвристика". Эвристика, это если бы ваш алгоритм предсказывал, что в момент прохождения клетки персонажем дверь в этой клетке будет закрыта.
rage вне форума Ответить с цитированием
Непрочитано 24.12.2013, 23:36   #12
Аватар для n3k0nation
Antihero

Автор темы (Топик Стартер) Re: Патчфинд 3.0

Цитата:
Сообщение от rage Посмотреть сообщение
Боюсь по затратам памяти и проца это будет не выгодно. К тому же при построении пути нету инфы о наличии двери в конкретной клетке.
Как раз именно этот вариант будет выгоден, в отличие от Вашего, где бессмысленно и беспощадно, мы, условно, чекаем путь каждый тик.

Цитата:
Сообщение от rage Посмотреть сообщение
К тому же при построении пути нету инфы о наличии двери в конкретной клетке.
Эта вся информация у нас опять же есть. Если мы наложим граф проходимости на граф расположения игровых объектов, то получим... Я это уже все описывал в первом посте, под названием "коллизии".

Цитата:
Сообщение от rage Посмотреть сообщение
Это плюсом еще оверхед на хранение этой инфы.
В каком месте у нас возникнет оверхед? На хранение доп. ссылок точек, которые изменили свое состояние? Не смешите, Вы сами знаете сколько занимает в памяти, ссылка, а не объект. На хренение самого метода в области перма? - Вообще бред, пара килобайт не добавит оверхеда, в данном случае, это не микроконтроллер в условиях ограниченных ресурсов.

Цитата:
Сообщение от rage Посмотреть сообщение
К тому же это не "эвристика". Эвристика, это если бы ваш алгоритм предсказывал, что в момент прохождения клетки персонажем дверь в этой клетке будет закрыта.
В данном случае, это эвристика, рекомендую более плотно ознакомиться с понятием "эвристический поиск пути".
__________________
m0nster.art - clear client patches, linkz to utils & code.
Гадаю по капче.
n3k0nation вне форума Ответить с цитированием
Непрочитано 25.12.2013, 07:53   #13
Аватар для rage
Герой

По умолчанию Re: Патчфинд 3.0

Цитата:
Сообщение от Pointer*Rage Посмотреть сообщение
Как раз именно этот вариант будет выгоден, в отличие от Вашего, где бессмысленно и беспощадно, мы, условно, чекаем путь каждый тик.
Ну да, конечно. Проверить NSWE у уже выбранной клетки несравнимо более затратная операция, чем накладывать графы, вычислять пересечения, хранить списки и бегать по ним с нотифями, да еще все это в многопоточной среде. К тому же если посмотреть как игроки бегают, они кликают по 10 кликов в сек. А если это режим фаллоу так ваще сказка, сколько раз в сек мы путь перестраиваем...

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

Цитата:
Сообщение от Pointer*Rage Посмотреть сообщение
Эта вся информация у нас опять же есть. Если мы наложим граф проходимости на граф расположения игровых объектов, то получим... Я это уже все описывал в первом посте, под названием "коллизии".
ок, вы хотите сказать, что эта операция дешевле чем чекнуть NSWE у клетки?

Цитата:
Сообщение от Pointer*Rage Посмотреть сообщение
В каком месте у нас возникнет оверхед? На хранение доп. ссылок точек, которые изменили свое состояние? Не смешите, Вы сами знаете сколько занимает в памяти, ссылка, а не объект. На хренение самого метода в области перма? - Вообще бред, пара килобайт не добавит оверхеда, в данном случае, это не микроконтроллер в условиях ограниченных ресурсов.


В данном случае, это эвристика, рекомендую более плотно ознакомиться с понятием "эвристический поиск пути".
Именно на хранение списков и бегание по этим спискам в конкурентной среде.

Подписание пути на уведомление должна быть синхронизированная операция, что уже не дешево. Список должен быть потокобезопасным, а это значит, что либо итерироваться по нему нужно будет из синхроблока либо копировать используя какойнить CopyOnWriteArrayList. Опять же, не дешевые операции. Учитывая то, что построенные пути живут не долго, в среднем пару сек. Все это видится мне крайне сомнительным.

В прочем не исключаю возможность эффективной работы данного алгоритма, это легко проверить. Есть уже реализация? Можно было бы сравнить производительность.
rage вне форума Ответить с цитированием
Непрочитано 27.12.2013, 22:18   #14
Аватар для rage
Герой

По умолчанию Re: Патчфинд 3.0

Еще один минус "уведомлений" о закрытие двери и т.д. это то, что нам нужно знать закрыта конкретная клетка для прохода или нет непосредственно в момент когда мы на нее хотим переместиться. Так как за то время пока мы добежим до двери она может и открыться. И следовательно, уведомления которые пришли раньше просто бесполезны.
rage вне форума Ответить с цитированием
Непрочитано 12.01.2014, 18:00   #15
Аватар для n3k0nation
Antihero

Автор темы (Топик Стартер) Re: Патчфинд 3.0

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

Цитата:
Сообщение от rage Посмотреть сообщение
Ну да, конечно. Проверить NSWE у уже выбранной клетки несравнимо более затратная операция, чем накладывать графы, вычислять пересечения, хранить списки и бегать по ним с нотифями, да еще все это в многопоточной среде. К тому же если посмотреть как игроки бегают, они кликают по 10 кликов в сек. А если это режим фаллоу так ваще сказка, сколько раз в сек мы путь перестраиваем...
Что мешает не перестраивать полностью путь, если новая точка назначения рядом с предыдущей? Достаточно просто достроить путь и прогнать сглаживание, причем можно делать его только в два прохода, ибо основной путь уже сглажен.
Для стрелок вообще должны предлагаться другие алгоритмы поиска пути, то что мы имеем сейчас никуда не годиться.


Цитата:
Сообщение от rage Посмотреть сообщение
К тому же сколько клеток попадают в двери относительного общего количества клеток? Сколько путей пролегает через двери относительно общего количества построенных путей? Дело конечно ваше, но я бы посмотрел на такой двиг в плане быстродействия
Проверить ссылку на нулевой адрес памяти конечно очень затратная операция, много больше, чем вытаскивать двери из таблицы региона, а потом еще и искать нужную


Цитата:
Сообщение от rage Посмотреть сообщение
ок, вы хотите сказать, что эта операция дешевле чем чекнуть NSWE у клетки?
Мы не просто чекаем NSWE у клетки, а строим прямую с проверкой NSWE у всех ее точек. И да, проверить нулевую ссылку, а потом булеан значение двери будет таки медленее, но не сильно, в любом случае мы всего лишь потратим на один такт больше, что в данном случае бесконечно малая нагрузка


Цитата:
Сообщение от rage Посмотреть сообщение
Именно на хранение списков и бегание по этим спискам в конкурентной среде.

Подписание пути на уведомление должна быть синхронизированная операция, что уже не дешево. Список должен быть потокобезопасным, а это значит, что либо итерироваться по нему нужно будет из синхроблока либо копировать используя какойнить CopyOnWriteArrayList. Опять же, не дешевые операции. Учитывая то, что построенные пути живут не долго, в среднем пару сек. Все это видится мне крайне сомнительным.
Маловероятно, что в одной точке будет более 5-ти событий одновременно.
Зачем нам глобальные нотификаторы? Нам нужны только для точек, не более.

Цитата:
Сообщение от rage Посмотреть сообщение
В прочем не исключаю возможность эффективной работы данного алгоритма, это легко проверить. Есть уже реализация? Можно было бы сравнить производительность.
К сожалению сейчас нет времени работать над прототипом, возможно реализую ближайшие месяца, как будет время, тогда уже можно будет говорить о практической эффективности, ну а пока будем рассуждать только по теоритической части

Цитата:
Еще один минус "уведомлений" о закрытие двери и т.д. это то, что нам нужно знать закрыта конкретная клетка для прохода или нет непосредственно в момент когда мы на нее хотим переместиться. Так как за то время пока мы добежим до двери она может и открыться. И следовательно, уведомления которые пришли раньше просто бесполезны.
Да, такая проблема есть, по идее нужно реализовать жесткую остановку задачи "перепоиска" пути, при этом сохранять старый путь.
__________________
m0nster.art - clear client patches, linkz to utils & code.
Гадаю по капче.
n3k0nation вне форума Ответить с цитированием
Ответ

Метки
генерация, геодата, патчфинд, поиск пути


Здесь присутствуют: 1 (пользователей: 0 , гостей: 1)
 
Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход


© 2007–2020 «Форум администраторов игровых серверов»
Защита сайта от DDoS атак — StormWall
Работает на Булке неизвестной версии с переводом от zCarot
Текущее время: 17:58. Часовой пояс GMT +3.

Вверх