Вы все про пиво, да про пиво. А помочь не хотите?

← →
Blackweber (2002-02-08 01:16) [0]

Это ни какая не олимпиадная задача, ничего такого. Просто месяца 4 назад я попросил задачку на форуме(здесь). Так вот с тех пор и маюсь, уже написал несколько других прог, сдал экзамены, и все такое. В связи с этим на задачу у меня ушло на данный момент около 2 месяцев, но я никак не могу ее закончить. Я сказал что не отступлюсь пока не решу ее, но 2 МЕСЯЦА практически безрезультатной работы по 6час/сутки... И вот я решился на такой отчаянный шаг, как спросить у вас - мастеров. Может кто такое когда-то делал в ранней юности? Задача - нахождение кратчайшего пути в произвольном лабиринте. Может ее вообще нельзя решить так как я ее решаю. А именно, координатным методом.
Здесь еще мешает, то что америкосская(или где там Delphi делают) система координат имеет начало в правом верхнем углу монитора :) . Слышал что подобное решается методом затухающей волны, но не пробовал(не знаю как именно). Пожалуйста помогите мне с ней разделаться, а то поговорки типа: "упорство и труд - все перетрут" меня уже выводят из себя.
Вот EXE того что я имею на сегодняшний день http://delphi.mastak.ru/download/326.zip или в кладовке/готовые программы/лабиринт.
Большое спасибо.

:(

← →
wicked (2002-02-08 11:50) [1]

не плачь..... глянь на www.delphigfx.narod.ru... там есть статья, описывающая разные методы поиска пути.... кстати, мой любимый - алгоритм Дийкстры... ;)

← →
VictorT (2002-02-08 18:25) [2]

>Слышал что подобное решается методом затухающей волны
Иначе называется "волновой алгоритм". Сейчас, к сожалению :), конец робочего дня и я иду домой, но в понедельник, если тебе ещё нужно будет, то я его опишу. Данный алгоритм находит действительно кратчайший путь. Кстати, когда-то давно я с его помощью делал на Спектруме игрушку типа Пакмана. Этот алгоритм упоминается во многих книжках по методам разводки печатных плат. Короче, до понедельника.

← →
Blackweber (2002-02-08 19:18) [3]

Мне это нужно было в течении 2 месяцев и 2 дня погоды не составит.

← →
Иван Шихалев (2002-02-08 19:20) [4]

А пиво лучше :)

← →
copyr25 (2002-02-08 19:50) [5]

Лучше пузо от пива, чем горб от работы:))

← →
VictorT (2002-02-11 18:28) [6]

Описываю "волновой алгоритм". Пусть твой лабиринт описывается двухмерным числовым масивом, в котором запрещённые зоны (стены), обозначены например 0, а разрешённые - например 1. Дальше в точке, в которую надо попасть, возбуждается волна. Делается это так: в данный элемент массива ставится 2 (т. к. 0 и 1 используются как идентификаторы). Дальше по всему массиву ищутся 2 и если рядом с ними есть 1, то они заменяются на 3. После соответственно ищутся 3 и примыкающие к ним 1 на 4 и т. д. (цыкл). Условие выхода из цыкла - когда нечего заменять. Теперь, находясь в любой точке лабиринта, можно определить, в каком направлении нужно шагнуть, чтобы придерживаться кратчайшего пути к точке назначения - для этого нужно выбрать из примыкающих к данному елементу массива тот, который меньше данного. Вроде всё. Объяснение получилось сумбурное, если непонятно, спрашивай.

← →
Blackweber (2002-02-11 22:47) [7]

>Дальше по всему массиву ищутся 2 ...
Точка, в которую нам надо попасть одна, так? Значит, как могут существовать другие двойки?
Насколько я понял получаем что-то вроде числового лабиринта, т.е.

0000000000000000000000000000000
0100100 ................... 0
0111111 ................... 0 Прям матрица какая-то :^)
0001100 ................... 0
0000110 ................... 0
0111110 ................... 0
0000000000000000000000000000000

