2Д Игра Долгая дорога домой: Поиск пути

[s-andriano]

Сообщение от Arigato

Классический вариант рекурсивного поиска пути вообще ничего не отсекает, он проходит по всем доступным клеткам.

Я не знаю, что такое "классический вариант", могу лишь заметить, что вариант с рекурсией в принципе не может являться не только оптимальным, но даже близким к оптимальному.
Причины этому, минимум, две:
1. Реализация: вариант с очередью/стеком намного эффективнее, причем сразу с нескольких сторон: как по используемой памяти, так и по вычислительным ресурсам. А на современных суперскалярных процессорах разница еще больше возрастает.
2. Алгоритмически: для данной задачи оптимальнее вариант с очередью, а рекурсия безальтернативно подразумевает только стек.

PS. Вообще мне кажется неверным привязываться к какой-либо "классической" реализации, которая когда-то была опубликована автором исключительно в демонстрационных целях.
Основное - идея алгоритма. Я, например, не называю алгоритм своим именем, хотя и изобрел его самостоятельно, причем именно в оптимальной реализации - с очередью и без рекурсии. А называю алгоритмом Дейкстры - исключительно потому, что до основной идеи Дейкстра додумался раньше меня.

[intmain]

А на современных суперскалярных процессорах разница еще больше возрастает.

Кста, а этот алгоритм поиска можно потом под многоядерность заточить ?
Там вроде нужно чтобы куски памяти рабочей области не использовались разными потоками одномоментно, и один главный рулил дочерними нитками ? Как это вообще может быть представлено в многоядерной реализации?
Вот тебе Ваня кусок карты и иди на лево! И вот тебе Петя тоже кусок карты иди на право! Младший вообще идет лесом! А их батя обоих с колокольни мониторит и кричит куда идти и идти ли при этом не допускает их встречи иначе работа встанет ??

Я, например, не называю алгоритм своим именем, хотя и изобрел его самостоятельно

А вот и зря. Я вот тоже от природы скромный, но всегда все называю своим, даже если это не я придумал )

[Arigato]

s-andriano, хотелось бы на вашу реализацию глянуть.

На счет моей реализации, то могут быть и плохие ситуации, когда потребуется обойти почти все клетки. То есть я не говорю, что алгоритм оптимален, просто проведена оптимизация одного из самых примитивных алгоритмов (не знаю, есть ли у него какое-то официальное название). Но при желании еще есть над чем работать.

P.S. На счет имени, то я его своим именем не называл, в коде комментарий указывает на то, что "Алгоритм реализовал Arigato", а не разработал. Не исключаю, что реализованные идеи были кем-то раньше уже опробованы.

[intmain]

Не исключаю, что реализованные идеи были кем-то раньше уже опробованы.

Алгоритм реализовал Arigato

Не надо скромничать, ну вот не надо, а надо называть вещи своими именами.
1. Рекурсивный алгоритм поиска пути от Arigato. (C)(tm)(R) (Year).
И всем все понятно. Кто не согласен см. п1.

[s-andriano]

Сообщение от intmain

Кста, а этот алгоритм поиска можно потом под многоядерность заточить ?

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

А вот и зря. Я вот тоже от природы скромный, но всегда все называю своим, даже если это не я придумал )

Как сказать...
Когда я изобретал алгоритмы, И-нета у меня не было, а бумажная литература была в большом дефиците. Не говоря о том, что ни в одном учебном заведении в нашей стране подобные алгоритмы не изучали.
Сегодня же - "изобретательность" скорее свидетельствует о недостатках образования и неумением пользоваться поиском.
Так что палка о двух концах.

[s-andriano]

Сообщение от Arigato

s-andriano, хотелось бы на вашу реализацию глянуть.

Ну, это зависит от того, насколько хочется.
Код, как я уже говорил, был написан во времена 100-166 МГц процессоров. В принципе, я барахольщик и ничего не выбрасываю, а также не допускаю непреднамеренной потери данных.
Но по этой же причине найти что-то в старых архивах - дело не совсем простое.
Алгоритм был написан на Ассемблере с развернутыми циклами и "заточен" под конкретную задачу (опять же, для обеспечения максимальной производительности), так что возможность адаптировать его на более общий случай - под вопросом.
В общем, если это действительно интересно (т.е. больше, чем просто любопытно), то поищу, но это займет некоторое время.

PS. Да, еще: алгоритм умышленно не отсекался после нахождения пути. Во-первых, при различной проходимости клеток вполне возможна ситуация, когда содержащий большее количество клеток путь может оказаться намного короче. А во-вторых, мне нужно было все поле, чтобы при "пролете" мышки над каждым квадратом сразу было видно расстояние (переопределялся курсор мыши) .

[intmain]

Как сказать...
Когда я изобретал алгоритмы, И-нета у меня не было, а бумажная литература была в большом дефиците.

Тогда, вы счастливчик вам посчастливилось использовать по назначению гораздо больше нервных клеток, в отличие от современных гугло-копи-пасто-шарпо-программистов. Вы преобрели коллосальный опыт, а гугло-копи-пасто-шарпо-программер лишь отчативает нажатие клавишь ctrl+с, ctrl-v.

был написан во времена 100-166 МГц процессоров

Жсть, но вроде бы в те времена на них бодренько бегал и Квейк2, боты там вроде тоже умные были бегали как путёвые по путям. И винда 95 / 98 летала и даже не в бсод, а просто.

Если первое, то во втором нет никакой необходимости.

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

[Arigato]

s-andriano, ну если сложно найти, да и реализация специфическая, то не надо утруждаться
Основная идея моей реализации - уменьшить количество проходов по неправильным клеткам, чтобы они все лежали недалеко от идеального пути. Не всегда, но зачастую это удается. Волновой же алгоритм в общем случае просмотрит все клетки в некотором радиусе. Вот, кстати, неплохой онлайн тест алгоритма: http://suvitruf.ru/2012/05/13/1176/ Видно, что он выдает хуже результат, чем у меня.

[s-andriano]

Сообщение от intmain

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

Процессор в подсказках не нуждается. Он работает по алгоритму.
И - никакой самостоятельности.
Могу только повториться, пытаться распараллелить конкретный алгоритм и пытаться решить задачу за минимальное время - далеко не одно и то же.
Любое распараллеливание требует дополнительных ресурсов, причем, нередко бывает, что объем этих ресурсов превосходит выигрыш от распараллеливания.
Что касается алгоритма Дейкстры, то для интересных с точки зрения практики случаев IMHO может представлять интерес пускать его однопоточную версию в разных потоках для разных юнитов.

[Пепел Феникса]

шарпо-программистов.

у вас комплекс по поводу шарпа?
хотите об этом поговорить?