Motivation

For anyone looking to make their own games, this book will provide the fundamentals of math and low level programming. I will explain everything in an informal style. A background in programming is not necessary to follow.

Is this book for you?

Yes if you:

• Learn through exploration
• prefer small examples over long explanations
• No AI. Understanding over shipping fast.

Odin and Raylib

I chose minimal and joyful technologies. No magic or blackboxes. Odin is easy to get started with and is fully equipped for building complex games.

About me

After spending over a decade in web development, I had enough. It is too repetitive and boring. I decided to pursue my childhood dream of making games.

Find me on Github.

This book is licensed under CC BY SA 4.0.

Installing Odin

Setting up odin is already covered in detail. I will jump straight into code. If everything went well, you will have odin command available.

❯ odin
odin is a tool for managing Odin source code.
Usage:
        odin command [arguments]
Commands:
        build             Compiles directory of .odin files, as an executable.
                          One must contain the program's entry point, all must be in the same package.
        run               Same as 'build', but also then runs the newly compiled executable.
        bundle            Bundles a directory in a specific layout for that platform.
        check             Parses and type checks a directory of .odin files.
        strip-semicolon   Parses, type checks, and removes unneeded semicolons from the entire program.
        test              Builds and runs procedures with the attribute @(test) in the initial package.
        doc               Generates documentation from a directory of .odin files.
        version           Prints version.
        report            Prints information useful to reporting a bug.
        root              Prints the root path where Odin looks for the builtin collections.

For further details on a command, invoke command help:
        e.g. `odin build -help` or `odin help build`

Exercise

Explore the odin command. Try running the help for each subcommand. For example:

odin check --help

How do you check the style of your odin code?

Hello World

Create a folder odin_course and a file hello.odin inside it.

package hello

import "core:fmt"

main :: proc() {
    fmt.println("Hellope!")
}

You can run the program using the command odin run .

$ odin run .
Hellope!

Explanation

I will give only a quick explanation of each line. Each chapter goes deeper and eventually towards full understanding.

package hello

Declare the package name hello. All odin files should start with a package declaration and all odin files in a folder should have the same package name.

import core::fmt

core is like a standard library of Odin. It contains utilties that we can use in our program. core:fmt Has the fmt.println which we use to print Hellope to the screen.

main :: proc() {
  // do something here
}

main is a procedure (or function). It is the entry point of the program. When you run odin run . inside a folder, Odin looks for the main procedure in all files in that folder and runs whatever is inside.

There should be only one main procedure.

Understanding ::

It is used to declare compile time constants. The compiler will copy paste all instances of main with whatever is on the right of ::.

For example:

LUCKY_NUMBER :: 7

main() :: proc() {
    fmt.println(LUCKY_NUMBER + 3)
}

The line fmt.println(LUCKY_NUMBER + 3) would be replaced by fmt.println(7 + 3).

Procedures

Reusing code with procedures

Procedures are are the simplest black boxes in code. To use a procedure, you just need to know what it does. You don’t need to see what happens inside it until it does something unexpected or wrong. Let’s write a function that doubles a number.

/// Doubles a number and returns
double :: proc(n: int) -> int {
    return 2 * n
}

Comments

Comments are ignored by Odin. They are only for humans to make the code easier to understand.

• Use lines that start with /// above procedures to explain them. These are called doc strings.
• Use // for comments
• Put multiline comments between /* ... */

Input and output types

double :: proc(n: int) -> int

proc(n: int) indicates that that it takes an int (integer) called n and -> int means the proc returns an int. The int type is inbuilt. It can store both negative and positive numbers.

Return statement

return 2*n means the procedure exits with a value of 2 * n for any n passed into it.

Let’s use this proc to print double of 3 and 5.

main :: proc() {
    fmt.println(double(3)) // prints 6
    fmt.println(double(5)) // prints 10
}

We will look at procs and types (like int) in detail in the coming chapters.

The Fibonacci Sequence

is an infinite sequence of numbers that is defined as follows:

• The 1st two numbers are 0 and 1.
• The next numbers are generated by adding previous two numbers.

$$\begin{array}{rl}{F}_0& =0\\ F_1& =1\\ F_n& =F_{n-1}+F_{n-2}\end{array}$$

The first few numbers of the sequence are:

$$0,1,1,2,3,5,8,13,21,34,55,\dots$$

Concepts covered in this chapter

• Using integers
• Procedures and Recursion
• Caching repeated computations
• Analyzing the speed of your program

Recursion

is the most powerful construction for programming computers. You can write any program with just recursion and branching (if statement). We cannot say the same about loops like a for loop (next chapter).

