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:
1. determine whether the cell at 0,0 is either ship or non ship, record this as the region type
1. 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.
2. 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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
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];
for (j = 0; j < MAP_SIZE; j++)
{
for (i = 0; i < MAP_SIZE; i++)
{
if ((improvements[i][j] & LAND_FLAG) != regionType)
{
regionType = improvements[i][j] & LAND_FLAG;
id = ++masterId;
cellRegionMapping[id] = 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 ((improvements[i - 1][j] & LAND_FLAG) == regionType)
{
for (k = 0; k < MAX_NO_POTENTIAL_REGIONS; k++)
{
if (cellRegionMapping[k] == otherId)
{
cellRegionMapping[k] = id;
}
}
}
}
}
region[i][j] = id;
}
}
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
1
| 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.
