Цитата(Sartorius @ 31.1.2007, 09:43  ) |
| волновым алгоритмом искать кратчайший путь от одной точки до другой |
Где бы еще найти вменяемую реализацию этого алгоритма. Потому как реализация его достатчно трудоемкий процесс
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Навигация (теория) |
| Автор: Gold Dragon 30.1.2007, 08:44 |
| Мне нужно сделать интерактивную навигацию по определённому району. Т.е. грубо говоря определить несколько контрольных точек, где сделать фотографии выбранных направлений. И соответственно затем навигацию от одной точки к другой. В принципе всё это легко когда улицы или прямые. Здесь просто определяю направления верх, низ, право, лево относительно нумерации улицы. Но как только встречается не правильный перекрёсток или кольцевая и т.п. то тут возникают проблемы. Вот и вопрос, как связывать одну точку с другой, да ещё одну фотку с другой? |
| Автор: Bitter 31.1.2007, 00:27 |
| А нельзя задавать не направления "вверх", "вниз" и т.д., а действия "поверуть влево", "повернуть вправо". Тогда каждой точке нужно задать количество направлений, их фотки и переключать их при "поворотах". Да, и ещё указать к какой точке переходить в каждом направлении. Т.е. структура точки такова: два массива "следующие точки" и "фотки". При этом длинна массива - количество направлений. |
| Автор: Gold Dragon 31.1.2007, 08:52 |
| Да всё равно, можно и направление. Только получится, что у каждой точке разное количество направлений. А как мне их учитывать. Ну грубо говоря, как мне сделать единую базу с у чётом того, что могут появляться новые точки, например, между двумя уже сущестующими? |
| Автор: Sartorius 31.1.2007, 09:43 |
| Советую задавать карту и волновым алгоритмом искать кратчайший путь от одной точки до другой каждый раз. |
| Автор: DENNN 31.1.2007, 12:32 | ||
Где бы еще найти вменяемую реализацию этого алгоритма. Потому как реализация его достатчно трудоемкий процесс |
| Автор: Gold Dragon 31.1.2007, 14:13 |
| а хоть поясните что это такое |
| Автор: Sartorius 31.1.2007, 14:20 |
| http://www.firststeps.ru/theory/karta.html |
| Автор: Akina 31.1.2007, 14:22 |
| Какие вправо-влево? Строишь граф узловых точек (перекрестки-пересечения-повороты). Поиск пути в графе - задача, обсосанная ну просто до неприличия. А уж описание каждого конкретного поворота... это расчитывается из описания узла, вернее из взаиморасположения в плоскости сходящихся в узле путей. |
| Автор: Sartorius 31.1.2007, 14:28 |
| ИМХО на реальной карте слишком много вершин придется заводить. Ясно, что поиск пути на графе проще поиска в лабиринте(и по реализации и по производительности), но гораздо проще создать лабиринт для карты, чем граф. |
| Автор: Gold Dragon 31.1.2007, 16:27 |
ну вы даёте... закидали меня терминами, которые я не понимаю  попытался это всё осознать, но так и не смог. У меня тупо есть определённый район города, есть фотоаппарат. с чего начать то? т.е. мне нужно найти карту этого района, обозначить точки и от них уже плесать на месте? И это как-то должно потом отображаться на экране с управлением. Это не постойка игравых лабиринтов. |
| Автор: Akina 31.1.2007, 18:45 | ||||
Создание точек, в отличие от поиска пути - операция одноразовая. Что выгоднее? Добавлено @ 18:46
С поиска нормальной, поддающейся оцифровке, карты района |
| Автор: izver 17.5.2007, 10:31 |
У меня схожая проблема.  У меня есть карты районов города. Мне надо установить ряд точек на карте, найти крайчайший путь. Алгоритм взял волновой (самый эфективный). Есть 2 поблемы: 1) на карту наложить невитимую матрицу или тупа задавать координаты точек (возникает еще одна проблема - как определить где дороги). 2) когда точки находятся в одном районе поиск понятен, но что делать когда точки в разных районах города? P.S. карту нужно создать как фон или как? Если как фон, то как это сделать на Java под Eclipse?  |