Suppose I am designing a game of tic-tac-toe game playing in an infinite board. The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row wins. What is the best data structure to represent it? I can only think of hash table to record positions. For each new position, check its surroundings are checked to evaluate a win.
Any other better idea?
Although you have an infinite board, you should still allocate coordinate for your game. The coordinate could be something like from 0 to a a very large number.
Now, you have a practically infinite coordinate. Why not a simple dictionary of coordinates? C++:
std::map<std::pair<long, long>, MySquare> m;
For example, you are on (460,670), you would like to check (461,671). Simply check if (461,671) is in m, if not you add a new entry.
This very simple design is robust as it allocates memory only if you really need it.
Don't overcomplicate yourself.
