Autor Wątek: Compo "Zrozumieć programowanie" - 03-17.11.2015 [wyniki]  (Przeczytany 7981 razy)

Offline Dab

  • Redaktor
    • blog

  • +1
# Listopad 03, 2015, 12:09:06
Z okazji premiery książki "Zrozumieć programowanie" której autorem jest nie kto inny jak Gynvael Coldwind mamy dla was nietypowe Compo.

1. Celem Compo jest napisanie aplikacji która będzie przetwarzała bitmapy.
2. Przykładowa bitmapa dostępna jest pod adresem http://warsztat.gd/files/warsztat.bmp
3. Aplikacja na podstawie zadanej bitmapy oraz współrzędnych źródła światła powinna wyliczyć które piksele bitmapy mogą być oświetlone, a które są zasłonięte przez przeszkody. Ilustuje to poniższy schemat (za Red Blob Games/Amit Patel):

4. Znaczenie kolorów bitmapy wejściowej (indeksy - bitmapa jest w trybie 8BPP):
  • 0 - skała/kamień, nie przepuszcza światła
  • 1 - drzewo (pień), nie przepuszcza światła
  • 2,3,4,5 - różne rodzaje terenu przepuszczające światło
  • Pozostałe kolory nie są używane i można je zignorować.
5. Bitmapa wyjściowa również musi być w trybie 8BPP, gdzie następujące indeksy oznaczają:
  • 0 - światło nie dociera do danego piksela
  • 255 - światło dociera do danego piksela
6. Program (zgłoszenie użytkownika) musi działać na platformie Windows.
7. Program będzie uruchamiany w jednym z dwóch trybów:
  • przetwarzania danych. W tym trybie aplikacja powinna wczytać bitmapę i parametry, wyliczyć widoczność światła, zapisać wynik do bitmapy i zakończyć swoje działanie. Aplikacja będzie uruchamiana w następujący sposób:
    nazwa_aplikacji.exe <input> <output> <x1> <y1> <x2> <y2> <x3> <y3> ...
    gdzie xn/yn to współrzędne kolejnych źródeł światła (0,0 to piksel w lewym górnym rogu).
    Przykładowe uruchomienie:
    zgloszenie.exe input.bmp output.bmp 10 10 400 200 106 660
  • interaktywnym. W tym trybie aplikacja powinna wczytać bitmapę a następnie pokazać ją w swoim oknie, dając użytkownikowi kontrolę nad wizualizacją (np. pozycją światła).
    Przykładowe uruchomienie:
    zgloszenie.exe input.bmp --interactive
Aplikacje będą oceniane w trzech różnych kategoriach. Nagrodą w każdej z nich jest książka "Zrozumieć programowanie" Gynvael Coldwinda.

1. Wydajność. Organizatorzy Compo dokonają pomiarów wydajności i dokładności działania zgłoszeń po czym wybrane zostanie najlepsze rozwiązanie.

2. Wizualizacja. Ta część będzie oceniana przez uczestników jak w trakcie tradycyjnego Compo (głosowanie). Oceniana będzie interaktywna część działania aplikacji.

3. Mystery challenge! Przykładowy plik (http://warsztat.gd/files/warsztat.bmp) skrywa pewną tajemnicę. Kto pierwszy będzie w stanie znaleźć ukrytą wiadomość? :)

Compo trwać będzie od chwili ogłoszenia do 17.11.2015 24:00 CET
Zgłoszenia należy wysyłać na adres [email protected]

W sprawach nieujętych regulaminem tej edycji obowiązują zasady ogólne: http://forum.warsztat.gd/index.php?topic=29527.0
« Ostatnia zmiana: Lipiec 16, 2016, 12:16:36 wysłana przez Dab »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Kyroaku

  • Użytkownik

# Listopad 03, 2015, 15:23:19
Co to jest za dziwny format, że FreeImage, ani SDL go wczytać nie chce ? :D

Offline Dab

  • Redaktor
    • blog

# Listopad 03, 2015, 15:58:29
No cóż, zadanie jest z pogranicza gamedevu i security. Plik jest poprawny... z małą niespodzianką. ;)
(md5sum: 9043e60ce248ac88809f5155838b4620)