Let’s write a procedure that returns the $n^{th}$ fibonacci number.

fibonacci_recursive :: proc(n: int) -> int {
	if n == 0 || n == 1 {
		return n
	}
	return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
}

Tracing our code

Recursion might seem strange at first like a snake eating its own tail. How can a procedure call itself?

Let’s trace what happens when you run fibonacci_recursive(3). Let’s call fibonacci_recursive F for short.

• Computing F(3)

  • The procedure first checks if n is less than or equal to 1. Nope.
  • It reaches the line F(3-1) + F(3-2).
  • Computing F(3-1) = F(2)
    • Now we call F(2). 2 is not 0 or 1. So now we reach the line F(2-1) + F(2-2).
    • Computing F(2-1) = F(1)
      • return 1
    • Computing F(2-2) = F(0)
      • return 0
    • return 1 + 0
  • Computing F(3-2) = F(1)
    • return 1
  • return 1 + 1

  So in the end we get F(3) = 2. In this way, the computer can calculate larger fibonacci numbers like F(10).

Stack overflow

When we call a proc, the computer allocates a constant chunk of memory to this procedure. It’s called a stack frame. The stack frame contains the state of the proc - all its data and state of execution. Once the proc returns, the stack frame is destroyed.

When F(10) recursively calls F(9) and F(8). The stack frames for F(9) and F(9) will be inside the stack frame for F(10). Since the outer stack frame has constant memory, as we keep going deeper, we may run out of memory. This is called a stack overflow.

We can cause a stack overflow by calling F(1000). Avoid recursion as much as possible to prevent this error. We will see a better approach to compute the fibonacci sequence in the next chapters.

Analyzing the speed of our code

Exercise

Write a proc that uses recursion to add numbers from 1 to n. Call this proc in main and print the sum of numbers from 1 to 25.

Iteration

Our previous code to generate the fibonacci numbers starts at n and then recursively calls smaller values of n until we reach base cases (n = 0 or n = 1). This lead to a lot of repeated computations and slowed down our code.

How about we do the reverse? I.e start with the base cases and build up higher and higher fibonacci numbers.

Let’s say we want to calculate F(5). This works as follows:

• Start with F(0) = 0 and F(1) = 1.
• Calculate F(2) = F(1) + F(2) = 0 + 1 = 1.
• Calculate F(3) = F(2) + F(1) = 1 + 1 = 2. (Use F(2) from previous calculation.)
• Calculate F(4) = F(3) + F(2) = 2 + 1 = 3.
• Calculate F(5) = F(4) + F(3) = 3 + 2 = 5.

Simple. This is how we calculate fibonacci numbers on paper. Translating this logic into odin:

fibonacci_iterative :: proc(n: int) -> int {
	a, b := 0, 1

	for _ in 1 ..= n {
		a, b = b, a + b
	}

	return a
}

Storing values in variables

For the first time ever, we are assigning values to variables. To understand the line a, b := 0, 1, let’s start with the basics. The basic syntax for declaring a variable is:

a: int = 2

The compiler can infer the type of 2 to be an int. So you can skip writing int:

a := 2

You can also assign multiple values at once.

a, b: int = 0, 1
a, b, c: int = 0, 1, 2

And skip specifying the type just like before.

a, b := 0, 1
a, b, c := 0, 1, 2

For Loop

Though odin also supports C like for loops, I prefer for i in .. as it is easy to reason about and prevents off by one errors. 0..<n is an exclusive range. It goes from 0, 1, 2, …, until n - 1. If you want to include n, you can write 0..=n. For example:

for i in 0 ..< 5 {
    fmt.println(i)
}

prints

0
1
2
3
4

