Creating a Maze class in C++ using 16bit unsigned int array?

Answer 1

try with std::vector

Answer 2

Well setArrayValue doesn't do anything yet (though you've probably noticed that by now). Also you don't have a delete function so mazeGrid will never be deallocated. Otherwise it looks alright to me.

Answer 3

There's a problem with the constructor - you use "width" and "height" before they are assigned. You also need a destructor to free the memory:

~Maze()
{
    delete [] mazeGrid;
}

Other than that, it looks ok.

Answer 4

You can use the std::bitset

Answer 5

In C++ Construction is initializations. so you can rewrite the c'tor:

    Maze(int mazeWidth, int mazeHeight) 
       :width(mazeWidth), height(mazeHeight), mazeGrid(new uint16_t[width*height])
    {
    }

Notice that the data members are initialized in the order they are defined in the class, not the order you initialize them.
Also notice unsinged int16_t turned to uint16_t. if you're going to use these guys, better go all the way.
It is customary for data members to be called m_width and m_height and not just width and height.

Instead of the set and get methods I would define an operator[] which returns uint16_t* this way you get a more natural syntax which mimics a primitive type:

   ....
   uint16_t* operator[](int col) { return &(mazeGrid[col*width]); }
   ....

   uint16_t d = mymaze[col][row];

I'll let you figure out why this works correctly.

Answer 6

This is going to be a long answer so that it will touch some programming/c++ concepts: encapsulation, RAII, initialization lists, destructors, const-ness, defining operators,template classes, template functions and bit-fields by working on the given problem.

First thing is that I always start designs from the user point of view. To design a data structure for a maze, the user will be the programmer (probably you) that wants to use the data structure. From that point of view, the fact that the structure is memory optimized is an implementation detail, less relevant than the usage.

With your knowledge base I would start by changing the interface so that the user does not need to care about the internal structure by defining a class that encapsulates the bit operations, similar to this (I will later work on it):

class cell {
public: 
  void setBacktrace( unsigned int value ); // value must be between 0-15
  unsigned int getBacktrace() const;
  // same for all other fields
private:
  uint16_t data;
};

Now the user does not need to care about the low level details. The caller code can simply write:

cell c;
c.setBacktrace( 5 ); // set the backtrace value to 5
std::cout << c.getBacktrace() << std::endl;

Now the maze is a container around cell objects. As pointed by others you can use a std::vector to simplify the operations or you can define your own container. Since I take it that you are learning, we will follow the long path:

class maze {
public:
   maze( size_t width, size_t height );
   ~maze();
   cell getCell( size_t row, size_t col ) const;
   void setCell( size_t row, size_t col, cell c );
private:
   size_t width_;
   size_t height_;
   cell * data_;
};

The changes in the interface from your code are: adding a destructor. It will take care of releasing the resources that your constructor requests, following the RAII idiom. The accessor to a cell element is marked as const since it will just return a value without changing the structure. This is another concept that you should start using from the very beginning: mark all non-mutating methods as const.

Now to the implementation:

// Constructor and destructor
maze::maze( size_t width, size_t height ) 
   : width_( width ), height_( height ), data_( new cell[width*height] )
{
}
maze::~maze()
{
   delete [] data_;
}

The constructor is defined using a initialization list. In the initialization list the fields constructors for the fields width_, height_ and data_ are called passing a width, height and the returned pointer of the new sentence as arguments.

There are two reasons for using initialization lists instead of adding the equivalent code inside the constructor block ({}). Initialization lists are more efficient than the equivalent code inside the brackets (not so important) but mainly allow you to call specific constructors or initialize references, neither of which can be done inside the constructor block.

I have added a destructor to release the data you acquire. If you do not add a destructor to your class, the compiler will provide a default destructor that will call the destructor of all the attributes in your class. In your case, the default destructor will not release the memory acquired during construction.

I won't go into details for the other methods. Up to now what we have from the user point of view:

int main() {
  maze m( 10, 50 ); // Consctruct the maze
  cell c;
  c.setBacktrace( 5 );
  m.setCell( 3, 4, c);  // Store c in the container
  assert( m.getCell( 3, 4 ).getBacktrace() == 5 );
}

We can make this code more user friendly by changing a little the interface. If we provide an operator() that takes two indexes and returns a reference to a cell element the usage will be simpler (C++ FAQ lite on array-of-array interface):

class maze {
    // most everything as before, changing set/get to:
public:
   cell const & operator()( size_t row, size_t col ) const;
   cell & operator()( size_t row, size_t col ); 
};

Then the usage would be simpler:

int main()
{
   maze m( 10, 10 );
   m( 3, 4 ).setBacktrace( 5 );
   assert( m( 3, 4 ).getBacktrace() == 5 );
}

There is no need to construct a cell object and applying changes to it and then storing the object, we can modify the stored object directly. Now the implementation:

cell const & maze::operator()( size_t row, size_t col ) const
{
   return *data_[ row + col*width_ ];
}
cell & maze::operator()( size_t row, size_t col )
{
   return *data_[ row + col*width_ ];
}

Both of the implementations are similar with the only difference that the first one is telling the compiler that it will not change the contents of the maze and it returns a constant reference to guarantee that the caller does not change the cell.

