CODEWITHSUNDEEP
algorithmdata-structures
derek
derek

Reputation: 10207

Best data structure for tic-tac-toe game with infinite board

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?

Upvotes: 1

Views: 2341

Answers (1)

SmallChess
SmallChess

Reputation: 8116

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.

Upvotes: 1

Related Questions