Automatyczny rozwiązywacz labiryntów

[guest4368]

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)

[ABu]

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).

[guest4368]

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

[Davidsonxx]

CPU: AMD Athlon 64 X2 4600+
System: XP SP3

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

[guest4368]

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ą:)

[Davidsonxx]

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

[popatrz]

Ciekawa sprawa. @james.szczesny podasz ogólny algorytm i metody?

[nazgvl]

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)

[guest4368]

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

[janek32]

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.

[guest4368]

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).

[qamil]

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.

[Artur PKP]

Dlaczego ten program sam się zamyka po 10-15 sekundach?

[Niebugoclaw]

Wersja demo :D

[guest4368]

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.

[qamil]

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?

[El Mecánico]

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.

[guest4368]

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

[Artur PKP]

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 ;)

[guest4368]

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

[ryba825]

i7-3610QM
L2: 2,01 s
L4: 0,94 s :)

[guest4368]

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?