Конференция VBStreets

**Tin** » 18.10.2004 (Пн) 9:38

Драсьте... Такое дело - нужен ХОРОШИЙ алгоритм нахождения кротчайшего пути в 8 направелниях... Впринципе - не обязательно кротчайшего, но что бы прямых было побольше... Расмотрю любые варианты...

**tyomitch** » 18.10.2004 (Пн) 10:41

Волна?
http://algolist.manual.ru/maths/graphs/ ... h/wave.php

**alibek** » 18.10.2004 (Пн) 11:01

Волна в реализации VB не самое хорошее решение, тормозить будет. Разве что с основательной оптимизацией.

**Tin** » 19.10.2004 (Вт) 6:28

Волна действительно тормозит...
Есть ещё идеи?

**tyomitch** » 19.10.2004 (Вт) 17:40

Tin писал(а):Волна действительно тормозит...
Есть ещё идеи?

А ты попробовал её, или заранее знаешь, что она тормозит? ;-)

Вообще, все алгоритмы тут: http://algolist.manual.ru/maths/graphs/shortpath/

**Tin** » 20.10.2004 (Ср) 6:31

Волну пробовал - не понравилось, а оптимайзить сложно - намудрено сильно

**Tarik** » 20.10.2004 (Ср) 16:17

Раз уж такая тема... Кто-нибудь знает, какой алгоритм применить к объекту с постоянно меняющимися координатами?

**Sirik** » 20.10.2004 (Ср) 17:12

Можно попробовать алгоритм с возвратом, смесел следующий:

Код: Выделить всё: sub Paint(L, x, y: integer); a(y,x) = L if ( <(x,y) — целевая точка> ) then exit if (<можно пройти направо>) then Paint(L+1, x+1, y); if (<можно пройти налево>) then Paint(L+1, x-1, y); if (<можно пройти вверх>) then Paint(L+1, x, y-1); if (<можно пройти вниз>) then Paint(L+1, x, y+1); end sub

Например можно пройти направо:

Код: Выделить всё: если (a(x+1,y)=0) или (a(x+1,y)>a(x,y)+1)

У меня на таком алгоритме игрушка реализована

**tyomitch** » 20.10.2004 (Ср) 17:15

Это поиск в глубину.
Им путь найдётся не кратчайший, а произвольный.

**Tin** » 21.10.2004 (Чт) 6:32

А есть у когонить уже нормально реализованый алгоритм? Киньте исходы - посмотрим.

Я сталкиваюсь с основной проблемой - путь действительно находится кротчайший, НО персонаж уж сильно веляет - т.е. персонаж двигается в 8 направлениях и он должен двигатся толкьо по прямой или по диагонали в 45 градусов...

**Sirik** » 21.10.2004 (Чт) 8:08

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

А ты его пробовал? Наверное нет.

Посмотри условие a(x+1,y)>a(x,y)+1.

Поэтому и находится кратчайший путь (Линии тоже на этом алгоритме, и Atomica тоже)

YB » 21.10.2004 (Чт) 9:20

Я так понимаю, что тебе необходимо построить ориентированный граф, где есть набор узлов, соединённых рёбрами и найти кратчайший маршрут. Есть замечательная книга "Готовые алгоритмы на Visual Basic", где всё расписано. Всё в Exam_rar.exe. Разбирайся!!! :lol:

**tyomitch** » 21.10.2004 (Чт) 9:52

Sirik писал(а):
tyomitch писал(а):Это поиск в глубину.
Им путь найдётся не кратчайший, а произвольный.

А ты его пробовал? Наверное нет.

Ага, сорри. Спутал :oops:

Конференция VBStreets

Кратчайший путь

Кратчайший путь

Кто сейчас на конференции