sobota, 23 marca 2013

Edytor map w MS Excel / LibreOffice Calc

Pare dni temu widziałem prostą gierkę pisaną przez początkującego programistę. Gra polega na chodzeniu ludzikiem (znak ASCII) po mapie rysowanej kodem ASCII. Nie ma szału, ale to doskonały projekt aby wykazać że dobra organizacja kodu ratuje (grzebie) projekt.

Osoba pisząca tą grę wymyśliła sobie problem rysowania mapy w ten sposób, że każda mapa była rysowana oddzielną procedurą. Okey... ale skąd brano topologie mapy? No jasne, że z palca! Każda linia mapy była pisana z palca, znak w znak. W zasadzie procedury rysujące mapy różniły się jedynie sekwencją znaków, a nie samym działaniem. Koszmar :/

Podrzuciłem pomysł rysowania mapy w Excelu. Tak, tak.. w tym arkuszu kalkulacyjnym. Tutaj pokaże to samo używają OpenOffice / LibreOffice Calc, aczkolwiek w Excel też zadziała.

Moja gra będzie oparta na scenariuszu chodzenia po mapie przypominającej labirytnt. Zakładam, że ściany będę oznaczał symbolem "x", podczas gdy punkt startowy gracza oznaczę "@", a punkt docelowy przez "&". Okey, a co ma do tego Excel?

Zaznaczam wszystkie wiersze i kolumny ( przycisk nad wierszem 1, na lewo od kolumny A ), ustalam szerokość kolumny na 0,8 ( zlokalizowane arkusze kalkulacyjne używają przecinka jako separatora części ułamkowej ).


Teraz cały arkusz wygląda mniej-więcej, jakby był złożony z kwadratów. Chciałbym, aby po wstawieniu w komórkę znaku x ta komórka się zaczerniła. Dzięki temu będę lepiej widział jak wygląda rysowana mapa. Aby nie kolorować ręcznie, użyję formatowania warunkowego.
Ustalam 3 reguły:
  • czarne tło dla znaku x
  • zielone tło dla znaku startu @
  • czerwone dla końca &


[ LOffice Calc sprytnie zauważy, że czarny tekst na czarnym tle jest średnio widoczny, więc automatycznie wypełnione na czarno komórki będą miały kolor czcionki zmieniony na biel ]

Mapa wyświetlana na terminalu Windows ma domyślnie 80x25 znaków, czyli plansza w Excel zaczyna się na komórce (A,1) a kończy na (CB, 25). Postawiłem ramkę wokół tego obszaru + zmieniłem domyślne tło na niebieski. Dzięki temu nie przedobrzę z obszarem rysowania.

Tak oto za pomocą stawiania x-ów, jednego startu i jednego końca namalowałem mapę. Tutaj jest ona dużo węższa, niż szerokość terminala, ale to w niczym nie przeszkadza.


Ważne, że to co widać w Excel będzie wiernie odwzorowane na ekranie gracza. Tak zrobioną mapę zapisuję do formatu CSV ( comma separate values ). Jako separator ustawiam średnik ( ; ). Urok formatu CSV polega na tym, że w wypadku danych numerycznych obsługuje go każdy cywilizowany program obliczeniowy - począwszy od R przez Matlaby, MathCADy, Mathematica, Octave, NumPy a kończywszy na Excel i Calc. Dodatkowo ten format jest idealny do parsowania. Prościej się nie da.

Po obejrzeniu tego pliku w dowolnym edytorze tekstowym powinien on wyglądać mniej więcej tak:
Puste komórki zostały pominięte, czyli zapis ;; oznacza, że dana komórka nie miała wartości. Obraz może wydawać się "rozjechany", ale bezproblemowo można go poskładać, tj. usunąć znak separatora, a puste pola zamienić na spację. Terminale używają czcionek monospace, dzięki czemu całość pięknie wyrówna się na ekranie.

Na szybko napisałem funkcję, która realizuje wyświetlenie takiego pliku mapy w formacie CSV na konsoli. Kod:

#include <iostream>
#include <fstream>
using namespace std;

