- Home
- Learn Linux
- Learn Electronics
- Raspberry Pi
- Programming
- Projects
- LPI certification
- News & Reviews
This is an introduction to algorithm design. This is designed to be a simple explanation for those starting in computer science and watching to understand about why we design algorithms, how to create better algorithms and how to evaluate those algorithms.
This is based around a practical example of drawing circles on a Badger 2040 hackable ID badge, similar to the Raspberry Pi Pico.
This is going to explain about how I came up with 3 different algorithm designs. The first two I created using mathematical principles, the third is based on a real world algorithm which is more efficient.
In the video I also discuss some unique aspects of the Badger 2040 including how to create an interactive game which is usuable despite the refresh mechanism used for e-paper displays. This is based on a pass-and-play implementation of Tic-Tac-Toe.
An algoirithm is a process or set of rules which are followed to perform a calculation or to solve a problem. A useful analogy is with a cooking recipe. Just like a recipe describes the ingredients and how you combine them into something to eat, an algorithm tells you of the variables that you need and how the computer processes them to achieve the desired result. An algorithm can be as simple as saying increase x by 1, which would have something move left to right across the screen, or more complex such as finding the optimal route on a car satellite navigation system.
In this example the aim is to tell a computer how to draw a circle on the screen. This is done by calculating all the pixels that need to be coloured in. As you will see there are different ways that this can be achieved with different performance and correctness.
The first example is based on basic rules of trigonometry.
The hypotenuse is shown as r, which is the radius of the circle. We need to know the co-ordinates x and y, which are calculated using the cosine and the sine of the angle. By starting the angle at zero and moving around the circle then the position of each of the pixels can be calculated.
An issue with this algorithm is that it involves a lot of processing to calculate all these points. This is known as time complexity.
The next algorithm is an approximation algorithm. The aim is to have an algorithm that creates an approximation of what is desired, or in this case something that looks like a circle, even if it’s not.
This is actually quite a common technique, especially for problems that are NP-hard, effectively those who would need huge amounts of processing to perform a certain task. An example is the classic travelling salesman problem which is about choosing an optimum route between cities. The idea of using an approximation algorithm is that rather than trying to calculate every possible solution to find the shortest (which you can do with a small number of cities) then to have an algorithm which instead works out a route that is approximately the best solution.
We also use approximations in other aspects of computer science. For example JPEG images you capture with a phone use a technique to reduce the size of the files by using a lossey compression algorithm. The aim to have a picture that looks the same to a human as the original, but uses much less storage.
The approximation I used with the circle is to have something that looks like it’s made with curved lines, but is actually made of straight lines. This is particularly useful for use with the Badger 2040 as the library has a function for drawing a straight line, but not one for drawing curved lines.
At it’s most accurate a line could be just 1 pixel long and it would be exactly the same as a true circle (in the case of my 200 pixel circle that’s made up of about 1000 lines), or we could reduce it to only 100 lines (a Hectogon) or 10 lines a Decagon (as shown in the image below).
This is farly intuitive and easy to understand. It also reduces the number of trigonometry calculations needed. This is the technique I used in the tic-tac-toe game for the Badger 2040. The code for drawing the circle is shown below.
def draw_circle(cx, cy, radius=10):
degree_step_size = 10
# build list of points
points = []
for i in range (0, 360, degree_step_size):
irad = math.radians(i)
this_x = int(cx + radius * math.cos(irad))
this_y = int(cy + radius * math.sin(irad))
points.append ((this_x, this_y))
for i in range(len(points)-1):
display.line (*points[i], *points[i+1])
# final back to the start
display.line(*points[len(points)-1], *points[0])
This is a more mathematically based algorithm which is used in real-world implementations of circle drawing functions.
For this to work you need to consider the circle split into 8 segments. The algorithm shown will calculate the values for the (x,y) segment and then you will need to apply the various translations to calculate for all 8 segments. This algorithm is based on calculating a single arc in the (x, y) segment.
To implement this then you start at x = radius and y = 0
The next pixel is either (x, y+1) or (x-1, y+1).
To determine which then find the mid-point p of the two possible values (x-0.5, y+1) and if p is inside or on the perimeter then plot (x, y+1) otherwise plot (x-1, y+1).
To determine if p is inside or outside the circle use:
F(p) = x2 + y2 - r2
F(p) < 0 : inside the cricle
F(p) = 0 : on the perimeter
F(p) > 0 : outside the circle
The source code for the calculation of x, y and p is shown below.
This has performance improvements compared to both the above and meets the correctness criteria.
This has been used to create a game which you can play on the Badger 2040. It's a pass-and-play version of tic-tac-toe.
This is the source code from the tic-tac-toe game. This uses the algorithrm that creates a circle using straight lines and the E-ink refresh settings.
import time, math
import badger2040
import badger_os
# Global Constants
WIDTH = badger2040.WIDTH
HEIGHT = badger2040.HEIGHT
# Tic-Tac-Toe / Noughts and Crosses game
# Grid is x,y
# x is 0 to 2 (left to right)
# y is 0 to 2 (top to bottom)
def draw():
display.pen(15)
display.clear()
# Show grid
display.pen(0)
display.thickness(2)
display.line(103, 49, 193, 49)
display.line(103, 79, 193, 79)
display.line(133, 19, 133, 109)
display.line(163, 19, 163, 109)
# draw any played positions
for gy in range (0, 3):
for gx in range (0, 3):
if (grid[gx][gy] == 0):
# draw a cross
draw_cross(gx, gy)
elif (grid[gx][gy] == 1):
# draw a nought
draw_nought(gx, gy)
# Only show player and cursor if in game
if state == "play":
# Show current player
display.text("Player", 20, 20, 0.5)
if (player == 0):
draw_x (40, 50)
elif (player == 1):
draw_circle (40, 50)
draw_cursor(*cursor)
if state == "gameover":
display.text ("Game Over", 10, 20, 0.5)
# If there is a winner show the line
winner = is_won()
if winner >= 0:
# Draw line
display.line(*winning_line)
display.text ("Winner", 10, 40, 0.5)
if winner == 0:
draw_x (40, 70)
if winner == 1:
draw_circle (40, 70)
# It's a draw
else:
display.text ("Draw", 10, 40, 0.5)
# Draw the noughts and crosses
# Top level - draw nought on grid
def draw_nought(gridx, gridy):
# Approximation of a circle using lines
# get centre of circle
(cx, cy) = grid_to_coord(gridx, gridy)
draw_circle (cx, cy)
# Lower level needs co-ords - useful for player scores etc.
def draw_circle(cx, cy, radius=10):
degree_step_size = 10
# build list of points
points = []
for i in range (0, 360, degree_step_size):
irad = math.radians(i)
this_x = int(cx + radius * math.cos(irad))
this_y = int(cy + radius * math.sin(irad))
points.append ((this_x, this_y))
for i in range(len(points)-1):
display.line (*points[i], *points[i+1])
# final back to the start
display.line(*points[len(points)-1], *points[0])
# High level - draw cross on grid
def draw_cross(gridx, gridy):
# get centre of cross
(cx, cy) = grid_to_coord(gridx, gridy)
draw_x (cx, cy)
# Lower level needs co-ords - useful for player scores etc.
def draw_x (cx, cy):
display.line (cx -10, cy -10, cx + 10, cy + 10)
display.line (cx +10, cy -10, cx - 10, cy + 10)
def draw_cursor(gridx, gridy):
# draw square
(cx, cy) = grid_to_coord(gridx, gridy)
display.rectangle (cx -4, cy -4, 8, 8)
# ------------------------------
# Helper methods
# ------------------------------
# Convert x,y position to centre of square
def grid_to_coord (gridx, gridy):
x = 118 + 30 * gridx
y = 34 + 30 * gridy
return (x, y)
# Checks for possible wins
def is_won ():
global willing_line
# start with first square on a possible line, check that has a player assigned
# then check rest of that line matches - if so then return the first square value
# which will equal the player number. If not return -1
# Check vertical lines
for col in range (0, 3):
if grid[col][0] != -1 and grid[col][0] == grid[col][1] and grid[col][1] == grid[col][2]:
winning_line[0] = 118 + col * 30
winning_line[1] = 19
winning_line[2] = 118 + col * 30
winning_line[3] = 109
return grid[col][0]
# Check horizontal lines
for line in range (0, 3):
if grid[0][line] != -1 and grid[0][line] == grid[1][line] and grid[1][line] == grid[2][line]:
winning_line[0] = 103
winning_line[1] = 34 + line * 30
winning_line[2] = 193
winning_line[3] = 34 + line * 30
return grid[0][line]
# check 2 diagnals
if grid[0][0] != -1 and grid[0][0] == grid[1][1] and grid[1][1] == grid[2][2]:
winning_line[0] = 103
winning_line[1] = 19
winning_line[2] = 193
winning_line[3] = 109
return grid[0][0]
if grid[2][0] != -1 and grid[2][0] == grid[1][1] and grid[1][1] == grid[0][2]:
winning_line[0] = 193
winning_line[1] = 19
winning_line[2] = 103
winning_line[3] = 109
return grid[2][0]
# reach here no match
return -1
# ------------------------------
# Program setup
# ------------------------------
# Create a new Badger and set it to update NORMAL
display = badger2040.Badger2040()
display.led(128)
# ------------------------------
# Main program
# ------------------------------
state = "play"
# Player 0 = crosses (goes first on first game)
# Player 1 = noughts
player = 0
cursor = [0,0]
# number of goes played - when reach 9 know that grid is full
played = 0
# Grid is x y (cols then rows) - so array does not look the same
# -1 = none
# 0 = player 0
# 1 = player 1
grid = [
[-1,-1, -1],
[-1,-1,-1],
[-1,-1,-1]]
# winning_line used as a global to determine where to draw line when someone wins
winning_line = [0,0,0,0]
# Display initial screen
draw()
display.update()
while (1):
# wait for action (uses loop)
while (1):
if state == "play":
display.update_speed(badger2040.UPDATE_TURBO)
if display.pressed(badger2040.BUTTON_A):
if cursor[0] > 0:
cursor[0] -= 1
break
if display.pressed(badger2040.BUTTON_C):
if cursor[0] < 2:
cursor[0] += 1
break
if display.pressed(badger2040.BUTTON_UP):
if cursor[1] > 0:
cursor[1] -= 1
break
if display.pressed(badger2040.BUTTON_DOWN):
if cursor[1] < 2:
cursor[1] += 1
break
if display.pressed(badger2040.BUTTON_B):
display.update_speed(badger2040.UPDATE_MEDIUM)
# If empty then place the mark
# If not empty then ignore button press
if (grid[cursor[0]][cursor[1]] == -1):
grid[cursor[0]][cursor[1]] = player
played += 1
# Swap player and reset cursor
if player == 0:
player = 1
else:
player = 0
# return cursor to top left
cursor[0] = 0
cursor[1] = 0
break
# Otherwise press B to start game
else:
if display.pressed(badger2040.BUTTON_B):
state == "play"
if is_won() >= 0 or played >= 9:
state = "gameover"
draw()
display.update()
More information about the Badger 2040 badge.
See my other programming guides at:
