• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Wyjście z labiryntu

VPS Starter Arubacloud
+4 głosów
2,673 wizyt
pytanie zadane 21 kwietnia 2015 w C i C++ przez pulpet112 Użytkownik (760 p.)
Witam wszystkich!!

Mam ciekawy problem do rozwiązania. Myślę, że dla doświadczonych koderów może to być interesujące - ja dopiero zaczynam, jednak już muszę umieć zrobić coś takiego.

Chodzi o napisanie programu, który poszuka drogi wyjścia z labiryntu. Labirynt mam docelowo podany (http://snag.gy/EFIZr.jpg  - # to ściany a kropki to korytarze), jednak powinien być modyfikowalny w pliku tekstowym. Program pobiera sobie do tablicy dwuwymiarowej wzór takiego labiryntu (sam ten etap juz sprawia mi trudność), następnie "szuka" drogi wyjścia (nie musi być najkrótrza) . W sumie sam nie wiem jak miałoby wyglądać wyświetlenie rozwiązania. Może po znalezieniu tej drogi wymieni kropki np na pauzy albo jakkolwiek inaczej.

W zasadzie to nie mam bladego pojecia jak sie za to zabrać. Na pewno trzeba sprawdzać po kolei elementy tablicy czy są # czy kropki i od tego uzależnić dalszą "podróż" po elementach ale jak to dokładnie zrobić to nie wiem...

Z góry dzięki za każdą pomoc

Pozdrawiam

5 odpowiedzi

+2 głosów
odpowiedź 22 kwietnia 2015 przez MoWerr Obywatel (1,940 p.)
edycja 9 czerwca 2015 przez MoWerr
 
Najlepsza
Zrobiłem ten kod z "trzymaniem się prawej strony". Wszystko działa bardzo fajnie, ale nie patrzyłem na czytelność kodu (za bardzo podjarałem się zadaniem) , więc nie dzieliłem tego na funkcje, moduły itd. Zajmę się tym w weekend. Aktualny kod masz wysłany na PW.

Zasada działania jest taka: w folderze z programem musisz mieć plik "labirynt.dat". Program wczytuje labirynt do dynamicznej tablicy i później błądzi po labiryncie. Możesz zobaczyć drogę jaką przechodzi (dodałem to, bo sam byłem ciekaw ^^). Labirynt pojawia Ci się z aktualną drogą programu. Każde kliknięcie entera to przejście do następnej pozycji ;]. Na koniec program generuje plik "wynik.dat" W którym start jest oznaczony "S", koniec "K", a droga literami "o". Jak coś kompilowałem po Windowsem, więc na Linuxa program może wymagać niewielkich zmian :D

Muszę się przyjżeć temu algorytmowi A*. W weekend postaram się dopracować ten program ;]
komentarz 23 kwietnia 2015 przez pulpet112 Użytkownik (760 p.)
oo faktycznie bez spacji program działa i to jak..... ;) Jestem pod wrażeniem. Teoretycznie to bez znaczenia ale lepiej to wygląda gdy są spacje ( ten obrazek ktory wrzucilem na poczatku jest ze spacjami). Tak czy siak, jest co analizować, naprawde super sprawa. Dzieki Ci ogromne, a jakby ci się chciało to jeszcze dopracować tak jak mówisz to z ogromną przyjemnością bym to zobaczył ;)
komentarz 23 kwietnia 2015 przez MoWerr Obywatel (1,940 p.)
Jak tylko pojawi się coś nowego (uporządkowane albo ulepszone) to dam znać :D
komentarz 27 kwietnia 2015 przez pulpet112 Użytkownik (760 p.)
@MoWerr

analizuje ten twój kod już jakiś czas no i oczywiście niestety nie wszystko rozumiem i pewnie wielu rzeczy nigdy nie zrozumiem ;) ale czy moglbys mi na poczatek wyjaśnic jak dzialaja te kierunki UP DOWN itp ?
komentarz 27 kwietnia 2015 przez pulpet112 Użytkownik (760 p.)
Edit: w sumie kierunki jak kierunki, wiele do tłumaczenia tutaj chyba nie ma (chyba że cały kod) ale zastanawia mnie teraz bardziej konstrukcja "pozycja" bo najpierw w linii 19 masz cos takiego: Punkt pozycja = {0,0};

a następnie posługujesz się konstrukcją "pozycja.x" albo "pozycja.y"

