| Вопрос: Лабиринт... кратчайший путь??? | Добавлено: 23.06.06 19:56 |
Автор вопроса:  EROS
|
|
Вопрос к специалистам по алгоритмам и математикам...
Задача: Есть матрица 25*25 клеток, представляющая собой лабиринт в котором клетки помечены цифрами: 0-пустая клетка 1-стены 2-финиш 3-старт Финиш всегда имеет координа 0;0(верхний левый угол) Старт может распологаться где угодно... Вопрос: нужно найти кратчайший путь от старта к финишу Результат должен быть представлен массивом клеток (координат).. описываюших последовательность шагов кратчайшего пути к финишу.. Надо учитывать такие моменты: -наличие нескольких решений.. (соответственно выбрать самое короткое) -отсутствие решения вообще.. -каким то образом отсекать тупиковые ветки.. P.S. приму в дар решение на любом из VB-наречий... (у меня уже череп дымит.. :-((( |
| Ответы | Всего ответов: 28 |
|
Номер ответа: 1 Автор ответа: Алексей ICQ: 207504159 Вопросов: 1 Ответов: 14 |
Web-сайт: Профиль | | #1 | Добавлено: 23.06.06 20:11 |
|
Есть "Волновой алгоритм поиска пути". Максимально просто, но не очень быстро.
Подробнее читай тут: http://lehs.info/astar.zip Не помню откуда я взял этот документ, поэтому выложил на своем сайте для тебя. |
||
|
Номер ответа: 2 Автор ответа:  EROS Вопросов: 58 Ответов: 4255  |
Профиль | | #2 | Добавлено: 23.06.06 22:35 |
|
Алексей
За статью отдельное спасибо.. во всяком случае хоть что-то прояснилось... А нет ли кода реализующего данную идею? З.Ы. это как раз мой вариант.. т.к. в моей задаче по диагонали тоже ходить нельзя... |
||
|
Номер ответа: 3 Автор ответа: АлексейICQ: 207504159 Вопросов: 1 Ответов: 14 |
Web-сайт: Профиль | | #3 | Добавлено: 24.06.06 09:35 |
|
Код есть, но на Паскале. Я писал игру для мобильника на MidletPascal. Посмотри, может и разберешся. Я по этой статье делал - все довольно просто.
http://lehs.info/astargame.zip |
||
|
Номер ответа: 4 Автор ответа: MorpheusВопросов: 224 Ответов: 3777 |
Web-сайт: Профиль | | #4 | Добавлено: 24.06.06 11:43 |
|
эх, вот делали мы с телепортами даже такие - то есть есть клетки из которых можно попасть в любую такую же клетку телепорт...
хотя некоторые думают (не скажу кто гыгы), что олимпиадники - это бедняги с искалечиной паскакалём психикой  )
п.с. 1-стены
2-финиш 3-старт кто ж задаёт так старт и финиш? надо метить старт единицей, а финиш никак не метить а то как ходы то от 2 и 3 отличить? гы. |
||
|
Номер ответа: 5 Автор ответа: EROSВопросов: 58 Ответов: 4255 |
Профиль | | #5 | Добавлено: 24.06.06 13:13 |
|
кто ж задаёт так старт и финиш? надо метить старт единицей, а финиш никак не метить а то как ходы то от 2 и 3 отличить?
да помечай ты их как душе угодно... это не суть важно... |
||
|
Номер ответа: 6 Автор ответа: Sacred Phoenix ICQ: 304238252 Вопросов: 52 Ответов: 927 |
Профиль | | #6 | Добавлено: 24.06.06 18:49 |
| ищи доки по A* Algorithm. Я сам в последнее время усиленно изучал поиск пути. У меня даже где-то примеры на vb.net и vb6 по поиску пути есть... | ||
|
Номер ответа: 7 Автор ответа: Sacred PhoenixICQ: 304238252 Вопросов: 52 Ответов: 927 |
Профиль | | #7 | Добавлено: 24.06.06 18:50 |
| и кста, пытался его переделывать под шестиугольное поле)), а раз у тя тут квадраты - эт ещё легче)) | ||
|
Номер ответа: 8 Автор ответа: HACKERРазработчик Offline Client Вопросов: 236 Ответов: 8362 |
Профиль | | #8 | Добавлено: 24.06.06 19:08 |
| есть на vb6, в точности удовлетворяющий вопросу. Но насколько он там "кратчайший" х.з. но на глаз и вижу и короче? Если не найдёшь я могу выложить пример | ||
|
Номер ответа: 9 Автор ответа: LeXICQ: 301424893 Вопросов: 28 Ответов: 277 |
Web-сайт: Профиль | | #9 | Добавлено: 24.06.06 19:20 |
|
http://vbkoders.info/gate.html?name=Forums&file=viewtopic&t=110#862
Там есть пример игры. Цель построить такой лабиринт, чтобы жучок бегал по нему как можно дольше. Идет жучок по самому короткому пути (во всяком случае должен). Исходник есть только к первой версии... |
||
|
Номер ответа: 10 Автор ответа: Sacred PhoenixICQ: 304238252 Вопросов: 52 Ответов: 927 |
Профиль | | #10 | Добавлено: 24.06.06 20:12 |
|
http://vbstreets.ru/VBdotNET/Sources/65847.aspx
vb.net 2003 |
||
|
Номер ответа: 11 Автор ответа: Sacred PhoenixICQ: 304238252 Вопросов: 52 Ответов: 927 |
Профиль | | #11 | Добавлено: 24.06.06 20:14 |
|
http://theory.stanford.edu/~amitp/GameProgramming/
Описание A* Algorithm. На английском |
||
|
Номер ответа: 12 Автор ответа: EROSВопросов: 58 Ответов: 4255 |
Профиль | | #12 | Добавлено: 24.06.06 20:14 |
|
HACKER
буду весьма признателен... eros@fromru.com |
||
|
Номер ответа: 13 Автор ответа: EROSВопросов: 58 Ответов: 4255 |
Профиль | | #13 | Добавлено: 24.06.06 20:19 |
|
LeX
вот по типу этой игры я и делаю.. сыну в школе по информатике задали, вот я и решил помочь, сделать на VB 2005 А тот пример я смотрел.. )) даже улыбнулся...
не хочу обижать автора той игры, но там все через одно место сделано.. |
||
|
Номер ответа: 14 Автор ответа: LeXICQ: 301424893 Вопросов: 28 Ответов: 277 |
Web-сайт: Профиль | | #14 | Добавлено: 24.06.06 20:41 |
|
2HACKER
И мне тоже можно Я думал тот пример нормальный... Покажу ему пример HACKER'а Может его и оставим
|
||
|
Номер ответа: 15 Автор ответа: HACKERРазработчик Offline Client Вопросов: 236 Ответов: 8362 |
Профиль | | #15 | Добавлено: 24.06.06 22:25 |
|
vb.hut1.ru/ai.rar
вообще то что там, это не лаберинт, но мож алгоритм посмотриш... |
||