Trasa medzi bodmi A a B

Leopik 2x:
„Ako nájdem cestu medzi bodmi A a B?“
Potřebujete mapu rozdělenou na cesty a uzly. V podstatě se testují všechny možné trasy, dokud ostatní možné nejsou delší než nejkratší nalezená. Pro urychlení lze použít i centrální uzly, mezi kterými jsou trasy již nalezené. Ale tohle váš problém zřejmě neřeší.

Jakou formu mají ty čáry, nestačilo by porovnat počet pixelů dané barvy?

Leopik 2x:
Nejlepší by bylo, kdybyste sem dal ukázku vašeho obrázku. Obecné řešení tohoto problému není snadné.

Leopik 2x:
„Cesty budú zapísané v databáze.“
Tak potom k tomu nepotrebuješ žiadny obrázok, ale priamo vyrátaš dĺžky trás.
Cesty budú zapísané akým spôsobom?

Ahoj,
koukni se na dijkstrův algorytmus. Jde vlastně o hledání nejkratší cesty v grafu.

Leopik 2x:
Ten problém je trochu zložitejší.
Môžu byť na mape aj slepé cesty?
Bude vždy platiť, že v tom zápise sa bude x-ová aj y-ová súradnica meniť najviac o 1?
Ako budeš mať zapísaný šikmý smer, teda môžu sa zmeniť súčasne obe súradnice v jednom kroku?
Podľa toho, v akom tvare sú dáta zapísané, bude pre každý spôsob existovať veľa rôznych algoritmov.

Jedna otázka, není náhodou jedno kde je uzel položen? Přeci hledáš nejkratší cestu z bodu A do bodu B a důležitá je pro tebe cesta která je ohodnocená a ta může precí vést nohoru dolu, je to jedno.

Leopik 2x:
„vždy sa bude meniť maximálne 1 súradnica“
To je ďalšia komplikácia.
Potom nastáva ďalšia otázka, aké dlhé sú šikmé čiary?
Ak by si to rátal po jednom kroku, potom by ti vyšlo, že rovná čiara z (0, 0) do (10,10) má dĺžku 20, lebo by to rátalo ako dĺžku schodov.

Leopik 2x:
„ale aj tak by to bola tá najkratšia cesta z A do B“
Ale ak by si mal ešte jednu cestu, ktorá by nešla z A do B takto priamo, ale by bola zalomená, najprv rovno doprava a potom hore k B, tak by vyšla rovnaká vzdialenosť ako priama úsečka, čo v skutočnosti neplatí.

Leopik 2x:
A*

Leopik 2x:
Zběžně jsem si pročetl diskuzi - jestli máš obrázek "bludiště", tedy mřížku, kde je vzdálenost každých dvou pixelů sousedících hranou (tedy ne diagonálně - rohem) stejná, jednotková, navíc nejde cestovat skrz roh pixelu po diagonále, tak vůbec nepotřebuješ Dijkstru ani A*. Bohatě ti stačí poměrně jednoduché prohledávání do šířky - najdeš nejkratší cestu podle jedné barvy, pak podle druhé barvy, porovnáš délky cest a je to.

Jinak cestu zpět (i v A* a Dijkstrovi) najdeš tak, že si u každého pixelu resp. vrcholu grafu zapamatuješ, odkuď jsi do něj přišel. Každopádně jestli ti jde jen o délku cesty, tak tohle u prohledávání do šířky vůbec nepotřebuješ, mělo by ti stačit pamatovat si, kolik jsi vybral pixelů z fronty.

Tak nějak. Do fronty nejdřív přidáš počáteční bod, pak v každém kroku odebereš z fronty první bod, zkontroluješ, jestli náhodou nejde o cíl, a když ne, tak daný bod označíš jako navštívený (můžeš na to použít třeba dvourozměrné pole) a do fronty přidáš ty z jeho 4 sousedů, kteří mají požadovanou barvu a zároveň ještě nebyli navštívení. Algoritmus skončí buď nalezením cíle nebo vyprázdněním fronty, pokud cesta z počátku do cíle neexistuje.