After working on the maze class, you can notice that the only thing that makes it a maze is that the stored data is a cell, but all the logic is just that of a plain 2D array. We can take advantage of it and redefine it a as a template class so that we can reuse the code in different situations, with different definitions of the stored type:

template <typename T> // stored data
class array_2d
{
public:
   array_2d( size_t width, size_t height );
   ~array_2d();
   T const & operator()( size_t row, size_t col ) const;
   T & operator()( size_t row, size_t col );
private:
   size_t width_;
   size_t height_;
   T* data_;
};

And the usage will be:

int main()
{
   array_2d<cell> maze( 10, 10 );
   maze( 3, 4 ).setBacktrace( 5 );
}

Defining the implementation will be a little different but not that much more complex:

template <typename T>
array_2d<T>::array_2d( size_t width, size_t height )
   : width_( width ), height_( height ), data_( new T[ width*height ] )
{
}

And similarly when defining the implementation of each method. Not that hard, is it?

Finally, we can go back to the definition of cell and make it more natural to work with. What we have are a set of accessor methods that will perform bitwise operations to interact with each of the four internal fields (backtrack, solution, borders, walls). The cell is just about a POD (plain old data) structure that stores four integer fields, similar to:

struct big_cell
{
   unsigned int backtrack;
   unsigned int solution;
   unsigned int borders;
   unsigned int walls;
};

That would be used as:

int main()
{
   array_2d<big_cell> maze( 10, 10 );
   maze( 3, 4 ).backtrack = 5;
   assert( maze( 3, 4 ).backtrack == 5 );
}

But that structure will take more space than what we require. The storage implementation detail has forced us to change the usage of the class. Lets try to work on that. Changing the unsigned integers to unsigned chars will reduce the size of the structure to 32 bits (instead of the 16 that the fully optimized structure):

struct medium_cell
{
   unsigned char backtrack;
   unsigned char solution;
   unsigned char borders;
   unsigned char walls;
};

This solution only wastes 2 bytes per cell, which will probably not too much (double the space requirements, but memory is cheap nowadays). Also this can be faster in execution in 32 bit processors. Some 32 bit architectures take longer to retrieve and operate on 16 bit elements.

At any rate, if you are still interested in the fully compact memory model, you can use a not well known feature in C++: bit fields. They allow you to define that some field in your structure just takes a number of bits:

struct small_cell {
   uint16_t backtrack : 4; // take 4 bits from the uint16_t
   uint16_t solution : 4;
   uint16_t borders : 4;
   uint16_t walls : 4;
};

And ussage will be:

int main() 
{
   small_cell c;
   c.solution = 5; 
   c.backtrack = 3;
}

Now this structure takes just 16 bits of memory and can be used just as the previous two structures. As the maze is now just a templated 2d array, you can test the three structures quite easily. You can define a template function for the test.

#include <time.h>

// templated for comparissons with cell types
template <typename CellStruct>
void test()
{
   array_2d< CellStruct > maze;
   // Test operations...
}

void print_test( std::string const & test, clock_t ticks )
{
   std::cout << "Test: " << test << " took " << ticks 
      << " ticks, or " << ticks / CLOCKS_PER_SEC << " seconds." 
      << std::endl;
}

int main()
{
   clock_t init = clock();
   test< big_cell >();
   clock_t after_big = clock();
   test< medium_cell >();
   clock_t after_med = clock();
   test< small_cell >();
   clock_t end = clock();

   print_result( "big_cell", after_big - init );
   print_result( "medium_cell", after_med - after_big );
   print_result( "small_cell", end - after_med );
}

The test function is templated only so that it can be executed with different cell implementations. Once you know what implementation best suits your problem domain, you can make specific code that will use the specific cell type.

Answer 7

Write a small macro to convert 2d coordinates to improve readability. Something like. this:

#define TWO_DIM(x,y,w) (x+y*w)

Use STL containers:

// Define and get memory
std::vector <int16_t> mazedata;
mazedata.resize(newsize);
// Assign values
mazedata[TWO_DIM(row,col,width)]=newvalue;

Remember that STL implements memory efficient std::vector<bool> which can be used like normal array yet take 1 bit per bit of data. In case of large arrays you will not notice the overhead of STL.

Answer 8

Not addressing your main space issues, but here's a simple version that doesn't involve you with explicit dynamic memory management:

#include <vector>
#include <iostream>
using namespace std;

class Maze {
    public:

        Maze(int mazeWidth, int mazeHeight) {
           for ( int i = 0; i < mazeHeight; i++ ) {
              mMaze.push_back( vector <int>( mazeWidth ) );
           }
        }

        int At(int row, int col) const {
           return mMaze.at(row).at(col); 
        }

        int & At(int row, int col) {
           return mMaze.at(row).at(col); 
        }

    private:

        vector < vector <int> > mMaze;
};


int main() {
    Maze m( 5, 5 );
    m.At( 2, 2 ) = 42;
    cout << m.At( 2, 2 ) << "\n";
}

Answer 9

One thing not mentioned in the previous answers is that when your class contain a pointer to allocated memory you should either provide copy constructor and assignment operator or simply forbid them to avoid use of the default implementations for these that C++ is providing.