Патчфинд 3.0

[rage]

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

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

[n3k0nation]

Боюсь по затратам памяти и проца это будет не выгодно. К тому же при построении пути нету инфы о наличии двери в конкретной клетке.

Как раз именно этот вариант будет выгоден, в отличие от Вашего, где бессмысленно и беспощадно, мы, условно, чекаем путь каждый тик.

К тому же при построении пути нету инфы о наличии двери в конкретной клетке.

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

Это плюсом еще оверхед на хранение этой инфы.

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

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

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

[rage]

Как раз именно этот вариант будет выгоден, в отличие от Вашего, где бессмысленно и беспощадно, мы, условно, чекаем путь каждый тик.

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

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

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

ок, вы хотите сказать, что эта операция дешевле чем чекнуть NSWE у клетки?

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


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

Именно на хранение списков и бегание по этим спискам в конкурентной среде.

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

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

[rage]

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

[n3k0nation]

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

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

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

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

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

ок, вы хотите сказать, что эта операция дешевле чем чекнуть NSWE у клетки?

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

Именно на хранение списков и бегание по этим спискам в конкурентной среде.

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

Маловероятно, что в одной точке будет более 5-ти событий одновременно.
Зачем нам глобальные нотификаторы? Нам нужны только для точек, не более.

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

К сожалению сейчас нет времени работать над прототипом, возможно реализую ближайшие месяца, как будет время, тогда уже можно будет говорить о практической эффективности, ну а пока будем рассуждать только по теоритической части

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

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