C je high level jezik?!?

Dosta literature, a i predavanja na fakultetu (još uvjek) na spomen programskog jezika C istiće da je isti high level jezik. S druge strane, npr. diskutirate s nekim o izradi grafičkog enginea, kada se kaže da nešto treba napraviti na low level razini, zapravo znači da to treba biti napisano C-u. Uzrok te dvoličnosti C-a se može objasniti tromošću prilagodbe obrazovnih materijala novim tehnologijama. Dok neki iskusan programer napiše knjigu ili postane profesor, prođe 5 do 10 godina a u tom vremenoskom razdoblju svijet se dvaput prevrne.

Kako se mišljenje o tome što je high level mjenja s vremenom, neki su se dosjetili da umjesto pojmova low level i high level uvedu nazive koji zapravo govore što je na kojoj razini. Jedan od takvih pokušaja su generacije jezika (http://www.computerhope.com/jargon/num/1gl.htm), no i tamo je C high level jezik a sve što je iznad je praktički ljudski jezik. Što pak nije istina, između C-a (3. generacije jezika) i skriptnih jezika (4. generacija), postoje jezici kao što su C++, C# i Java. Drugi od pokušaja su paradigme. C je primjer proceduralne paradigme a Java i C#, objektne. Na trećem mjestu idu još dalje, paradigme su omotane u modele:

• model zasnovan na proceduralnoj paradigmi
• model zasnovan na objektima
• model zasnovan na komponentama
• model zasnovan na uslugama

Taj treći primjer je zanimljiv jer pokazuje kako trenutni modeli već nadilaze moderne programske jezike. Komponenti model se relativno lagano ostvaruje pomoću objektnog modela ali za model usluga, u većini slučajeva, još uvjek nema načina da ga se ostvari bez gubitka apstrakcije. Vjerojatno će se uskoro pojaviti nešto kao što je C++ bio u vrijeme C-a.

Suma sumarum, nakupilo se razina iznad assemblerskih jezika i high i low level nazivlje se svakako treba osuvremeniti. Moji osobni pristup bi bio slijedeći:

• Sklopvska razina (hardware i možda strojni kod)
• Assemblerska razina (assembler i možda strojni kod, stari low level)
• Algoritamska razina (današnje poimanje low levela)
• Objektna razina (povezivanje algoritama)
• Komponentna razina (povezivanje procesa)
• Razina usluga

Anegdote podrazumjevanog

Joj joj joj. Napravim nekom program, meni radi korisniku ne. Popravim problem i nakon nekog vremena novi problem. Na drugom mjestu al zbog iste stvari. Zvuči ko da sam šeprtljavo napravio program, je l' da? Dam vam 5 minuta, razmislite. Koliko je teško pretvoriti niz znakova u broj?

Vrlo

Vrlo teško, pogotovo kad ne znate da l imate decimalnu točku ili zarez. To što ste si u operacijskom sustavu postavili možete si objesit za rep, to vam korisnik programa može a i ne mora poštivati. Eeee, al ima još jedna zamka jer da je nema, mogli bi ste točku ili zarez pretvoriti u znak po volji i dalje imat predvidivu situaciju. Zamka je u tome što je sasvim legalno imati znak koji razdvaja tisućice. A da zamka bude s otrovanim šiljcima, taj znak je isto ili točka ili zarez. I za to bi mogli smislit postupak koji pazi na to ali tada smo već daleko od jednostavnosti i korak bliže umjetnoj inteligenciji. Eh, ni umjetna inteligencija ne bi radila ak ne bi znala "domenu" odnosno koji raspon brojeva očekivati. To vam je stvar koja se podrazumjeva da kao programer znate napraviti.

Locale

U C#-u (a valjda i Javi) ugrađene funkcije za pretvaranje stringa (niza znakova) u broj gledaju u postavkama operativnog sustava koji su znakovi za što u formatu brojeva i na temelju toga vrše pretvorbu. No, po mom sudu, škrtare na dojavi pogreške. Da vam ispričam jednu anegdotu.

Na svom računalu postavke o formatu brojeva imam uštimano na ono što sam učio u osnovnoj školi: tisućice odvajaj s pola razmaka a decimale s točkom, ne sa zarezom nego s točkom. Pošto pola razmaka nije lako za utipkat, obično stavljam cijeli. I s tim postavkama sam počeo raditi Zvjezdojeca i bilo mi dobro na Zemlji. Jednom prilikom sam bio dao frendu proba Zvjezdojeca na svom računalu, i kako je upalio igru odmah sam imao što vidjet. Zvijezde su bile pre prevelike. Tada nisam znao u čemu je problem a Vi iz teksta kojeg sam napisao možete pretpostaviti. Problem sam skužio tek kada sam reinstalirao operativni sustav. Naime, prije toga nisam mogao na svom računalu rekonstruirati problem a nakon reinstalacije sam zaboravio pošimat format brojeva. Pošto Microsoft misli da mi Hrvati koristimo točku između tisućica i zarez između decimala i cijelobrojnog dijela broja, ugrađene funkcije za pretvaranje stringa u broj su krivo tumačile tekst. Tekst koji glasi "0.2" bi prevele u broj 2. Osobno bih za takvo nešto očekivao da mi baci NumberFormatException iznimku s tekstom "kak moš imat 0 tisućica i nakon toga samo 2 bez još 2 znamenke?". Ono što je bilo još gore u cijeloj priči je da je taj propust u ugrađenim funkcjama bio vidljiv samo djelomice. Kada su veličine jednog tipa zvijezda trebale biti pomnožene s faktorom između 0.2 i 0.6, on bi množio s faktorom između 2 i 6 a ja bi jednostavno vidio 10 puta veću sliku nego što bi trebala biti i tražio bi uzrok na totalno desetom mjestu. Hvala Bogu, imo sam tip zvijezda koji ima faktor veličine između 0.7 i 1, koji kada se krivo prevede je od 7 do 1 a pošto je tada minimum veći od maksimuma, ispalo je da su zvijezde tog tipa bile sve iste veličine.

MS SQL Express 2005

U svojoj igri mogu reć da ću svugdje koristiti određen znak. Korisniku aplikacije mogu reć da je krivo unio broj. Ali bazi podataka ne mogu reć da je sama sebi nedoslijedna. To je još jedan biser oko pretvorbe teksta u broj i broja u tekst. MS SQL baza iz naslova će vam uredno vratiti unose s decimalnim zarezom odnosno točkom, ovisno o tome kako imate u OS-u postavljeno ali kad unosite podatak on mora biti s točkom. I opet, kod mene radi a kod korisnika ne. I samo za MS-ovu bazu moram ubacivati dio kôda koji ko za retardirane pretvara broj u tekst koji ona može prihvatiti.

Hvala Bogu sad to radi! A ima vam još jedna zafrkancija oko obrade teksta s kojom još nisam morao imati posla, sortiranje. Što po abecedi ide prije? C ili Č? U nas Hrvata C je l' da. E, al kako idu E-ovi s črčkama? Poredajte mi po abecedi E, Ě, Ę, É i Ë.

Matematičko savršenstvo i pilotiranje

Projekt svemirske simulacije sporo se kreće, primarno jer skoro uopće ne radim na njemu, baveći se umjesto toga obiljem drugih stvari (koje, eto, ipak nisu društvenog i sportskog tipa). Zadnji put sam pisao o filozofskim i praktičnim problemima rada na 3D AI-ju. Ono malo što radim na njemu, pokazuje kako, za razliku od naziva ovog bloga, to baš i ne radi.

Pa o čemu se radi?

Kako (valjda) rekoh i prije, jako se treba paziti na svaki detaljčić, i borba protiv kolizije postaje jednako bitna kao i sama borba. Niti ne pokušavam pokriti slučaj gdje brod svojim skretanjem može udariti u drugi brod koji, eto, nailazi istim putem. Zasad bi to bilo previše za jedan projektić koji radim u slobodno vrijeme. Naravno, možemo razmišljati o raznim teoretskim rješenjima kao "ajde prođi sve pod kutem prema kojem se krećeš, i ako ti je tamo prepreka, odluči ići negdje drugdje". No prvo treba napraviti rješenje da brod uopće dođe do jednog odredišta prema kojem je odlučio letiti, a bez da se zaleti u neki drugi komad metala koji lebdi.

Slijedi opis moje ideje za AI, a nakon toga daljnja osobna gnjavaža.

Eksperimentalni AI

Naš AI nazovimo Pilotom koji rješava Zadatke.

 Dakle Pilot odluči koje zadatke će vršiti paralelno, i nakon što se oni odvrte, koji će se zatim početi rješavati. Očito, pilot ima listu zadataka koji idu jedan iza drugoga -- to jest, nakon što jedan završi, odmah se pokrene sljedeći na listi. Svaki zadatak ima listu paralelnih zadataka. Sam zadatak nije gotov dok i svi njegovi paralelni zadaci nisu gotovi.

Pilot može biti agresivac, pasivac, kukavica, trgovac -- uglavnom, možemo za različite karakterne osobine imati različite klase s definicijom koda pilota (PilotTrgovac, PilotAgresivan). Naravno, ne moramo; sve to mogu biti mali parametri. Također, možemo imati i nazovi-apstraktnog pilota, a to je PilotMrezni odnosno PilotIgrac, ili pak PilotDaljinskiUpravljan. Trenutno ne implementiram igrača kao pilota koji prima input, ali teoretski mogu i čak je moguće da ću to odraditi. Ovi ostali piloti očito neće imati tipične zadatke i tipično odlučivanje. PilotMrezni recimo uistinu ne treba imati zadatke, kao ni PilotIgrac, ali PilotDaljinskiUpravljan prima konkretne precizne naredbe od igrača.

A kakvi zadaci mogu postojati? Primjer jednog zadatka je ZadatakLeti (JobFly). Ovaj zadatak je trenutno jedini koji implementiram, a trenutno sadrži i kod za odlazak na neko odredište, ali i kod za slijediti nekoga. Planiram uskoro razdvojiti ovaj zadatak u dva: ZadatakLeti i ZadatakSlijedi.  Također, može postojati i ZadatakPucajDoPrilaska, ZadatakPucajStojecki, i slično. Zadaci ne sadrže pametno odlučivanje.

Trenutno u svojem jedinom zadatku implementiram detekciju prevelikog približavanja meti, detekciju potencijalne kolizije i slično. Konceptualno, to je krivo, i to leti van iz koda, odnosno o tome će odlučivati Pilot. Naime, Pilot može uistinu željeti zaletiti se u odredište. Takav je Pilot, primjerice, projektil. Stoga, svi zadaci trebaju biti vrlo jednostavni. Možemo uistinu implementirati dio kontrole kada je ona uistinu korisna (ZadatakPucajDoPrilaska), odnosno onda kada nam uistinu odgovara naslagati nekoliko naredbi za redom, no zadatak ne smije sam određivati paralelne zadatke ili one koji slijede nakon njega.

E sad, kako najavih, prelazimo na jadanje.

Programersko prigovaranje

Pilot i jedini implementirani zadatak, kao što je par puta rečeno,  trenutno imaju nekoliko gadnih konceptualnih propusta. Zadatak pokušava previše odlučivati, a Pilot to radi premalo. Sve to je tako jer je AI eksperimentalan i work-in-progress. Da nisam ovo napravio, ne bih ni znao da postoji kriv način izrade AI-ja.

Trenutno AI bi trebao implementirati napadački mentalitet. AI pokuša letiti prema igraču, no odluči da će se sudariti i izbjegava ga tako da predaleko odleti. Zatim se vrati, i počne kružiti u blizini igrača, gotovo nikada ga ne naciljajući  zastvarno jer, jednostavno, kruži preblizu. Najvažnije pitanje je ovdje, otkuda AI-ju ideja da tako daleko odleti, a zatim da ne ponavlja to ponašanje?

 Spomenuo sam u naslovu matematičko savršenstvo. To se odnosi na pilotovo izbjegavanje.

Tu je ključna bila detekcija točne točke kolizije ako se pilot nastavi gibati po istom pravcu. Svaki objekt sastavljen je od više sudarnika (collidera). Sudarnik može biti ili kugla, ili trokut. Relevantne točke (jedna ili tri) definirane su relativno u odnosu na objekt u svemiru.

Imam veliku sreću da sam naletio na odlični ozcollide ruskog programera Igora Kravčenka koji je odradio velik dio prvog ciklusa gradiva Matematike 2, a i više. Ova biblioteka (il' što bi neki profesori rekli, "knjižnica" ... brrrr) uvelike mi je olakšala koliziju kugle i trokuta, te trokuta i trokuta. Štoviše, biblioteka za neke od kombinacija predviđa i udaljenost do sudara za zadani vektor brzine -- točno ono što meni treba!

No biblioteka ne pokriva kombinaciju kugla-kugla. A ja sam, kako je poznato, vrlo ... kržljav što se tiče matematike. Stoga sam potrošio velik dio razmišljanja u zadnjih par "sessiona" bavljenja igrom upravo na razmišljanje i pokušaje implementacije gore navedenog. S obzirom da sam vrlo sklon greškama u implementaciji imalo složenijih fora od y=x+5, tu sam zapeo, no uz ideju i određenog "rješavača" matematičkih formula koji nosi ime po prvom grčkom slovu, te uz odvojeni mali frameworkić za testiranje koji sam si složio, i to sam implementirao. Je, vraga. Treba paziti i na jezik u kojem se radi, na svako moguće dijeljenje i množenje, da ne bi ispalo cjelobrojno ... vražji C/++ :-)

I eto, dobijem točku gdje se kugla premjesti da bi udaljenost centara bila točno R1+R2, i zatim povučem liniju između dvije kugle, shvatim kao vektor, normaliziram je i pomnožim s R1. Konačno dodam na onaj "odredišni" (x,y) gdje će kugla biti. Voila! Riješeno.

Za referencu, rješava se ova formulica:

[(x_1 + t v_x) - x_2]^2 +  [(y_1 + t v_y) - y_2]^2 + [(z_1 + t v_z) - z_2]^2 = (R_1 + R_2)^2

(Lakše ćete je pročitati ako je kopirate u OpenOfficeov matematički modul. Osim toga... skoro pa je TeX :-) )