inline void parseLine(string s)
{
 char c;
 char delim=';', fill=' ';
 size_t pos=-1;
 
 if (s.empty()) return;
 
 do {
  pos = s.find(delim, pos+1);
  if ( pos != string::npos )
  {
   if ( pos==0 || s[pos-1]==delim) cout << fill;
   else cout << s[pos-1];
  }
 } while (pos != string::npos);
 
 cout << ( c=s[s.size()-1],c == delim ? fill : c ) << endl;
}

int main()
{
 ifstream mapa("mapa.csv");
 string s;
 

 if (!mapa)
 {
  perror("Blad ladowania mapy");
  return -1;
 }

 while ( !mapa.eof() && mapa )
 {  
  getline(mapa, s);
  parseLine(s);
 }

 mapa.close();
 return 0;
}

W rezultacie całość wygląda w konsoli tak:


Przy tak prostych aplikacjach wysilanie się na własny edytor map jest przerostem formy nad treścią. Bardzo zachęcam do korzystania np. z Calc/Excela w takich sytuacjach.

środa, 20 marca 2013

MongoDB, NoSQL, Spring Data i Strefa 89

Dzisiaj w Strefie 89 obyło się szkolenie z MongoDB prowadzone przez Macieja Walkowiaka ( organizatorem był JUG ). Szkolenie super. Oprócz szybkiego wprowadzenia do idei NoSQL pokazano także Spring Data mongoDB. W zasadzie to 80% szkolenia poświęcone było SDmDB.

Nie jestem przekonany, że Java to najbardziej elastyczny język świata, natomiast wygoda operowania danymi, jaką utworzono w SDmDB bardzo zaskakuje. Łatwość mapowania dokumentów Mongo na klasy, predefiniowane operacje pobrania i filtracji niezależnie od sposobu budowy dokumentu, rozwiązywanie dziedziczenia, etc ... przerosła moje oczekiwania.

Trochę głupio mi to powiedzieć, ale czas powoduje, że przełamuję się do Javy.

Dodatkiem do dobrego wrażenia jest Strefa 89. Niesamowite miejsce z bardzo kreatywnym wnętrznem, barem, przestrzenią co-workingu oraz fajną atmosferą. Lokalizacja w samym centrum Szczecina, prawie na deptaku.

Polecam ^^

sobota, 16 marca 2013

Darmowe wykłady renomowanych uczelni

Otwarte, darmowe kursy prowadzone pod szyldem renomowanych uczelni ( Stanford, Princeton, University of California ... ) z rozmaitych dziedzin: od produkcji muzyki przez antropologię, programowanie i kryptografię.

Wszystko za friko: https://www.coursera.org

sobota, 9 marca 2013

Znalazłem bardzo, bardzo dobry podręcznik do matematyki dla informatyków. Napisany jest lżej, niż "Matematyka konkretna" Grahama. Całość za darmo i dostępna online ^-^

Eric Lehman and Tom Leighton: "Mathematics for Computer Science" - http://www.cs.princeton.edu/courses/archive/spr10/cos433/mathcs.pdf

wtorek, 5 marca 2013

Warsztaty dla studentów piszących w C, Java, PHP

SzLUUG organizuje cykl szkoleń dla studentów wprowadzający w świat "realnego programowania", czyli pracy w środowisku wieloosobowym, z rozbudowaną dokumentacją, metodologią, z dużym kodem źródłowym.
Chcemy pokazać studentom coś nowego + zainteresować ich programowaniem pod Linux (kto nie spróbował nie zrozumie) + zachęcić do FLOSS : jako idei, jako programów i jako sposobu aktywności.

Już w tą niedzielę (10.03) prowadzę warsztat z "realnego programowania" w C. Nie ma mowy o kursie języka. Zakładam, że uczestnicy będą go znać co najmniej w stopniu średniozaawansowanym i ruszymy z Linuxową otoczką programowania w C, czyli:
  • Autotools, bootstrap
  • configure i Makefile
  • Git
  • Czytanie dokumentacji
  • "Coding standards"
  • Branchowanie / diffowanie / commitowanie
  • Valgrind i gdb (oby nie trzeba było ;) )
  • SDL
  • Korzystanie z zewnętrznego API
