Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 29.01.2013, 18:04   #1
Alexandr555
Форумчанин
 
Регистрация: 23.03.2011
Сообщений: 310
По умолчанию Поиск пути

Есть массив символов, есть символ обозначающий препятствие, есть конечная точка и стартовый объект 3x3 клетки,
не подкинете идею как находить путь к конечным координатам?
Alexandr555 вне форума Ответить с цитированием
Старый 29.01.2013, 18:10   #2
Blind Guard
Форумчанин
 
Регистрация: 14.03.2012
Сообщений: 139
По умолчанию

Если я правильно понял, то это может выглядеть так?
Код:
000
010
002
/* 0 - пустая клетка
1 - препятствие 
2 - конечная точка */
Если так, то каждый элемент массива лучше сделать объектом.
Объект должен описывать свойства рядом стоящих объектов.
Самый краткий путь достигается либо по диагонали, либо по вертикали/горизонтали (в зависимости от расстановки препятствий)
Сначала узнайте местоположение конечного объекта, потом смотрите какой из 3-х путей выбрать (либо совмещённый).
По-мойму в алгоритме не должно быть сложных замутов (стандартные ij алгоритмы)
Если будут более узкие вопросы, то спрашивайте, самому интересно)

Последний раз редактировалось Blind Guard; 29.01.2013 в 18:15.
Blind Guard вне форума Ответить с цитированием
Старый 29.01.2013, 18:19   #3
Abstraction
Старожил
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
По умолчанию

У Вас есть дискретный мир, в котором Ваш объект может иметь только какие-то определённые координаты и Вам нужно составить последовательность шагов, приводящую в заданную точку? Ищите по словам "алгоритмы поиска пути". Если достаточно хорошо знаете английский, вот здесь был хороший материал.
Abstraction вне форума Ответить с цитированием
Старый 29.01.2013, 19:05   #4
Grand_Daddy
Пользователь
 
Регистрация: 01.05.2012
Сообщений: 14
По умолчанию

Самый лучший и универсальный вариант - реализовать алгоритм А*. http://ru.wikipedia.org/wiki/%D0%90%...D0%BA%D0%B0_A*
Правда, в вашем случае лучше реализовать поиск пути "тупо беря быка за рока". Прогоняйте по всем возможным вариантам и сравнивайте их друг с другом. Из найденных путей выбирайте самый короткий - вот вам и путь найден.
Grand_Daddy вне форума Ответить с цитированием
Старый 29.01.2013, 19:29   #5
Alexandr555
Форумчанин
 
Регистрация: 23.03.2011
Сообщений: 310
По умолчанию

Grand_Daddy, идти во все свободные стороны и так каждый раз, отмечая посещенные и не ходить если она посещена, но полученный путь надо или хранить или каждый раз по новой после каждого хода находить, я посмотрел можно еще трассировкой
т.к. краткость пути не важна
Надежная трассировка. http://pmg.org.ru/ai/stout.htm#robust_trace
Alexandr555 вне форума Ответить с цитированием
Старый 29.01.2013, 20:00   #6
Smitt&Wesson
Старожил
 
Аватар для Smitt&Wesson
 
Регистрация: 31.05.2010
Сообщений: 13,964
По умолчанию

В машине, координаты известны. Ха + уb. Где a и b, смещение.
Проверяем координаты на смещение, если на пути встречается "препятствие", обходим его, используя ту-же формулу.
Пиши пьяным, редактируй трезвым.
Справочник по алгоритмам С++ Builder
Smitt&Wesson вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
поиск пути Nikita1111 Visual C++ 1 09.02.2012 00:44
Поиск пути Federal Помощь студентам 1 19.06.2011 12:24
поиск кратчайшего пути LENA_M Общие вопросы C/C++ 0 29.05.2010 22:15
Поиск пути в лабиринте s2dentishe Помощь студентам 2 13.03.2010 18:36
поиск пути NiCola999 Общие вопросы C/C++ 19 16.11.2009 09:25