Просмотр полной версии : Алгоритм Дейкстры во флеше
Нужна помощь.
Вот уже неделю мучаюсь - надо доделать алгоритм поиска кратчайшего пути по графу. Граф-то строит, а потом при поиске пути чето с массивами не то творится. Посмотрите кто-нибудь. Основная проблема с функцией generalStep()
Исходник прилагается
Хорошо! Сам писал? Если да - уважаю.
graphLinesConstructor у тебя ссылается сам на себя. Образуется какая-то сранная рекурсия. Массив matrix отсутствие пути обозначет как 9999, не проще ли null. За полчаса ничего не нашел. Посижу еще. А вообще - молодец. Я всегда говорил - программинг на AS - круто (хотя некоторые "большие" программеры меня шпыняли)
greyshaman
10.04.2004, 00:31
Мжно вопрос к усатому дядьке не относящийся.
Зачем он тебе нужен?
Толст по определению.
К сожалению в большинстве случаев в AS классика не катит.
Необходимо выводить частныый случай.
К сожалению в большинстве случаев в AS классика не катит.
А вот с этим я бы поспорил.
А кроме того, надо стимулировать производителей :)
greyshaman
10.04.2004, 00:53
попробуй :)
Что попробовать? Поспорить? Что классика в большинсве случаев не катит?
Пожалуйста. Назови мне пример, в еотором классика не прокатывает, плз.
:)
Писал-то сам. Я тут своими флешами всю кафедру экономкибернетики на уши поставил.
Они-то все на делфях да на сях. А я попробовал реализовать волновой алгоритм
(обход препятствий) на AS и получилось. А вот с дейкстрой проблемы какие-то.
Там вроде функция классическая, а с массивом C[],
по которому путь строим какая-то лажа выходит
И кстати 9999 не нулем заменять в дейкстре,
а Positive_Infinity правильнее (нет хода).
И надо бы еще правильно отлавливать момент когда прохода нет вообще
из данной вершины в целевую, т.е. вершина отдельно от графа.
Но сейчас у меня времени в обрез уже этим заняться. Аттестацию по AI и
так поставили. Так что если кто закончит начатое мной буду только рад.
ЗЫ Ну конечно AS для программирования подобных вещей не лучший выбор,
но ведь интересно, блин...
greyshaman
10.04.2004, 01:49
любой алгоритм на n^n
Есть задача, у нее всегда есть частное решение, есть общее
решение. Надо искать частное.
BlooDHounD
10.04.2004, 01:49
Если мне не изменяет память, то, когда я учился в школе (и учил C++), алгоритм, который искал кратчайший путь в графе (про твой я не говорю!), носил имя Флойда.
А пример этокого на Флэше я видел у nuran (http://www.flash.plux.ru/html/rus/flash/other/floid.htm)'а.
greyshaman
10.04.2004, 01:52
Оригинал написал(а) Sh@man
А я попробовал реализовать волновой алгоритм
а пошукать по форуму?
2greyshaman
А я попробовал реализовать волновой алгоритм
Так ведь получилось у человека! А их, т.е. победителей не судят.
А n^n решается. Даже не смотря на 255 ур. рекурсии. При пороге 254 я генерил новую рекурсивную функцию. (я вообще-то в последнее время и сам на Java как суслик вкалываю, но AS - не трожь! Святое!)
2greyshaman Так точно. Как суслик. Времени мало. Если б не так все срочно было. Positive_Infinity - правильнее, согласен.
2BlooDHounD у nuran'a там какой-то замудреный рекурсивный алгоритм. Я, честно говоря, запутался.
Уф, отписался.
greyshaman
10.04.2004, 02:08
ест мнение что алгоритм применим к MMF если его выполнение занимает <20 ms остальное туфталогия.
BlooDHounD
10.04.2004, 02:12
2BlooDHounD у nuran'a там какой-то замудреный рекурсивный алгоритм. Я, честно говоря, запутался.Я тоже. Но на сях и дэлфях, когда-то реалезововал.
Алгоритм в MMF напрямую завязан с FPS (если есть анимация) если ее нет, то время выполнения скрипта не принципиально. Имхо.
Кстати, на макромедиа.ком лежат классы для программной анимации. Скрипт там выполняется столько времени, сколько задаст пользователь(setInterval). Тонкие места конечно есть, но все в работе.
А про 20 ms - гон. Имхо.
Оригинал написал(а) BlooDHounD
Если мне не изменяет память, то, когда я учился в школе (и учил C++), алгоритм, который искал кратчайший путь в графе (про твой я не говорю!), носил имя [B]Флойда.
Ну Флойда он находит путь минимальной суммарной длины во взвешенном графе с произвольными весами а не с неотрицательными как Дейкстра.
Nox Noctis
10.04.2004, 02:25
Оригинал написал(а) Dindin
Алгоритм в MMF напрямую завязан с FPS (если есть анимация) если ее нет, то время выполнения скрипта не принципиально. Имхо. тут нет имхов. есть анимация или нет её - не важно. насильно задерживать смену кадров безболезненно не получится.
Оригинал написал(а) Dindin
Кстати, на макромедиа.ком лежат классы для программной анимации. Скрипт там выполняется столько времени, сколько задаст пользователь(setInterval). Тонкие места конечно есть, но все в работе.не позорьтесь, сударь, это совсем не о том :)
Оригинал написал(а) greyshaman
ест мнение что алгоритм применим к MMF если его выполнение занимает <20 ms остальное туфталогия. всё зависит от фпс ведь..
лично я считаю, что алгоритм жизнеспособен когда он занимает по времени меньше чем три-четыре длительности одного кадра (впс всем рулит, что делать :) ). да, это создаёт тормоза, бесспорно. но если сильно нужно, то вполне сойдет.
естесственно, это касается только алгоритмов, которые не предполагают выполнения в каждом кадре :))
(уважительно) Авторитет сказал...
greyshaman
10.04.2004, 02:33
иди сортируй пузырьками :)
Nox Noctis
10.04.2004, 02:36
Оригинал написал(а) Dindin
(уважительно) Авторитет сказал... хорош ехидничать :) если есть что возразить - мы это с удовольствием обсудим :)
А я не ехидничаю. Я, между прочим, серъезно :)
Чето я, парни, не найду на flasher'e реализованный во флеше алг-тм Флойда. Может у кого завалялся исходник?
Вроде так. Хотя я не уверен, что оно работает как надо :)
Nox Noctis said:
не позорьтесь, сударь, это совсем не о том :)
Да я просто себе скрытую рекламу делаю, разве не ясно? :) ;)
Спасибо Диндинь. Это ты SWF dec'ом вырезал? Позже разберу
Так точно. Им самым:) Не люблю императора :)
Работает на vBulletin ® версия 3.7.3. Copyright ©2000-2026, Jelsoft Enterprises Ltd. Перевод: zCarot
Copyright © 1999-2008 Flasher.ru. All rights reserved.