Brainfuck Tutorial – part 3 (for expertes only!)

Ok, now let’s move into even more advanced stuff.

In this tutorial I will talk about conditions and booleans.

For making conditional statements, we need []. Let’s say you want to run a code only if a cell is ‘true’ (non zero). This one is the easiest!

[ [-] your code ]

“your code” only runs if the initial cell is non zero. After entering the first loop it clears the cell so it won’t repeat ‘your code’ again and again.

Let’s say you want to run a code if a cell is not true. Our structure is like this

..ab..
..^

And here is the code. I put some comments (numbers) into code so hopefully it will be easier to understand.

1>+< 2[[-]>-<] >[ - your code ]<

We need a temporary cell for this stuff. In this example a is the test value and 'your code' will only run if it is 0. b is the temporary cell.

First (1) it sets b to 1. After that (2) it returns to a and sets be to zero again if a is non zero. In next step (3) it goes back to b and run your code only if b is non zero.

Basically we are holding !a in another cell. If a is zero, b remains 1 and code will be executed. If a is non-zero, b will be cleared so 'your code' won't run.

After those simple booleans, on next tutorial, I will talk about == and !=. It is actually quite easy, see ya!

Game of Life (WebGL)

WebGL üzerinde geliştirdiğim bir game of life implementasyonu (hemen hemen kullandığım bütün platformlarda/dillerde geliştirdim sanırım :))

Güzel yanı tamamen opengl olması, çizimlerin yanında hesaplamalar da shader’lar ile yapılmakta.

Aslında tahtanın boyu 2048*2048 boyunda, canvas’ın boyu ise 300×300. Sağ tuş işe zoom out yapabilirsiniz. Wrap yaptığı için pek farkedilemeyecektir sınırlar, sanki sonsuza gidiyor gibi ama değil 🙂

İleride önceden tanımlanmış initial state ler falan koyacağım, bir de belki daha smooth geçiş verebilirim pixellere. Ayrıca ana sayfada birden fazla webgl olunca performans sıkıntıları başladı, belki aynı anda sadece bir tane oynatacak şekilde çalışmaları sağlanabilir.

edit: hayalimdeki haline geldi gibi, ayrıca tam ekranda çıkacak şekilde bir sayfa yaptım, buradan ulaşabilirsiniz.

Sleepsort (hem de BF ile!)

Favori sıralama algoritmalarım arasında bulunan sleep sort’u sizlerle paylaşmak istedim.