Za lakše shvaćanje, i lijeva i desna strana su kvadrirane. Lijeva bi trebala biti pod korijenom i time dati udaljenost između točke (x_1+tv_x, y_1+tv_y, z_1+tv_z) i točke (x_2, y_2, z_2). Ta udaljenost treba biti R_1+R_2, te kada to izjednačimo dobijemo parametar t -- odnosno njih dva -- pomoću kojeg možemo odrediti odredišnu točku, tj. prvu od dvije koje sam napisao u ovom odlomku.

U rješenju računam da brzina postoji, tj. da bar jedan od v_x, v_y i v_z nije 0. Inače se kolizija nikako ne događa. To rješava problem nule u nazivniku. Također, dobivamo dva rješenja -- jedno na ulazu, a drugo na izlazu iz kolizije. Ako uzmemo ono bliže, to je to. Po iskustvu, to bi trebalo biti ono kod kojeg nemamo negativni predznak.

I sve to računanje...

Poanta ove priče je ... rezultantna formula je podulja, uključuje mnogo kvadriranja, jedan korijen jedno dijeljenje. Bez nekih benchmarka, iznijet ću ono što se može vidjeti u kodu Ogre3d
enginea: sqrt() je skup. Ogre3d zbog toga ima getSquaredDistance() u vektoru, koji ga izbjegava.

