Конференция VBStreets

GM » 05.11.2004 (Пт) 8:50

Только строго не судите, сам я это никогда не делал вот и спрашиваю.
Вот и два вопроса:
1.Что будет быстрее искать кратчайший путь на ВБ или передать эту функцию на обработку длл-ки написаной на Делфи?
2.Читал на одном сайте, что перед началом игры можна составить карту путей. Может кто знает как?

**Andrey Fedorov** » 05.11.2004 (Пт) 9:12

1.Что будет быстрее искать кратчайший путь на ВБ или передать эту функцию на обработку длл-ки написаной на Делфи?

При компиляции в Native Code разницы в скорости практически нет.

**Oxygen** » 05.11.2004 (Пт) 9:58

А еще как вариант написать библу на C++, а потом вызавать оттуда функции. ИМХО, так будет несколько быстрее.

**Mikle** » 05.11.2004 (Пт) 10:46

Лучше писать на том, что знаешь лучше, на чем сможешь лучше оптимизировать алгоритм. От этого быстродействие зависит больше, чем от выбора языка. Я иногда делаю DLL на Дельфи только ради ассемблерных вставок.

**Faust** » 05.11.2004 (Пт) 12:47

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

GM » 05.11.2004 (Пт) 23:01

Faust писал(а):Насчет 2-го вопооса. А каким образом задается карта - мир клеточный или как? Я в свое время мулялся проблемой поиска пути - может, чем смогу помчь.

Да мир клеточный 64х64, есть массив который содержит к примеру 0 - пустая клетка, 1 - препятствие(значения другие). Путь ищется с помощью волнового алгоритма, но уже начинает притормаживать.

**ToT** » 07.11.2004 (Вс) 21:55

А как ты собираешься хранить эти пути? Если ты хочешь найти сразу все пути из каждой клетки в каждую, то это будет занимать много памяти. Для мира 64х64 клетки это будет 4096 исходных клеток и 4096 конечных клеток, т.е. нужен массив 4096х4096, каждым элементом которого будет путь из i-той клетки в j-тую. Правда можно еще придумать оптимизацию, учитывая, что если нашли путь из i-той в j-тую, то не надо находить путь из j-той в i-тую; также из блокированных клеток и в блокированные пути составлять тоже не надо и из i-той в i-тую тоже не надо, но все равно памяти тратиться дофига, да и время уйдет немало, если уже начинает притормаживать.
Ну это только прикидка, я с этой темой всерьез не разбирался, может есть какие-то спец.алгоритмы...
А на счет первого вопроса, скорее всего передать поиск в длл-ку будет быстрее(осбенно сишную, как сказала Oxygen), главное преодолеть накладные расходы на вызов ф-ии. Это надо замерять.

**Faust** » 07.11.2004 (Вс) 22:53

Достаточно сохранять только направление первого шага из данной стартовой точки, так что для каждой пары "старт-финиш" придется выделить 2 бита (или 3, если разрешено движение по диагоналям).

**Oxygen** » 08.11.2004 (Пн) 8:30

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

GM » 08.11.2004 (Пн) 8:44

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

Так писали на одном с форумов.

**Oxygen** » 08.11.2004 (Пн) 8:51

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

**Faust** » 08.11.2004 (Пн) 10:59

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

**ToT** » 08.11.2004 (Пн) 13:52

Faust писал(а):Достаточно сохранять только направление первого шага из данной стартовой точки, так что для каждой пары "старт-финиш" придется выделить 2 бита (или 3, если разрешено движение по диагоналям).

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

GM » 09.11.2004 (Вт) 8:53

Нашел три алгоритма нахождения кратчайшего пути А*, волновой алгоритм, алгоритм Деикстры.Какой лучше использовать в RPG/RTS?

**Oxygen** » 09.11.2004 (Вт) 9:56

Дейкстра по-моему, намного побыстрее будет, чем волновой, он с самого начала был ориентирован на поиск кратчайших путей. А волновых 2 - поиск в ширину и в глубину.

**DragonTriste** » 27.11.2004 (Сб) 14:04

может я конешно чтото и не так понял....
но попоему проще запоминать уже пройденые пути, чем просчитывать все варианты. на крайний случай если есть 2-3 извесных пути из А в В то просто сравнивать и выбирать более короткий (или более безопасный как вариант :roll:

)

**tyomitch** » 27.11.2004 (Сб) 19:26

Oxygen писал(а):Дейкстра по-моему, намного побыстрее будет, чем волновой, он с самого начала был ориентирован на поиск кратчайших путей. А волновых 2 - поиск в ширину и в глубину.

Волновой 1 - в ширину; в глубину - не волновой.

GM » 29.11.2004 (Пн) 8:38

Почему-то на геймеркеских сайтах, все уверяют что А* лучший.

**tyomitch** » 29.11.2004 (Пн) 17:52

Что такое - A* ?

GM » 02.12.2004 (Чт) 2:18

Алгоритм такой

Конференция VBStreets

Что будет быстрее?

Что будет быстрее?

Кто сейчас на конференции