How to create a dynamic matrix of custom data type?

[Ethin Probst]

I am in the process of writing a maze generator for a game I'm creating. I would like to use a matrix to store each cell object (each maze is made up of "cell" objects with an x and y coordinate). As I want the maze generated as fast as possible, I chose blaze for my matrix system, but when I compile it, I get the following error (MSVC 2017):

blaze\blaze/math/typetraits/UnderlyingNumeric.h(93): error C2039: 'ElementType': is not a member of 'Map::Cell'
src\cell.h(10): note: see declaration of 'Map::Cell'
blaze\blaze/math/typetraits/UnderlyingNumeric.h(102): note: see reference to class template instantiation 'blaze::UnderlyingNumeric<Map::Cell>::Other<T>' being compiled
        with
        [
            T=Map::Cell
        ]

I would define an ElementType structure, but the Cell cannot be solely represented by a built-in C++ type (hence the class), and I can find nothing about this particular error and this is confusing me. I'm obviously missing something... so, what do I need to define in my classes to store them in matrices?

[Klaus Iglberger]

Hi Ethin!

Thanks for creating this issue. You are allowed to use custom data types for DynamicMatrix, but depending on which operations you use these data types are expected to provide certain operations. E.g. it is expected that it is possible to compare your data type via operator==() and operator!=():

struct Cell {};

bool operator!=( Cell, Cell ) { return true; }
bool operator!=( Cell, Cell ) { return false; }

blaze::DynamicMatrix<Cell> A( 10UL, 10UL );  // Compiles flawlessly

Could you please provide a minimum example to enable us to analyze the problem?

Best regards,

Klaus!

[Ethin Probst]

I'm not sure wha you mean by a 'minimum example'. I'll try, anyway... My cell class defines operator== and operator!=:

// todo: figure out (somehow) whether this class violates DCL52-CPP (Never qualify a reference type with const or volatile) (section 2.3) of the SEI CERT C++ Coding Standard, 2016 ed.
inline bool operator==(const Cell &rhs) const {
return (GetX() == rhs.GetX()&&GetY() == rhs.GetY());
}

inline bool operator!=(const Cell &rhs) const {
return !(GetX() == rhs.GetX()&&GetY() == rhs.GetY());
}

My maze class defines the following private members:

unsigned long long maxSizeX = 10;
unsigned long long maxSizeY = 10;
unsigned long long maxMapSizeX = 0;
unsigned long long maxMapSizeY = 0;
unsigned long long minRooms = 3;
unsigned long long maxRooms = 6;
unsigned long long minRoomWidth = 2;
unsigned long long maxRoomWidth = 3;
unsigned long long roomPenalty = 100;
unsigned long long hallPenalty = 3;
unsigned long long straightness = 30;
std::shared_ptr<WalkMap> walkMap;
blaze::DynamicMatrix<short> explored; // I tried declaring this using bool instead (since explored is either true or false) and it wined about it.
blaze::DynamicMatrix<Cell> grid;
blaze::DynamicMatrix<Cell> inflatedGrid;
std::vector<Cell> unvisitedCells;
std::vector<Cell> visitedCells;
unsigned long long floor = 0;
std::vector<Room> rooms = std::vector<Room>();
unsigned long long sparseness = 7;
bool loopDeadEnds = false;

Do you need any more than that?

[Klaus Iglberger]

Hi Ethin!

We would appreciate a short piece of code that we can directly compile to reproduce your compilation problem. Else we can only guess what you are trying to do. Thanks!

blaze::DynamicMatrix<short> explored; // I tried declaring this using bool instead (since explored is either true or false) and it wined about it.

blaze::DynamicMatrix is not designed as a general purpose container, but as a linear algebra matrix type. Thus it expects types that can be used for numeric operations. bool is not a suitable data type for any numerical operation (addition, subtraction, multiplication, ...).

Best regards,

Klaus!

[Ethin Probst]

I can't really provide you with a suitable code example to reproduce the problem. The system won't let me attach files, and I'd practically need to upload the entire program (its all linked together). I can try and split it and only upload cell.h and the files that uses it, though even that will be hard.

[Klaus Iglberger]

I would help to know which operations you try to use. The code you posted compiles flawlessly (even the line with blaze::DynamicMatrix<bool>) since no operation (e.g. addition, multiplication, reduction, ...) is used. The problem must be somehow connected to the way you try to use the matrices. Without this information we unfortunately cannot help.

[Ethin Probst]

Its very hard to figure out the actual problem since it seems as though the library uses recursive template programming, which is throwing my compiler for a loop, quite literally. If I alter the short to a bool, I get this error:

blaze\blaze/math/views/submatrix/Dense.h(888): error C4146: unary minus operator applied to unsigned type, result still unsigned

If I remember right, this (should be) a warning, not an error. So a bit confused with that. It goes on to say:

blaze\blaze/math/views/Submatrix.h(818): note: see reference to function template instantiation 'blaze::Submatrix<MT,blaze::unaligned,false,true>::Submatrix<size_t,size_t,size_t,size_t>(MT &,size_t,size_t,size_t,size_t)' being compiled
        with
        [
            MT=blaze::DynamicMatrix<bool,false>
        ]

