Как должен быть построен код кратчайшего поиска пути?

Question

[Zimaell]

Сразу хочу сказать что в сети есть много примеров но они мне не совсем понятны, да и пока смотрел примеры и теории вообще запутался, поэтому решил задать вопрос и разобраться как это должно работать...
У меня есть сетка к примеру x,y 50 на 50, все клетки это
0 (стена - передвижение невозможно)
1 (дорога - самый быстрый способ передвижения)
2 (простая земля - передвижение в два раза медленнее)
3 (вода - передвижение в 4 раза медленнее)
Есть объект X который должен переместится из точки А в точку B.

Как в моем случае должен выглядеть код?

Если у кого-то есть готовые примеры то буду рад это увидеть, а если нет то как это должно быть построено?

Comments

[BATPYIIIKOB]

Обрати внимание на теорию графов и задай для каждого пути вес.

[Zimaell]

BATPYIIIKOB, графы на сколько я понял это ломанные линии до точки назначения (если путь не прямой), далее уже по этим ломанным вычислить какой выгоднее.
Как получить изначально эти графы?
То есть как должен быть построен массив перебора чтобы получить на выходе все возможные пути?

Answer 1

[Zimaell]

Я вот сделал такую вот сетку

0 1 2 3 4 5
1 1 2 3 4 5
2 2 2 3 4 5
3 3 3 3 4 5
4 4 4 4 4 5
5 5 5 5 5 5

И так далее (загрузить скриншот почему-то не получилось...), согласно вики сетка построена правильно, но там сказано что идти потом от точки до точки путем наименьшего значения рядом, но если попадается к примеру стена

0 1 2 3 4 5
B 1 2 3 4 5
2 2 2 # 4 5
3 3 3 # 4 A
4 4 4 # 4 5
5 5 5 5 5 5

Как тогда вычислять? Пока что в голову не приходит как их все перебрать...

Comments

[BATPYIIIKOB]

Графы. Поиск.

Графы

[Zimaell]

BATPYIIIKOB, на сколько я понял это поиск уже по построенным "возможным" путям, задаются возможные пути и вычисляется кратчайший путь, а как вычислить возможные пути?

там вон даже в примере

$graph_array = array(
                    array("a", "b", 7),
                    array("a", "c", 9),
                    array("a", "f", 14),
                    array("b", "c", 10),
                    array("b", "d", 15),
                    array("c", "d", 11),
                    array("c", "f", 2),
                    array("d", "e", 6),
                    array("e", "f", 9)
               );

задаются вершины, а как их изначально вычислить?

[BATPYIIIKOB]

Zimaell, Нахождение кратчайшего пути в графах 1

Нахождение кратчайшего пути в графах 2

Поиск самого дешевого маршрута на PHP алгоритмом Д...

Туда же

Ну и ХАБР

Визуализация поиска кратчайшего пути по алгоритмам

[Zimaell]

с этого ресурса пробовал

www.o2b.ru/%D0%BF%D0%BE%D0%B8%D1%81%D0%BA-%D1%81%D...

пишет не хватает памяти, смотрю по загруженности - за 5-7 сек забирает всю оперативу, что-то не так а что, всего ребер получается 19тыс

Визуализация поиска кратчайшего пути по алгоритмам

Все классно если бы это было на PHP...

Ну и ХАБР

Не могу понять как применять эти "кучи" в моем варианте....

У меня сетка x,y 50 на 50, заполнена допустим 0 и 1000, то есть 0 это проход а 1000 стена...