Autor Wątek:  Automatyczny rozwiązywacz labiryntów  (Przeczytany 11372 razy)

0 użytkowników i 1 Gość przegląda ten wątek.

guest4368

  • Gość
Automatyczny rozwiązywacz labiryntów
« dnia: 29 Września 2012, 17:43:51 »
Witam, chciałbym wam przedstawić moje ostatnie dzieło. Programik, który przechodzi labirynty z obrazka.
Kilka uwag technicznych dot. obrazka:
1) Tło labiryntu musi być białe
2) Ściany labiryntu nie mogą dotykać krawędzi obrazka
3) Ściany mogą być dowolnego koloru (oprócz białego)
4) W przypadku labiryntu, w którym trzeba dojść np. do jego centrum, w punkcie docelowym musi być kropka.

Własny labirynt można narysować w paincie.
W załączniku przesyłam archiwum z exe oraz trzema przykładowymi obrazkami.
Proszę o ocenę prędkości rozwiązywania na waszych komputerach (który z przykładowych labiryntów, czas w sekundach oraz rodzaj procesora i system operacyjny). Wymagania: Windows oraz .NET Framework 2 (chyba).

Najnowsza wersja w załączniku (z dnia 3.10.2012)

Offline ABu

  • Zasłużony dla Symulatora
  • Wiadomości: 511
    • Zobacz profil
  • Otrzymane polubienia: 45
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #1 dnia: 29 Września 2012, 18:03:41 »
Fajne, przypomniały mi się czasy zabaw programistycznych na Amidze :)

Działa ok, dość szybko, ale trasa nie jest optymalna. W załączniku przykład powstały z modyfikacji labiryntu 3 (wymazanie niektórych ścianek).
ABu

guest4368

  • Gość
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #2 dnia: 29 Września 2012, 18:06:32 »
On znajduje wszystkie możliwe drogi.

Rozprawił się nawet z tym:
http://upload.wikimedia.org/wikipedia/commons/c/cf/MAZE.png
w ciągu 1min 45sek.

Proszę pamiętać, że maksymalna waga zdjęcia w załączniku, to 250 kb. Proszę poprawić, później można usunąć moją notatkę.
Rozi

Offline Davidsonxx

  • Wiadomości: 140
    • Zobacz profil
  • Otrzymane polubienia: 0
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #3 dnia: 29 Września 2012, 19:20:23 »
CPU: AMD Athlon 64 X2 4600+
System: XP SP3

Labirynt 1: 5 sekund
Labirynt 2: 16 sekund
Labirynt 3: 3 sekundy

guest4368

  • Gość
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #4 dnia: 30 Września 2012, 16:04:07 »
W załączniku poprawiona wersja programu. Przyspieszone rozwiązywanie labiryntów, w szczególności tych opartych na siatce prostokątnej.
Wyrównałem wyniki @Davidsonxx pomimo słabszego sprzętu (przyspieszenie obliczeń o około 40%). Dodatkowy labirynt l4 - zobaczycie różnicę w rozwiązaniu nowszą wersją a poprzednią:)

Offline Davidsonxx

  • Wiadomości: 140
    • Zobacz profil
  • Otrzymane polubienia: 0
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #5 dnia: 30 Września 2012, 18:01:27 »
CPU: AMD Athlon 64 X2 4600+
System: XP SP3

Labirynt 1: 3 sekundy
Labirynt 2: 12,5 sekundy
Labirynt 3: 2,5 sekundy
Labirynt 4: 9 sekund (na starej wersji 10 sekund)



CPU: AMD Athlon 64 X2 4600+
System: Win 7 x64

Labirynt 1: 5 sekund
Labirynt 2: 21 sekund   <-- wow, nie spodziewałem się takiego wyniku
Labirynt 3: 4,5 sekundy
Labirynt 4: 14 sekund



CPU: Intel Core i5-M450 2,4GHz
System: Win 7 x64

Labirynt 1: 4 sekundy
Labirynt 2: 18 sekund
Labirynt 3: 3,5 sekundy
Labirynt 4: 12 sekund
« Ostatnia zmiana: 30 Września 2012, 18:39:26 wysłana przez Davidsonxx »

Offline popatrz

  • Wiadomości: 588
    • Zobacz profil
  • Otrzymane polubienia: 2
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #6 dnia: 30 Września 2012, 18:21:56 »
Ciekawa sprawa. @james.szczesny podasz ogólny algorytm i metody?

