алгоритм расчета кратчайшего пути между двумя пунктами

[player]

алгоритм расчета кратчайшего пути между двумя пунктами

Доброго времени суток!

Есть интересная проблема:

Дано:
карта местности, распределённая на сушу и море/воду.
Вопрос:
как реализовать расчет кратчайшего сухопутного пути между двумя точками на карте (хотя бы грубо)
Интересно будет услышать ваше мнение к проблеме, спасибо

 

[ksnk]

А что еще что-нибудь на карте есть? Леса, горы, овраги, реки, дороги и протч ... А скорости движения по этим картографическим сущностям определены?
Надеюсь, нужно найти кратчайший маршрут, который измеряется во времени, а не кратчайшее расстояние

 

[player]

А что еще что-нибудь на карте есть? Леса, горы, овраги, реки, дороги и протч ... А скорости движения по этим картографическим сущностям определены?

если к этой проблеме тоже есть решение то было бы не плохо, но не обязательно

Надеюсь, нужно найти кратчайший маршрут, который измеряется во времени, а не кратчайшее расстояние

не вижу разницы между этими двумя понятиями, но имею ввиду маршрут, который измеряется во времени

 

[aleks_raiden]

алгоритм А* (А-стар) - в гугле есть реализации. еще есть книга про программировние АИ в играх, это типичная задача.

 

[denver]

1. проводим прямую.
2. если на пути прямой нет воды то решение найдено
3. иначе проводим несколько касательных к выступающим углам озера (или чего угодно что надо обойти)
4. считаем "периметр" озера по этим касательным, с одной и с другой стороны прямой.
5. обходим там где "периметр" будет меньше, и снова доходим до нашей прямой.
6. goto 2.

 

[player]

алгоритм А* (А-стар) - в гугле есть реализации. еще есть книга про программировние АИ в играх, это типичная задача.

попробую поискать, еще не имею представления как это можно спрограммировать

denver
еще не осмыслил как реализовать это в программе

Тогда еще один вопрос: если программа работает на сервере с парой тысяч игроков, не слишком ли много ресурсов будут отбирать эти алгоритмы, карта находится в базе данных MySQL.
И какие есть альтернативные возможности, не такие точные но хотя бы примерные

 

[aleks_raiden]

player - а что вы такое делаете? а то мы как раз тоже самое игра наверное?

На сайт королевства дельфи был как то пример и статья детально описывающая, правда на паскале но для нормального прогерра алгоритм важен а его в сети полно.

-~{}~ 11.09.06 23:50:

можете написать мне приватом... может что-то подумаем вместе..

 

[SiMM]

> не вижу разницы между этими двумя понятиями
Хрена се, математик
Кратчайшее расстояние между двумя точками - прямая.

> алгоритм А*
http://algolist.manual.ru/maths/graphs/shortpath/smartmove.php#a_star

Вообще вопрос конечно по теории, но к PHP не имеет ни малейшего отношения.

 

[denver]

SiMM
Кратчайшее СХОПУТНОЕ расстояние между двумя точками - может быть и кривой

aleks_raiden

игра наверное?

GPS навигатор.. для запора

 

[player]

SiMM
к тому же не расстояние а путь

Спасибо за ссылку, щас начну изучать...

 

[MuXaJIbI41981]

SiMM блин опередил. Я тоже раньше много чего там брал

 

[nerezus]

Алгоритм фронта волны.

 

[aleks_raiden]

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

 

[player]

а для алгоритма А* никто не знает где достать готовые решения (класс или функция)?
намного упростило бы задачу...

 

[aleks_raiden]

player - алгоритмы и готвые функции вам уже тут показали. даже ссылки дали. Гугл покажет остальное (искать надо - A star)

на РНР, подозреваю, єтого никтоне реализововал в силу специфичности и "не веб-ориентованности"... впрочем может koders.com покажет что-то?