Pathfinding...

Патхфайндинг... вечния въпрос...
Интересно ми е писал ли е някой тук йерархичен такъв?
Множеството в което тървим път е битов масив 2048x2048.
Има ли идеи за ускорение, нещо което би работило по-добре от А* (и по-читаво от multiresolution такава)?
Аз лично се сещам за 2-3 неща, но ще ги спомена след като ги пробвам на практика.
Внимание: отговори включващи думичката 'google' не се приемат

Малка грешчица:
не 'multiresolution', а 'multilevel' исках да кажа...
т.е. не една голяма А* от началото до края, ами няколко по-малки последователни....

... отговора е както е казал поета "Сей земеделецо, сега му е времето!"

Поздрави от m.o.p.

:)))

Мерси, това ще свърши работа... тъкмо се бях отчаял.
А link ще дадеш ли?

...
Моля да предефинираме?

-2048x2048 bit matrix.
-pathfindin'.
....
Ако e това и с помощта на разбивката A* ще се нарадвам като видя как решенията (както сам е открил Zemedelec :) никнат и радват очите ми като добре избуяла нива, разпростряла се край китните градини...
....
А вие моля поправете и доуточнете условието, ако е необходимо!
И нека да е берекет!!!

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">

2048ь2048 булев грид е просто планарен граф, замаскиран под черно-бял масив чиито клетки показват дали са проходими или не, и са 8-свързани, т.е. за съседи на една клетка считаме четирите долепени до нея отгоре, отдолу, отляво и отдясно плюс и тези по ъглите спрямо нея...
Pathfinding... това е алгоритъм който в случая би трябвало да намира колкото се може по-къса (не най :) крива съставена от свързани помежду си отсечки, или по друг начин от точки като от i-тата точка има пряка видимост до i-1 и i+1-вата, т.е. между две съседни точки от пътя да няма препятствия...
Първата точка е точката от която тръгваме, а последната точка трябва да е най-добрата според нашата оценка до точката която сме посочили за край, до която може да се стигне от началото. Т.е. ако някой иска да намери път до непроходимо място в масива, или да отиде до друга компонента на свързаност (до друг остров), алгоритъма да намери 'най-близката' точка да местото където искаме да отидем...
.....
Хубав алгоритъм е А* но не би могъл да се пуска в рамките на един граф с 4М върха и да се очаква да извършва няколкостотин pathfinding-а за секунда, че и за друго да му остане дъх на процессора...

Най-малкото данните над които работим са твърде големи за цялосно претърсване, т.е. или то трябва да се прави разтегнато във времето, или да се работи с други данни подменящи графа на този 2048x2048 грид.

Имам няколко идеи, ама и без това този пост стана дългичък

Има едно такова нещо, което е разработвано съвместно с военни в американски университет, което се казва light-like pathfinding и служи за намиране на "оптимални" пътища в масиви от 1 000 000^2. Само дето не помня точно къде го бях чел. Ако си намеря линка ще ти го пратя.