Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [VB6]Построение карты и минимального пути

Автор: manuntd 10.3.2010, 16:13

Помогите пожалуйста, нужно написать прогу по построению карты и нохождения минимального пути от одной точки до другой. Очень надо. На VB6. Буду благодарен хоть за любые кусочки этой проги.

Автор: alex77755 10.3.2010, 16:41

Что имеется в виду под построением карты?
Сколько задано точек, как. Координатами? На карте?

Автор: alex77755 10.3.2010, 17:19

Цитата

Буду благодарен хоть за любые кусочки этой проги.

Ну вот тебе начало:

Код


Option Explicit
Dim T()
Private Sub Комманда1_Click(Index As Integer) ' обнуляем точки
Dim I
For I = 0 To П.Count - 1
П(I).Value = 0
Next I
End Sub

Автор: manuntd 10.3.2010, 18:11

Цитата(alex77755 @ 10.3.2010, 17:19)

Цитата

Буду благодарен хоть за любые кусочки этой проги.

Ну вот тебе начало:

Код


Option Explicit
Dim T()
Private Sub Комманда1_Click(Index As Integer) ' обнуляем точки
Dim I
For I = 0 To П.Count - 1
П(I).Value = 0
Next I
End Sub

спс

Добавлено через 1 минуту и 38 секунд

Цитата(alex77755 @ 10.3.2010, 16:41)

Что имеется в виду под построением карты?
Сколько задано точек, как. Координатами? На карте?

Просто поставить точек 10 какие нибудь ограждения между ними и все найти минимальный путь от одной до другой точки

Автор: alex77755 10.3.2010, 19:08

Всё равно непонятно. Между какими двумя? Или просто попарно между всеми точками, но с условием препятствий?
Если произвольно расставлять точки и прептствия - бред получитсяю Точки могут оказаться рядом и без препятствий. Значит надо самому расставлять хотя бы точки, а препятствия можжно накидать рандомно. или тоже самому. Но в любом случае вариант с объездом препятствий значительно усложняет задачу.
Вряд ли кто захочет делать её за так

Автор: manuntd 10.3.2010, 19:54

Цитата(alex77755 @ 10.3.2010, 19:08)

Сделай как получится как тебе удобно.

Автор: Sanaff 11.3.2010, 18:38

Цитата(manuntd @ 10.3.2010, 14:13)

Помогите пожалуйста, нужно написать прогу по построению карты и нохождения минимального пути от одной точки до другой.

Самый лучший алгоритм для такого - волновой алгоритм обхождения препятствий. Сам алгоритм найти легко. реализовать сложнее)) Действительно, за так делать вряд ли будут. Я могу взяться.
ICQ 373-628-456

Добавлено через 5 минут и 26 секунд
______Обход препятствий: волновой алгоритм_______
прокладка маршрута по карте с препятствиями

Суть его в том, что для поиска пути используется принцип расходящихся на воде кругов от брошенного в воду камня. При этом для повышения эффективности работы алгоритма применяется принцип обратной трассировки. Поиск пути ведется из точки финиша в точку старта.
Волновой алгоритм очень прост.
Переходим из клетки в клетку, считая длину пути от нее до точки начала расчета. В точку старта помещаем единицу. Это - начало пути. Почему не ноль? Потому что нолями преед началом расчета заполняются все точки нашей карты. Препятствия (стены) заполнены некими заранее заданными значениями, например -1. Впрочем, подойдет любое число, заведомо отличимое от пустой клетки.
На следующем шаге осматриваем соседние клетки, на которые можно перейти. Их не больше четырех: по одной клетке справа, слева, сверху и снизу. Перейти можно на поля, не занятые препятствиями и не пройдеными на одном из предыдущих шагов. В нашем примере Это поля, в которых записан ноль. Если такие поля находятся среди соседей клетки, мы пишем в них расстояние от исходной точки расчета. На втором шаге это расстояние будет равно двум. На нашейкарте такая клетка всего одна, поскольку точка начала расчета (точка финиша для искомого пути, помним про обратную трассировку!) расположена в "кармане".

После этого поочередно для каждой изученной на предыдущем шаге клетки ищем незанятые соседние клетки, в которые заносим следующее значение длины пути, в нашем примере тройку. Таким образом, с каждым шагом мы заполняем все большее и большее число клеток, расширяя границу изученной территории. Для точки "3" уже есть две клетки-соседкиа, в каждую из которых мы пишем знкачение "4", поскольку в каждую можно попасть из точки начала расчета за 4 шага. Для клетки "5" соседей тложе два, а вот для клетки "6" уже находится три соседние клетки, в каждую из которых помещаем значение "7".

Расчет заканчивается, когда мы приходим в точку цели. После этого, пользуясь простым правилом перехода на клетку с меньшим значением, мы, двигаясь из точки нашего старта (в ней, кстати, будет значение, равное длине нашего пути!) в точку финиша, в которой будет значение "1".