please wait
How to recognise a shape in a grid (multidimensional arrays)
Feb 6, 2013 at 6:00pm
So guys, say you have a tic-tac-toe game which already works. When is the winner declared? When you find three matching characters in a row, horizontally, vertically or diagonally. In the basic game, this would be on a 3x3 grid, most likely
But how do I check the condition without brute-forcing if statements? Sure it could be easy to work out some solution where you check if an entire row is 'X' or 'O' with a loop or something, but even that's awkward for diagonals.
My actual problem, though, is much harder to deal with than tic-tac-toe results. What if my grid is [10][10] and I want something to happen if there's a T shape somewhere? Or if there's a Tetris S shape? You can't brute force that, there are thousands of possibilities. To help illustrate:
Note: I realise that the above looks like Tetris but the idea is that you choose a space on the grid to claim it. By making specific shapes, something is triggered.
So in short, how could I "cleanly" check if one of the above shapes is created? Thanks in advance for your help.
grid[3][3]. |
|
But how do I check the condition without brute-forcing if statements? Sure it could be easy to work out some solution where you check if an entire row is 'X' or 'O' with a loop or something, but even that's awkward for diagonals.
My actual problem, though, is much harder to deal with than tic-tac-toe results. What if my grid is [10][10] and I want something to happen if there's a T shape somewhere? Or if there's a Tetris S shape? You can't brute force that, there are thousands of possibilities. To help illustrate:
|
|
Note: I realise that the above looks like Tetris but the idea is that you choose a space on the grid to claim it. By making specific shapes, something is triggered.
So in short, how could I "cleanly" check if one of the above shapes is created? Thanks in advance for your help.
Feb 6, 2013 at 6:38pm
If you know the shape you are interested in, you can just brute-force (it will be around 100 checks for 10x10 grid). If not, you can determine connected components: http://en.wikipedia.org/wiki/Connected-component_labeling
Feb 6, 2013 at 9:32pm
Yeah like I said brute-forcing isn't really an option. There could be 4 shapes each with 4 rotations on a 15x15 grid for all I know. Too much coding, too much room for errors.
But that wiki page is definitely along the lines of what I'm looking for, thank you. Of course it's incredibly wordy so I have to try and scrape something together out of it..
But that wiki page is definitely along the lines of what I'm looking for, thank you. Of course it's incredibly wordy so I have to try and scrape something together out of it..
Feb 7, 2013 at 11:16pm
Anyone else have any ideas? If my question is too vague then I'll try to clarify, but I'm really quite stumped.
Topic archived. No new replies allowed.