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!

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.

Brainfuck Tutorial – part 2

In this tutorial I will talk more about loops and how to do basic higher level stuff in Brainfuck. If you already know BF operators, you can start from this part. Else, read the previous tutorial.

[] operators are used for creating conditional loops in BF. As long as value of current pointer is non zero (when program executes [ command), it loops between [ and ]*You obviously know this if you read previous tutorial.

So what can we do with this information? Well, pretty much everything. Here are some higher level stuff that you can do with loops.

The first and easiest one is clearing a cell. It is simply

[-]

If cell is non zero, it enters this loop and decreases it until it is zero. You might ask what is the use of this. It is usually used when implementing booleans or if conditions.

Another one is moving a cell to another.

[->+<]

Let's say our array is like this

...ab...
...^

Initially pointer points to a. With this loop it decreases a until it is zero and increases b by 1 on each iteration. So it basically moves content of a from b. (Actually if b is non zero, it is *b=*b+*a; *a=0;, in this tutorial I will assume cells are 0 unless it is specified).

And finally, copy operation

[->+>+<<]

It moves (adds) current cell to two cell on the right.

These are most basic things in brainfuck. While implementing more complex stuff, you will those a lot. For example let's draw a triangle like this.

...*
..***
.*****
*******

So in C, this is done like this.

int k = 4; //line num
int i, j;
for(i=0; i

Implementing this directly in BF would be a lot harder, some higher level operators a lot harder to implement. I will 'simplify' it for BF.

int k = 4; //line num
int a, b, i, j;
a = k;
b = 1;
while(a--){
  i = a;
  while(i--) printf(" ");
  j = b;
  while(j--) printf("*");
  printf("\n");
  b+=2;
}

So this does the same thing but it is a lot easier for BF. Basically a holds the number of spaces while b holds the number of stars for each line. Before starting writing my program, i will first decide my structure for array.

ktabijs*n
012345678

This is my array structure that I will use in my program. First line is the name of each cell and second line is indices of each cell. I already decided which cells will hold which values. k, i, j, a, b are the values in previous C code. t is a temp cell. "s*n" are the cells that will contain ascii values for ' ' (space), '*' and '\n' (newline).

So first lets begin with building "s*n". Space is 32, '*' is 42 and '\n' is 10. I will use cell j as a temporary cell to make a loop and set these cells to correct value. Initially pointer is at cell k (0th cell).

!bf!>>>>> (move cell j)
+++++ +++++ (set j to 10)
[- (as long as j is non zero)
  > +++ (increase cell s by 3)
  > ++++ (increase cell * by 4)
  > + (increase cell n by 1)
  <<< (move back to cell j)
]

So after this code, s will be 30, * will 40 and n will be 10 (and j will be 0). But we want 32, 42 and 10 so let's increase s and * by 2

>++>++

So the cells that holds the ascii values are ready! Now let's input cell k from user. I am assuming user will enter a single digit. But it is in ascii so I have to decrease it by 48 ('0') to convert it to a real number. With the addition of previous code, now the pointer is at cell *. Move it back to cell k, input a character and decrease it by 48. While at it let

!bf!<<<<<<< (move back to cell k)
, (input a character)
> +++ +++ (set t to 6)
[ - < ---- ---- >] (decrease k by 8 for each iteration of t) (in total 48)

Now cells ks*n are ready. Now let's initialize cell a and b. a should be initially equal to k and b should be 1. In previous code we were at j.

!bf!< (move back to cell k)
[->+>+<<] (copy k to t and a)
> [-<+>] (move t back to k)
>> + set b to 1

Some of those look familiar? Basically we are creating two copies of cell k at cell t and cell a then move t back to cell k. We can't copy a cell to directly to another without clearing content of the first. We have to create 2 copies, move 1 to back.
After that it sets b to 1. So our initializing process is done. Let's look at our current structure.

!bf!k  0  k  1  0  0  32  42  10
k  t  a  b  i  j  s   *   n
0  1  2  3  4  5  6   7   8
            ^

First line holds the values, second line is the name of the cells and last line is the index of each cell. Now we can start actual programming!

First line of C code is while(a--). This is our main loop, as long as a is non zero create a loop. After beginning of each iteration it decreases a by 1 How could we achieve such a thing in Brainfuck. In our previous code, we left pointer at b. We want a loop that runs until a is non zero.

!bf!< (move back to a)
[
  - (decrease a by 1)
  {snip}
]

And that is all!. In snip part we should implement inside of the main while loop. Our first operation is printing number of spaces that is equal to a. For that we copy a to i, and print space as long as i-- is true. Pointer is at a

!bf!!nr![- <+> >>+<<] (make copies of a at t and i)
<[->+<]> (move t back to a) 
>> [->>.<<] (move to i and print spaces (cell s) until it is 0)

First we make two copies of cell a at t and i. And then move t back to a so value of a is not changed (We will need it on next iteration) after that it simply moves pointer to i, enters a loop and for each iteration it moves to cell s (contains ' ' (space)) and prints it). That is it, we already printed our spaces. Now move to the starts, it is basically same code but on different cells. (instead of a i s, it is b j *). In the last code we left pointer at cell i.

!bf!!nr!
<
[- <<+>> >>+<<] (make copies of b at t and j)
<<[->>+<<]>> (move t back to b) 
>> [->>.<<] (move to j and print stars(cell *) until it is 0)

As you can see, I just modified previous code a little. With this we printed our spaces and starts. Finally let's print a new line and end finish this line. With last code, pointer is now at cell j

!bf!!nr!>>>. (move to cell n and print it)

Finally. We printed all necessary stuff and done for this line. However before beginning to next iteration, we have to change value of a and b correctly. After each line, number of spaces is decreased by 1 (a) (which we did in the beginning) and number of stars are increased by 2. We were at cell n

!bf!<<<<< ++(move to cell b and increase it by 2)
<  (and move back to a)

That is it! We implemented {snip} part of our main loop. As you can notice, pointer is at cell a so we have to move pointer to a in the end. Let's merge all of our stuff and test it!

!bf!>>>>> (move cell j)
+++++ +++++ (set j to 10)
[- (as long as j is non zero)
  > +++ (increase cell s by 3)
  > ++++ (increase cell * by 4)
  > + (increase cell n by 1)
  <<< (move back to cell j)
]
>++>++ (set s to 32 and * to 42)

<<<<<<< (move back to cell k)
, (input a character)
> +++ +++ (set t to 6)
[ - < ---- ---- >] (decrease k by 8 for each iteration of t) (in total 48)

< (move back to cell k)
[->+>+<<] (copy k to t and a)
> [-<+>] (move t back to k)
>> + set b to 1

(while(a minus minus){)
< (move back to a)
[
  - (decrease a by 1)

  (i=a; while(i minus minus) printf(" ");
  [- <+> >>+<<] (make copies of a at t and i)
  <[->+<]> (move t back to a) 
  >> [->>.<<] (move to i and print spaces (cell s) until it is 0)

  (j=b; while(j minus minus) printf("*");
  <
  [- <<+>> >>+<<] (make copies of b at t and j)
  <<[->>+<<]>> (move t back to b) 
  >> [->>.<<] (move to j and print stars(cell *) until it is 0)

  (printf("\");)
  >>>. (move to cell n and print it)

  (b = b plus 2)
  <<<<< ++(move to cell b and increase it by 2)

  <  (and move back to a)
] (} end of while(a minus minus)

And let's remove all comments from code abd format it a little(Enter input 'a' for more fun!)

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

(I added extra >> there to make it triangle)

And we build our first complex program, yay! Before finishing my post, I want to emphasize a couple of things.

  • Before starting coding, first you should build your structure on your mind (and write it in a paper/text editor). Which cells will be used for what, name each cell etc... You should decide it at the beginning. The structure I used is not the best, I could make a more compact one and it would reduce the code size a lot.
  • Try to split your program into smaller parts. For example in this program, first part creates ascii values for printed parts, second part inputs k and initialized a and and final parts prints stuff. If you separate them like this, you can test them separately and it will be much easier to write. Use a debugger if necessary, that shows your the content of each cell and see if you are doing correctly. This one is quite good and very fast
  • Always know where your pointer is. While coding, I usually put comments that shows where am I now. For example
    !bf!!nr!
      [- <+> >>+<<]a (make copies of a at t and i)
      +<]>a (move t back to a) 
      >> i[->>.<<] (move to i and print spaces (cell s) until it is 0)
      
    

    I don't write comments between () they are way too unnecessary. Only occasional comments like a, b, i, t in this example that shows where is the cursor at that point of comment. I also copy paste my array structure a lot to move my pointer correctly. After a while, basic algorithms will be easy for you (like copying, moving stuff etc) as long as you know where you are.

  • With more practice, you will be able to think how to write higher level stuff in BF. You will be able to make a general algorithm in your mind and after that it is just patience.
  • Well that is all for now. This was a fairly complex program (CS 101 stuff), I hope that I explained it well. I am planning on more tutorial with more complex examples).

    Brainfuck – Tutorial 1

    Hello Internet!

    In this tutorial I will talk about BF and how to make programs with it. Let’s start with what is BF and why you should love it.

    Brainfuck (unfortunate name, can’t really put it on your CV) is a minimalist esoteric language. Even simplest programs are a challenge in BF and that is the beauty of it. If you love the challenge and want some headaches, BF is the one for you.

    In BF you have an infinitely long *debatable, in some implementations it is constant, in others it reallocates new space as you need it 8bit byte array *again, it is usually byte but can be bigger and a pointer that points to one of the elements in this array. In a BF program, you move this pointer, alter the cell that it points to or do I/O operations for current cell. It is basically a turing machine, only even more simpler.

    BF has a full set of 8 operations. These are “+-<>[].,“. Any character other those 8 characters are disregarded by the interpreter and can be used as comments (and you will need them).

    Let’s talk about these 8 operations.

      Movement

    Movement operations are <>. They move pointer (or cursor, if you prefer) ‘left’ or ‘right’. Initially cursor points to beginning of the array and you use these operations to move the cursor. In some implementations it is forbidden to move left side of the initial position, in others it reallocates array or simply wraps to the other side of the array. So be careful about that. I always assume you can’t move left side of the initial position.

    These operations only move it 1 cell. For example initially you are at position 0 and if you call > it moves to position 1. If you call >>> after that it moves to position 4.

      Increment/Decrement

    As you probably guessed +- are increment and decrement operations *+ is increment, - is decrement if you didn't. They increase or decrease the content of the current. That is it. You have no other way (other than I/O) altering the contents of the current cell.

    At the beginning of the program, each cell is set to 0. These operations can cause integer overflows so if you call - when cell is 0, it will be -1 (or 255, if you don’t want to bother with signs) and + will cause it to overflow 0 again.

    You can’t set a cell to a constant. If you want a cell to be set to 10, you need to call ++++++++++*assuming it was 0 before, if you want to set it to 50 you will need 50 + operations*There are easier ways of course, I will talk about them in 'advanced' section 🙂

    So here is a very simple program that uses all operations we learned.

    ++++>+++--

    First we increase the cell0 by 4 then move cursor to the left. It increases cell1 by 3 and decreases it by 2 to set it 1. In the end our cell is “31000000…..” and cursor points to 1 (cell1)

      Input/Output

    We have an input and an output operator in BF. Basically they input a byte (or character) from stdin or outputs a byte (or character) to stdout. . outputs content of current to cell to stdout and , inputs a byte from stdin. Again they only alters/uses current cell.

    You will need basics of ascii to input/output meaningful data. For example if you set a cell to 48 and call . it will print ‘0’ to the console because ascii value for ‘0’ is 48. If you call , and press 2 it will set current cell to 50 (ascii value of 2).

    So here is a much more complicated BF program! You can press run to see output of the program.

    !bf!+++++ +++++ +++++ +++++
    +++++ +++++ +++++ +++++
    +++++ +++++ ++ set current cell to 52 (4)
    . print 4
    -- decrease current cell by 2 set it to 50 (2)
    . print 2
    > +++++ +++++ . go to cell1 and set it to 10 and print (\n)
    , input a charcter (i assume that user will press something between 0 and 9)
    + increase the inputted value
    . print new character

    First part is obvious, it first sets cell to ‘4’, prints it then set it to ‘2’ and prints it again. You get the answer to the life. It prints a \n after that to go next line.

    In second part it inputs a character from user and increases its value by and outputs it. If user inputs ‘0’ it is 48 in ascii, after + it is set to 49 and when printed it prints ‘1’. If user inputs 5, it prints 6. If he inputs 9, no it does not print 10. It prints ‘:’ because ascii value after ‘9’ is equal to ascii value of ‘:’. Printing two digit numbers are very tricky.

    That is all for I/O. Now comes the tricky part.

      Branch/Loops

    Our final two operations are []. These are used for creating loops or conditional statements. Every [ operation is matched by a ]. Any command between these two operations are evaulated if only a certain condition is satisfied.

    When a BF interpreter reaches a [ statement, it checks if value of current cell is zero or non zero. If it is zero, than code between [] is not evaulated and it jumps to the operator that comes after ]. If it is non zero than it simply jumps next operator after [ and continue to execute normally. When it finally reaches ] it rewinds back to [ and again if current cell is zero or non zero. It loops until current cell is non zero.

    It is basically a while loop that uses value of current cell as a boolean. zero = false, non-zero = true.

    Be careful that when it rewinds to the back, it does not move cursor to the old position. If you are using <> operations between [], you will probably want number of < is equal to >. And it does not alter the content of the current cell so you will want to decrease (or increase) current cell to break loop at some point.

    Now let's write a program that prints 10 exclamation marks using a loop.

    !bf!+++++ +++++ +++++ +++++
    +++++ +++++ +++ set current cell to 33 (!)
    > move cell1
    +++++ +++++ set cell 1 to 10
    [ start loop at cell 1
    < move cell 0 (contains !)
    . print !
    > move cell 1 again
    - decrease cell 1 by 1
    ] end loop

    First we set cell0 to ascii value of ! then it moves to cell1 and sets it to 10. Cell 1 is our test cell, as long as it is non zero this loop will be executed.
    At each iteration of loop it moves back to cell0 and prints it. Then it again moves back to cell 1 and decrease it. When it rewinds back to [ it will test if cell1 (current cell) is nonzero and if it is non-zero it will execute again. During the execution cell1 will be 10 9 8 .. 1 and finally 0 and execution of loop will stop.

    Previously I said that you can use a simpler/shorter way to set a cell to 50. Here it is

    +++++++[->+++++++<]>+

    It first sets cell0 to 7 and loops until it is zero. In each loop it moves to cell 1 and increases it by 7 again. It is basically a multiplaction operation at the end of the loop cell1 is 7x7=49. We increase it once again and set it to 50. Easier than +++++...+ times 50!

    That is it! Now you can write a doom clone in BF!

    I am planning more complex tutorials on BF. There are some tricks I learned that makes writing more complex program easier. I will make and explain some code examples that shows some essential stuff (printing two digit numbers for example :)). Stay tuned!