Cóż to takiego?
komentarz 27 kwietnia 2015 przez MoWerr Obywatel (1,940 p.)
UP DOWN itd. to po prostu oznaczenia kierunku w którą stronę aktualnie wędruje algorytm :D
Definiuję je na samym początku kodu np. "#define UP 1" i później kompilator w miejscu, w którym wpisuję "UP" widzi po prostu "1". Zwiększa to trochę czytelność kodu. (Który aktualnie jest w bałaganie ^^')

"pozycja.x" "pozycja.y" to po prostu odwołanie do pól struktury, w której przechowuję aktualne "położenie" programu. Równie dobrze mógłbym posługiwać się dwiema zmiennymi int np. "x" i "y". Po prostu myślałem, że będę potrzebował w programie więcej takich "punktów" i że będę musiał je ze sobą porównywać. Struktury by mi w tym pomogły.

Więcej na temat struktur znajdziesz chociażby tutaj:
http://pl.wikibooks.org/wiki/C/Typy_z%C5%82o%C5%BCone

Ogólnie to pewnie analiza kodu byłbay łatwiejsza, gdybym wprowadził jakikolwiek podział na funkcje, ale niestety w weekend nie miałem czasu. ;/ Jak tylko uda mi się trochę oderwać od studenckiej rutyny to usiądę do tego.

 

Edit: BTW. znalazłem pierwszego buga w tym algorytmie :D Kiedy w labiryncie pojawią się oczka, tzn. do danego korytarza będzie można wejść z dwóch stron, to program znajdzie wyjście, ale narysowana ścieżka będzie mówiąc najprościej dziwna :D
+1 głos
odpowiedź 21 kwietnia 2015 przez Eryk Andrzejewski Mędrzec (164,260 p.)
Zastosuj taki algorytm - trzymaj sie zawsze prawej stronu :D
komentarz 21 kwietnia 2015 przez HaKIM Szeryf (87,590 p.)

A pod koniec w tym obrazku nie trzeba byłoby pójść w lewo?

komentarz 21 kwietnia 2015 przez Eryk Andrzejewski Mędrzec (164,260 p.)
Sorki, ale nie miałem czasu wystarczająco. Chodzi o to, żebyś w miarę możliwości trzymał się prawej strony. Ja takiego sposobu używam w praktyce, gdy chcę wyjść z labiryntu :) Niesty mam mało czasu, ale później opiszę dokładnie o co chodzi.
komentarz 21 kwietnia 2015 przez niezalogowany

Ogólnie chyba chodzi Ci o to, żeby zawsze z prawej strony mieć #, chyba dobrze Cię zrozumiałem. Sorki za moje bazgroły, ale rysuję na touchpadzie. Mniej więcej to by tak wyglądało:

 

komentarz 21 kwietnia 2015 przez Eryk Andrzejewski Mędrzec (164,260 p.)
O to to to to :D
+1 głos
odpowiedź 22 kwietnia 2015 przez Mister123450 Dyskutant (8,700 p.)
Najlepiej zastosować algorytm A*
+1 głos
odpowiedź 22 kwietnia 2015 przez Do.Zzay Mądrala (5,700 p.)
0 głosów
odpowiedź 21 kwietnia 2015 przez niezalogowany
Mam pewien pomysł, nie znam języka C, ale pomyślałem trochę i poruszasz się tak: wchodzisz do labiryntu: poruszasz się prosto. Jak napotkasz na # skręcasz najpierw w prawo, jak napotkasz na # skręcasz w lewo, jak napotkasz znowu na # cofasz się aż znowu napotkasz # i tak w kółko. Problemem jest znalezienie wyjścia z labiryntu. Gdyby wyjście było oznaczone jakoś * czy coś byłoby zdecydowanie łatwiej, a tak nie mam innego pomysłu.
komentarz 21 kwietnia 2015 przez pulpet112 Użytkownik (760 p.)
Dzieki wielkie za zainteresowanie tematem ;)

Sposób MoWerra najbardziej do mnie przemiawia lecz nie wiem za bardzo jak przełożyc to na C...
komentarz 22 kwietnia 2015 przez MoWerr Obywatel (1,940 p.)
Tak z ciekawości. Masz to zrobić w C czy C++?
komentarz 22 kwietnia 2015 przez pulpet112 Użytkownik (760 p.)
Właściwie to po głębszym przemyśleniu w ogóle nie wiem jak to zastosować... Nie za bardzo rozumiem co oznacza że mam się kierować cały czas w prawo. Jesli tak bym zrobił, to już zaraz po wejściu do labiryntu, przy pierwszej przeszkodzie, sprawdzając cały czas prawą stronę po prostu bym z niego wyszedł wejściem.... Nie wiem czy ja czegos tutaj nie rozumiem....

 

@MoWerr ja mam to zrobić w C ale w sumie przełożyć z jednego na drugi to już kosmetyczna sprawa...
komentarz 22 kwietnia 2015 przez MoWerr Obywatel (1,940 p.)
Zaciekawił mnie ten problem i próbuję napisać kod tego programu :D
komentarz 22 kwietnia 2015 przez pulpet112 Użytkownik (760 p.)
Ja też próbuje, ale jak na razie mam minimalną wiedze w temacie i dość topornie mi to idzie. Mam nadzieje że Ty jesteś już bardziej doświadczony ;) Jakbyś coś miał to podrzuć tutaj, myślę że nie tylko ciebie to zaciekawiło i wielu chciałby to zobaczyc ;)

Podobne pytania

0 głosów
1 odpowiedź 431 wizyt
0 głosów
1 odpowiedź 196 wizyt
pytanie zadane 8 grudnia 2022 w C i C++ przez Pysa6 Nowicjusz (220 p.)
0 głosów
1 odpowiedź 200 wizyt
pytanie zadane 1 grudnia 2022 w C i C++ przez Pysa6 Nowicjusz (220 p.)

92,453 zapytań

141,262 odpowiedzi

319,086 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...