Turning Algorithms into Code
Algorithms are the fundamental building blocks of the code that we see around us. They take complicated problems and find solutions made of simple steps.
A few people have asked about how they can algorithms into code, so this post will go over the process.
This example will be recreating the A* pathfinding algorithm in JavaScript. This language will allow the results to be embedded right into the web. The same ideas should work perfectly fine with any other language and algorithm.
Algorithms Aren't as Scary as They Look
One of the most important things to realize is that algorithms are a combination of many simple steps and components. They can seem complicated with confusing parts but they're not that bad.
The steps in this post will show a way to turn an algorithm into working code but bugs and issues will almost always pop up. The goal of the post is to define steps to follow if someone doesn't know where to start.
Understanding the Problem
The first step when recreating any algorithm is researching the algorithm to understand what information it needs.
There are all sorts of algorithms on the internet with great descriptions. Reading up for a few minutes on your algorithm of choice is recommended to get an understanding of how it works.
It can be especially useful to find illustrations and animations depicting the algorithm at work. There are often long write-ups (often even including pseudo-code you can use as a base!) that discuss the inner workings of algorithms.
Algorithms often work with components like nodes and vectors but these just represent ways of storing data in an organized way.
You can use libraries that create and manage these components for you, but for this example will show you how to create these as well.
Representing the Problem in Code
A*, like other pathfinding algorithms, represents locations with edges and nodes. This means each major location is represented by a node, and the connections between the nodes are called edges.
A* then explores the nodes based on which nodes are the most beneficial (easy to travel to and bring us closer to the end). So we'll need a queue to store the list of nodes that the algorithm is looking into, as well as a list of nodes it is finished with.
Before programming, it can be very helpful to draw or take a note of how the code will work, as well as some of the functions the components will fulfill.
Before programming, it can be very helpful to draw or take a note of how the code will work, as well as some of the functions the components will fulfill.
Notes
/* Node
* An object that represents a point on the map
* Stores a h value (value that represents distance from finish line)
* Stores a g value (cost of cheapest path to node)
* Stores an f value (g + h)
* Stores references to all surrounding nodes that it has connections to as well as the associated costs
* Stores a reference to the node that precedes it on the cheapest known path
* Stores x, y, w, and h to show itself (Specific to my graphical implementation)
* Has many states associated with colours (Specific to my graphical implementation)
*/
/* Grid: Node[][]
* A cartesian graph of a bunch of nodes
* Helps organize and visualize the nodes for easy display
*/
/* Queue: Node[]
*
* A list of nodes to explore in order of which one should be looked at next
* Nodes are organized in order of cost (lowest to greatest)
* Based on the cost of the cheapest path to the node and its heuristic
*/
/* Closed: Node[]
* A list of nodes that have already been fully explored
Programming
Each step below has been linked to GitHub commit so you can follow along and see how the code evolved to reach completion.
Part 1: Data Structures
Now that the basics are outlined we can go ahead and make some template code. This represents the data and makes sure each of the parts we outlined is here.
sketch.js
// Values for graphical output
let nodeHeight = 30;
let nodeWidth = 30;
function setup() {
// Code to create an adaptive canvas
let canvasDiv = document.getElementById('canvas');
let width = canvasDiv.offsetWidth;
let height = canvasDiv.offsetHeight;
let canvas = createCanvas(width, height);
canvas.parent('canvas');
background(0, 0, 0);
// Setup values for grid
let columns = Math.floor(width / nodeWidth);
let rows = Math.floor(height / nodeHeight);
// Create 2D grid
let grid = new Array(columns);
for (let i = 0; i < columns; i++) {
grid[i] = new Array(rows);
}
// Create storage for nodes
let queue = [];
let closed = [];
}
function draw() {}
node.js
const states = {
OPEN: 'open',
BLOCKED: 'blocked',
START: 'start-node',
FINISH: 'end-node',
QUEUED: 'queued',
CLOSED: 'closed',
};
class MapNode {
constructor(x, y, w, h, state) {
// f, g, and h values
this.f = 0;
this.g = 0;
this.h = 0;
// Array to store all connections
this.connected = [];
// Ref to previous node
this.cameFrom = undefined;
// Data for visuals
this.xPos = x;
this.yPos = y;
this.width = w;
this.height = h;
this.state = state;
}
}
This part can vary depending on your implementation of the algorithm. This code declares a MapNode class, as the algorithm be working with many nodes. The class will make producing and managing the objects much easier. It will manage the data and functionality for each node.
Each list of nodes is declared as an array. Another data structure would work as well but arrays are easy to use in JavaScript and will work fine for this visualization.
The canvas is set up as soon as possible as it'll allow for easier debugging.
Part 2: Initialize the Algorithm
Most algorithms need to work on top of a data set that is organized in a specific way. Try to make sure that everything is ready for the algorithm to run.
sketch.js
// Grid Options
let percentFilled = 30;
let nodeHeight = 30;
let nodeWidth = 30;
...
function setup() {
...
// Fill the grid with nodes based on the % that should be open
for (let x = 0; x < columns; x++) {
for (let y = 0; y < rows; y++) {
if (Math.random() * 100 > percentFilled) {
grid[x][y] = new MapNode(
x,
y,
nodeWidth,
nodeHeight,
states.OPEN
);
} else {
grid[x][y] = new MapNode(
x,
y,
nodeWidth,
nodeHeight,
states.BLOCKED
);
}
}
}
// Set/init start and end points
start = grid[0][0];
finish = grid[columns - 1][rows - 1];
start.setState(states.OPEN);
finish.setState(states.FINISH);
start.g = 0;
start.h = dist(start.column * nodeWidth,
start.row * nodeHeight,
finish.column * nodeWidth,
finish.row * nodeHeight);
start.f = start.g + start.h;
// Add the start node to the queue
queue.push(start);
// Output the base grid
for (let x = 0; x < columns; x++) {
for (let y = 0; y < rows; y++) {
grid[x][y].show();
}
}
}
function draw() {
if (queue.length > 0) {
// Run main search loop
} else if (start.state != states.SUCCESS) {
// Search failed
}
}
You may have noticed that I'm calling functions in this loop such as `.setState()` and `.show()` but they don't exist. Doing so allows you to architect the code in an organized manner from the start. This practice lets you know which functions each class will need as well as how they should be declared.
Another concern may be that the connections between the nodes aren't initialized. This network is organized as a grid and is optimizing accordingly. The node network will be dynamically generated as the algorithm searches. This will also allow for the visuals to be customized down the line to better show the algorithm at work.
Part 1: Implement the Main Loop
Next up is the main loop of the algorithm. It helps to follow the steps the algorithm takes and translate them into code sequentially.
sketch.js
...
function draw() {
if (queue.length > 0) {
// Run main search loop
let currentNode = queue[0];
let newNodes = currentNode.getConnections(grid);
// Check if done
if (currentNode == finish) {
while (currentNode.cameFrom != undefined) {
currentNode.setState(states.SUCCESS);
currentNode.show();
currentNode = currentNode.cameFrom;
}
start.setState(states.SUCCESS);
start.show();
} else {
// Remove current node from queue
currentNode.setState(states.CLOSED);
currentNode.show();
closed.push(currentNode);
queue.shift();
// Insert each connection into the queue according to its f value
newNodes.forEach((node) => {
// Check if this is the quickest path to this node
let tempG =
currentNode.g +
dist(
currentNode.column * nodeWidth,
currentNode.row * nodeHeight,
node.column * nodeWidth,
node.row * nodeHeight
);
if (tempG < node.g) {
node.h = dist(
node.column * nodeWidth,
node.row * nodeHeight,
finish.column * nodeWidth,
finish.row * nodeHeight
);
node.cameFrom = currentNode;
node.g = tempG;
node.f = node.g + node.h;
}
// Add the node to the queue and sort
queue.push(node);
queue.sort((a, b) => a.f - b.f);
node.setState(states.QUEUED);
node.show();
});
}
} else if (start.state != states.SUCCESS) {
// Search failed
for (let x = 0; x < columns; x++) {
for (let y = 0; y < rows; y++) {
if (grid[x][y].state == states.CLOSED) {
grid[x][y].setState(states.FAILED);
grid[x][y].show();
}
}
}
}
}
You can see that the main algorithm is already done being implemented. There will likely be bugs during the first implementation but they should be ironed out in the next step.
By focusing in on one area it's easier to be mindful of what is happening, and thus it helps develop a better understanding of how the code works. This helps make the debugging process run smoother in the end.
Again, some of the methods being called don't exist yet. This makes sure that the main loop isn't doing too much. It's easy to go ahead and implement everything into this loop, but doing so makes for messier code that becomes more difficult to maintain.
Part 4: Making Your Code Functional
Now it's time to build the functions that have been called in the rest of the code. The functions can be added pretty quickly. The inputs, return values, and functionality is already outlined through the calls.
node.js
...
class MapNode {
...
// Returns an array with a list of connected nodes
getConnections(grid) {
if (!this.connected == []) {
if (
this.column != 0 &&
(grid[this.column - 1][this.row].state == states.OPEN ||
grid[this.column - 1][this.row].state == states.FINISH)
) {
this.connected.push(grid[this.column - 1][this.row]);
}
...
if (
this.row != grid[0].length - 1 &&
this.column != grid.length - 1 &&
(grid[this.column + 1][this.row + 1].state == states.OPEN ||
grid[this.column + 1][this.row + 1].state == states.FINISH)
) {
this.connected.push(grid[this.column + 1][this.row + 1]);
}
return this.connected;
} else {
return this.connected;
}
}
// Changes the state of the node
setState(state) {
this.state = state;
}
// Sets the cameFrom variable to a new node
setCameFrom(node) {
this.cameFrom = node;
}
}
At this point the code should be functional.
This step can take a long time as the bugs that were unnoticed in the previous steps tend to show themselves at this point.
This step can be frustrating due to all the debugging that can be involved, but it's also the one that finally gets your code to a working state.
Optimization & Finishing Touches
The last step of the process (usually also my favourite) is the finishing touches.
This is usually a lot of tweaking values and objects to get everything running and looking as nice as possible.
This step doesn't have any instructions or guidelines but that's the best part!
Conclusion
Throughout this post, we (hopefully) successfully translated an algorithm into code.
Go ahead and use this process to code something that interests you! The process won't be the same for every problem but that's the best part. Either way, you come out of the experience learning something new.
Reach out to me and let me know what you've made by following these steps!