For determining blocks that are apart of the ship you could use the algorithm I used to identify islands for the RTS i am currently making.
Note that i do not know the algorithm’s name as i derived it myself:
- determine whether the cell at 0,0 is either ship or non ship, record this as the region type
- scan your grid left to right. for each cell:
1a. check to see if the cell’s region type does not match the recorded region type. If it does not then:
1aa. update the recorded region type
1ab. increment the master id
1ac. set the current region id to the master id
1ad. set the initial regionIdMapping entry for this id to be this id.
1b. check to see whether the cell above’s region type matches the recorded region type. If is does then:
1ba. set the current region id to the regionIdMapping entry of the region id of the cell above.
1bb. check to see whether the cell to the left’s region type matches the recorded region type. If is does then:
1bba. iterate over the regionIdMapping entries and update those entries who map to the left cell’s region id to be now mapped to the current region id.
1c. update the current cell’s region id to be that of the current region id.
- scan your grid left to right. for each cell:
2a. consolidate the associated region ids by setting each cell’s region id to the regionIdMapping entry of the cell’s region.
This is implemented in my code as below:
/**
* Region identification
*/
int id = 0;
int masterId = 0;
int regionType = improvements[0][0] & LAND_FLAG;
int[] regionSize = new int[MAX_POTENTIAL_REGIONS];
int[] cellRegionMapping = new int[MAX_POTENTIAL_REGIONS]; // TODO use temp[]
for (j = 0; j < MAP_SIZE; j++)
{
for (i = 0; i < MAP_SIZE; i++)
{
// if the current region type does not match cell type then
// set region type to the opposite type and update the
// current region id
if ((improvements[i][j] & LAND_FLAG) != regionType)
{
regionType = improvements[i][j] & LAND_FLAG;
id = ++masterId;
cellRegionMapping[id] = id;
}
// check to see whether the cell above is the same region
// type. If so then set the current region id to the that
// cell's mapped region id
if (j > 0 && (improvements[i][j - 1] & LAND_FLAG) == regionType)
{
id = cellRegionMapping[region[i][j - 1]];
if (i > 0)
{
int otherId = region[i - 1][j];
// if the cell to the left is the same region type
// then ensure that any references to region id of
// that cell point to the current id.
if ((improvements[i - 1][j] & LAND_FLAG) == regionType)
{
for (k = 0; k < MAX_NO_POTENTIAL_REGIONS; k++)
{
if (cellRegionMapping[k] == otherId)
{
cellRegionMapping[k] = id;
}
}
}
}
}
// set the region id for the cell
region[i][j] = id;
}
}
// using the map of associated cell region ids, consolidate the
// regions ids to one per region
for (i = 0; i < MAP_SIZE; i++)
{
for (j = 0; j < MAP_SIZE; j++)
{
regionSize[region[i][j] = cellRegionMapping[region[i][j]]]++;
}
}
Note that this was code for a java4k game so is pretty rough. For your case I would suggest using a proper collection for the regionIdMapping.
Obviously you will need to change the
improvements[i][j - 1] & LAND_FLAG
test to be your test for a placed block. But you can then use the regionSize array to pick the largest group of ship blocks (region) and make the assumption that they represent the ship.
This algorithm also assumes that only non-diagonally touching cells are grouped together… if you want to do that then you need to repeat 1b above for the cell to the above left of current and for the cell to above right of the cell.