Offline nazgvl

  • Wiadomości: 14
    • Zobacz profil
  • Otrzymane polubienia: 0
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #7 dnia: 30 Września 2012, 20:46:39 »
CPU: AMD Athlon II X2 250 3GHz
Windows 7 SP1 x64 (w nawiasie wyniki po poprawce z postu poniżej)
L1 - 3,7 s (2,97s)
L2 - 16,4 s (11,3s)
L3 - 3,5 s (2,14s)
L4 - 10,8 s (7,7s)
« Ostatnia zmiana: 01 Października 2012, 16:42:23 wysłana przez nazgvl »

guest4368

  • Gość
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #8 dnia: 01 Października 2012, 10:28:36 »
Zdaje się, że program osiągną osiągnął już maksymalną prędkość. Na Pentium 4 2,79GHz labirynt L2  rozwiązuje w 12 sekund. W związku z tym jakie macie propozycje co do kolejnych funkcjonalności programu?

Najnowsza wersja w załączniku.

Rozi

Offline janek32

  • Wiadomości: 567
  • EMIT Ghp400M4C
    • Zobacz profil
  • Otrzymane polubienia: 1
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #9 dnia: 03 Października 2012, 21:35:48 »
Dodaję wyniki u mnie. AMD Phenom II X4 955 (3,2 GHz)+Windows 7 64-bit, wersja programu 1.2.
Labirynt 1: 2 sekundy
Labirynt 2: 10 sekund
Labirynt 3: 2 sekundy
Labirynt 4: 6 sekund
Labirynt z Wikipedii: 44 sekundy

A co do samego programu - może to niezbyt potrzebne, ale wg mnie przydałoby się ograniczyć zwiększanie rozmiaru okna do powiedzmy wielkości ekranu, a jeśli obrazek jest większy to dodawać suwaki do przewijania.
« Ostatnia zmiana: 03 Października 2012, 21:39:35 wysłana przez janek32 »
-Środa 844012.
-Zgłaszam się.
-Zapytaj energetykę, czy zapłacili rachunki, luzem ciągniemy i jest 2900.

guest4368

  • Gość
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #10 dnia: 03 Października 2012, 22:55:34 »
Pojawiły się suwaki do przewijania oraz funkcja drag&drop. Plik można przeciągnąć nad okno programu i upuścić a zostanie automatycznie wczytany.

Rozwiązywanie labiryntu L4 skrócone do 7 sekund na moim komputerze (poprzednio 9 sekund).

Offline qamil

  • Wiadomości: 46
    • Zobacz profil
  • Otrzymane polubienia: 3
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #11 dnia: 04 Października 2012, 10:28:44 »
Jeśli to ma komuś w czymś pomóc, dorzucę swoje wyniki :)
Procesor to Intel Core i5-3470 3.20GHz, system Win 7 x64.
L1: czerwona linia pojawia się po niecałych dwóch sekundach, ale pasek postępu potrzebuje chwilę dłużej na dojście do końca
L2: 7,5 sekundy
L3: 1,5 sekundy
L4: 5 sekund
Wikipedia: 35 sekund (zaznacza dwie drogi)

Testowane na najnowszej wersji (1.3.1). Co do przesuwania obrazu - fajnie by było, gdyby przesuwał się sam labirynt, a pasek menu i postępu był zablokowany - teraz przy dużych labiryntach trzeba wybierać, co chce się widzieć :) Przydałby się też wbudowany licznik czasu - teraz trzeba zewnętrznego stopera używać i ciężko o dokładny wynik.

Offline Artur PKP

  • Wiadomości: 153
  • Uwielbiam pojazdy szynowe. :D
    • Zobacz profil
  • Otrzymane polubienia: 0
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #12 dnia: 05 Października 2012, 19:15:06 »
Dlaczego ten program sam się zamyka po 10-15 sekundach?
Pozdrawiam, Artur.

Offline Niebugoclaw

  • Wiadomości: 1222
    • Zobacz profil
  • Otrzymane polubienia: 10
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #13 dnia: 05 Października 2012, 19:22:23 »
Wersja demo :D

guest4368

  • Gość
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #14 dnia: 20 Października 2012, 15:05:23 »
Wersja 1.4. Wbudowany licznik czasu, przyspieszenie algorytmu. Przebiłem nieznacznie na swoim komputerze (Pentium 4 2,79GHz, Win 7) czasy @qamil. Labirynt z Wikipedii do którego link był wcześniej podany rozwiązuje u mnie w 44s.

