Hello there!
Long story short -- I'm currently working on project where I have to implement simple board game and few algorithms working with it. One of first things I had to write was movements generator (which is supposed to find all possible moves from given game state, possible to do by selected player).
Problems started when I began using it to generate quite large amounts of moves... say 100'000. It was running incredibly slow... To start off, I removed widely used vectors, like this:
Code:
vector <OldGameStateClass*>* stateHolder;
...and replaced it with linked list class like this:
Code:
class GameState {
private:
int value;
signed char** currBoard;
GameState* childrenList;
GameState* nextElem;
};
This class holds pointer to next element (another move reachable from parent level) and also pointer to new list (children), moves available from this given game state.
It slightly improved whole generator, but it was still too slow.
Later, I changed ints to signed chars, as I was copying arrays very often -- it also helped a bit. Doing some tests later, I've found out copyBoard method was being major reason of time consumption.
And this is how it looks:
Code:
signed char** copyBoard(signed char **currBoard)
{
signed char **board = new signed char*[13];
for (int i = 0; i < 13; i++) {
board[i] = new signed char[8];
for (int j = 0; j < 8; j++)
board[i][j] = currBoard[i][j];
}
return board;
}
Generating 100'000 moves also means memory has to be allocated 100'000 times and values copied (but this doesn't seem to be much of a problem, it's rather memory allocation that is slow).
Are there faster ways of doing such? Or perhaps I should use different way of storing data (static arrays in class maybe?)?
Also, is there a way to make vector less slow? The whole push_back operation seems to take a lot of time, but using vector is quite comfortable. I also tried to use deque, but it seemed slow too.
If anybody had similar problems or knows best way of storing & copying many small game boards - I'll be thankfull for any help :-)