Flappy bird¶
У популарној игри Flappy Bird птица лети и не сме да додирне препреку. Игра је реализована тако што се птица налази стално у средини екрана (хоризонтално). Корисник управља птицом помоћу једног тастера тастатуре тако што је притиском на тај тастер подиже горе (она иначе стално пада на доле). Реализуј ову игру помоћу PyGame. Птичицу представи кругом, а препреке правоугаоницима који се спуштају са врха екрана наниже и са дна екрана навише. Између свака два пара правоугаоника треба да постоји пролаз кроз који се птица може провући. Програм се искључује у тренутку када птица дотакне препреку.
Централни део задатка чини провера да ли се наша лоптица сударила са правоугаоником. Круг сече правоугаоник ако и само ако јој се центар налази унутар правоугаоника или сече неку од његових ивица. Правоугаоници који чине наше препреке су постављени тако да су им све четири ивице паралелне координатним осама (две ивице су вертикалне, две су хоризонталне).
Размотримо прво како ћемо одредити да ли круг сече неку од вертикалних ивица препреке (с обзиром на природу игре, биће довољно проверавати само судар са левом вертикалном ивицом сваког правоугаоника). Нека је центар круга тачка \(O\) са координатама \((c_x, c_y)\) и нека му је полупречник једнак \(r\). Нека су темена вертикалне ивице правоугаоника тачке \(A\) са координатама \((x, y_1)\) и тачка \(B\) са координатама \((x, y_2)\). Јасно је да је пресек могућ само ако и само ако се довољно приближила тој ивици и није се превише удаљила од ње. Пресек може да постоји ако и само ако је хоризонтално растојање између центра круга и вертикалне праве на којој се налази дуж мање или једнако \(r\) тj. пресек може да постоји акко важи \(|c_x - x| \leq r\) тј. \(x - r \leq c_x \leq x + r\). Ако се \(c_x\) налази у интервалу \([x - r, x + r]\) пресек може, али не мора да постоји – то зависи од \(y\)-координате центра \(c_y\). Јасно је да пресек сигурно постоји ако се \(c_y\) налази у висини дужи (између \(y_1\) и \(y_2\)), међутим, могуће је да је центар мало изнад или мало испод висине дужи, а да пресек и даље постоји.
Одредимо које су то граничне висине на којима се круг и дуж секу. Горњи гранични положај је онај у којем круг само додирује дуж тј. садржи тачку \(A\). Означимо са \(M\) тачку која представља пројекцију тачке \(A\) на вертикалну праву која садржи центар круга \(O\). Троугао \(AOM\) је правоугли, са хипотенузом \(OA\) и катетама \(OM\) и \(MA\). На основу Питагорине теореме важи да је \(|OA|^2 = |OM|^2 + |MA|^2\). Пошто \(A\) лежи на кругу, знамо да је \(|OA| = r\). Такође, знамо да је \(|MA|^2 = (c_x - x)^2\). На основу тога, можемо да израчунамо да је \(|OM| = \sqrt{r^2 - (c_x - x)^2}\). Дакле, гранична висина центра \(c_y\) изнад које круг престаје да сече дуж је \(y_1 - |OM|\) тј. \(y_1 - \sqrt{r^2 - (c_x - x)^2}\). На веома сличан начин можемо одредити да је доња гранична висина једнака \(y_2 + \sqrt{r^2 - (c_x - x)^2}\).
Дакле, потребан услов да би круг секао дуж је да важи да \(c_x\) припада интервалу \([x-r, x+r]\), а ако то важи, онда је потребан и довољан услов пресека то да се \(c_y\) налази у интервалу \([y_1 - d, y_2 + d]\), где је \(d = \sqrt{r^2 - (c_x - x)^2}\).
Продискутујмо још и то да услов да \(c_x\) припада интервалу \([x-r, x+r]\) увек обезбеђује да је поткорена величина ненегативна. Заиста, важи да је \(|c_x - x| \leq r\), па отуда следи да је \((c_x - x)^2 \leq r^2\).
Потребно је још одредити да ли лоптица сече хоризонталну ивицу препреке. То би се могло урадити веома сличном анализом претходној, чиме би се добио наредни кôд.
Међутим, можемо и једноставније, ако анализу пресека круга са хоризонталном дужи успемо да сведемо на проблем пресека са вертикалном дужи. Пошто изометрије чувају инциденцију важи да круг сече дуж ако и само ако се њихове слике добијене применом неке изометријске трансформације секу. Потребно је да пронађемо неку изометријску трансформацију која хоризонталну дуж пресликава у вертикалну. Једна од најједноставнијих таквих је осна симетрија око праве \(y=x\). Том трансформацијом се произвољна тачка \((x, y)\) пресликава у тачку \((y, x)\). Круг са центром у тачки \((c_x, c_y)\) полупречника \(r\) се пресликава у круг са центром у тачки \((c_y, c_x)\) такође полупречника \(r\). Хоризонтална дуж са теменима \((x_1, y)\) и \((x_2, y)\) пресликава се у вертикалну дуж са теменима \((y, x_1)\) и \((y, x_2)\). Стога се пресек са хоризонталном дужи може веома једноставно испитати на следећи начин.
Сада можемо веома једноставно дефинисати функцију која проверава да ли се круг и правоугаоник секу.
Препреке чувамо у листи. Свака је препрека уређен пар два правоугаоника. Сваки правоугаоник је одређен четворком бројева који представљају координате његовог горњег левог темена, ширину и висину. У сваком кораку анимације све препреке померамо надесно (тако што пролазимо кроз листу препрека и умањујемо све x координате горњих левих темена правоугаоника). Ако се прва препрека у низу померила испред левог краја прозора, избацујемо је из низа. Ако се последња препрека у низу померила довољно од десног краја прозора, на крај низа убацујемо нову препреку са насумично одређеним положајем пролаза. У сваком кораку такође проверавамо и да ли птица сече неки од правоугаоника који сачињавају препреке и ако сече неки, искључујемо програм. Реагујемо на догађаје тастатуре и када детектујемо притисак на дугме, умањујемо y координату птице (тако подижемо птицу навише). Иначе, у сваком кораку анимације птицу спуштамо мало наниже.