[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

pl.comp.programming

Algorytm wychodzenia z labiryntu

kots

6/16/2007 7:46:00 AM

Witam

Czy zetknal kto sie moze z TAKIM schematem blokowym algorytmu wychodznie
z labiryntu.
A mianowice
Mamy do dyspozycji azymut ktory nakierowuje nasz na wyjscie, sciany moga
byc dowolne, pod wolonymi katami, dowolne petlne, duze puste
przestrzenie itp. (taka jaskinia). Dysponujemy tylko czyjnikiem
zblizzenia do sciany (mozemy sprawdzic czy przed nami jest sciana).
Wszelkie obroty wykonujemy w stopniach o 360 o 180 itp.
Moze ktos ma takowe rozwiazanie to bylbym wdzieczy.

pozdrawiam
12 Answers

Kopia Nowy folder (4)

6/16/2007 10:32:00 AM

0

Chyba najprostszym sposobem byloby stworzenie algorytmu sledzenia np.
prawej (lub lewej- ale ustalone na stale) sciany- jesli bedzie sie
poruszal ciagle przy prawej scianie to na pewno wyjdzie z labiryntu.

Musi tylko co pewien czas sprawdzac, czy ciagle znajduje sie przy
scianie. Jesli nie- skreca w prawo, dochodzi do sciany, skreca w lewo i
idzie dalej.

pozdr.
--
Guru,
hohohoho
hihihihihihihi :) :) :) :) :)
<ROTFL2> :* :))

kots

6/16/2007 11:24:00 AM

0

Kopia Nowy folder (4) pisze:
> Chyba najprostszym sposobem byloby stworzenie algorytmu sledzenia np.
> prawej (lub lewej- ale ustalone na stale) sciany- jesli bedzie sie
> poruszal ciagle przy prawej scianie to na pewno wyjdzie z labiryntu.
>
> Musi tylko co pewien czas sprawdzac, czy ciagle znajduje sie przy
> scianie. Jesli nie- skreca w prawo, dochodzi do sciany, skreca w lewo i
> idzie dalej.
>
Wlasnie nie jest tak latwo - podana przez ciebie metoda to mozna sobie z
prostego labityntu wyjsc gdzie sa proste sciany, jak masz juz jakas
jaskinie a po sordku okragly filar, a ruszysz z miejsca przy filarze to
bedzie, pozniej jakies petle to bedziesz sie krecil. Dlatego konieczne
jest tu wykorzystanie azymmutu (zakladajac ze nie mozly zapmaietywac
drogi przebytej)

slomek

6/17/2007 9:36:00 PM

0

On 16 Cze, 09:46, kots <k...@gmail.com> wrote:
> Witam
>
> Czy zetknal kto sie moze z TAKIM schematem blokowym algorytmu wychodznie
> z labiryntu.
> A mianowice
> Mamy do dyspozycji azymut ktory nakierowuje nasz na wyjscie, sciany moga
> byc dowolne, pod wolonymi katami, dowolne petlne, duze puste
> przestrzenie itp. (taka jaskinia). Dysponujemy tylko czyjnikiem
> zblizzenia do sciany (mozemy sprawdzic czy przed nami jest sciana).
> Wszelkie obroty wykonujemy w stopniach o 360 o 180 itp.
> Moze ktos ma takowe rozwiazanie to bylbym wdzieczy.
>
> pozdrawiam

Metoda potencjalowa. Brakuje co prawda odleglosci od celu, ale moze
udaloby sie jakos to obejsc (moze stala sila...).
Ogolnie- powinno byc troche na sieci na ten temat. W skrocie: robot
jest ladunkiem +, sciany sa ladunkiem +, wyjscie jest ladunkiem -.
CZyli wyjscie przyciaga robota, sciany odpychaja. Algorytm bylbyu mw
taki:
-rozgladasz sie w kolko z pewnym skokiem (np co 18stopni) mierzac
odleglosc od scian w kazdym kierunku
-pod uwage bierzesz tylko odleglosci ponizej jakiegos progu (zeby sie
pierdolami nie zajmowac)
-obliczasz sily dzialajace na robota ze strony scian (im blizej, tym
wieksza-konkretnych wzorow poszukaj albo wymysl...)
-obliczasz sile oddzialywania wyjscia na robota (jak wyzej)
-obliczasz sile wypadkowa
-na podstawie sily wypadkowej podejmujesz ruch: masz wyliczony
kierunek i zwrot, a wartosc sily wplywa na odleglosc/czas ruchu w
danym kroku
-rozgladasz sie w kolo...
i tak w kolko