break and continue work similar to other languages. We will explore them in the next chapters. By writing for _ in 1 ..= n { we are running the code inside the for loop n times.

Mutating variables

Say you declared a variable x with a value of 25.

x := 25

You can change it’s value with =. This is called mutation or reassignment.

x = 5

At the start of the program a stores F(0) and b contains F(1). To get the next value of b i.e F(2) we just have to add a and b. The next value of a is F(1) (the current value of b).

Therefore until we reach F(n), at each step we have to:

• update the value of a to b
• update the value of b to a + b

So then why didn’t we simply write the following?

// oops doesn't work
a = b
b = a + b

This doesn’t work because the value of a changes but we need the old value of a to update b. We can create a temporary variable to store the old value of a and then update a.

old_a := a // save the old value of a
a = b
b = old_a + b

Or we can update both at the same time!

a, b = b, a + b

Analysis

Exercise

Modify the above proc to return the sum of n fibonacci numbers. For example S(10) = F(0) + F(1) + ... + F(10) = 143.

Fibonacci Matrix

Here, I will discuss an efficient implementation of generating the fibonacci sequence. If you are not familiar with matrix multiplication, read the chapter on linear algebra. Until then, it is sufficient to know that we exploring ways to calculate powers quickly.

$$\left(\begin{array}{c}{F}_{n+1}\\ F_n\end{array}\right)=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}{F}_n\\ F_{n-1}\end{array}\right)$$ The above equation can be verified trivially. And by applying it to itself until we reach the base case, we end up with: $$\left(\begin{array}{c}{F}_{n+1}\\ F_n\end{array}\right)={\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)}^n\left(\begin{array}{c}1\\ 0\end{array}\right)$$

Exponentiation algorithm

Multiplications are expensive. Our ability to compute fibonacci numbers quickly is predicated on computing powers fast. I.e finding the value of $A^n$ where

$$A=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$$

This algorithm is quite intuitive. Suppose you want to calculate $3^{15}$. You either have to multiply 3 by itself 15 times. Or do the following:

$$\begin{array}{rl}{3}^{15}& =3\times 3^{14}\\ & =3\times (3^7{)}^2\\ & =3\times {\left(3\times (3^3{)}^2\right)}^2\\ & =3\times {\left(3\times (3\times 3^2{)}^2\right)}^2\end{array}$$

We can start multiplying and reduce this value from inside. $3^2=9$.

$$\begin{array}{rl}{3}^{15}& =3\times {\left(3\times (3\times 9{)}^2\right)}^2\\ & =3\times {\left(3\times 27^2\right)}^2\\ & =3\times {\left(2187\right)}^2\\ & =3\times 4782969\\ & =14348907\end{array}$$

We have done only 5 multiplications instead of 15 by repeated squaring! We can generalize this algorithm. $$\begin{array}{c}{A}^n=\{\begin{array}{ll}{\left(A^2\right)}^{\frac{n}{2}}& \text{if}\text{n is even}\\ A\times {\left(A^2\right)}^{\frac{n-1}{2}}& \text{if}\text{n is odd}\end{array}\end{array}$$

So we compute $A^2$ and pass it recursively with n halved (approximately).

Analysis

fibonacci_matrix :: proc(n: int) -> int {
	f := matrix[2, 1]int{
		0,
		1,
	}

	a := matrix[2, 2]int{
		1, 1,
		1, 0,
	}

	result := matrix_pow(a, n) * f
	return result[0, 0]
}

matrix_pow :: proc(m: matrix[2, 2]int, pow: int) -> matrix[2, 2]int {
	result := matrix[2, 2]int{
		1, 0,
		0, 1,
	}

	n := pow
	m := m

	for n > 1 {
		if n % 2 != 0 {
			result = m * result
			n -= 1
		}
		m = m * m
		n = n / 2
	}

	return result * m
}

Exercise

Modify this algorithm to use repeated cubing instead of squaring and repeat this analysis. Is this approach faster than repeated squaring?

More about Integers

Odin supports the following signed integers i8, i16, i32, i64 and i128. These numbers can hold negative numbers.

One bit is used to represent sign (negative or positive) and the rest hold the magnitude. For example, i8 is an 8-bit integer. 1 bit contains the sign. The remaining 7 bits can hold numbers from 0 to $\left(2^7-1\right)=127$. So the range of i8 is -127 to 127.

int is a platform specific type. On most modern systems (which are 64 bit), it is i64. On older systems it is i32.

Unsigned integers

Odin has integers which can represent only positive numbers: u8, u16, u32, u64, and u128 and the platform specific uint. E.g. u8 can hold values from 0 to $2^8-1=255$.

What to use?

In most cases, you can just use int or uint. Even on a 32-bit system, int can hold numbers up to a few billions which is often sufficient.

For specific use cases like age, you can use u8 because it lies in between 0-256. Smaller integers take less space and can be more efficient.

Integer Overflow

Consider this snippet. We set a to 255 which is the maximum value an u8 can represent. What happens if we add 1 to it?

a:u8 = 255
b := a + 1
fmt.println(b)

In Odin the integer types wrap around. You go back to 0. Similar thing happens when you try to subtract 1 from 0. The number will underflow to 255.

We should use sufficiently large integer types and pay attention to the possibility in our code.

Exercise

Use a calculator to determine the range of integers for u128 and i128. Can you think of a use case for these integer types?