Can anyone point me in the direction of an algorithm or concept which could do the below. My searches so far led me to "Shelf space allocation" and "Memory allocation". But I feel there could be something more specific for my need.
In my game, I have a 2d array, which represents the shape of a space ship. 1s represent the body of the ship, 0s represent the holes and space outside the ship's body.
I have N guns, each with dimensions in 2d. Now I want to find 1s in the matrix where each gun could be fit. So if I have 2 guns with dimensions 2x2 and 3 with dimensions 3x3. I want to find 2 non overlapping spots in the matrix, where 2x2 1s are available, 3 such spots in the matrix, where 3x3 1s are available.
Good to have:
- Symmetric arrangement of guns
- Guns with uneven/non square dimensions
- Account for space between guns, so two guns are not right next to each other
I just need names of some algorithms or process which I can use to achieve this.
Thank you.
There might be a more specific name, but I think what you are describing is called a packing problem, with the extra constraints of being on a discrete grid, and your list of good-to-haves.