Będziemy rozwijać projekt TuxPaint tworząc nowe filtry graficzne.

Zapraszam ^-^

poniedziałek, 4 marca 2013

Jak zrobić tablicę wielowymiarową bez tablicy wielowymiarowej

Załóżmy, że trzeba zrobić tablicę wielowymiarową. W C wielowymiarowość jest nieprzyjemna, szczególnie gdy chcemy uniwersalne funkcje operujące na tablicy o dowolnej wymiarowości. W C++ sprawa jest prostsza, bo są wektory, które można wzajemnie zagnieżdżać. Inne, że wygoda takiego rozwiązania jest podobna jak w C, z tym że odpada problem de-re-alokacji.

W Python jest NumPy, czyli jest cudownie ^^

Czy w zasadzie potrzebujemy tablic wielowymiarowych? Programowanie przypomina tworzenie filmu. Ważne jest co zobaczy użytkownik, a nie jak to powstało ( zastanawiam się czy aluzja do parówek nie była by bardziej stosowna ).

Załóżmy, że potrzebujemy napisać w C++ mechanizm wygodnej tablicy 1D, 2D i 3D. Nie chcemy robić wektora wektorów wektorów, bo to nieeleganckie, nieefektywne i siermiężne.

Tablicę dowolnej wymiarowości można trzymać w wektorze. Istnieje mapowanie tablicy dowolnej wymiarowości N na wymiarowość niższą, włączając jednowymiarową. Niech nasza tablica wygląda tak:

, a chcemy ją zapisać za pomocą wektora 1D, czyli szukamy mapowania


 Każde równanie mapujące tablicę ND na MD jest równaniem liniowym. My będziemy chcieli tablicę 2D sprowadzić do 1D. Sprowadzając cokolwiek do 1D nasze równanie będzie zawsze postaci wielowymiarowego równania linowego, np:





To, co stoi po lewej stronie to indeks liniowy, czyli pod którym indeksie w wektorze znajdzie się element, gdy tablicę ND sprowadzimy do wektora. W tym przypadku aby z wektora wydobyć element znajdujący się na w-tym wierszu i w k-tej kolumnie należy posłużyć się dwoma zmiennymi (w,k), czyli równaniem z dwoma zmiennymi:


Ściślej, nasze równanie będzie wyglądało i ( w, k ) = a*w+b*k+c. Niewiadomych ( a, b, c ) pozbędziemy się dzięki układowi równań. Typuję 3 indeksy z mojej tablicy, które posłużą mi do
wyznaczenia stałych ( a, b, c ). Zakładam dla siebie, że wiersze i kolumny indeksujemy od 0. Wektor w którym będziemy trzymać dane też jest indeksowany od 0. Wybrałem te elementy:



czyli dla elementów (w=1, k=2) wyliczam indeks liniowy (2), analogicznie dla elementów (w=1, k=0) oraz (w=1, k=1).


Gdyby wybrać indeks (w=0, k=0), od razu by było widać, że c=0.

Wracając, wśród współczynników widać wartość a=3. Ta trójka to nic innego, jak ilość kolumn w tabeli. Ostatecznie równanie funkcji mapującej 2D -> 1D to:

Widać, że  ilość wierszy nie ma żadnego przełożenia na to, pod jakim indeksem będzie trzymana wartość.

Poniżej kod prezentujący na szybko jak stosować taką tablicę:

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

typedef struct Tab2D
{
 private:
  vector<int> v; //jednowymiarowy
  size_t iw, ik;

 public: 
  typedef pair<size_t, size_t> wymiar;
  
  Tab2D(int w, int k, int wypelnienie=0)
  {
   v.resize( w * k, wypelnienie );
   iw=w;
   ik=k;
  }
  
  int& operator()(size_t indeksLiniowy)
  {
   return v.at ( indeksLiniowy );
  }
  
  int& operator()(size_t w, size_t k)
  {
   return v.at( w*ik + k ); //to wynika z rownania liniowego mapujacego 2D -> 1D
  }
  
  wymiar wezWymiar()
  {
   return make_pair(iw, ik);
  }
  
  void wypisz()     //TYLKO DO CELOW TESTOWYCH
  {
   cout << "-------" << endl;
   for (int w=0; w<iw; w++)
    for (int k=0; k<ik; k++)
     cout << w << ' ' << k  << ' ' << (*this)(w,k) << endl;
  }
 
} Tab2D;

