Поиск пути

[zap]

Поиск пути

Народ помогите создать алгорит А* поиска пути на ПХП, я сделал как мог, неполучается, код могу выложить или ссылку где это можно посмотреть код.

 

[Frol]

какого пути?

 

[Vital_N]

в светлое будущее

 

[zap]

блин ну вы даете, щас постараюсь объяснить что мне нужно

-~{}~ 10.02.05 11:55:

что значит поиск пути ?
допустим есть у нас карта(говорю про игры) на которой есть препядствия(деревья, камни, ямы) и для того чтобы добраться из точки А в точку Б нужно найти оптимальный путь следования обходя препятствия

что у нас есть?
есть у нас двумерный массив в котором записано где у нас препятствие а где нет(например: проходимо 1; непроходимо 0)

вроде все

 

[Vital_N]

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

 

[zap]

а если серьезно?? занимался ли таким(или чем нибудь подобным)??

 

[IBSN]

)) очень похоже на задачку из олимпиады.

 

[jer]

вообще-то это к ПХП никак не относится, тебе просто нужен алгоритм.

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

 

[zap]

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

в этом то и проблема нужно кудато чего то писать, я думал над этим и придумал такой массив незнаю может и кривой
$arr=array(1=>array(y=>'1',x=>'2',"yxres"=>'-'),"res"=>'-');

объясняю:
однерка(1) - есть многомерный массив в котором сохраняются(отмечаются те клетки по которым можно пройти(тоесть удачные комбинации)

дико извиняюсь за свои объяснения, лучше задайте вопрос по конкретному моменту(если непонятно )

-~{}~ 10.02.05 12:18:

в данный момент есть код который ориентируется на местности, тоесть переместился проверил, переместился проверил, и т.д.

 

[IBSN]

каким образом перемещается?

 

[zap]

по точкам(по массиву пример: я в точке 1х1)массив двумерный

 

[virakochi]

zap
Почитай немного про алгоритмы.. Путь нужен самый короткий или любой?

 

[rotoZOOM]

algolist.manual.ru и там будет тебе щастье.
Рекурсией делать нельзя на массивах больше 10x10 так как сложность экпоненциальная. Делай волной (разливом). Ну и по сайту пошарься, который дан, там подробнее найдешь

 

[zap]

блин жаль что я плохо знаю синтаксис С

 

[rotoZOOM]

zap php ты знаешь ? А Си нет ? Странно. Ну спрашивай. Может и ответят.

 

[SiMM]

> блин жаль что я плохо знаю синтаксис С
Синтаксически PHP похож на C.

 

[zap]

и всетаки там используется много того чего совершенно непонятно

-~{}~ 11.02.05 13:46:

и вот еще вопрос:
почему именно волновой алгоритм мне использовать?

 

[rotoZOOM]

Потому что это легкореализуемый стандартный алгоритм для поиска кратчайшего путя.
Можешь конечно реализовать Дейкстру со сложностью O(NlgN), но это сложнее.

 

[zap]

слушай может смогеш помоч, а я тебе помогу ??

 

[rotoZOOM]

Личные сообщения в приват.
Ты спроси конкретно, в каком месте тебе что не понятно, обязательно помогут. Вряд ли весь скрипт за тебя кто-то писать будет.