Поиск пути

[zap]

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

воть

-~{}~ 11.02.05 14:00:

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

 

[rotoZOOM]

Щас тему прикроют, но слушай, если ты

программер то что надо

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

 

[zap]

гг

с математикой плохо(хотя мож она и непричем)

 

[rotoZOOM]

математика точно не причем (разве что только дискретная),чистый программинг.
Хорошо попробуем на словах.
1. Заводишь очередь.
2. В нее пихаешь координаты начальной клетки
3. Теперь основной цикл:
3.1. Берем из очереди координаты текущей клетки.
3.2. Смотрим ближайшие клетки на которые можно шагнуть из текущей. Если клетка не занята и на нее мы раньше не шагали, то пометить эту клетку, как ту, на которую мы уже шагнули, и записать ее координаты в конец очереди, так же запомнить текущую клетку, как родитель для той.
3.3. Повторять с пункта 3.1. пока не дойдешь конечной точки.
3.4. Использовать backtracking, чтобы найти путь.

Теперь спрашивай какой пункт тебе непонятен ?

 

[zap]

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

вопрос: что такое бактракинг?

-~{}~ 11.02.05 15:30:

вопрос1: по поводу отметки шагов, какой должен быть массив(наилучшая для этого конструкция)
вопрос2:

... так же запомнить текущую клетку, как родитель для той... - что это значит?

 

[rotoZOOM]

1. Массив наверно двухмерный.
2. Пусть текущая клетка (x,y), из нее например ты можешь пойти в (x+1,y), тогда для клетки (x+1,y) родителем будет клетка (x,y), запоминаешь это тоже в массиве.
3. Бэктрэкинг - это когда ты стоишь в конечной точке и по ссылкам на родителя отматываешь путь до начальной точки, попутно запоминая путь в каком-нить массиве. В итоге ты находишь путь по которому надо идти (точнее один из кратчайших путей)

 

[zap]

ну эт ладно, понятно, где мне все это крутить в while или for?

 

[SiMM]

Где удобнее.

 

[zap]

ладно rotoZOOM закрывай эту тему, как и говорил, позже сделаю, выложу скрипт

 

[rotoZOOM]

zap это к админам