Ten algorytm tez moze sie zakleszczyc (w zwezajacych sie tunelach),
ale lepszego raczej nie znajdziesz. Moga byc pewne modyfikacje
uodparniajace go na takie sytuacje- moze Google dopomoze. ;)

Jakub Debski

6/17/2007 10:51:00 PM

0

> Moze ktos ma takowe rozwiazanie to bylbym wdzieczy.

Czy to co?, co projektujesz jest maszyn? stanow?? Je?eli tak, jak?
pamieci? dysponuje?

pozdrawiam
Jakub

kots

6/18/2007 3:02:00 PM

0

slomek pisze:

>
> Metoda potencjalowa. Brakuje co prawda odleglosci od celu, ale moze
> udaloby sie jakos to obejsc (moze stala sila...).
> Ogolnie- powinno byc troche na sieci na ten temat. W skrocie: robot
> jest ladunkiem +, sciany sa ladunkiem +, wyjscie jest ladunkiem -.
> CZyli wyjscie przyciaga robota, sciany odpychaja. Algorytm bylbyu mw
> taki:
>[cut]
Nie dysponuje takimi czujnikami zeby byla możliwa taka implemetnacja jak
twoja.
Jes tylko JEDEN czujnik ktory oresla czy przed toba jest sciana czy tez
nie (wyciagnieta reka do przodu) + czujnik ktory ZAWSZE moze mnie
ustawic na wyjscie (azymut).
Ale twoja propozycja jest ciekawa, jednak wymagala by conajmniej
czujnika odleglosci.

slomek

6/18/2007 3:32:00 PM

0

On 18 Cze, 17:02, kots <k...@gmail.com> wrote:

>Dysponujemy tylko czyjnikiem zblizzenia do sciany

To zabrzmia o jak "czujnik zbli eniowy"
W takiej sytuacji to poza trzymaniem sielewej/prawej ciany wiele nie
wsk?rasz.
Mo e co na wz?r metody grafu widzialno ci: jedziesz prosto na cel az
napotkasz sciane. Wtedy jedziesz przy scianie(zawsze w lewa/prawa
strone) do momentu, az bedziesz mogl znowu pojechac prosto na cel. To
chyba idealne rozwiazanie nie jest, ale ma pewien sens...

kots

6/18/2007 5:29:00 PM

0

slomek pisze:
> On 18 Cze, 17:02, kots <k...@gmail.com> wrote:
>
Wtedy jedziesz przy scianie(zawsze w lewa/prawa
> strone) do momentu, az bedziesz mogl znowu pojechac prosto na cel. To
> chyba idealne rozwiazanie nie jest, ale ma pewien sens...
>

Przy prostym labiryncie to jest metoda....Ale w dowolnie "zakreconym" to
juz sie nie sprawdza dlatego jest azymut... Tylko ze nie znam w pelni
funncjonalnego chocby schematu blokowego...A napewno mozna to zrobic i
na 95% trzeba wykorzystac azymut bo inaczej bediemy sie zapetlac.

Marcin Biegan

6/19/2007 1:00:00 AM

0

kots napisa3(a):
> slomek pisze:
>> On 18 Cze, 17:02, kots <k...@gmail.com> wrote:
>>
> Wtedy jedziesz przy scianie(zawsze w lewa/prawa
>> strone) do momentu, az bedziesz mogl znowu pojechac prosto na cel. To
>> chyba idealne rozwiazanie nie jest, ale ma pewien sens...
>>
> Przy prostym labiryncie to jest metoda....Ale w dowolnie "zakreconym" to
> juz sie nie sprawdza dlatego jest azymut... Tylko ze nie znam w pelni
> funncjonalnego chocby schematu blokowego...A napewno mozna to zrobic i
> na 95% trzeba wykorzystac azymut bo inaczej bediemy sie zapetlac.

http://en.wikipedia....*_search_algorithm
Ale brzmisz, jakby? mia3 pojedynczego robota, czy co? w tym stylu, wiec raczej
A* nie bedzie pasowaa.

--
pozdrawiam
Marcin Biegan

Radoslaw Jocz

6/19/2007 10:30:00 AM

0