Sıralama algoritması nedir? Bir liste alır, size listenin sıralanmış halini geri verir. Bir çok farklı türü var, yanılıyor olabilirim ama şu an quick sort en iyisi (en azından genel bir makinada çalışabilen). Quick sort’u heap sort ve insertion sort ile birleştirip intro sort isminde daha iyi bir algoritma (intro sort) üretilmiş ve şu an da da gnu C++’ın sorting algoritması olarak kullanılıyor (quick sort’a savaş açıp hezimete uğrayınca öğrendiğim bir bilgi :() Wiki‘ye göre .net de geçmiş.

Neyse, sleep sort. Sleep sort ise espri için yapılmış bir sıralama algoritması. Nasıl çalışıyor derseniz her eleman için bir thread açıyor, her thread input değeri kadar uyuyor ve elemanı ekrana bastırıyor. Mesele input 1 5 4 ise 3 thread açılıyor. İlk thread 1 saniye uyuyup ekrana 1 basıyor, 3 saniye sonra 4’ün thread e geliyor ve ekrana 4 basıyor. Son olarak da 1 saniye sonra 5’in thread i ekrana 5 basıyor. Dahiyane bir fikir! İlk 4chan/prog‘da çıkmış idi ve fena geyiği dönmüştü.

Bu da benim brainfuck implementasyonum.

>>>>>,[[->+>+<<]>+>[-
<<+>>]++++++++[-<----
-->]>>+<+[->>>>>+<<<<
<]>>,]>>>[<<<<[<<<[->
>+<<[->+>[-]<<]]>[-<+
>]>[-<<<.>>>>->>>>>[>
>>>>]<-<<<<[<<<<<]+<]
<<<<]>>>>>[>>>>>]<]

Teknik olarak string sort ediyor, 193182 gibi bir şey girin 112389. Ama araya istediğiniz karakteri serpiştirebilirsiniz, ascii değerine göre sort edecektir 😀

Bu neden sleep sort derseniz, benzer bir mantıkta çalışmakta. Array i input edince her iterasyonda elemanı tek tek azaltmaya başlıyor ve elemanın değeri 0 a düşünce elemanın (bir kopyasını) ekrana bastıyor. Kod boyutu olarak oldukça küçük oldu ve muhtemelen daha da küçültülebilir.

Bu kodu biraz’da Grace Hopper‘ın doğum günü için yazayım dedim. Kendisi programlama dillerinin makineden çok insana yakın olmasının gerektiğinin savunucularından. Şu anda insan gibi kod yazıyorsak kendisinin etkisi vardır. Şu videosunu izleyin derim, çok ilginç bir insan

Yakın zamanda daha ileri bir brainfuck dersi yazmak istiyorum, sık kullandığım BF üzerinde array benzeri kullanmaya izin veren bir yönetmi anlatacağım.

Collision Detection – Part 1 (Collision detection of two circles)


In this post I will talk about collision detection and avoidance algorithms. I will be talking about the algorithms that I used in Pigment (A 3d fps game) and my Android project (an Arkanoid clone).

In my Arkanoid clone (I will call it Good Child but it is not the final title :)), It is mostly the testing of a sphere (ball) with other spheres and polygons. In Pigment it is testing of a cylinder (player) with 3d polygons and ray testing (weapons, flag etc).

Let’s begin with Good Child, and the easier algorithm : collision detection of two circles in 2D.

Collision detection of two circles

Well, this is an easy one!

We have two circles with mid points of p1 and p2 and each have radius of r1 and r2. In this case distance between two circles must be greater than r1+r2 so they won’t collide, otherwise there is a collision. This works for higher dimensions too. You can drag green circle to test for collisions. In the case of Good Child, I am using this to testing for collision of ball with other circle objects such as circular bricks, arced walls and guards etc.

Testing circles is pretty easy and cheap operation, you can make it even cheaper by removing square root operation. Let’s say your original algorithm is like this.

function circleCollision(p1, r1, p2, r2){
    xdiff = p1.x-p2.x
    ydiff = p2.y-p2.y
    distance = sqrt(xdiff*xdiff + ydiff*ydiff)
    total_radius = r1+r2
    return  distance < total_radius
}

This should return true (if I didn’t make a cs101 mistake). however sqrt is a usually very costly operation. however you can remove it in this case.

function circleCollision(p1, r1, p2, r2){
	xdiff = p1.x-p2.x
	ydiff = p2.y-p2.y
	distance_squared = xdiff*xdiff + ydiff*ydiff
	total_radius = r1+r2
	total_radius_squared = total_radius*total_radius
	return distance_squared < total_radius_squared
}

Instead of comparing a < b, we are comparing a^2 < b^2 which is the same thing (since we know both are positive). Since it is a cheap way of testing if two thing collides or do not, it can be used before actual testing of two models. Let's say you have two very complex models, and collision testing of them is very costly. Before the actual test code, you can easily generate a boundary sphere for each model that completely surrounds the model and hit test this spheres instead. If this circle/sphere test fails then two objects does not hit other, otherwise they might but you can't know that before the actual collision detection algorithm. This method can save you a lot of cycles since majority of the items will fail the sphere test and you won't waste CPU on more complex test operations. Also instead of using a boundary sphere, you can use a boundary box and test those two boxes. In this case, we only thought about stationary objects. Assuming the time is standing still, we can test if two circles are touching each other or not. However this is not always the case. Collision detection for moving circles