Offline hashedone

  • Użytkownik

# Listopad 03, 2015, 20:28:12
Z tego wynika, że najlepiej samemu zakodować otwieranie bitmapy - jest chociaż określone która wersja nagłówka DIP jest użyta? Sam nagłówek to w sumie nie problem, można pominąć, ale pytanie czy implementacja i ewentualne testowanie RLE i innych bzdur z nowoczesnych nagłówków to też część zadania? Oczywiście nie chodzi mi o plik przykładowy - tam można łatwo sprawdzić, ale pytanie o złośliwość przy testowaniu.

Offline Dab

  • Redaktor
    • blog

# Listopad 03, 2015, 21:37:45
Nie przewidujemy dodatkowych utrudnień przy testowaniu, pliki testowe będą w tym samym formacie co przykładowy.

# Listopad 03, 2015, 21:45:39
Serio FreeImage/SDL go nie obsługują? Hah, a to zabawne.
To standardowy BMP 8-bit RLE - szczerze nie spodziewałem się, że liby będą miały z nim problem (szczególnie, że przeglądałem sporo implementacji loaderów BMP i większość z nich sobie spokojnie z RLE 8-bit radziła).
No nic, wygląda na to, że jest to nieprzewidziane utrudnienie pod tytułem "znajdź lib ogarniający RLE8" ew. "napisz samemu dekoder RLE8" (format jest trywialny).

Natomiast jak Dab pisał - nie planujemy być złośliwi przy testach jeśli chodzi o format pliku - będzie to to samo co w przypadku pliku testowego.

Offline hashedone

  • Użytkownik

# Listopad 03, 2015, 21:55:29
RLE8 nie jest trudny, ale nie znam na pamięć co jeszcze w tych nagłówkach BMP może w teorii siedzieć dlatego pytam - też jestem bardzo zdziwiony, że popularne biblioteki sobie z tym nie radzą.
« Ostatnia zmiana: Listopad 03, 2015, 22:00:53 wysłana przez hashedone »

Offline lethern

  • Użytkownik

# Listopad 03, 2015, 21:58:40
Nie chce nic mówić, ale firefox też go poprawnie nie czyta/nie wyświetla

# Listopad 03, 2015, 22:13:46
O, ciekawe. Opera też wyświetla tak jak Firefox.
Natomiast MSPaint / IrfanView / Chrome / IE / GIMP nie mają problemów.
Ciekawe co tam w Firefoxie/Operze namieszali...

Offline Kyroaku

  • Użytkownik

# Listopad 03, 2015, 22:32:57
Cytuj
To standardowy BMP 8-bit RLE - szczerze nie spodziewałem się, że liby będą miały z nim problem (szczególnie, że przeglądałem sporo implementacji loaderów BMP i większość z nich sobie spokojnie z RLE 8-bit radziła).
Ależ nie mają problemu.
Zarówno FreeImage, jak i SDL poprawnie czytają 8-bit RLE. Nie czytają tylko i wyłącznie waszej bitmapki :D
Wczytałem to photoshopem i zapisałem w formacie 8-bit RLE.
Wczytało się :)

Cytuj
O, ciekawe. Opera też wyświetla tak jak Firefox.
Jeśli chodzi o częsciową niezgodność kolorów pikseli, to paint też sobie nie radzi. Co dziwniejsze, mimo, że obraz jest źle wyświetlany, to po zapisaniu go do "normalnego" formatu wszystko się zgadza :)

Wasze dzieło zagina cyber-przestrzeń :)

Offline albireo

  • Użytkownik