kots wrote:
> Witam
>
> Czy zetknal kto sie moze z TAKIM schematem blokowym algorytmu wychodznie
> z labiryntu.
> A mianowice
> Mamy do dyspozycji azymut ktory nakierowuje nasz na wyjscie, sciany moga
> byc dowolne, pod wolonymi katami, dowolne petlne, duze puste
> przestrzenie itp. (taka jaskinia). Dysponujemy tylko czyjnikiem
> zblizzenia do sciany (mozemy sprawdzic czy przed nami jest sciana).
> Wszelkie obroty wykonujemy w stopniach o 360 o 180 itp.
> Moze ktos ma takowe rozwiazanie to bylbym wdzieczy.
>
> pozdrawiam

z pewnoscia musisz rozwazyc kilka typow algorytmow wychodzenia z
labirytnu (i inne alborytmy) a im wiecej tym lepiej i wybrac odpowiedni
dla swoich zalozen, ewentualnie zmodyfikowac jeden z nich, lub
wykorzystac wiecej niz jeden na raz, (lub zmodyfikowac wlasne zalozenia
w najgorszym przypadku)

dosc latwe w implementacji z ktorymi sie spotkalem:
- algoryzm wychodzenia z labirytnu z nawrotami, wykorzystuje pamiec
przegadajac kolejne wezly grafu reprezentujacym labirynt i zapamietujac
gdzie juz byl

- ponumerowanie pol (drogi wyjscia z labirytntu labirynt w postaci
planszy) od wyjscia rosnaco do obiektu ktory ma z niego wyjsc,
obiekt poprostu bedzie wchodzil na kolejne pola o nizszym numerze
przesuwajac sie coraz blizej wyjscia
ponumerowane pola beda czyms w rodzaju drzewa a wyjscie to korzen,
obiekt znajduje sie na lisciu wiec musi tylk przejsc do korzenia co jest
banalne, wyznaczenie drzewa tez jest latwe

linki
http://www.ii.uni.wroc.pl/~wzychla...
http://www.google.com/search?hl=en&rls=com.microsoft:en-us:IE-SearchBox&rlz=1I7SKPB&sa=X&oi=spell&resnum=1&ct=result&cd=1&q=algorytm+labirynt&a...

Kamil Burzynski

6/19/2007 10:48:00 AM

0

On Sat, 16 Jun 2007 09:46:03 +0200
kots <kots@gmail.com> wrote:

> Witam
>
> Czy zetknal kto sie moze z TAKIM schematem blokowym algorytmu wychodznie
> z labiryntu.
> A mianowice
> Mamy do dyspozycji azymut ktory nakierowuje nasz na wyjscie, sciany moga
> byc dowolne, pod wolonymi katami, dowolne petlne, duze puste
> przestrzenie itp. (taka jaskinia). Dysponujemy tylko czyjnikiem
> zblizzenia do sciany (mozemy sprawdzic czy przed nami jest sciana).
> Wszelkie obroty wykonujemy w stopniach o 360 o 180 itp.
> Moze ktos ma takowe rozwiazanie to bylbym wdzieczy.

Nie opisales jak porusza sie robot. Pojedynczy krok robota jest liczba
calkowita, czy tez wartosci rzeczywiste tez wchodza w gre? Teoretycznie
gdy sciany sa nieskonczenie blisko siebie - robot przejdzie czy nie?
Czy tez sciany nie sa az tak dowolne - bo maja jakies ograniczenia na
pozycje/katy? Obracasz sie zawsze w pelnych katach czy tez w ulamkach?

Ogolnie jest tak ze jak masz azymut, to mierzac kat z 2 roznych
pozycji, znajac odleglosc miedzy pozycjami jestes w stanie dokladnie
wyliczyc gdzie i w jakiej odleglosci jest wyjscie. Potem trzeba
tylko narysowac mape :)

Czujnik odleglosci od sciany mozesz zasymulowac (w
dosc nieoptymalny sposob) - poruszasz sie do przodu (pamietajac o ile
sie poruszyles) az trafisz na sciane, wtedy cofasz sie o tyle ile sie
poruszyles. Obracasz sie o kat delta, i znowu ruch w przod, tyl. W ten
sposob zbadasz odleglosc scian dookola. Stad algorytmy opisane w innych
postach w tym watku beda mialy wieksza szanse zadzialania.

--
Best regards from
Kamil Burzynski