Offline qamil

  • Wiadomości: 46
    • Zobacz profil
  • Otrzymane polubienia: 3
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #15 dnia: 20 Października 2012, 20:30:27 »
Po zobaczeniu nowego posta w tym temacie miałem po prostu pobrać i przetestować, ale skoro mnie wywołałeś, to zaktualizuję wyniki :) Faktycznie, widać różnicę w czasie - bardzo mnie ciekawi jak to wygląda od strony programistycznej, na czym polega to "przyspieszenie algorytmu", problem w tym że wątpię czy zrozumiałbym wyjaśnienia - moja wiedza w tej kwestii jest praktycznie zerowa.
L1 - 0,73s
L2 - 4,15s
L3 - 0,79s
L4 - 2,38s
Wikipedia - 19,13

Przy okazji, czym mogą być spowodowane różnice w czasie rozwiązywania na tym samym sprzęcie? Zrobiłem kilka testów, i np. L2 rozwiązywał się w czasie od 4,11 do 4,20, przy wikipedii widełki wynosiły prawie 2 sekundy. Czy to raczej efekt aktualnego zużycia procesora (mimo że w teorii odpalone są te same programy w tle, bo testy robiłem pod rząd), czy może to kwestia programu i jakiejś losowości podczas rozwiązywania?

Offline El Mecánico

  • Wiadomości: 1067
  • Dawniej El Driver
    • Zobacz profil
    • Stowarzyszenie POLARIS - OPP
  • Otrzymane polubienia: 2
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #16 dnia: 20 Października 2012, 21:33:26 »
Pamiętaj, że mniej lub bardziej delikatny (w zależności od sprzętu) wpływ na bieżące obciążenie proca ma sieć. Obsługą wszelkich protokołów sieciowych zajmuje się przecież OS.
www.polaris.org.pl
www.ciemneniebo.pl
MaSzyna_LD w trakcie tworzenia...

guest4368

  • Gość
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #17 dnia: 20 Października 2012, 22:26:12 »
Program w zasadzie operuje wyłącznie na danych logicznych - porównania true/false... Owszem jest wrażliwy na to, co jest aktualnie odpalone - inne aplikacje także muszą "dobrać się" do procesora. Do napisania tego programu nie wystarczy sama wiedza programistyczna. Nawet ktoś dobrze znający znający C/C++/C#/Java (zdaje się mój kod algorytmu można przenosić między tymi językami) zdziwi się jak zobaczy te if'y - same w sobie nic nie znaczą. Podpowiem tylko, że to nie jest algorytm prawej/lewej ręki (takie coś można zrobić w Gimpie lub Photoshopie).


Po kolejnej optymalizacji labirynt z Wikipedii jest rozwiązywany u mnie w 18 sekund.
L2 - 4.2s
L4 - 2.3s

Offline Artur PKP

  • Wiadomości: 153
  • Uwielbiam pojazdy szynowe. :D
    • Zobacz profil
  • Otrzymane polubienia: 0
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #18 dnia: 13 Listopada 2012, 11:02:21 »
Nudziło mi się więc postanowiłem zrobić władny labirynt. Na moim laptopie rozwiązał go w ok. 2,5 s.
Jeszcze spróbuje bez tej kropki ;)
« Ostatnia zmiana: 13 Listopada 2012, 12:19:13 wysłana przez Artur PKP »
Pozdrawiam, Artur.

guest4368

  • Gość
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #19 dnia: 16 Marca 2013, 11:44:10 »
Zawsze coś jeszcze można wycisnąć:) Poprawa zauważalna głównie przy labiryntach, gdzie jest dużo "białego".
L2: 3.83s
L4: 1.89s

Offline ryba825

  • Wiadomości: 83
    • Zobacz profil
  • Otrzymane polubienia: 0
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #20 dnia: 16 Marca 2013, 13:37:05 »
i7-3610QM
L2: 2,01 s
L4: 0,94 s :)

guest4368

  • Gość
Odp: Automatyczny rozwiązywacz labiryntów
« Odpowiedź #21 dnia: 21 Sierpnia 2013, 08:55:18 »
Kod napisany w C++.Algorytm w zasadzie ten sam, z lekkimi modyfikacjami kodu. Labirynt z Wikipedii rozwiązywany w 14s. Ze względu na nieco inną konfigurację mojego komputera chciałbym, byście porównali z ostatnią wersją na swoich komputerach.

Edit:Program do chodzenia po labiryntach w 3D. Mam pytanie do osób piszących w OpenGL: używaliście czegoś takiego jak Fragment Shader, cieniowanie Phonga?