• Create Account

## More on Vectors and Matrices

Posted by , in Programming 27 August 2011 - · 614 views

My original plan for this second entry was to also add a matrix class that interacts with the vector class from my last journal entry. In the meanwhile Splinter of Chaos gave us a reason why we should use vectors in his journal and in the comments to said journal entry JTippetts brought up the problem that lots of libraries etc. use their own vector type. The "heterogeneity" of the C++ library landscape sadly isn't something we can change now, but when designing our own Vector type, we can at least take it into account.

## Integration of other (array style) Vector data

So going back to my earlier implementation of a Vector class I'd like to add a way to interact with other implementations and "raw vectors" (also known as array). Luckily everything is already based around expression templates which are easily extendable. What I want is a way to interpret raw data as a Vector compatible with my implementation. All I have to do for that is copy & paste my whole Vector class, change its name to "InPlaceVector", replace "T data[D];" with "T *const data;" and provide a constructor that takes a pointer. Then I add the following function for convenience
[source lang="cpp"]template<unsigned D, class T>InPlaceVector<T,D> MakeVector(T *const p){ return InPlaceVector<T,D>(p);}[/source]
and can apply the full functionality of my Vector class to any kind of other vector class or representation that stores its data in an array.
Example:
[source lang="cpp"]double raw_vector[3];Vector<double, 3> a(1,2,3);MakeVector<3>(raw_vector) += a;[/source]
And since the InPlaceVector object only contains a const pointer, it will once again very likely be optimized away and we don't even incur any conversion overhead.

So with that problem out of the way (sort of). We can move on to matrices.

## The Matrix

So if we are already in need of vectors chance are we also want matrices. A simple Matrix class can be obtained by just copy pasting my Vector class, replace the "operator[](unsigned)" with "operator()(unsigned, unsigned)" etc. When implementing matrices one also has to decide between row and column major order for storage. I went with column major since that makes the matrices directly usable with OpenGL. An argument for row major order would be that the native c++ matrices (double mat[3][3]) are row major and are therefore more natural in C++.
Besides the element wise operations we "inherited" from the vector class we also need matrix-vector multiplication and matrix-matrix multiplication. These could be implemented directly, but to make it more elegant we will first introduce a way to access the rows and columns like they were vector expressions. I guess this can be considered a form of the decorator pattern:
[source lang="cpp"]template<class T, unsigned D1, unsigned D2, class A>class RowVectorExpr : public VectorExpr<T, D2, RowVectorExpr<T, D1, D2, A> > {public: RowVectorExpr(const A& pa, const unsigned& i) : a(pa), index(i) { } inline T operator[](unsigned i) const { return a(index, i); }private: const A& a; const unsigned index;};template<class T, unsigned D1, unsigned D2, class A>inline RowVectorExpr<T,D1,D2,A>Row(const MatrixExpr<T,D1,D2,A> &a, const unsigned &index){ return RowVectorExpr<T,D1,D2,A>(a, index);}//similarly for columns[/source]
There are other interesting "operations" that can and should also be implemented like this like submatrix access and transposition.