That's the only error that I get with the bool version of the explored matrix. I don't use that matrix; here's how I use the grid and inflatedGrid matrices:

void Dungeon::setupSizes() {
maxMapSizeX = maxSizeX * 2;
maxMapSizeY = maxSizeY*2;
walkMap = std::make_shared<WalkMap>(maxSizeX * 2 + 1, maxSizeY * 2 + 1);
explored = blaze::DynamicMatrix<bool>(maxSizeX * 2, maxSizeY * 2);
grid = blaze::DynamicMatrix<Cell>(maxSizeX+1, maxSizeY+1);
inflatedGrid = blaze::DynamicMatrix<Cell>(maxSizeX * 2+1, maxSizeY * 2+1);
for (unsigned long long i = 0; i <= maxSizeX; ++i) {
for (unsigned long long j = 0; j <= maxSizeY; ++j) {
grid(i, j) = Cell(i, j);
unvisitedCells.push_back(Cell(i, j));
}
}
for (unsigned long long k = 0; k <= maxSizeX * 2; ++k) {
for (unsigned long long l = 0; l <= maxSizeY * 2; ++l) {
inflatedGrid(k, l) = Cell(k, l);
}
}
}

I did the <= condition in the above loops because I kept getting bad indexes (my algorithm was going out of range) when I was using boost.uBLAS, which was odd since the matrix was supposedly big enough. So that's to ensure that the matrix is always large enough to hold the grid of cells. I'd post the full algorithm but its over 800 lines, so...

Edit: OK, so I removed the matrix temporarily since its not used. I still get this error though:

blaze\blaze/math/views/submatrix/Dense.h(888): error C4146: unary minus operator applied to unsigned type, result still unsigned
blaze\blaze/math/views/Submatrix.h(818): note: see reference to function template instantiation 'blaze::Submatrix<MT,blaze::unaligned,false,true>::Submatrix<size_t,size_t,size_t,size_t>(MT &,size_t,size_t,size_t,size_t)' being compiled
        with
        [
            MT=blaze::DynamicMatrix<Map::Cell,false>
        ]
blaze\blaze/math/views/Submatrix.h(822): note: see reference to function template instantiation 'blaze::Submatrix<MT,blaze::unaligned,false,true>::Submatrix<size_t,size_t,size_t,size_t>(MT &,size_t,size_t,size_t,size_t)' being compiled
        with
        [
            MT=blaze::DynamicMatrix<Map::Cell,false>
        ]
blaze\blaze/math/smp/openmp/DenseMatrix.h(149): note: see reference to function template instantiation 'ReturnType blaze::submatrix<blaze::unaligned,MT,false,>(const blaze::Matrix<MT,false> &,size_t,size_t,size_t,size_t)' being compiled
        with
        [
            MT=blaze::DynamicMatrix<Map::Cell,false>
        ]

Do I need to apply the +, -, *, and / operators to my Cell class?

[Иннокентий Алайцев]

Hello!

Excuse me for interfering, but it seems to me that you are trying to use a wrong instrument for your problem at hand. Neither Blaze nor Boost.uBLAS provide general-purpose functionality and containers (fix me if I'm wrong). Looks like you just need a multi-dimensional array which is Boost.MultyArray. If you want better performance then try using some kind of parallel execution. The simplest is OpenMP, which is supported by most mainstream compilers (even MSVC has support for an outdated OpenMP 2.0). If you want to take advantage of vectorisation and other optimisations, provided by Blaze or any other linear algebra library, then you should change the way your data and algorithms are organised. It may worth to use the Struct of Arrays approach and to formalise your algorithms in the form of some kind of matrix equations.

Once again, sorry for the noise.

Best regards, Innokentiy Alaytsev.

[Ethin Probst]

It may be the wrong instrument of usage, I agree. However, I am representing each cell within the matrix as (x, y). It just feels wrong to use it as [x][y]. Ug. That could easily become a huge nightmare. Or even worse. if I use bounds checking, .at(x).at(y). Gross! :)

I can see another approach -- I make a custom class explicitly designed to hold these cells. Perhaps something like CellVector, something that makes attaining the ? cells intuitive so I can access them as (x, y) instead of [x][y] (std::vector<std::vector<>>/boost.multi_array). As I said, I'd like the cleanest interface to cells accessed via coordinates, which is why I chose a matrix.

[Klaus Iglberger]

Hi Ethin!

I agree with Innokentiy that DynamicMatrix might not be the correct tool for your purposes. However, of course we are still interested in resolving as many obstacles as possible for using custom data types. In commit a67701f we have implemented a probably long overdue modernisation of the UnderlyingNumeric type trait, which hopefully resolves the compilation issues you have. The major change is that it longer requires a nested ElementType type member for non-fundamental types. Could you please use the current master and report back if this resolves your problem? Thanks,

Best regards,

Klaus!

[Klaus Iglberger]

Commit a67701f resolves the compilation issue for custom data types without nested ElementType type. The fix is immediately available via cloning the Blaze repository and will be officially released in Blaze 3.6.