# Listopad 03, 2015, 23:04:13
Jeśli chcecie sprawdzać dokładność działania, to pasowałoby podać parę szczegółów, jak:
- czy źródło światła jest punktowe (i czy w takim wypadku leży w środku piksela, czy w węźle siatki), czy obszarowe (cały piksel, a może koło o średnicy piksela),
- kiedy piksel uznajemy za oświetlony: jeśli światło dociera do niego w jakikolwiek sposób, jeśli dociera do jego środka, oświetla 50% powierzchni czy może oświetla go w całości
- czy piksel blokujący światło jest kwadratem, czy kołem (w tym drugim przypadku ukośne linie będą miały prześwity).

# Listopad 04, 2015, 01:07:10
Ależ nie mają problemu.
Zarówno FreeImage, jak i SDL poprawnie czytają 8-bit RLE. Nie czytają tylko i wyłącznie waszej bitmapki :D
Wczytałem to photoshopem i zapisałem w formacie 8-bit RLE.
Wczytało się :)
Fun fact - ten BMP był wygenerowany przez GIMP ^_-
Mógłbyś mi wysłać plik wygenerowany photoshopem na mejla? [email protected]

Jeśli chodzi o częsciową niezgodność kolorów pikseli, to paint też sobie nie radzi.
Hmm, sprawdziłem na MSPaint na Windows 7 i 10 i na obu wygląda OK. Z jakiej wersji painta korzystałeś?

Co dziwniejsze, mimo, że obraz jest źle wyświetlany, to po zapisaniu go do "normalnego" formatu wszystko się zgadza :)

Wasze dzieło zagina cyber-przestrzeń :)
^_- What the... ;)


@albireo
Jeśli chodzi o dokładność, to przede wszystkim sprawdzimy, czy bitmapa nie została zmniejszona przed wyliczeniem światła. Nie mieliśmy w planach czepiać się drobnych różnic w wynikach (takich na poziomie pojedynczych pikseli).

Odpowiadając na Twoje pytania:
- światło punktowe; ad w którym miejscu piksela leży punkt - ja bym zostawił tu dowolność, chyba, że Dab się ze mną nie zgodzi
- "kiedy piksel uznajemy za oświetlony" -tu bym też zostawił dowolność
- piksel jest kwadratem i między pikselami nie ma prześwitów (nawet, jeśli stykają się tylko rogami)

Dab, co sądzisz o tym?

Offline Dab

  • Redaktor
    • blog

  • +1
# Listopad 04, 2015, 01:24:46
Przyjmijmy takie założenia:
- światło punktowe położone na środku piksela
- kiedy piksel oświetlony - dopuszczamy dowolność w implementacji
- piksele są kwadratami bez prześwitów

Zdajemy sobie sprawę że rasteryzacja na liczbach całkowitych rządzi się swoimi prawami wobec czego nasze testy będą uwzględniały dopuszczalną (nie)dokładność.

Offline albireo

  • Użytkownik

# Listopad 04, 2015, 09:17:08
Nie mieliśmy w planach czepiać się drobnych różnic w wynikach (takich na poziomie pojedynczych pikseli).
Tyle że bez doprecyzowania tego co podałem, to w zależności od doboru warunków, różnice w niektórych przypadkach mogłyby być ogromne, założenia Daba dają już dość sensowną porównywalność.
« Ostatnia zmiana: Listopad 04, 2015, 09:35:34 wysłana przez albireo »

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Listopad 04, 2015, 09:30:49
Cytuj
Zdajemy sobie sprawę że rasteryzacja na liczbach całkowitych rządzi się swoimi prawami wobec czego nasze testy będą uwzględniały dopuszczalną (nie)dokładność.
Rasteryzacja czego? Może za dużo swego czasu się bawiłem na OI i ACM, ale mi to wygląda jak typowe zadanie na miotłę i z dodatkiem wektorów na liczbach całkowitych wyznaczenie oświetlenia wygląda że można zrobić o O(1) względem liczby pikseli.


Co do określenia całego zadania widzę tu jeszcze jedno ważne pytanie:
- czy piksel zasłania sam siebie? (tj. czy wszystkie blokujące piksele mają być nieoświetlone, czy zewnętrzna warstwa pikseli jednak ma być oświetlona?)