- Symulator MaSzyna -
Hyde Park => Inne niekolejowe => Wątek zaczęty przez: guest4368 w 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)
-
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).
-
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
-
CPU: AMD Athlon 64 X2 4600+
System: XP SP3
Labirynt 1: 5 sekund
Labirynt 2: 16 sekund
Labirynt 3: 3 sekundy
-
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ą:)
-
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
-
Ciekawa sprawa. @james.szczesny podasz ogólny algorytm i metody?
-
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)
-
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
-
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.
-
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).
-
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.
-
Dlaczego ten program sam się zamyka po 10-15 sekundach?
-
Wersja demo :D
-
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.
-
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?
-
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.
-
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
-
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 ;)
-
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
-
i7-3610QM
L2: 2,01 s
L4: 0,94 s :)
-
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?