int main()
{
 Tab2D t(3,2);
 
 cout << t.wezWymiar().first << ' ' << t.wezWymiar().second << endl;
 
 t.wypisz();
 
 for (int w=0; w<t.wezWymiar().first; w++)
  for (int k=0; k<t.wezWymiar().second; k++)
   t(w, k) = w+k;

 t.wypisz();

 return 0;
}

niedziela, 3 marca 2013

(C/C++) Smaczki ukryte w operatorach

Krzak pisał o tajemnym operatorze w C: downto, to może też dorzucę coś od siebie ;)

W C i C++ tablice nie są obiektami, natomiast swobodny dostęp do nich realizowany jest przez operator nawiasu kwadratowego. Truizm.

Czy wiesz, że taki kod:
char[] str="Alicja";
std::cout<< str[3] <<endl;

może być zapisany tak:

char[] str="Alicja";
std::cout<< 3[str] <<endl;

Zdziwienie?
W C++ operator [] jest przemienny, tj. tab[i] jest tożsame z i[tab]. To prowadzi do absurdalnych wniosków, jakoby mozna było indeksować liczby tablicami. Owszem, można.

Rozwiązanie zagadki: Tablice w C są wskaźnikami. Formalnie: tworząc tablicę na prawdę uzyskujemy wskaźnik do zadeklarowanego obszaru pamięci. Operator nawiasu kwadratowego na wskaźniku działa następująco:
std::cout<<tab[ind]<<std::endl;
//jest tozsame z
std::cout<<*(tab+ind)<<std::endl;

Skoro dodawanie jest przemienne, to *(tab+ind) jest tożsame z *(ind+tab), czyli ind[tab]. Oto cała tajemnica....

piątek, 1 marca 2013

Testowanie wizualne z Processing

Wspomniałem kiedyś o Processing, który ogromnie cenię za szybkość prototypowania algorytmów i wielopoziomowość. Z jednej strony daje łatwość współpracy obiektami wysokiego poziomu (np. abstrakcyjne struktury danych w Java, systemy okienkowe) oraz niskim poziomem, np. Arduino czy port szeregowy + operacje bitowe.

Pare dni temu siedziałem nad detektorem kolizji dla prostej gry 2D. "Coś" nie działało, więc pierwsze podejrzenie na funkcję analizującą, czy 2 prostokąty nachodzą na siebie. Wyglądało to mniej więcej tak:

boolean doesColide(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2)
{
    return (
                max(ax1, ax2) >= min(bx1, bx2) &&
                min(ax1, ax2) <= max(bx1, bx2) &&
                min(by1, by2) <= max(ay1, ay2) &&
                max(by1, by2) >= min(ay1, ay2)  );
}


Pisanie testów? Zdecydowanie nie. Testowanie interaktywne jest szybsze i łatwiej wypatrzeć gdzie algorytm się nie sprawdza. Przeniosłem kod tej metody do Processing ( czyli Javy :P ), obudowałem wizualizacją (jeden kwadrat nieruchomy, drugi porusza się wraz z kursorem). Jeżeli ruchomy jest zielony - brak kolizji. W przeciwnym wypadku - czerwony.

Czas pisania kodu: 2 minuty. Czas testowania: 2 minuty.
boolean doesColide(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2)
{
    return (
                max(ax1, ax2) >= min(bx1, bx2) &&
                min(ax1, ax2) <= max(bx1, bx2) &&
                min(by1, by2) <= max(ay1, ay2) &&
                max(by1, by2) >= min(ay1, ay2)  );
}

void setup()
{
 size(400, 400);
 background(255); 
}

void draw()
{
  background(255);
  rect(150, 150, 100, 100);
  if (doesColide(mouseX-50, mouseY-50, mouseX+50, mouseY+50, 150, 150, 250, 250) ) 
    fill(255, 0, 0);
  else fill(0, 255, 0);
  rect(mouseX-50, mouseY-50, 100, 100);
  fill(0);
}