How I Used Recursion in My Jigsaw Puzzle Game
In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code.
Recursion can seem like a simple concept at first but can be hard to grasp. There are several examples to get a better understanding like finding a factorial using recursion or the Fibonacci sequence. But I think it is a concept that is better understood by relatable examples. So I will give an example of how I used recursion while developing my video game.
When I started developing my first console game during my internship, I had heard about recursion but never used it before. But during the development of the game, I came across a problem I haven't encountered before.
To make the problem more understandable, I'll give a brief explanation of the game. The game I developed was a simple jigsaw puzzle game. There is a puzzle image split into pieces and scattered around the play area. The goal of the game is to solve the puzzle by putting each piece to its original location.
There was an additional mechanic I had to add to the game. Normally, you can select a piece and move it around. But I wanted it so that when there were multiple pieces that are connected to each other, moving one of them would also move the others. For example, when 3 pieces are connected at the side, I could move all 3 of them by selecting just one of them.
The first thing I had to do was access all the pieces that are connected to the selected piece. The way I coded the piece class was convenient for this because the class included an array of adjacent pieces. So I could access all the adjacent pieces using that array. But the tricky part was getting the adjacent pieces of all the adjacent pieces. I could see that the process started repeating itself but I didn't know how to proceed using loops. I didn't know how many times it should iterate and I couldn't think of a way to access the adjacent pieces for each adjacent piece in the adjacent pieces list. Then I asked myself, is this where I am supposed to use recursion?
I had to write a function to get a list of all the pieces that are connected to piece 1 (1,2,3,4,5,6). So how did I proceed? First, I started simple. I thought how would I get all the adjacent pieces for the first piece.
def get_adjacent_pieces(piece):
output = []
for adjacent_piece in piece.adjacent_pieces:
if adjacent_piece is not None:
output.append(adjacent_piece)
Now I had to do this for every adjacent piece of every adjacent piece.
def get_adjacent_pieces(piece, output = None):
if output is None:
output = []
for adjacent_piece in piece.adjacent_pieces:
if adjacent_piece is not None:
output.extend(get_adjacent_pieces(adjacent_piece, output))
return output
So now our function traverses through all the adjacent pieces and adds each one of them to the output because it calls the get_adjacent_pieces function for each adjacent piece of the given piece argument.
But I did a mistake that would lead to a stack overflow exception. Did you catch it?
So since piece 2 is adjacent to piece 1 it means piece 1 is adjacent to piece 2. This means when I call get_adjacent_pieces(1), it will call get_adjacent_pieces(2) since piece 2 is adjacent to piece 1. But now, get_adjacent_pieces(2) will call back get_adjacent_pieces(1) causing an infinite loop.
def get_adjacent_pieces(piece, output = None, caller = None):
if output is None:
output = []
for adjacent_piece in piece.adjacent_pieces:
if adjacent_piece is not None and adjacent_piece is not caller:
output.extend(get_adjacent_pieces(adjacent_piece, output, piece))
return output
I added a parameter called caller so now we can store the piece that called the function. This way, I can check if an adjacent piece is the piece that called the function. For this to work, I need to pass the current piece as caller for each function call to the get_adjacent_pieces function.
There is still a slight problem though. Our function adds adjacent pieces to its output but not the initial piece. So calling get_adjacent_pieces(1) will return (2,3,4,5,6) but it won't include 1. Because it is never stated to add the given piece to the output, only the adjacent pieces. We could simply add output.append(piece) but this would result in duplicate pieces since for example piece 2 will be added twice because it is first added as piece 1's adjacent piece when get_adjacent_pieces(1) is called and secondly as current piece when get_adjacent_pieces(2) is called.
One workaround to avoid that would be checking if caller is assigned. So we can determine if we are in the first call and add the current piece to the output only then.
def get_adjacent_pieces(piece, output = None, caller = None):
if output is None:
output = []
for adjacent_piece in piece.adjacent_pieces:
if adjacent_piece is not None and adjacent_piece is not caller:
output.extend(get_adjacent_pieces(adjacent_piece, output, piece))
if caller is None:
output.append(piece)
return output
Looking good. Now our function works as we want. Passing any piece from 1 to 6 will return (1,2,3,4,5,6). So now the player can access and move all the pieces by just selecting one of them.
There's still a problem though. Having 4 adjacent pieces like this would result in an infinite loop. Think of it like this. Let's denote our get_adjacent_pieces as gap for convenience. Let's say you call gap(piece1). Now our function call will call gap(piece2, output, piece1) and gap(piece7, output, piece1). Then they will both call gap(piece4) but with different caller arguments. piece7's call will result in gap(piece2) and piece2's call will result in gap(piece7) which, in the end, will call in gap(piece1), resulting in an infinite loop.
This is a big problem and will cause the program to crash because of the infinite loop it results in. So how would you solve it? Let me know in the comments :)
Comments
Post a Comment