In Good Child, currently all objects other than ball and user controlled guards are static. So I will assume only one of the circles are moving and other one is stationary. In computer games, movements are done in timesteps. Usually same as fps. On each ‘tick’, you move your objects a bit, then test for collisions. So you have a initial and final positions for each objects. To check for collisions, you have to think of all cases between those positions. If object collides in any of those points, then you must alter the final position in this ‘tick’ to evade collision. Let’s show a graphic.

In this diagram, everything is animated so you can think I will simply check distance again on each tick and stop the ball (or bounce it by changing its vector) when distance is below r1+r2 again. However objects can jump each other if fps is low enough and you might miss the collision. This does not looks like correct for circles but think about a wall. A wall is usually a line (for 2d), if you are testing a fast moving bullet, it is pretty much guaranteed that bullet will be on one side of the wall in one tick and on the other side on next. As previously mentioned, you have to think for all possible positions that the object traveled on those tick.

So in previous animation it moves smoothly from 50,50 to 150,150. Let’s assume that instead of moving smoothly, it moved same amount in only one frame. So we have a stage like this.

Now as you can see, circle 1 creates a shape like tube while moving. Since circle 2 touches this shape, then we can say that circle 1 hits the circle 2 if it moves from p0 to p1 in one frame.

Since human has excelent visual processing algorithms in their brain, we can see that two shapes touches. But it is not as easy for a computer to see that. To make things a lot easier for CPU, let’s reduce to circle 1 to a point and increase radius of circle 2 by same amount!


(You can move objects around to test different cases)

This scene is same as the other but it is much easier to test for collisions. Basically if this line segment represents the path that the ball moves and the circle represent that the area that the line shouldn’t touch. If they are touching, there is a collision. And to check collision, we have to do a…

Line Segment – Circle collision detection

This is a little more complex than two circles. Now we want to test if any point of this line segment is inside the circle.

And before that we should find the closest distance from this line segment to center of the circle.

And before that we should find the closest point on the line.

“If you wish to make an apple pie from scratch, you must first invent the universe.”
–Carl Sagan

So let’s begin with the finding the point on this line segmeent that is the closest to circle. I will first post the code for that.

function closestPointToACircleFromALine(p0, p1, c, r) {
    v1 = c - p0
    v2 = p1 - p0
    dot_product = v1.x*v2.x + v1.y*v2.y
    len = v2.x*v2.x + v2.y*v2.y
    t = dot_pruduct/len
    if(t<0) t = 0;
    else if(t>1) t = 1;
    out.x = p0.x + t*v2.x
    out.y = p0.y + t*v2.y
    return out
}

And here is a canvas that shows how this algorithm works. Drag points to check for different cases.

Now, let’s start explaining things. It might look complicated but it really isn’t. Basically, all we use is a dot product. Dot products gives us a projection of one vector to another.

This algorithm creates two vectors, v1 and v2. v1 is vector from p0 to c and v2 is the vector from p0 to p1. Then it finds dot product of those two vectors. dot_product gives us the squared distance from out to p0. After that it is trivial, it finds t which is the ‘weight’ of out between p0 and p1. If t is 0, then out is on p0. If t is 1.0, then out is on p1. t can go below 0 or above 1 so we crop it to between those values to keep closest point between p0 ad p1. After calculating weight, it finds the position of out using v2 and p0 and returns it.

So how useful is this for finding collisions? The answer is distance from this point to c is smaller than circle’s radius then there is a collision.

In this example you can move objects around to test the algorithm. Left Image is what our scene looks like, and right scene is the simplified form of this scene. Ball moves from p0 to p1 in one frame and the gray area on the left is the area that the ball covers. If it hits the object, then there is a collision. And on the right, the simplified scene, we find the point 'out' and calculate the distance to c. If it is below radius of ball + radius of object then there is a collision.

In this post I only talked about collision detection for two circles, on next posts I will dive into more about what to do when there is a collision.