I recently wrote a post on Pascal's Triangle and in this post I will write a program in C to implement a Galton Board simulator, a Galton Board being an actual physical gadget following the Pascal Triangle's probabilistic characteristics.
This is the graphic I used in the previous post to illustrate a five-row Pascal's Triangle.
A key characteristic of Pascal's Triangle is that if you start at the top and than trace a path downwards, randomly choosing to go left or right, each number you land on tells you how many different paths there are to that number. The probability of taking any path is
Pascal's Triangle Path Probability
0.5number of rows - 1
(We subtract 1 from the row count as there is no choice involved on the first row, there only being one number.)
So for example in the 5-row triangle above the probability of taking a particular path is
5-Row Pascal's Triangle Path Probability
0.54 = 0.0625
The total number of paths is 16 so the total probability is
5-Row Pascal's Triangle Total Path Probabilities
0.0625 * 16 = 1
Probabilities always add up to 1, indicating certainty - if you start at the top and keep going, whatever path you take and wherever you end up, you are certain to get to one of the numbers in the last row.
Another key characteristic of Pascal's Triangle is that the probabilities build up row by row into an approximation of the normal distribution, another topic I covered in a previous post.
This is all very abstract but the concept can be made physical with a contraption called a Galton Board, named after Sir Francis Galton but also called a bean machine of quincunx. It is a bit like a simple pinball machine with pegs arranged in the pattern of a Pascal's Triangle and mounted vertically to let gravity do the work of propelling balls from one peg to the next. There also need to be containers of some kind to catch the balls from each final destination so they can be counted. There are plenty of images and videos if you want to do a quick search.
The Simulation
Implementing a software simulation of a Galton Board is straightforward: we just need some kind of data structure representing the board and some kind of code simulating the random passage of balls through it. We also need to keep a running total of how many balls have taken each path, and finally some kind of visual display of what is happening.
I will use the very rudimentary graphical and animation abilities of the terminal for this project, but the data structure and associated logic can be used, if suitably designed, with any environment offering graphical output such as GTK+. To this end I will keep the data structures and logic completely separate from the visual output, so a new output can be "plugged in".
The actual mechanism I will use to do this is to pass function pointers to the functions controlling the board. These will be called when something happens requiring the graphical output to be updated. The code can therefore be used with any form of output by just passing the appropriate function pointers.
Specifically there are three things a Galton Board can do which require an update to the visual output:
- The board can be created
- A ball can move
- A total can be incremented
When any of these things happens the specified function will be called, the Galton Board code itself having no responsilibity for or knowledge of how the visual output is handled.
Aside from the file containing the main function there are two other files, one for the Galton Board code and one for the functions which draw the output. The latter file can be replaced with any other providing it has a set of functions with the same parameters. In a later post I will do just that by writing an alternative implementation using the Ncurses library.
Coding
Create a new folder and within it create these empty source code files. You can download the source code as a zip or clone/download from Github if you prefer.
- galtonboard.h
- galtonboard.c
- galtonboardview.h
- galtonboardview.c
- main.c
Source Code Links
In galtonboard.h type or paste the following code.
galtonboard.h
#include<stdlib.h> #include<stdbool.h> #include<stdio.h> #include<math.h> //-------------------------------------------------------- // STRUCT galtonboard //-------------------------------------------------------- typedef struct galtonboard { char** board; int rowcount; int ballcount; int* totals; int gridrows; int gridcolumns; int ballx; int bally; int prevballx; int prevbally; int pause_ms; } galtonboard; //-------------------------------------------------------- // FUNCTION PROTOTYPES //-------------------------------------------------------- galtonboard* galtonboard_create(int rowcount, int ballcount, int pause_ms, void(*oncreate)(galtonboard* gb)); void galtonboard_start(galtonboard* gb, void(*onballmoved)(galtonboard* gb), void(*ontotalchanged)(galtonboard* gb, int index, int count)); void galtonboard_free(galtonboard* gb);
A few of the members of the struct might need a bit of explanation.
- board is a 2D array of chars representing the board itself. Most values will be ' ' (space) but the pegs will be 'O' (upper case letter O). Textual outputs can use these characters, and graphical outputs can use them as flags to draw a more realistic peg.
- ballx, bally, prevballx and prevbally indicate the current and previous ball position. The previous positions can be used to overwrite the ball before drawing it in its current position to simulate movement.
The functions are straightforward, they just let us create a board and start it running, as well as freeing up the memory when we're done. Note though that the first two take function pointers to be called when the board is created, when the ball moves and when a total is updated, therefore allowing our choice of visual output behaviour to be injected into the code.
Now let's move on to galtonboard.c.
galtonboard.c part 1
#include<stdlib.h> #include<stdbool.h> #include<stdio.h> #include<string.h> #include<math.h> #include<time.h> #include"galtonboard.h" //-------------------------------------------------------- // FUNCTION PROTOTYPES //-------------------------------------------------------- static int left_or_right(); //------------------------------------------------------------------------- // FUNCTION galtonboard_create //------------------------------------------------------------------------- galtonboard* galtonboard_create(int rowcount, int ballcount, int pause_ms, void(*oncreate)(galtonboard* gb)) { int gridrows = ((rowcount * 2) - 1) + 3; int gridcolumns = (rowcount * 2) + 1; int rowpegcount = 1; int pegsdrawn = 0; int firstpegx = floor(gridcolumns / 2); int pegx = firstpegx; int pegy = 3; galtonboard* gb = malloc(sizeof(galtonboard)); if(gb != NULL) { // create struct *gb = (galtonboard){.board = malloc(gridrows * sizeof(char*)), .rowcount = rowcount, .ballcount = ballcount, .pause_ms = pause_ms, .totals = malloc( (rowcount + 1) * sizeof(int) ), .gridrows = gridrows, .gridcolumns = gridcolumns, .prevballx = -1, .prevbally = -1}; // if struct created, create 2D array of pegs using letter 'O' to indicate a peg if(gb->board != NULL && gb->totals != NULL) { for(int r = 0; r < gridrows; r++) { gb->board[r] = malloc(gridcolumns * sizeof(char)); if(gb->board[r] != NULL) { for(int c = 0; c < gridcolumns; c++) { if(r == pegy && c == pegx && pegsdrawn < rowpegcount) { gb->board[r][c] = 'O'; pegsdrawn++; pegx+= 2; } else { gb->board[r][c] = ' '; } } if(r > 2 && (r%2) == 0) { rowpegcount++; pegsdrawn = 0; firstpegx--; pegx = firstpegx; pegy+= 2; } } else { galtonboard_free(gb); return NULL; } } // set all totals to 0 for(int t = 0; t < rowcount + 1; t++) { gb->totals[t] = 0; } oncreate(gb); return gb; } else { galtonboard_free(gb); return NULL; } } else { return NULL; } }
After the prototype for the static function left_or_right which we'll come to later we have galtonboard_create. Firstly we need to calculate how many rows and columns the board needs, allowing for spaces between the pegs and a bit of a drop before the ball hits the first peg. There are also a few variables for how many pegs for the current row, how many have so far been created, the starting peg position, and the actual current peg location.
We use malloc several times to grab the required memory for the struct and its contents. The return value of malloc is always checked before proceeding; if at any time it is NULL we call galtonboard_free to free any memory which has been allocated so far and then return NULL.
After malloc'ing memory for the struct we assign the memory to an actual struct, setting its members as necessary, using malloc again a couple more times.
Next we iterate the rows, allocating memory for each and then setting the chars corresponding to a peg position to 'O'. After each row we increment the number of pegs required as each row has one more than the previous, and also shift the horizontal position of the first peg to the left.
Next the totals are initialized to 0, and finally the function supplied to the oncreate pointer is called to let whatever function has been assigned to draw the board know that it needs to do its stuff.
galtonboard.c part 2
//------------------------------------------------------------------------- // FUNCTION galtonboard_start //------------------------------------------------------------------------- void galtonboard_start(galtonboard* gb, void(*onballmoved)(galtonboard* gb), void(*ontotalchanged)(galtonboard* gb, int index, int count)) { struct timespec t; t.tv_sec = 0; t.tv_nsec = 1000000 * gb->pause_ms; int totalindex; srand(time(NULL)); // loop for number of balls for(int b = 1; b <= gb->ballcount; b++) { // set ball horizontal position to centre gb->ballx = floor(gb->gridcolumns / 2); // loop through rows of grid for(int r = 0; r < gb->gridrows; r++) { gb->bally = r; // if we hit a peg move left or right if(gb->board[r][gb->ballx] == 'O') { gb->ballx += left_or_right(); } onballmoved(gb); gb->prevballx = gb->ballx; gb->prevbally = gb->bally; if(r < gb->gridrows - 1) { nanosleep(&t, NULL); } } // calculate index of totals for current ball position if(gb->ballx == 0) { totalindex = 0; } else { totalindex = gb->ballx / 2; } gb->totals[totalindex] += 1; ontotalchanged(gb, totalindex, b); } }
The galtonboard_start function is at the heart of this whole program as it sets the board running by creating balls, bouncing them off pegs and keeping running totals when they drop off the bottom.
Firstly we have a timespec struct to pass to the nanosleep function to provide a suitable delay between each ball move. This is a fiddly thing to use as you have to set times of 1 second or multiples of 1 second in tv_sec, and fractions of a second in tv_nsec. If you want, for example, 1.5 seconds you need to set tv_sec to 1 and tv_nsec to 500000000 (half a billion). You can't just set tv_nsec to 1500000000 (one and a half billion) or any value over 999999999. That shouldn't be a problem here but if you are doing what I have done and set timespec by multiplying up from milliseconds in a situation where you might need a delay of a second or more it will need to be more carefully coded.
Having seeded the random number generator with the current time we can start to iterate through the number of balls. Firstly its horizontal position is set to the middle of the board, and then for each ball we iterate the rows of the grid. The bally variable is set to the current row number, simulating it dropping downwards each iteration. However, if we hit a peg we need to move left or right at random so add the return value of the left_or_right function to the horizontal position. As we'll see later this just returns 1 or -1 at random. Next we call the onballmoved function to let whatever code is drawing the ball that it has moved, and reset the previous ball positions. If we haven't yet reached the bottom of the board the code sleeps for the specified time.
When each ball has reached the bottom of the board the relevant total is incremented and the ontotalchanged function is called to show the updated totals. In practice this means dropping the ball into the relevant container and updating the numeric count displayed on screen.
galtonboard.c part 3
//------------------------------------------------------------------------- // FUNCTION galtonboard_free //------------------------------------------------------------------------- void galtonboard_free(galtonboard* gb) { if(gb != NULL) { if(gb->board != NULL) { for(int r = 0; r < gb->gridrows; r++) { free(gb->board[r]); } free(gb->board); } free(gb->totals); free(gb); } } //-------------------------------------------------------- // FUNCTION left_or_right //-------------------------------------------------------- static int left_or_right() { if((rand() % 2) == 0) { return -1; } else { return 1; } }
The galtonboard struct has three levels of dynamic memory which is reflected in the nested ifs in galtonboard_free. This function can be run on a fully malloced struct but also on a partially allocated one if one of the second or third level mallocs failed.
Lastly there is the left_or_right function which returns -1 or 1, this value being added to the horizontal position of a ball if it hits a peg, moving it randomly left or right.
I initially made the mistake of seeding the random number generator in this function. However, that meant the same seed was being used up to 10 times (assuming a 100ms pause) so the ball would go left or right up to 10 times in succession. Serious bug! Easily fixed though by calling srand in galtonboard_start, meaning it is only called once during the entire run.
Now lets move on to the set of functions passed to the code in galtonboard.c which are called to actually draw the board on the screen.
galtonboardview.h
#include"galtonboard.h" //-------------------------------------------------------- // FUNCTION PROTOTYPES //-------------------------------------------------------- void galtonboardview_oncreate(galtonboard* gb); void galtonboardview_onballmoved(galtonboard* gb); void galtonboardview_ontotalchanged(galtonboard* gb, int index, int count);
The function prototypes in the header match the pointers passed to the galtonboard.c functions.
galtonboardview.c part 1
#include<stdio.h> #include<time.h> #include"galtonboardview.h" #define RED "\x1B[31m" #define GREEN "\x1B[32m" #define RESET "\x1B[0m" #define X_OFFSET 2 #define Y_OFFSET 6 //------------------------------------------------------------------------- // FUNCTION gotoxy //------------------------------------------------------------------------- static void gotoxy(int x, int y) { printf("%c[%d;%df", 0x1B, y, x); }
There are a few #defines for colours, and a couple of offsets to allow for the heading and space on the left of the output. The gotoxy function is rather crypting and I have scattered several patterns like this around. In a later post I'll explore them in detail but for now this one sets the cursor position.
galtonboardview.c part 2
/-------------------------------------------------------- // FUNCTION galtonboardview_oncreate //-------------------------------------------------------- void galtonboardview_oncreate(galtonboard* gb) { // clear screen printf("\e[1;1H\e[2J"); puts("-----------------"); puts("| codedrome.com |"); puts("| Galton Board |"); puts("-----------------\n"); // iterate rows and columns to draw board for(int r = 0; r < gb->gridrows; r++) { putchar(' '); for(int c = 0; c < gb->gridcolumns; c++) { putchar(gb->board[r][c]); } puts(""); } puts(""); // draw buckets for(int r = 0; r < 16; r++) { for(int c = 0; c <= gb->rowcount + 1; c++) { printf(GREEN "| " RESET); } printf(GREEN "%d\n" RESET, abs(r - 16)); } }
Another one of those cryptic patterns! This one just clears the screen. The rest is straightforward - after the heading we just iterate the rows and columns, printing the contents of the grid, ie a letter 'O' for a peg and a space for no peg. Finally we draw what I have termed buckets for holding the balls after they drop off the last peg.
galtonboardview.c part 3
//-------------------------------------------------------- // FUNCTION galtonboardview_onballmoved //-------------------------------------------------------- void galtonboardview_onballmoved(galtonboard* gb) { // delete ball if it has a previous position if(gb->prevballx >= 0 && gb->prevbally >= 0) { gotoxy(gb->prevballx + X_OFFSET, gb->prevbally + Y_OFFSET); printf(" "); fflush(stdout); } // draw ball in new position gotoxy(gb->ballx + X_OFFSET, gb->bally + Y_OFFSET); printf(RED "o" RESET); fflush(stdout); }
This function implements some basic animation by printing a space in the previous ball position if it is >= 0, and then draw a red 'o' in the current ball position.
galtonboardview.c part 4
//-------------------------------------------------------- // FUNCTION galtonboardview_ontotalchanged //-------------------------------------------------------- void galtonboardview_ontotalchanged(galtonboard* gb, int index, int count) { struct timespec t; t.tv_sec = 0; t.tv_nsec = 1000000 * gb->pause_ms; int bottom_of_bucket = 4 + gb->gridrows + 19; int bucketx; if(index == 0) { bucketx = 2; } else { bucketx = (index + 1) * 2; } // animate ball into bucket int starty = bottom_of_bucket - 17; int end_y = bottom_of_bucket - gb->totals[index]; for(int y = starty; y <= end_y; y++) { nanosleep(&t, NULL); gotoxy(bucketx, y-1); printf(" "); fflush(stdout); gotoxy(bucketx, y); printf(RED "o" RESET); fflush(stdout); } // show totals vertically char totalstr[8]; int total_y = bottom_of_bucket + 1; int total_x = 2; for(int t = 0; t < gb->rowcount + 1; t++) { sprintf(totalstr, "%d", gb->totals[t]); for(int c = 0; c < 7; c++) { gotoxy(total_x, total_y + c); printf("%c", totalstr[c]); } total_x += 2; } // show ball count gotoxy(2, bottom_of_bucket + 4); printf("Ball %d of %d\n", count, gb->ballcount); }
This function is called after each ball has reached the bottom of the board and the corresponding total is incremented, and animates the ball down into the "bucket" and prints the totals.
After another timespec as described above we need to calculate where the bottom of the bucket is. This is the height of the heading plus the height of the board, plus a small gap, and then the height of the buckets. We then calculate the horizontal position of the bucket corresponding to the total which has changed.
Having calculated where we want the ball to start and stop we enter a for loop, overwriting the previous ball position and printing it in its new position.
Next the totals are printed vertically so they line up with the buckets. To do this they are printed to a string using sprintf and each character printed below the previous. Finally the current ball count and total number of balls is shown.
The main code is now finished so we just need to run it, so let's write a main function to do so.
main.c
#include<stdio.h> #include<math.h> #include<time.h> #include<locale.h> #include<stdlib.h> #include"galtonboardview.h" //-------------------------------------------------------- // FUNCTION main //-------------------------------------------------------- int main(int argc, char* argv[]) { galtonboard* gb = galtonboard_create(7, 40, 100, galtonboardview_oncreate); if(gb != NULL) { // hide cursor printf("\e[?25l"); fflush(stdout); galtonboard_start(gb, galtonboardview_onballmoved, galtonboardview_ontotalchanged); galtonboard_free(gb); // unhide cursor printf("\e[?25h"); fflush(stdout); return EXIT_SUCCESS; } else { puts("Cannot create board"); return EXIT_FAILURE; } }
Firstly galtonboard_create is called and, if successful, we start off by hiding the cursor with yet another cryptic collection of characters. Then we just need to call the start and free functions before unhiding the cursor.
Compile and run the program with these commands in the terminal.
Compile and run
gcc main.c galtonboard.c galtonboardview.c -D_POSIX_C_SOURCE=199309L -std=c11 -lm -o main
./main
This is an example of what the output looks like after a run.
Program Output
-----------------
| codedrome.com |
| Galton Board |
-----------------
O
O O
O O O
O O O O
O O O O O
O O O O O O
O O O O O O O
| | | | | | | | | 16
| | | | | | | | | 15
| | | | | | | | | 14
| | | | | | | | | 13
| | | |o| | | | | 12
| | | |o| | | | | 11
| | | |o|o| | | | 10
| | | |o|o| | | | 9
| | | |o|o| | | | 8
| | | |o|o| | | | 7
| | |o|o|o| | | | 6
| | |o|o|o|o| | | 5
| | |o|o|o|o|o| | 4
| | |o|o|o|o|o| | 3
| |o|o|o|o|o|o| | 2
|o|o|o|o|o|o|o| | 1
1 2 6 1 1 5 4 0
2 0
Ball 40 of 40
The terminal-based output is pretty basic and in particular the animation leaves a lot to be desired. There is also the problem that if any total exceeds the bucket size it will overflow. However, as I mentioned earlier a key feature of this project is that the output is separated from the logic and so can easily be replaced by something better.