Experimenting with Maze code in C++

June 11

Starting in Ruby

Recently I’ve been chipping away at Jamis Buck’s ‘Mazes for Programmers’. I’m loving it and highly recommend the book. The code examples are quick to write, intuitive and good to learn from. They are written in Ruby and quietly introduce good design practices.

Whilst I’m working through the book I’m uploading my work in progress to https://github.com/alexallmont/JamisMazes. It’s been a while since I’ve pushed anything to GitHub because I started working on some of the ‘try at home’ sections at the end of each chapter; as I was working through it I started restructuring the core libraries on a new branch. I’ve gone down the refactor rabbit hole.

Moving to C++

I’ve managed to distract myself further by making my own maze library in C++. At the time of writing the repo https://github.com/alexallmont/MazeCpp is a simple C++ library which links into a demo and unit tests. My goal here was to brush up on my C++14 and experiment with continuous build systems. Over the last few days though I’ve been irked by the clunky design on the first draft. There’s lots of aliasing early on, the code was already feeling flabby.

Playing with templates

Today I’ve been experimenting with a templatised version that compiles down to practically nothing. I wanted to exploit that these mazes are fixed size, so I can use std::array to store data rather than std::vector. This means a huge amount of work can be done at compile time. Today’s experiments are at https://godbolt.org/g/ko0WIz.

The main class Grid2D is declared as a template with fixed rows and columns. Having the rows and column sizes declared at compile time means that a lot of the API boils down to constexpr functions. Rather than have a separate ‘Cell2D’ class, each Grid2D declares a nested Cell class that is a lightweight wrapper for querying individual cells in the maze graph.

Screen Shot 2017-06-11 at 17.26.09

I was hoping that I could reduce each cell to be a single integer, it’s index in the grid (row * NUM_ROWS + column). Unfortunately reducing to an int was not possible because each cell has query methods that reference non-static methods in Grid2D, so they also need to store an instance pointer to their owning grid. The alternative to this aliasing would be to pass the grid to every Cell function call, but that breaks the encapsulation and does not read well in code. However when building optimised the pointers boil away.

I’d prefer to store each cells Grid2D by reference rather than pointer and I’m exploring options as to whether that’s possible with std::array. As far as I know one can only use std::array on simple data types, no fancy construction is allowed, so the Cell class is friendly with Grid2D which does all the initialisation.

Regardless the simple test case compiles down ridiculously small, just 4 ops!

Screen Shot 2017-06-11 at 17.23.56

Screen Shot 2017-06-11 at 17.26.50



No Responses Yet to “Experimenting with Maze code in C++”

  1. Leave a Comment

Leave a Reply

Your email address will not be published. Required fields are marked *