Flood-fill o którym mówisz jest powszechnie znany jako Breath First Search. Pomyślałem o tym, ale łatwo wymyśleć przykład gdzie BFS będzie niemiłosiernie wolny w porównaniu do A*, gdy prawie cała mapa to ocean. Co więcej, redukcja symetrii nie jest kompatybilna z BFS, wagi krawędzi nie są wszystkie równe 1 po redukcji. Spójrz na obrazek, wiele więcej wierzchołków zostaje odwiedzonych.
PS. Test na mniejszej mapie 300x150, 94 wyspy: sumarycznie A* odwiedził 1.2mln wierzchołków, Dijkstra 1.5mln, BFS... 34mln. Tak, po trójce nie ma kropki.
Chętnie spróbuję!
Dziękuję! Twoje wyniki zgadzają się z moimi.
Na stronie jest wyjaśnione na czym to polega. harablog.wordpress.com/2011/09/ ... reduction/
Wierzchołki wewnątrz prostokąta zostają usunięte a wierzchołki na obrzeżu zostają połączone z wierzchołkami po drugiej stronie prostokąta (wagi są długością skoku, nie 1). Pomiędzy dowolnymi wierzchołkami na obrzeżu można się przemieszczać bez użycia tych wewnątrz, z zachowaniem kosztów dojścia.