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:
...and replaced it with linked list class like this:Code:vector <OldGameStateClass*>* stateHolder;
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.Code:class GameState {
private:
int value;
signed char** currBoard;
GameState* childrenList;
GameState* nextElem;
};
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:
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).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;
}
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 :-)