Форум: "Потрепаться";
Поиск по всему сайту: delphimaster.net;
Текущий архив: 2002.04.04;
Скачать: [xml.tar.bz2];




Вниз

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


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 (точно не помню), и в его обработчике перерисовуется изображение. Сообщение посылается окну как-раз в таких случаях когда нужно его перерисовать (перекрывание, сворачивание и т.п.)
>как возводить в степень
Уже ответили то-ли в Потрепаться, то-ли в Основной (не помню), но ты-то думаю помнишь, где спрашивал.




Форум: "Потрепаться";
Поиск по всему сайту: delphimaster.net;
Текущий архив: 2002.04.04;
Скачать: [xml.tar.bz2];




Наверх





Память: 0.76 MB
Время: 0.03 c
3-9391            DPro                  2002-03-12 19:07  2002.04.04  
Как програмно задать в свойствах IE домашнюю страницу?


3-9417            bos                   2002-03-13 14:37  2002.04.04  
роли & interbase


1-9560            -=GaLaN=-             2002-03-24 19:19  2002.04.04  
Как перетаскивать форму за какой-нибудь компонент?


6-9594            ReY                   2002-01-22 10:51  2002.04.04  
Как сделать независаемое приложение?


3-9379            KPOT                  2002-03-12 12:30  2002.04.04  
TIBDatabase iz DLL