P.S.Да, извини, конечно, но слово ЦИКЛ пишется через И.

← →
Serguar (2002-02-12 08:12) [8]

Держи файлик на мыло, там описание. Желаю удачи.

← →
VictorT (2002-02-12 10:12) [9]

>>Дальше по всему массиву ищутся 2 ...
>Точка, в которую нам надо попасть одна, так? Значит, как могут существовать другие двойки?
Да, двойка действительно одна, но просто в цикле сначала ищутся все двойки, потом все тройки и т. д., т. е. просто не учитывается то, что двойка только одна... (но можно в принципе и учитывать).
>Насколько я понял получаем что-то вроде числового лабиринта
>Прям матрица какая-то :^)
Правильно понял, именно матрица.

← →
Blackweber (2002-02-12 22:43) [10]

2Serguar&VictorT&wicked
Огромное спасибо за объяснения.
Вроде понял.

← →
VictorT (2002-02-13 12:54) [11]

Когда чё небудь сваяешь, свисти, будет интересно посмотреть.

← →
Blackweber (2002-02-14 00:40) [12]

Ok. Добавлю ваш имэйл в Избранное, а вы не качали с вышеприведенной ссылки?

← →
VictorT (2002-02-14 10:21) [13]

Качал, как только ты дал ссылку. А там уже чего-нибудь изменилось?

← →
Blackweber (2002-02-15 00:08) [14]

Нет, просто интересно. Как первые впечатления?

← →
VictorT (2002-02-15 10:03) [15]

Интерфейс так ничё. Насчёт поиска, я так понял, у тебя проблема не только в том, как искать, а вообще в том, что ты не выловил все глюки, потому что путь проходит через стенки.
Желаю удачи! Если есть ещё вопросы, спрашивай.

← →
savva (2002-02-15 12:03) [16]

>Blackweber © (15.02.02 00:08)
>Нет, просто интересно. Как первые впечатления?

пока прога "ищет" путь - она не реагирует на сообщения вндовые...
мелочь, исправляется бытро, а неприятно...:))

← →
VictorT (2002-02-15 12:43) [17]

>пока прога "ищет" путь - она не реагирует на сообщения вндовые...
>мелочь, исправляется бытро, а неприятно...:))
Достаточно использовать отдельный Tread для поиска.

← →
VictorT (2002-02-21 20:24) [18]

Ну чё, уже чего небудь наваял?

← →
Blackweber (2002-02-21 23:49) [19]

Нет, пока времени нет.
И еще я в печали.
Козлы, наших лыжниц дисквалифицировали.
Я пару дней не был в инете, так что извините что не отвечал сразу на ваши сообщения.
Да, кстати на счет моей проги, можно ли как-нибудь предотвратить стирание изображения на канвасе моей формы, при перекрывании ее другими формами и сворачивания.
P.S. В институте заставляют на Паскале(Турбо) писать лабы.Кто-нибудь знает как возводить в степень, аналог Power(x,y) в Delphi. Можно было бы сделать цикл, но степень определяется путем перемножения различных констант, и имеется в виде переменний, чем естественно не может заканчиваться цикл.

← →
VictorT (2002-02-22 18:58) [20]

>можно ли как-нибудь предотвратить стирание изображения на канвасе моей формы, при перекрывании ее другими формами и сворачивания.
Почему-то думал, что VCL сам за этим следит (никогда не рисовал в Дельфях), но в MFC (Visual C) перехватывается сообщение OnDraw (точно не помню), и в его обработчике перерисовуется изображение. Сообщение посылается окну как-раз в таких случаях когда нужно его перерисовать (перекрывание, сворачивание и т.п.)
>как возводить в степень
Уже ответили то-ли в Потрепаться, то-ли в Основной (не помню), но ты-то думаю помнишь, где спрашивал.

Вы все про пиво, да про пиво. А помочь не хотите? Найти похожие ветки