Now with easy acess to rows and columns we can write the matrix-matrix multiplication as:
[source lang=cpp"]template<class T, unsigned D1, unsigned D2, class A, class B> class MatMatMulExpr : public MatrixExpr<T, D1, D2, MatMatMulExpr<T, D1, D2, A, B> > { public: MatMatMulExpr(const A& pa, const B& pb) : a(pa), b(pb) { } inline T operator()(unsigned i, unsigned j) const { return dot(Row(a,i),Column(b,j)); } private: const A& a; const B& b; }; template<class T, unsigned D1, unsigned D2, unsigned D3, class A, class B> inline MatMatMulExpr<T,D1,D3,A,B> operator*(const MatrixExpr<T,D1,D2,A> &a, const MatrixExpr<T,D2,D3,B> &b){ return MatMatMulExpr<T,D1,D3,A,B>(a, b); }//similarly for matrix-vector and vector-matrix multiplications[/source]

## Expression templates and pitfalls

So this is the point where after all the praise for expression templates I have to address a problem with them. Expression templates offer a form of lazy evaluation. This means that operations are not carried out immediately. Instead they are carried out when the result is actually needed. This has advantages when not the whole calculation is actually required. Using the tools we just introduced consider for example this:
[source lang="cpp"]Matrix<double,4,4> A, B;//fill A and B with some valuesVector<double,4> v = Row(A*B,2); //save the third row of A*B in v[/source]
In the assignment to v only the matrix elements that lie in the requested Row are actually calculated!
The downside of this is that the elements will be calculated multiple times if they are requested multiple times. This can happen when more than two matrices are multiplied in a single expression. In that case the temporary objects we avoided with the expression templates might actually be beneficial from a performance perspective. Even worse, operations where the left operand of an assignment is also part of the expression will even produce wrong results.
[source lang="cpp"]Matrix<double,4,4> A;A = A*Transpose(A); //gives wrong result![/source]
For pure Vector operations this usually isn't a problem given that the dependencies are only component wise, but for matrix and matrix-vector multiplications this has to be taken into account.
An easy way to solve both of these problems is to use an explicit evaluation function:
[source lang="cpp"]template<class T, unsigned D, class A>inline Vector<T, D> eval(const VectorExpr<T, D, A>& a){ return Vector<T, D>(a);}template<class T, unsigned D1, unsigned D2, class A>inline Matrix<T, D1, D2> eval(const MatrixExpr<T, D1, D2, A>& a){ return Matrix<T, D1, D2>(a);}[/source]
This allows us to force the execution of an expression and get a temporary from it.
[source lang="cpp"] Matrix<double,4,4> A,B,C,D;A = eval(A*Transpose(A)); //correct!A = eval(B*C)*D//less operations in exchange for a temporary object! [/source]
It would also be possible to have the expression templates detect these situations by passing "source" references through the expression tree and some template specialization magic. At the moment I'll stick with the "eval" solution.

Here is the extended Vector header and the Matrix header I'm using right now:
Vector.h

[source lang="cpp"]/* * MathVector.h - Copyright © 2011 Jakob Progsch * * This software is provided 'as-is', without any express or implied * warranty. In no event will the authors be held liable for any damages * arising from the use of this software. * * Permission is granted to anyone to use this software for any purpose, * including commercial applications, and to alter it and redistribute it * freely, subject to the following restrictions: * * 1. The origin of this software must not be misrepresented; you must not * claim that you wrote the original software. If you use this software * in a product, an acknowledgment in the product documentation would be * appreciated but is not required. * * 2. Altered source versions must be plainly marked as such, and must not be * misrepresented as being the original software. * * 3. This notice may not be removed or altered from any source * distribution. *//* * Vector.h provides a simple static vector template class with * a basic expression template ansatz for vector operations. */ #ifndef VECTOR_H#define VECTOR_H#include <cmath>#include <algorithm>#include <ostream>template<class T, unsigned D> class Vector;//base class for all expression templatestemplate<class T, unsigned D, class A>class VectorExpr {public: inline operator const A&() const { return *static_cast<const A*>(this); }};//better use macros instead of copy pasting this stuff all over the place#define MAKE_VEC_VEC_EXPRESSION(NAME, EXPR, FUNCTION) \template<class T, unsigned D, class A, class B> \class NAME : public VectorExpr<T, D, NAME<T, D, A, B> > { \public: \ NAME(const A& pa, const B& pb) : a(pa), b(pb) { } \ inline T operator[](unsigned i) const { return EXPR; } \private: \ const A& a; \ const B& b; \}; \ \template<class T, unsigned D, class A, class B> \inline NAME<T,D,A,B> \FUNCTION(const VectorExpr<T,D,A> &a, const VectorExpr<T,D,B> &b) \{ \ return NAME<T,D,A,B>(a, b); \} #define MAKE_VEC_SCAL_EXPRESSION(NAME, EXPR, FUNCTION) \template<class T, unsigned D, class A> \class NAME : public VectorExpr<T, D, NAME<T, D, A> > { \public: \ NAME(const A& pa, const T& pb) : a(pa), b(pb) { } \ inline T operator[](unsigned i) const { return EXPR; } \private: \ const A& a; \ const T& b; \}; \ \template<class T, unsigned D, class A> \inline NAME<T,D,A> \FUNCTION(const VectorExpr<T,D,A> &a, const T &b) \{ \ return NAME<T,D,A>(a, b); \} #define MAKE_SCAL_VEC_EXPRESSION(NAME, EXPR, FUNCTION) \template<class T, unsigned D, class A> \class NAME : public VectorExpr<T, D, NAME<T, D, A> > { \public: \ NAME(const T& pa, const A& pb) : a(pa), b(pb) { } \ inline T operator[](unsigned i) const { return EXPR; } \private: \ const T& a; \ const A& b; \}; \ \template<class T, unsigned D, class A> \inline NAME<T,D,A> \FUNCTION(const T &a, const VectorExpr<T,D,A> &b) \{ \ return NAME<T,D,A>(a, b); \} #define MAKE_VEC_EXPRESSION(NAME, EXPR, FUNCTION) \template<class T, unsigned D, class A> \class NAME : public VectorExpr<T, D, NAME<T, D, A> > { \public: \ NAME(const A& pa) : a(pa) { } \ inline T operator[](unsigned i) const { return EXPR; } \private: \ const A& a; \}; \ \template<class T, unsigned D, class A> \inline NAME<T,D,A> \FUNCTION(const VectorExpr<T,D,A> &a) \{ \ return NAME<T,D,A>(a); \}//create actual functions and operatorsMAKE_VEC_VEC_EXPRESSION (EMulExpr, a[i] * b[i], multiply_elements)MAKE_VEC_VEC_EXPRESSION (EDivExpr, a[i] / b[i], divide_elements)MAKE_VEC_VEC_EXPRESSION (AddExpr, a[i] + b[i], operator+)MAKE_VEC_VEC_EXPRESSION (SubExpr, a[i] - b[i], operator-)MAKE_VEC_SCAL_EXPRESSION(DivExpr, a[i] / b, operator/)MAKE_VEC_SCAL_EXPRESSION(MulExpr1, a[i] * b, operator*)MAKE_SCAL_VEC_EXPRESSION(MulExpr2, a * b[i], operator*)MAKE_VEC_EXPRESSION (NegExpr, -a[i], operator-)//sub vector proxytemplate<class T, unsigned D, class A> class SubVectorExpr : public VectorExpr<T, D, SubVectorExpr<T, D, A> > { public: SubVectorExpr(const A& pa, const unsigned& o) : a(pa), offset(o) { } inline T operator[](unsigned i) const { return a[i+offset]; } private: const A& a; const unsigned offset; }; template<unsigned D1, class T, unsigned D2, class A> inline SubVectorExpr<T,D1,A> SubVector(const VectorExpr<T,D2,A> &a, const unsigned &o) { return SubVectorExpr<T,D1,A>(a, o); }//static size assertion since the vector size ist also statictemplate<unsigned I, unsigned J>struct STATIC_DIMENSION_MISMATCH_ASSERTION;template<unsigned I>struct STATIC_DIMENSION_MISMATCH_ASSERTION<I,I> { };#define ASSERT_DIMENSION(I, J) sizeof(STATIC_DIMENSION_MISMATCH_ASSERTION<I,J>)//actual vector classtemplate<class T, unsigned D>class Vector : public VectorExpr<T, D, Vector<T,D> > {public: static const unsigned Dim = D; typedef T Type; Vector() { std::fill(data, data+Dim, T()); } Vector(const T &p1) { ASSERT_DIMENSION(1, Dim); data[0] = p1; } Vector(const T &p1, const T &p2) { ASSERT_DIMENSION(2, Dim); data[0] = p1; data[1] = p2; } Vector(const T &p1, const T &p2, const T &p3) { ASSERT_DIMENSION(3, Dim); data[0] = p1; data[1] = p2; data[2] = p3; } Vector(const T &p1, const T &p2, const T &p3, const T &p4) { ASSERT_DIMENSION(4, Dim); data[0] = p1; data[1] = p2; data[2] = p3; data[3] = p4; } T* raw() { return data; } template<class A> Vector(const VectorExpr<T, D, A>& a) { const A& ao ( a ); for(unsigned i = 0;i<Dim;++i) data[i] = ao[i]; } T& operator[] (unsigned i) { return data[i]; } const T& operator[] (unsigned i) const { return data[i]; } const Vector& operator*=(const T &b) { for(unsigned i = 0;i<Dim;++i) data[i] *= b; return *this; } const Vector& operator/=(const T &b) { for(unsigned i = 0;i<Dim;++i) data[i] /= b; return *this; } template<class A> const Vector& operator+=(const VectorExpr<T, D, A>& a) { const A& ao ( a ); for(unsigned i = 0;i<Dim;++i) data[i] += ao[i]; return *this; } template<class A> const Vector& operator-=(const VectorExpr<T, D, A>& a) { const A& ao ( a ); for(unsigned i = 0;i<Dim;++i) data[i] -= ao[i]; return *this; } template<class A> Vector& operator=(const VectorExpr<T, D, A>& a) { const A& ao ( a ); for(unsigned i = 0;i<Dim;++i) data[i] = ao[i]; return *this; } Vector& normalize() { *this /= abs(*this); return *this; }private: T data[Dim];};//InPlaceVector to use raw datatemplate<class T, unsigned D>class InPlaceVector : public VectorExpr<T, D, InPlaceVector<T,D> > {public: static const unsigned Dim = D; typedef T Type; InPlaceVector(T *const d) : data(d) { } template<class A> InPlaceVector(const VectorExpr<T, D, A>& a) { const A& ao ( a ); for(unsigned i = 0;i<Dim;++i) data[i] = ao[i]; } T* raw() { return data; } T& operator[] (unsigned i) { return data[i]; } const T& operator[] (unsigned i) const { return data[i]; } const InPlaceVector& operator*=(const T &b) { for(unsigned i = 0;i<Dim;++i) data[i] *= b; return *this; } const InPlaceVector& operator/=(const T &b) { for(unsigned i = 0;i<Dim;++i) data[i] /= b; return *this; } template<class A> const InPlaceVector& operator+=(const VectorExpr<T, D, A>& a) { const A& ao ( a ); for(unsigned i = 0;i<Dim;++i) data[i] += ao[i]; return *this; } template<class A> const InPlaceVector& operator-=(const VectorExpr<T, D, A>& a) { const A& ao ( a ); for(unsigned i = 0;i<Dim;++i) data[i] -= ao[i]; return *this; } template<class A> InPlaceVector& operator=(const VectorExpr<T, D, A>& a) { const A& ao ( a ); for(unsigned i = 0;i<Dim;++i) data[i] = ao[i]; return *this; } InPlaceVector& normalize() { *this /= abs(*this); return *this; }private: T *const data;};template<unsigned D, class T>InPlaceVector<T,D> MakeVector(T *const p){ return InPlaceVector<T,D>(p);}template<class T, unsigned D, class A>inline Vector<T, D> eval(const VectorExpr<T, D, A>& a){ return Vector<T, D>(a);}//"reduction" functions that don't return expression templatestemplate<class T, unsigned D, class A>inline T sum(const VectorExpr<T, D, A>& a){ const A& ao ( a ); T res = 0; for(unsigned i = 0;i<D;++i) res += ao[i]; return res;}template<class T, unsigned D, class A, class B>inline T dot(const VectorExpr<T, D, A>& a, const VectorExpr<T, D, B>& b){ return sum(multiply_elements(a, b));}template<class T, unsigned D, class A>inline T squared_norm(const VectorExpr<T, D, A>& a){ const A& ao ( a ); T res = 0; for(unsigned i = 0;i<D;++i) { T tmp = ao[i]; res += tmp*tmp; } return res;}template<class T, unsigned D, class A>inline T abs(const VectorExpr<T, D, A>& a){ return std::sqrt(squared_norm(a));}template<class T, unsigned D, class A>std::ostream& operator<<(std::ostream& out, const VectorExpr<T, D, A>& a){ const A& ao ( a ); out << '(' << ao[0]; for(unsigned i = 1;i<D;++i) { out << ", " << ao[i]; } out << ')'; return out;}#undef MAKE_VEC_VEC_EXPRESSION#undef MAKE_VEC_SCAL_EXPRESSION#undef MAKE_SCAL_VEC_EXPRESSION#undef MAKE_VEC_EXPRESSION#endif[/source]

Matrix.h
[source lang="cpp"]/* * MathMatrix.h - Copyright © 2011 Jakob Progsch * * This software is provided 'as-is', without any express or implied * warranty. In no event will the authors be held liable for any damages * arising from the use of this software. * * Permission is granted to anyone to use this software for any purpose, * including commercial applications, and to alter it and redistribute it * freely, subject to the following restrictions: * * 1. The origin of this software must not be misrepresented; you must not * claim that you wrote the original software. If you use this software * in a product, an acknowledgment in the product documentation would be * appreciated but is not required. * * 2. Altered source versions must be plainly marked as such, and must not be * misrepresented as being the original software. * * 3. This notice may not be removed or altered from any source * distribution. *//* * Matrix.h provides a simple static Matrix template class with * a basic expression template ansatz for Matrix operations. */ #ifndef Matrix_H#define Matrix_H#include "Vector.h"template<class T, unsigned D1, unsigned D2> class Matrix;//base class for all expression templatestemplate<class T, unsigned D1, unsigned D2, class A>class MatrixExpr {public: inline operator const A&() const { return *static_cast<const A*>(this); }};//better use macros instead of copy pasting this stuff all over the place#define MAKE_MAT_MAT_EXPRESSION(NAME, EXPR, FUNCTION) \template<class T, unsigned D1, unsigned D2, class A, class B> \class NAME : public MatrixExpr<T, D1, D2, NAME<T, D1, D2, A, B> > { \public: \ NAME(const A& pa, const B& pb) : a(pa), b(pb) { } \ inline T operator()(unsigned i, unsigned j) const { return EXPR; } \private: \ const A& a; \ const B& b; \}; \ \template<class T, unsigned D1, unsigned D2, class A, class B> \inline NAME<T,D1,D2,A,B> \FUNCTION(const MatrixExpr<T,D1,D2,A> &a, const MatrixExpr<T,D1,D2,B> &b)\{ \ return NAME<T,D1,D2,A,B>(a, b); \} #define MAKE_MAT_SCAL_EXPRESSION(NAME, EXPR, FUNCTION) \template<class T, unsigned D1, unsigned D2, class A> \class NAME : public MatrixExpr<T, D1, D2, NAME<T, D1, D2, A> > { \public: \ NAME(const A& pa, const T& pb) : a(pa), b(pb) { } \ inline T operator()(unsigned i, unsigned j) const { return EXPR; } \private: \ const A& a; \ const T& b; \}; \ \template<class T, unsigned D1, unsigned D2, class A> \inline NAME<T,D1,D2,A> \FUNCTION(const MatrixExpr<T,D1,D2,A> &a, const T &b) \{ \ return NAME<T,D1,D2,A>(a, b); \} #define MAKE_SCAL_MAT_EXPRESSION(NAME, EXPR, FUNCTION) \template<class T, unsigned D1, unsigned D2, class A> \class NAME : public MatrixExpr<T, D1, D2, NAME<T, D1, D2, A> > { \public: \ NAME(const T& pa, const A& pb) : a(pa), b(pb) { } \ inline T operator()(unsigned i, unsigned j) const { return EXPR; } \private: \ const T& a; \ const A& b; \}; \ \template<class T, unsigned D1, unsigned D2, class A> \inline NAME<T,D1,D2,A> \FUNCTION(const T &a, const MatrixExpr<T,D1,D2,A> &b) \{ \ return NAME<T,D1,D2,A>(a, b); \} #define MAKE_MAT_EXPRESSION(NAME, EXPR, FUNCTION) \template<class T, unsigned D1, unsigned D2, class A> \class NAME : public MatrixExpr<T, D1, D2, NAME<T, D1, D2, A> > { \public: \ NAME(const A& pa) : a(pa) { } \ inline T operator()(unsigned i, unsigned j) const { return EXPR; } \private: \ const A& a; \}; \ \template<class T, unsigned D1, unsigned D2, class A> \inline NAME<T,D1,D2,A> \FUNCTION(const MatrixExpr<T,D1,D2,A> &a) \{ \ return NAME<T,D1,D2,A>(a); \}//create actual functions and operatorsMAKE_MAT_MAT_EXPRESSION (MATEMulExpr, a(i,j) * b(i,j), multiply_elements)MAKE_MAT_MAT_EXPRESSION (MATEDivExpr, a(i,j) / b(i,j), divide_elements)MAKE_MAT_MAT_EXPRESSION (MATAddExpr, a(i,j) + b(i,j), operator+)MAKE_MAT_MAT_EXPRESSION (MATSubExpr, a(i,j) - b(i,j), operator-)MAKE_MAT_SCAL_EXPRESSION(MATDivExpr, a(i,j) / b, operator/)MAKE_MAT_SCAL_EXPRESSION(MATMulExpr1, a(i,j) * b, operator*)MAKE_SCAL_MAT_EXPRESSION(MATMulExpr2, a * b(i,j), operator*)MAKE_MAT_EXPRESSION (MATNegExpr, -a(i,j), operator-)//transpositiontemplate<class T, unsigned D1, unsigned D2, class A> class TransExpr : public MatrixExpr<T, D1, D2, TransExpr<T, D1, D2, A> > { public: TransExpr(const A& pa) : a(pa) { } inline T operator()(unsigned i, unsigned j) const { return a(j,i); } private: const A& a; }; template<class T, unsigned D1, unsigned D2, class A> inline TransExpr<T,D2,D1,A> Transpose(const MatrixExpr<T,D1,D2,A> &a) { return TransExpr<T,D2,D1,A>(a); }//Row, Column vector and submatrix proxiestemplate<class T, unsigned D1, unsigned D2, class A> class RowVectorExpr : public VectorExpr<T, D2, RowVectorExpr<T, D1, D2, A> > { public: RowVectorExpr(const A& pa, const unsigned& i) : a(pa), index(i) { } inline T operator[](unsigned i) const { return a(index, i); } private: const A& a; const unsigned index; }; template<class T, unsigned D1, unsigned D2, class A> inline RowVectorExpr<T,D1,D2,A> Row(const MatrixExpr<T,D1,D2,A> &a, const unsigned &index) { return RowVectorExpr<T,D1,D2,A>(a, index); } template<class T, unsigned D1, unsigned D2, class A> class ColumnVectorExpr : public VectorExpr<T, D1, ColumnVectorExpr<T, D1, D2, A> > { public: ColumnVectorExpr(const A& pa, const unsigned& i) : a(pa), index(i) { } inline T operator[](unsigned i) const { return a(i, index); } private: const A& a; const unsigned index; }; template<class T, unsigned D1, unsigned D2, class A> inline ColumnVectorExpr<T,D1,D2,A> Column(const MatrixExpr<T,D1,D2,A> &a, const unsigned &index) { return ColumnVectorExpr<T,D1,D2,A>(a, index); }template<class T, unsigned D1, unsigned D2, class A> class SubMatrixExpr : public MatrixExpr<T, D1, D2, SubMatrixExpr<T, D1, D2, A> > { public: SubMatrixExpr(const A& pa, const unsigned& i, const unsigned& j) : a(pa), offseti(i), offsetj(j) { } inline T operator()(unsigned i, unsigned j) const { return a(i+offseti, j+offsetj); } private: const A& a; const unsigned offseti, offsetj; }; template<unsigned D3, unsigned D4, class T, unsigned D1, unsigned D2, class A> inline SubMatrixExpr<T,D3,D4,A> SubMatrix(const MatrixExpr<T,D1,D2,A> &a, const unsigned &i, const unsigned &j) { return SubMatrixExpr<T,D3,D4,A>(a, i, j); }//matrix-vector and vector-matrix multiplicationstemplate<class T, unsigned D1, unsigned D2, class A, class B> class MatVecMulExpr : public VectorExpr<T, D1, MatVecMulExpr<T, D1, D2, A, B> > { public: MatVecMulExpr(const A& pa, const B& pb) : a(pa), b(pb) { } inline T operator[](unsigned i) const { return dot(Row(a, i), b); } private: const A& a; const B& b; }; template<class T, unsigned D1, unsigned D2, class A, class B> inline MatVecMulExpr<T,D1,D2,A,B> operator*(const MatrixExpr<T,D1,D2,A> &a, const VectorExpr<T,D2,B> &b) { return MatVecMulExpr<T,D1,D2,A,B>(a, b); }template<class T, unsigned D1, unsigned D2, class A, class B> class VecMatMulExpr : public VectorExpr<T, D2, VecMatMulExpr<T, D1, D2, A, B> > { public: VecMatMulExpr(const A& pa, const B& pb) : a(pa), b(pb) { } inline T operator[](unsigned i) const { return dot(Column(a, i), b); } private: const A& a; const B& b; }; template<class T, unsigned D1, unsigned D2, class A, class B> inline VecMatMulExpr<T,D1,D2,A,B> operator*(const VectorExpr<T,D1,B> &b, const MatrixExpr<T,D1,D2,A> &a) { return VecMatMulExpr<T,D1,D2,A,B>(a, b); }template<class T, unsigned D1, unsigned D2, class A, class B> class MatMatMulExpr : public MatrixExpr<T, D1, D2, MatMatMulExpr<T, D1, D2, A, B> > { public: MatMatMulExpr(const A& pa, const B& pb) : a(pa), b(pb) { } inline T operator()(unsigned i, unsigned j) const { return dot(Row(a,i),Column(b,j)); } private: const A& a; const B& b; }; template<class T, unsigned D1, unsigned D2, unsigned D3, class A, class B> inline MatMatMulExpr<T,D1,D3,A,B> operator*(const MatrixExpr<T,D1,D2,A> &a, const MatrixExpr<T,D2,D3,B> &b){ return MatMatMulExpr<T,D1,D3,A,B>(a, b); }template<class T, unsigned D1, unsigned D2> class Identity : public MatrixExpr<T, D1, D2, Identity<T, D1, D2> > { public: inline T operator()(unsigned i, unsigned j) const { return i==j?1:0; } };//actual Matrix classtemplate<class T, unsigned D1, unsigned D2>class Matrix : public MatrixExpr<T, D1, D2, Matrix<T,D1,D2> > {public: static const unsigned Dim1 = D1; static const unsigned Dim2 = D2; typedef T Type; Matrix() { std::fill(data, data+Dim1*Dim2, T()); } template<class A> Matrix(const MatrixExpr<T, D1, D2, A>& a) { const A& ao ( a ); for(unsigned j = 0;j<Dim2;++j) for(unsigned i = 0;i<Dim1;++i) operator()(i,j) = ao(i,j); } T* raw() { return data; } T& operator() (unsigned i, unsigned j) { return data[i+j*Dim1]; } const T& operator() (unsigned i, unsigned j) const { return data[i+j*Dim1]; } const Matrix& operator*=(const T &b) { for(unsigned i = 0;i<Dim1*Dim2;++i) data[i] *= b; return *this; } const Matrix& operator/=(const T &b) { for(unsigned i = 0;i<Dim1*Dim2;++i) data[i] /= b; return *this; } template<class A> const Matrix& operator+=(const MatrixExpr<T, D1, D2, A>& a) { const A& ao ( a ); for(unsigned j = 0;j<Dim2;++j) for(unsigned i = 0;i<Dim1;++i) operator()(i,j) += ao(i,j); return *this; } template<class A> const Matrix& operator-=(const MatrixExpr<T, D1, D2, A>& a) { const A& ao ( a ); for(unsigned j = 0;j<Dim2;++j) for(unsigned i = 0;i<Dim1;++i) operator()(i,j) -= ao(i,j); return *this; } template<class A> const Matrix& operator*=(const MatrixExpr<T, D1, D2, A>& a) { const A& ao ( a ); *this = eval(*this * a); return *this; } template<class A> Matrix& operator=(const MatrixExpr<T, D1, D2, A>& a) { const A& ao ( a ); for(unsigned j = 0;j<Dim2;++j) for(unsigned i = 0;i<Dim1;++i) operator()(i,j) = ao(i,j); return *this; } private: T data[Dim1*Dim2];};//InPlaceMatrix to use raw data COLUMN MAJOR!template<class T, unsigned D1, unsigned D2>class InPlaceMatrix : public MatrixExpr<T, D1, D2, InPlaceMatrix<T,D1,D2> > {public: static const unsigned Dim1 = D1; static const unsigned Dim2 = D2; typedef T Type; InPlaceMatrix(T *const d) : data(d) { } template<class A> InPlaceMatrix(const MatrixExpr<T, D1, D2, A>& a) { const A& ao ( a ); for(unsigned j = 0;j<Dim2;++j) for(unsigned i = 0;i<Dim1;++i) operator()(i,j) = ao(i,j); } T* raw() { return data; } T& operator() (unsigned i, unsigned j) { return data[i+j*Dim1]; } const T& operator() (unsigned i, unsigned j) const { return data[i+j*Dim1]; } const InPlaceMatrix& operator*=(const T &b) { for(unsigned i = 0;i<Dim1*Dim2;++i) data[i] *= b; return *this; } const InPlaceMatrix& operator/=(const T &b) { for(unsigned i = 0;i<Dim1*Dim2;++i) data[i] /= b; return *this; } template<class A> const InPlaceMatrix& operator+=(const MatrixExpr<T, D1, D2, A>& a) { const A& ao ( a ); for(unsigned j = 0;j<Dim2;++j) for(unsigned i = 0;i<Dim1;++i) operator()(i,j) += ao(i,j); return *this; } template<class A> const InPlaceMatrix& operator-=(const MatrixExpr<T, D1, D2, A>& a) { const A& ao ( a ); for(unsigned j = 0;j<Dim2;++j) for(unsigned i = 0;i<Dim1;++i) operator()(i,j) -= ao(i,j); return *this; } template<class A> const InPlaceMatrix& operator*=(const MatrixExpr<T, D1, D2, A>& a) { const A& ao ( a ); *this = eval(*this * a); return *this; } template<class A> InPlaceMatrix& operator=(const MatrixExpr<T, D1, D2, A>& a) { const A& ao ( a ); for(unsigned j = 0;j<Dim2;++j) for(unsigned i = 0;i<Dim1;++i) operator()(i,j) = ao(i,j); return *this; } private: T *const data;};template<unsigned D1, unsigned D2, class T>InPlaceMatrix<T,D1,D2> MakeMatrix(T *const p){ return InPlaceMatrix<T,D1,D2>(p);}template<class T, unsigned D1, unsigned D2, class A>inline Matrix<T, D1, D2> eval(const MatrixExpr<T, D1, D2, A>& a){ return Matrix<T, D1, D2>(a);}template<class T, unsigned D1, unsigned D2, class A>std::ostream& operator<<(std::ostream& out, const MatrixExpr<T, D1, D2, A>& a){ const A& ao ( a ); for(unsigned i = 0;i<D1;++i) { out << '|' << ao(i, 0); for(unsigned j = 1;j<D2;++j) out << ", " << ao(i, j); out << "|\n"; } return out;}#undef MAKE_MAT_MAT_EXPRESSION#undef MAKE_MAT_SCAL_EXPRESSION#undef MAKE_SCAL_MAT_EXPRESSION#undef MAKE_MAT_EXPRESSION#endif[/source]

## Implementing Vector types in C++

Posted by , in Programming 15 August 2011 - · 1,503 views

Vector types are used in almost any kind of game code. Position, velocity, acceleration, forces, points in polygons and polyhedra etc. are all using some sort of vector type. Writing a vector class isn't particularly hard, but since it's such a central part of the code it might be worth it to have a closer look. Over the last couple years I implemented and customized several versions of vector classes and will now try to present my collected findings and thoughts here.

## Two types of Vectors

While mathematically the same, "small" and "big" vectors are not identical from a programmers perspective. Especially in the case of game programming we typically have the small vectors that are two or three dimensional and are used for positions, velocities and so forth. Then there are the vectors we use for example when solving linear equation systems. These are often way larger and their dimension isn't necessarily known beforehand. Simply put, there are the vectors that scale in dimension with the problem size and those that don't. For example the vectors you need to represent positions of units in a game have fixed size. No matter how many units there are in the game, their positions always are two- or three-dimensional. On the other hand if you are calculating splines (which requires you to solve a linear equation system) the vector size in your linear system depends on the amount of points you want to calculate the spline for. This concept of knowing the size beforehand is relevant to programming C++ since you have to decide whether to have the size defined statically at compile time or dynamically at run time. This is also a performance concern since dynamic sizes always require memory allocations while static sizes allow you to place the vector data directly on the call stack and compilers usually have an easier time optimizing for the static case.

In this entry I'll focus on the static/small vector case.

## So how should my class look like?

Coming from mathematics a lot of people like calling the components of their vectors x, y and z. This leads to the obvious implementation of a vector struct as:
[source lang="cpp"]struct Vector3d { Vector3d() : x(0), y(0), z(0) {}; Vector3d(double xx, double yy, double zz) : x(xx), y(yy), z(zz) {}; double x, y, z;};[/source]
Then we implement a bunch of overloaded operators and functions like
[source lang="cpp"]inline Vector3d operator+(const Vector3d &a, const Vector3d &b){ return Vector3d(a.x+b.x, a.y+b.y, a.z+b.z);}inline double dot(const Vector3d &a, const Vector3d &b){ return a.x*b.x + a.y*b.y + a.z*b.z;}//...[/source]

But in C++ there isn't really a reason why we should restrict ourselves to a type and dimension at this point. So we probably should make type and dimension template arguments. For the type this is trivial, we just replace every "double" with "T". But the dimension is a problem with the way we named the components. A obvious solution to allow arbitrary dimensions is to have the components in an array.
[source lang="cpp"]template<class T, unsigned D>class Vector {public: Vector3d() { std::fill(data, data+D, T()); } inline T& operator[](unsigned i) { return data[i]; } inline const T& operator[](unsigned i) const { return data[i]; }private: T data[D];};[/source]
Sadly we lose the ability to access the components via x, y and z. If we really want that we can explicitly specialize the template and add references. For the 3D case this would look like:
[source lang="cpp"]template<class T>class Vector<T, 3> {public: Vector3d() : x(data[0]), y(data[1]), z(data[2]) { std::fill(data, data+D, T()); } inline T& operator[](unsigned i) { return data[i]; } inline const T& operator[](unsigned i) const { return data[i]; } T &x, &y, &z;private: T data[D];};[/source]
I personally don't like doing this since writing myvec[0] instead of myvec.x is just as intuitive to me and it automatically reduces the chances that I'm writing copy/paste code since having the index operator in the sources makes it more obvious where I should use loops. Also as soon as you write a function using x, y and z, chances are you're restricting yourself to writing that function for the 2D or 3D case when you could just as well write it for the general case.

The operators and functions obviously have to be rewritten:
[source lang="cpp"]template<class T, unsigned D>inline Vector<T, D> operator+(const Vector<T, D> &a, const Vector<T, D> &b){ Vector<T, D> result; for(unsigned i = 0;i<D;++i) { result[i] = a[i] + b[i]; } return result;}template<class T, unsigned D>inline T dot(const Vector<T, D> &a, const Vector<T, D> &b){ T result = 0; for(unsigned i = 0;i<D;++i) { result += a[i] * b[i]; } return result;}//...[/source]

Woha... suddenly we have loops and local variables? Isn't that going to affect performance?
Luckily compilers optimize this kind of stuff. Since D is known at compile time and usually small, the compiler will unroll that loop and after inlineing it will probably also optimize away the local variables if possible

## Getting rid of temporary objects

There is still room for improvement in the way vector operations are handled. The operators produce temporary objects for intermediate results and that can be expensive when the temporary object is of nontrivial size.
The compiler will very likely turn this
[source lang="cpp"]Vector<float, N> a,b,c,d;a = b+c+d;[/source]
into something like
[source lang="cpp"]Vector<float, N> tmp1;for(unsigned i = 0;i<N;++i) tmp1[i] = b[i]+c[i];Vector<float, N> tmp2;for(unsigned i = 0;i<N;++i) tmp2[i] = tmp1[i]+d[i];for(unsigned i = 0;i<N;++i) a[i] = tmp2[i];[/source]
when the whole operation could actually be written as
[source lang="cpp"]for(unsigned i = 0;i<N;++i) a[i] = b[i] + c[i] + d[i];[/source]
which is obviously preferable.
The solution to this problem are expression templates. The idea is to have operators and functions return a operation object instead of carrying out the operation themselves. So an expression like the one above will be turned into a tree of operation objects which can then be evaluated by the assignment operator.
To achieve this we first need a base class for everything that has "vectorlike behavior":
[source lang="cpp"]template<class T, unsigned D, class A>class VectorExpr {public: inline operator const A&() const //cast operator for convenience { return *static_cast<const A*>(this); } };[/source]
The new vector class now inherits from this and also gets a modified operator= and "copy constructors"
[source lang="cpp"]template<class T, unsigned D>class Vector : public VectorExpr<T, D, Vector<T,D> > {public: static const unsigned Dim = D; typedef T Type; Vector() { std::fill(data, data+Dim, T()); } template<class A> Vector(const VectorExpr<T, D, A>& a) { const A& ao ( a ); for(unsigned i = 0;i<Dim;++i) data[i] = ao[i]; } template<class A> Vector& operator=(const VectorExpr<T, D, A>& a) { const A& ao ( a ); for(unsigned i = 0;i<Dim;++i) data[i] = ao[i]; return *this; } T& operator[] (unsigned i) { return data[i]; } const T& operator[] (unsigned i) const { return data[i]; }private: T data[Dim];};[/source]
And finally the operators look like
[source lang="cpp"]template<class T, unsigned D, class A, class B>class AddOp : public VectorExpr<T, D, AddOp<T, D, A, B> > {public: AddOp(const A& pa, const B& pb) : a(pa), b(pb) { } inline T operator[](unsigned i) const { return a[i] + b[i]; }private: const A& a; const B& b;};template<class T, unsigned D, class A, class B>inline AddOp<T,D,A,B>operator+(const VectorExpr<T,D,A> &a, const VectorExpr<T,D,B> &b){ return AddOp<T,D,A,B>(a, b);} [/source]

The whole AddOp object will get optimized away at compile time and the result is the nice loop we wanted without any temporary objects (apart from the operation objects that aren't actually constructed at runtime).

And here is the full source code of the vector class I'm using at the moment:
[source lang="cpp"]/* * MathVector.h - Copyright (c) 2011 Jakob Progsch * * This software is provided 'as-is', without any express or implied * warranty. In no event will the authors be held liable for any damages * arising from the use of this software. * * Permission is granted to anyone to use this software for any purpose, * including commercial applications, and to alter it and redistribute it * freely, subject to the following restrictions: * * 1. The origin of this software must not be misrepresented; you must not * claim that you wrote the original software. If you use this software * in a product, an acknowledgment in the product documentation would be * appreciated but is not required. * * 2. Altered source versions must be plainly marked as such, and must not be * misrepresented as being the original software. * * 3. This notice may not be removed or altered from any source * distribution. *//* * MathVector.h provides a simple static vector template class with * a basic expression template ansatz for vector operations. */#ifndef VECTOR_H#define VECTOR_H#include <cmath>#include <algorithm>#include <ostream>#include <boost/static_assert.hpp>template<class T, unsigned D> class Vector;//base class for all expression templatestemplate<class T, unsigned D, class A>class VectorExpr {public: inline operator const A&() const { return *static_cast<const A*>(this); }};//better use macros instead of copy pasting this stuff all over the place#define MAKE_VEC_VEC_EXPRESSION(NAME, EXPR, FUNCTION) \template<class T, unsigned D, class A, class B> \class NAME : public VectorExpr<T, D, NAME<T, D, A, B> > { \public: \ NAME(const A& pa, const B& pb) : a(pa), b(pb) { } \ inline T operator[](unsigned i) const { return EXPR; } \private: \ const A& a; \ const B& b; \}; \ \template<class T, unsigned D, class A, class B> \inline NAME<T,D,A,B> \FUNCTION(const VectorExpr<T,D,A> &a, const VectorExpr<T,D,B> &b) \{ \ return NAME<T,D,A,B>(a, b); \}#define MAKE_VEC_SCAL_EXPRESSION(NAME, EXPR, FUNCTION) \template<class T, unsigned D, class A> \class NAME : public VectorExpr<T, D, NAME<T, D, A> > { \public: \ NAME(const A& pa, const T& pb) : a(pa), b(pb) { } \ inline T operator[](unsigned i) const { return EXPR; } \private: \ const A& a; \ const T& b; \}; \ \template<class T, unsigned D, class A> \inline NAME<T,D,A> \FUNCTION(const VectorExpr<T,D,A> &a, const T &b) \{ \ return NAME<T,D,A>(a, b); \}#define MAKE_SCAL_VEC_EXPRESSION(NAME, EXPR, FUNCTION) \template<class T, unsigned D, class A> \class NAME : public VectorExpr<T, D, NAME<T, D, A> > { \public: \ NAME(const T& pa, const A& pb) : a(pa), b(pb) { } \ inline T operator[](unsigned i) const { return EXPR; } \private: \ const T& a; \ const A& b; \}; \ \template<class T, unsigned D, class A> \inline NAME<T,D,A> \FUNCTION(const T &a, const VectorExpr<T,D,A> &b) \{ \ return NAME<T,D,A>(a, b); \}#define MAKE_VEC_EXPRESSION(NAME, EXPR, FUNCTION) \template<class T, unsigned D, class A> \class NAME : public VectorExpr<T, D, NAME<T, D, A> > { \public: \ NAME(const A& pa) : a(pa) { } \ inline T operator[](unsigned i) const { return EXPR; } \private: \ const A& a; \}; \ \template<class T, unsigned D, class A> \inline NAME<T,D,A> \FUNCTION(const VectorExpr<T,D,A> &a) \{ \ return NAME<T,D,A>(a); \}//create actual functions and operatorsMAKE_VEC_VEC_EXPRESSION (EMulExpr, a[i] * b[i], multiply_elements)MAKE_VEC_VEC_EXPRESSION (EDivExpr, a[i] / b[i], divide_elements)MAKE_VEC_VEC_EXPRESSION (AddExpr, a[i] + b[i], operator+)MAKE_VEC_VEC_EXPRESSION (SubExpr, a[i] - b[i], operator-)MAKE_VEC_SCAL_EXPRESSION(DivExpr, a[i] / b, operator/)MAKE_VEC_SCAL_EXPRESSION(MulExpr1, a[i] * b, operator*)MAKE_SCAL_VEC_EXPRESSION(MulExpr2, a * b[i], operator*)MAKE_VEC_EXPRESSION (NegExpr, -a[i], operator-)MAKE_VEC_VEC_EXPRESSION (EMaxExpr, std::max(a[i],b[i]), max)MAKE_VEC_VEC_EXPRESSION (EMinExpr, std::min(a[i],b[i]), min)//sub vector proxytemplate<class T, unsigned D, class A>class SubVectorExpr : public VectorExpr<T, D, SubVectorExpr<T, D, A> > {public: SubVectorExpr(const A& pa, const unsigned& o) : a(pa), offset(o) { } inline T operator[](unsigned i) const { return a[i+offset]; }private: const A& a; const unsigned offset;};template<unsigned D1, class T, unsigned D2, class A>inline SubVectorExpr<T,D1,A>SubVector(const VectorExpr<T,D2,A> &a, const unsigned &o){ return SubVectorExpr<T,D1,A>(a, o);}//actual vector classtemplate<class T, unsigned D>class Vector : public VectorExpr<T, D, Vector<T,D> > {public: static const unsigned Dim = D; typedef T Type; Vector() { std::fill(data, data+Dim, T()); } Vector(const T &p1) { BOOST_STATIC_ASSERT(Dim==1); data[0] = p1; } Vector(const T &p1, const T &p2) { BOOST_STATIC_ASSERT(Dim==2); data[0] = p1; data[1] = p2; } Vector(const T &p1, const T &p2, const T &p3) { BOOST_STATIC_ASSERT(Dim==3); data[0] = p1; data[1] = p2; data[2] = p3; } Vector(const T &p1, const T &p2, const T &p3, const T &p4) { BOOST_STATIC_ASSERT(Dim==4); data[0] = p1; data[1] = p2; data[2] = p3; data[3] = p4; } T* raw() { return data; } template<class T2, class A> Vector(const VectorExpr<T2, D, A>& a) { const A& ao ( a ); for(unsigned i = 0; i<Dim; ++i) data[i] = ao[i]; } T& operator[] (unsigned i) { return data[i]; } const T& operator[] (unsigned i) const { return data[i]; } const Vector& operator*=(const T &b) { for(unsigned i = 0; i<Dim; ++i) data[i] *= b; return *this; } const Vector& operator/=(const T &b) { for(unsigned i = 0; i<Dim; ++i) data[i] /= b; return *this; } template<class A> const Vector& operator+=(const VectorExpr<T, D, A>& a) { const A& ao ( a ); for(unsigned i = 0; i<Dim; ++i) data[i] += ao[i]; return *this; } template<class A> const Vector& operator-=(const VectorExpr<T, D, A>& a) { const A& ao ( a ); for(unsigned i = 0; i<Dim; ++i) data[i] -= ao[i]; return *this; } template<class A> Vector& operator=(const VectorExpr<T, D, A>& a) { const A& ao ( a ); for(unsigned i = 0; i<Dim; ++i) data[i] = ao[i]; return *this; } Vector& normalize() { *this /= abs(*this); return *this; }private: T data[Dim];};//actual InPlaceVector classtemplate<class T, unsigned D>class InPlaceVector : public VectorExpr<T, D, InPlaceVector<T,D> > {public: static const unsigned Dim = D; typedef T Type; InPlaceVector(T *const d) : data(d) { } T* raw() { return data; } T& operator[] (unsigned i) { return data[i]; } const T& operator[] (unsigned i) const { return data[i]; } const InPlaceVector& operator*=(const T &b) { for(unsigned i = 0; i<Dim; ++i) data[i] *= b; return *this; } const InPlaceVector& operator/=(const T &b) { for(unsigned i = 0; i<Dim; ++i) data[i] /= b; return *this; } template<class A> const InPlaceVector& operator+=(const VectorExpr<T, D, A>& a) { const A& ao ( a ); for(unsigned i = 0; i<Dim; ++i) data[i] += ao[i]; return *this; } template<class A> const InPlaceVector& operator-=(const VectorExpr<T, D, A>& a) { const A& ao ( a ); for(unsigned i = 0; i<Dim; ++i) data[i] -= ao[i]; return *this; } template<class A> InPlaceVector& operator=(const VectorExpr<T, D, A>& a) { const A& ao ( a ); for(unsigned i = 0; i<Dim; ++i) data[i] = ao[i]; return *this; } InPlaceVector& normalize() { *this /= abs(*this); return *this; }private: T *const data;};template<unsigned D, class T>InPlaceVector<T,D> MakeVector(T *const p){ return InPlaceVector<T,D>(p);}template<class T, unsigned D, class A>inline Vector<T, D> eval(const VectorExpr<T, D, A>& a){ return Vector<T, D>(a);}//"reduction" functions that don't return expression templatestemplate<class T, unsigned D, class A>inline T sum(const VectorExpr<T, D, A>& a){ const A& ao ( a ); T res = 0; for(unsigned i = 0; i<D; ++i) res += ao[i]; return res;}template<class T, unsigned D, class A, class B>inline T dot(const VectorExpr<T, D, A>& a, const VectorExpr<T, D, B>& b){ return sum(multiply_elements(a, b));}template<class T, unsigned D, class A>inline T squared_norm(const VectorExpr<T, D, A>& a){ const A& ao ( a ); T res = 0; for(unsigned i = 0; i<D; ++i) { T tmp = ao[i]; res += tmp*tmp; } return res;}template<class T, unsigned D, class A>inline T abs(const VectorExpr<T, D, A>& a){ return std::sqrt(squared_norm(a));}template<class T, unsigned D, class A>inline T norm(const VectorExpr<T, D, A>& a){ return std::sqrt(squared_norm(a));}template<class T, unsigned D, class A>inline Vector<T,D> normalize(const VectorExpr<T, D, A>& a){ return eval(a/norm(a));}template<class T, unsigned D, class A>std::ostream& operator<<(std::ostream& out, const VectorExpr<T, D, A>& a){ const A& ao ( a ); out << '(' << ao[0]; for(unsigned i = 1; i<D; ++i) { out << ", " << ao[i]; } out << ')'; return out;}#undef MAKE_VEC_VEC_EXPRESSION#undef MAKE_VEC_SCAL_EXPRESSION#undef MAKE_SCAL_VEC_EXPRESSION#undef MAKE_VEC_EXPRESSION#endif[/source]

Suggestions and critique appreciated.

## Making a Board Game (Part 1)

Posted by , in Board Games 10 August 2011 - · 545 views

I just started my first attempt at designing a board game. This is the first entry in hopefully a series of journal entries that takes me from the very start to a fun to play prototype.

## Motivation

I was spending time lately watching some of the presentations in the gdcvault including the ones about board games (here and here) which made me think about non-digital games again. I always had phases where I was thinking about board/card games from a more abstract perspective, especially back when I was a very active MTG player. So yesterday when I was walking by a toy store I decided to buy some material and give board game design a try.

## General Idea, Guidelines and Principles

Since this is the first time I am actually doing this I decided to not search for a super unique game idea/concept. It's going to be a rather generic dungeon crawling game and I will focus more on the details/rules. I always liked the idea of "realistic" board games where you are playing as an actual character as opposed to abstract games (I consider settlers or dominion abstract in this context). My main problem with existing games of that kind is that they tend to have relatively complex rules. While games with complex rules are completely fine for me, they just don't fit into the more "casual" circle of friends I usually get to play boardgames with. My goal is to get complex/emergent gameplay from rules that you don't need a whole evening to explain.
So since I already spent some time thinking about problems I'm trying to solve and things I want to achieve I figured I should build a set of constraints and guidelines as a mental tool. So every time I introduce something or make a decision I can also make a sanity check against "my rules". So here is the first one:

Constraint: The rules have to fit on one side of a A5 "rules card".

Clarification: That is the rules about the game you need to know during play. Setup and examples are allowed to go on the back of the card.

Another important aspect is that I don't want to keep players waiting. So there should only be a minimum of "mechanics". With mechanics I mean the part of the game where you are doing calculations, throw dice, move around stuff and such to figure out what happens as opposed to the part where you make decisions and are actually playing. As an example: I don't want a player to make the simple decision "attack" and then stall the gameflow by a plethora of dice rolls (hit, damage, dodge, armor etc.).

Guideline: Prefer (instant) deterministic behavior over time consuming mechanics.

Also waiting for your own turn shouldn't be boring. Having very elaborate turn structures or allowing players to in principle do an arbitrary amount of things in a turn (Dominion) can make watching other players turns very annoying.

Constraint: Turns have a constant upper "action" limit.

Guideline: Allow all players to contribute to the game every turn.

I'll probably add more of these as I go along.

## What I have done so far

I bought a pack of blank memory cards (6x6cm, 60 pcs) and lots of empty playing cards. I already knew that I want the playing field to be built from tiles (there just isn't any reason not to besides maybe setup time) so I painted dungeon walls on most of the memory cards.

In the rules department I so far decided that the interaction will revolve around playing cards. So this going to be kinda MTGish in the sense that apart from maybe some sort of health and level, all the stats will be determined by cards attached to characters/monsters and that it will be possible to play "spells" (during your own and the opponents turn).
At the moment I imagine the turn structure to look something like this:
• Draw a card
• Either move to a neighboring tile, attack a player/monster that is standing on the same tile or do nothing
• Starting with the active player each player may play a card
• Combat takes place (each monster on the same tile as you automatically attacks you)
This will possibly change, but I don't want it to get significantly more complicated. Obviously most of the action will happen during the card playing phase.

Combat will probably look like: Use the players/monsters level as base damage, apply any modifiers on cards, reduce the amount of health points by the resulting damage.

I'm not yet sure what the goal will be. Possible something as simple as "reach level 20 first" or "reach level 20 and escape the dungeon". Another possibility I am considering is to give every player a unique win condition at the beginning of the game. This makes it more likely that some sort of actual story unfolds.

Here is what a 6x6 dungeon with the prototype tiles looks like.

S M T W T F S
1234567
891011121314
15161718192021
22 23 2425262728
293031