Finding a random WxH rectangle fitting in a MxN array region, where array[x][y] == number

I'm programming a game where a random map is generated whenever a new game is started. The开发者_运维问答 game field is a MxN boolean array (true=ground, false=air.) From that array I calculate each connected free (air) regions, generating a new MxN int array where the int value is 0 if there's is ground, or the region number if it's free space (each free space has the same region # as their neighbour free spaces.) Now my random playfield has been separated in numbered rooms.

E.g.:

Ground data:

000001100111000

000011000001110

000111000001111

000001110000001

000000011000011

Room data:

111110022000333

111100222220003

111000222220000

111110002222220

111111100222200

I need to populate these rooms with monsters, object, etc. so I need some way to find, given a rectangle size and a room #, a random place inside that room where the WxH rectangle would fit.

Obviously I could just blindly try random coordinates until the criteria is matched, but I don't think that's really the way to go, because it may take ages for the random number to meet the requirements (or not, it's random.)

I don't care if the random region is reusable later, I mean, I don't care if the same random region can be randomly selected twice (in other words, if objects spawn on top of other objects), but it would be preferable to be able to handle that situation too.

Thanks :)

You could make a list of valid positions for the objects (using logic similar to your room-determination algorithm), and randomly select an index into that list.

I would make a third MxN array that has a 0 or 1 in each spot. 0 means a WxH would not fit there and 1 means it would. This should be calculated at the same (or really, right after the time) you create the second array,