# Determine if set of connected tiles can fit inside grid

Feel free to edit the title; I had a hard time figuring out how to explain it in a single line.

Here goes. I'm trying to generate these grids automatically, and randomly.

I have a grid of 25 tiles (indicated by #)

#####
#####
#####
#####


Let's say that I have 2 monsters I want to place in this grid, each monster occupies 3 or 4 tiles, with different patterns (these are not random, but is defined somewhere).

Monster 1 indicated by the letter A Monster 2 indicated by the letter B

An example of this:

#AA##
#BA##
#BBB#
#####


Or it could be (this is whre the randomness comes in):

AA###
#A###
#B###
#BBB#


How would I go about calculating where, for example, monster B fits in the grid after A has been placde? Monster B has a pattern of:

B
BBB


And A has a pattern of:

AA
A


A possible pattern could also be (for a different monster than A and B):

C
C
C


Is this even possible to automate? Hope that makes sense, otherwise I can try drawing it instead.

Thanks

The best way to do this would be to randomly pick a tile, and just do checks for the other tiles needed to place the monster. If the monster can't fit being placed in the tile given, then loop until a spot is found where it can fit.

int[,] monsterA = [[1,1]
[0,1]]

int[,] level = [[0,0,0]
[0,0,0]
[0,0,0]]

point placeLocation(int[,] layout, int[,] monster)
{
bool completed = false

point chosenPoint

while (completed == false}  //while a good spot hasn't been found
{
//method which picks a random point from the array
chosenPoint = getRandomPoint(layout)

bool fail = false
for (int i = 0;i<monster.width;i++)
{
for (int j=0; j<monster.height;j++)
{
if (monsterA[i,j] == 1 && level[chosenPoint.X + i,chosenPoint.Y + j] != 0
{

//if any point of the monster is blocked, fail is set to true
fail = true;
}
}
}
if (fail == false){
//monster can fit here
completed = true
}
}
return chosenPoint
}


If you want to prevent the loop from running forever, you could put a limited number of tries on it or keep track of chosen points until all of them have been exhausted.

• Very interresting! Is there a way to, given you have 3 patterns that you know (3 monsters), pick a tile that has the highest chance of all the monsters fitting? If I place a 4x4 monster in the middle of a 5x5 grid - there is no room for monster C (check it's pattern above). That seems to be the deal breaker in this concept. Appreciate your reply, I'll play around with your example :) Feb 12 '16 at 23:20
• I don't see why you would need that unless you're operating on really large scale maps that it needs to be optimized so much. There's probably ways that you could do it if you needed to, though. Feb 12 '16 at 23:26