An Introduction

For an algorithm to be considered recursive its code must be recursive, doing recursive things doesn’t cut it. What I mean is that finding nested data is a recursive action, because the data is literally contained within other data you are searching recursively to find more data; however that isn’t recursive code, which I thought was odd at first. Recursive code, in general, is recursive because the code will execute itself. The call stack is what’s recursive here, and with that in mind the separation between doing something recursively and being recursive makes total sense.

In this case the algorithm, itself, is what’s recursive. In order to find a path the algorithm will execute recursively.

Description

This project was another data structures assignment, and the goal was to create a recursive pathfinding algorithm. Our instructor, an intelligent fellow, knew that as programmers our instincts would always lead us to do the job as efficiently as possible. That is to say, we’re lazy so we’d try to do the least amount of work. So to make sure we got the job done, with all the pain he wished to inflict (me excluded), he specified a map size of 1024×1024 tiles. The next requirement was many geological features of our “Mars” tile map, crevices and cliffs. These two requirements would make sure that our algorithms would reach at least~ 1000 levels of recursion. Last, he explicitly specified at least 3 types of tiles: Dirt, Boulders, Crevices. You can guess which of the three was the only traversable terrain to our Mars Rover.

I took those requirements and happily begun designing. I designed the project with a map size of 256×256 regions. Where each region has a size of 4×4 tiles, and is stored as a 32 bit unsigned integer; YAY bit packing(!). Now if you’re sharp you know that means each tile can use up at most 2 bits of information, and based on the requirements there is at least 2 bits of information needed. Optimizing data structures can only ever take you so far when the you expect your algorithm to reach several hundred/thousand levels of recursion. I also increased the stack size initially, and later implemented a recursion limit. When the algorithm reaches the recursion limit the stack unwinds into a container to be used as a non recursive form of backtracking.

Objectives

Any time I am given a challenge where packing as much information into as small a package as possible, I get excited. So – needless to say – I was thrilled by the challenge of this project. I didn’t see this project as difficult, and I couldn’t envision any especially clever ways to do it. Instead I simply focused on doing the best job I could.

• Use bit packing (Of course!!!)
• Prevent stack overflows
• Optimize algorithm
• Avoid requiring an altered stack size

Highlights

Successes

• Packed sixteen variables into one variable. As previously mentioned, I designed the map using regions. Each region was a map in of itself, each with a size of 4×4 tiles. Now each region was little more than an encapsulated integer. I designed regions as classes merely to simplify their use; I believe its almost always better to black-box functionality when it is complicated.
• Prevented stack overflows regardless of the map size, or path length. I didn’t test this extensively, but if it prevents one stack overflow, it will prevent all of them. The algorithm has a recursion limit built into it, which can be changed with a macro (requires a new build). Once the recursion limit is reached the stack unwinds into a container, then the algorithm continues going as it was. When or if the algorithm backtracks to the point it reaches 0 recursion it will begin unwinding data from the container just as if it were the stack.
• Optimized the rover instruction set. The rover can and will find the shortest path possible using straight forward recursion; or you can rebuild using a different macro and optimize the instruction set to search for less time. I am skeptical that any better can be done while using a recursive search.

Challenges

• Verifying my intuition was correct when it came to optimizing the rover instruction sets. I had to perform actual tests to verify I had started with the best instruction set.
• None, that’s it. Even verifying instruction set performance was pretty straight forward and easy. It was tedious though.

Results

The results were good. I finished in about a week,