Što bi mogli napraviti? Da li bi bilo brže napraviti nekakav fiksan set koraka koji gleda kvadriranu udaljenost i procjenjuje da li je dovoljno daleko udaljeno, i lupiti aproksimiranu brojku?

Iskreno, za ovo uopće nemam ideje kako to gluplje i brže izvesti. Osim toga, ovo se queryja kao zadnji korak -- ako objekti nisu dovoljno blizu da bi se skoro mogli kolidirati, onda uopće ne moramo razmišljati o tome koliko ovo traje.

Zašto uopće pričam o jednostavnijim rješenjima? Jer sam nedavno imao gadnih problema s jednom malom 2D igrom koju je trebalo napraviti. Umjesto da posegnem za što jednostavnijim rješenjem (povuci liniju, gledaj gdje se prvo kolidira, ograniči pomak do tamo), igrao sam se s pravim, matematičkim rješenjem sličnim ovom gore. Nažalost, cijela logika igre je umirala, a zbog neadekvatno delimitiranih objekata (što-je-tu-je) koje nisam mogao srediti na jednostavan način, postojala je hrpa rupa i nedozvoljenih poteza koje je igrač ipak mogao raditi. Nakon tjedan i pol rješavanja svega toga, nisam bio ništa bliže rješenju. To matematičko rješenje je na kraju odbačeno, i sad igra radi čudno, loše, ali bar igrač ne može raditi nedozvoljene poteze.

U predikciji odnosno predviđanju sudara kugli, formula ispada tako jednostavna. Dugačka, ali jednostavna i čista. Meni na sramotu je što mi je dugo trebalo da to izvedem kako spada.

Uz nadu da sljedeći post neće biti tek za 2 mjeseca, lijep pozdrav, i ne zaboravite čitati EmPov primarni blog (link sa strane). A tko zna, možda se pojavi i koji Kramerijanski post :-)