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.

flowchart LR;
    input -->  newLines["`**Procedure**
    Line 1
    Line 2
    Line 3
    ...`"] --> output;

/// 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.

Asymtotic Complexity

Any code we write should execute in a reasonable amount of time with limited computing resources. Solving problems with tiny inputs is trivial. So we need a mathematical framework to understand how fast our code runs as the input size grows.

Rate of Growth

Let’s use a calculator and play with a few math functions. We will compute $f(x)$ for inputs 1, 5, 10, 20, 25, 100.

Constant function

$$f(x)=600$$

Always returns a constant value. This function doesn’t grow and is independent of input size.

Linear function

$$f(x)=x$$

Returns the input without changing it.

f(1) = 1
f(5) = 5
...
f(100) = 100

Square

$$f(x)=x^2$$

f(1) = 1
f(5) = 25
...
f(100) = 10000

Exponential function

$$f(x)=2^x$$

f(1) = 1
f(5) = 32
...
f(100) = 126...(31 digits)

Logarithmic function

$$f(x)={\log }_2(x)$$

f(1) = 0
f(5) = 2.3...
f(10) = 3.3...
...
f(100) = 6.6...

The exponential function grows extremely fast. And its inverse (log) grows insanely slowly. When we analyze how the number of operations and the memory usage of a piece of code grow w.r.t input size, we prefer slow growing functions.

• If it can run in constant or Logarithmic time, it’s excellent.
• If it’s linear or polynomial of n, then it can be acceptable.
• If it is exponential then we will quickly run out of computing resources as input size grows.

Depending on the problem, we cannot always choose a more efficient algorithm.

Consider only large inputs

Consider the function:

$$f(x)=100,000,000+x^2+8e^x$$

As x becomes very large, the constant value $100,000,000$ will become insignificant in comparison with $x^2$. We can neglect it in our analysis. Similarly, $x^2$ is overshadowed by $8e^x$. We can absorb 8 into e to form a new constant such that $8e^x=C^x$

Asymtotically, i.e. for large values of x, we can write

$$f(x)=\Theta (C^x)$$

It is an exponential function.

Exercise

Is it possible that a piece of code running a linear algorithm runs faster than a logarithmic algorithm? If yes, give an example.

Notes on Performance

Fast and snappy games delight users and run well on low end devices.

Algorithms and Data Structures (DSA)

Computer scientists spend their lives inventing faster ways to solve problems. Choosing the right algorithms and data structures can be the difference between your code finishing in a few millseconds vs a billion years. DSA improves asymptotic complexity.

We’ll go through a simple example in the next chapter. Strive to choose the best algorithms and data structures. Most often these are inbuilt in our language. You just have to recognize and call the appropriate procedures.

Micro optimization

We will walk through some techniques of optimizing code like choosing compact bit representations of data, CPU level parallelism, multithreading etc.

Micro optimization increases code complexity. Keep code as simple as possible and use it sparingly when parts of your game are too slow. In my experience, if you use DSA properly and utilize data driven design principles, you won’t need micro optimizations.

Counting in Billions

It’s quite useful to maintain a mental model of computation limits of modern computers. Modern CPUs run at clock speeds in Ghz. This translates to approximately a billion simple operations (like addition of numbers) per second.

Odin is fast. If you are coding in other languages there is a slowdown by a constant factor.

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 and fundamental 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)
}

If statement

We can conditionally execute code with if.

// cond is of type boolean (either true or false)
if cond {
	// this block of code gets executed when cond is true	
}

== checks for equality. n == 0 is true when n is 0. || is the or operator. n == 0 || n == 1 is true when at least one of the conditions is met i.e. when n is either 0 or 1.

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).

The execution flow resembles a tree. I put numbers to indicate the sequence of procedure calls.

flowchart TD;
a["F(3)"] -.1.-> b["F(2)"];
b -.2.-> d["F(1)"];
d -.3.-> b;
b -.4.-> e["F(0)"];
e -.5.-> b;
b -.6.-> a;
a -.7.-> c["F(1)"];
c -.8.-> a;
a -.9.-> out([Output = 2]);

style out stroke-width:0;

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.

Asymptotic Analysis

The procedure fibonacci_recursive compares n with 0 and 1. Then it calls itself recursively with n-1 and n-2 as inputs. Let’s say the comparisons take C time. The procedure takes T(n) time. We get:

$$T(n)=C+T(n-1)+T(n-2)$$

To find the exact value of T, we need a more elaborate analysis. Since $$T(n-1)>T(n-2)$$, We can say that T is at least as large as this other function.

$$\begin{array}{rl}T(n)& =C+T(n-1)+T(n-2)\\ & \ge C+2T(n-2)\end{array}$$

Let’s substitute the value of T(n-1) recursively in this equation.

$$\begin{array}{rl}T(n)& \ge C+2T(n-2)\\ & \ge C+2C+4T(n-4)\\ & \ge 3C+4T(n-4)\\ & \ge 2^{k-1}C+2^{k}T(n-2k)\end{array}$$

When n is even and $2k=n$ we get,

$$\begin{array}{rl}T& \ge 2^{\frac{n}{2}-1}C+2^{\frac{n}{2}}T(0)\\ & \ge 2^{\frac{n}{2}}{C}_1\end{array}$$

Since $T(0)$ is a constant. If n is odd, we will be left with T(1) but the asymptotic bound will remain the same. (Try it out!)

Conclusion: This algorithm takes exponential time and is extremely slow for large inputs. We get the same equation for memory usage because of recursive stack frames.

Exercise

Call this proc in main and experiment. Pass various values of n to fibonacci_recursive. You can measure execution time by running:

$ time odin run .

Do you think the time is increasing exponentially? What is the 40th fibonacci number and how long did your computer take to calculate it?

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.

This time the logic looks like a sequence of steps.

flowchart LR;
a["F(0)"];
b["F(1)"];
c["F(2)"];
d["F(3)"];
e["F(4)"];
f["F(5)"];

a --> c;
b --> c;

c --> d;
b --> d;

d --> e;
c --> e;

e --> f;
d --> f;

f --> out([Output = 5]);

style out stroke-width:0;

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

Easy. We have a single for loop going from 1 to n. We do n steps in total and a constant amount of work in each step. So it a linear algorithm and way faster than our previous implementation.

$$T(n)=\Theta (n)$$

For memory requirements, fibonacci_iterative store a and b and _ (the for loop index). Memory usage is constant.

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

I will now discuss an efficient implementation of generating the fibonacci sequence.

If you are not familiar with matrix multiplication, you can read the next two sections (algorithm and analysis) and skip the rest. You can come back to read the code after reading the Linear Algebra chapter. $$\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: $$\begin{array}{c}\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)\end{array}$$

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

Knowing the above, we can write the time complexity equation:

$$\begin{array}{rl}T(n)& =C+T\left(\frac{n}{2}\right)\\ & =C+C+T\left(\frac{n}{4}\right)\\ & =kC+T\left(\frac{n}{2^k}\right)\end{array}$$

When $n=2^k$ or ${\log }_2(n)=k$ we reach the base case.

$$\begin{array}{rl}T(n)& =C{\log }_2(n)+T(1)\\ T(n)& =\Theta (\log (n))\end{array}$$

This is a very fast logarithmic algorithm that can potentially compute the trillionth fibonacci number with it in under a second. The memory usage is once again constant. We declare some values and keep updating them.

Finally getting into code…

Equation (1) when translated into Odin looks like this:

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]
}

Most of it should be self explanatory. You can also specify the type on the left of = during assignment.

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

result[0, 0] returns the first element of the column matrix. We just need to implement matrix_pow that uses the above algorithm.

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 /= 2
	}

	return result * m
}

for n > 1 says that the loop has to continue as long as the condition is satisfied. Odin doesn’t have while. % is the remainder operator. n % 2 == 0 checks if the remainder of n divided by 2 is not 0 i.e if n is odd.

n -= 1 is an shorter syntax for n = n - 1. We are subtracting 1 from n and updating the value of n. Remember = is mutation not mathematical equality. Similarly, n /= 2 is short for n = n / 2.

Exercise

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

Benchmarks

It is time to put theory to the test and see how each of these fibonacci implementations perform. We will build an optimized binary with the command:

$ odin build . -o:speed

and then run it with hyperfine. Let’s keep the code code minimal.

package main

import "core:fmt"

fibonacci_recursive :: proc(n: int) -> n {
    // ...
}


fibonacci_iterative :: proc(n: int) -> n {
    // ...
}


fibonacci_matrix :: proc(n: int) -> n {
    // ...
}

main :: proc() {
    fmt.println(fibonacci_recursive(45))
    // fmt.println(fibonacci_iterative(45))
    // fmt.println(fibonacci_matrix(45))
}

We will first run the recursive version with hyperfine. Then comment out that line and uncomment the iterative version, measure and so on..

F(45)

• Recursive algorithm

❯ hyperfine ./fibonacci
Benchmark 1: ./fibonacci
  Time (mean ± σ):      3.328 s ±  0.026 s    [User: 3.315 s, System: 0.002 s]
  Range (min … max):    3.295 s …  3.351 s    10 runs

• Iterative algorithm

❯ hyperfine ./fibonacci --shell=none
Benchmark 1: ./fibonacci
  Time (mean ± σ):     879.8 µs ± 211.7 µs    [User: 241.2 µs, System: 511.0 µs]
  Range (min … max):   666.6 µs … 1764.0 µs    3518 runs

• Matrix implementation

❯ hyperfine --shell=none ./fibonacci
Benchmark 1: ./fibonacci
  Time (mean ± σ):     902.2 µs ± 221.5 µs    [User: 229.9 µs, System: 550.8 µs]
  Range (min … max):   650.5 µs … 1630.1 µs    3252 runs

The recursive version was unbearably slow and finished in 3.3 seconds. The iterative and matrix implementations are 3500x faster.

F(1_000_000_000)

• Recursive algorithm

Maybe it’ll finish running if I wait till the end of the universe and until time loops back to the present?

• Iterative algorithm

❯ hyperfine --shell=none ./fibonacci
Benchmark 1: ./fibonacci
  Time (mean ± σ):     252.5 ms ±   1.9 ms    [User: 250.6 ms, System: 0.7 ms]
  Range (min … max):   249.8 ms … 256.3 ms    11 runs

• Matrix implementation

❯ hyperfine --shell=none ./fibonacci
Benchmark 1: ./fibonacci
  Time (mean ± σ):     863.3 µs ± 207.5 µs    [User: 234.7 µs, System: 508.0 µs]
  Range (min … max):   637.9 µs … 1546.5 µs    3426 runs

The iterative version of fibonacci is slowing down but the matrix implementation is still fast because $\log (n)$ grows insanely slow.

Exercise

Use fibonacci_matrix to calculate F(100_000_000_000). Is there anything wrong with the output? If so what do you think went wrong and how will you fix it?

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.

flowchart LR;
subgraph "Signed Integer"
  s["Sign (1 bit)"]
  m["Magnitude (k - 1 bits)"]
end

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?