# How Can I Find a Shape on 2D Array?

For the code in my test project, I want to find 2D[,] array shape on the char[][] list. I created an actual map with 'char[][]' array. So, how can I find a tileChar's shape on the worldChar array?

How to do this in Java, C#, JavaScript, pseudo-code, algorithm or etc.?

For Example;

List<string> mainShape = GetRandomShape().Split('#').ToList();
char[][] tileChar = mainShape .Select(a => a.ToArray()).ToArray();
char[][] worldChar = GenerateRandomWorld();


Example Image:

'*' -> NOT NULL

'-' -> NULL

• Is there a limit to the size of your world or tile? I'd be tempted to approach this with bitmasks but that doesn't necessarily scale to arbitrary sizes. ;) Jan 2, 2016 at 18:06
• Not limit for tileChar. (Min [1][1], Max [10][10]) But worldChar limited [10][10]. Can i use x4 for loop ? I do not know. Jan 2, 2016 at 18:14
• Can someone help me, please ? (: Jan 5, 2016 at 10:06
• You could create the shape in a separate 2D array and check the tile chars against the shaped ones Jan 5, 2016 at 14:15
• Have you any sample code for this ? or algorithm ? The function need to return true if two 2d arrays contain the same values. Jan 5, 2016 at 17:15

The solution below utilizes boolean values as opposed to chars as I found them easier to utilize for this solution, but it can easily be modified to support char instead.

The easiest way to perform this test in my mind is to loop through each possible origin point in the world that the shape can possibly fit at. Then, at each of those origin points, loop through each set of indexes in the shape array, testing if the shape matches (for the purposes of this function; if shape[x,y] is false or if shape[x,y] is true AND world[x,y] is true) the world at that point. If the shape matches at that point, continue on to check the other points in the shape, otherwise break the loop so that you can start the check at the next origin point.

public static bool doesShapeExistInWorld(bool[,] shape, bool[,] world)
{
int shapeWidth = shape.GetLength(0);
int shapeHeight = shape.GetLength(1);
int worldWidth = world.GetLength(0);
int worldHeight = world.GetLength(1);
if (shapeWidth <= worldWidth && shapeHeight <= worldHeight)
{
//Enumerate through each possible origin position for shape
for (int startY = 0; startY < worldHeight - shapeHeight; startY++)
{
for (int startX = 0; startX < worldWidth - shapeWidth; startX++)
{
//At each origin, test all points in shape against world
bool shapeExists = true;
for (int shapeY = 0; shapeY < shapeHeight; shapeY++)
{
for (int shapeX = 0; shapeX < shapeWidth; shapeX++)
{
shapeExists = !shape[shapeX,shapeY] || (shape[shapeX,shapeY] && world[startX + shapeX,startY + shapeY]);
if (!shapeExists)
{
break;
}
}
if (!shapeExists)
{
break;
}
}
if (shapeExists)
{
return true;
}
}
}
}
return false;
}


I should probably be the first to point out that the above is likely not as optimized as possible, but at least gives a rough starting point.

• I changed this code a bit, bool[,] shape to char[][] shape, but when i tried it, its give me a error on this line ; shape.GetLength(1) -> Array index out of range. I think, because it is rectangular, am i true ? How can i fix it without use jagged array instead of 2d array ? Or, can i change my jagged array to 2d ? Jan 9, 2016 at 18:16