Contiguity algorithm?

-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0\|714\|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
Socoder -> Cobra -> Contiguity algorithm?
Sun, 23 May 2010, 14:34
HoboBen	I've got this simple loop that attempts to identify contiguous terrain, like so: (left - terrain, right - identified contiguous groups) (Each contiguous group is given its own colour) While it's probably "good enough", it's not 100%, as you can see parts of the ocean are shown as different colours. Does anyone know the name of an algorithm or method that would provide the best results? Ideally without being too exponentially slow. The code: Procedure wgen_DetermineContiguousAreas() ; export Var x, y, i, mincg1, mincg2: Integer Begin //Init map For y = 0 to (worldH-1) For x = 0 to (worldW-1) contiguousMap[x,y] = 1 Next Next i = 2 For y = 1 to (worldH-1) For x = 1 to (worldW-1) If (worldTile[x,y].tileType <> worldTile[x-1,y].tileType) and (worldTile[x,y].tileType <> worldTile[x,y-1].tileType) then contiguousMap[x,y] = i Inc(i) Else mincg1 = 0 mincg2 = 0 If (worldTile[x,y].tileType = worldTile[x,y-1].tileType) then contiguousMap[x,y] = contiguousMap[x,y-1] mincg1 = contiguousMap[x,y-1] Endif If (worldTile[x,y].tileType = worldTile[x-1,y].tileType) then contiguousMap[x,y] = contiguousMap[x-1,y] mincg2 = contiguousMap[x-1,y] Endif If (mincg1 <> 0) and (mincg2 <> 0) then contiguousMap[x,y] = Min(mincg1, mincg2) Endif Endif Next Next contiguousAreaCount = i End --v -=-=- blog \| work \| code \| more code
Sun, 23 May 2010, 15:01
Jayenkai	Whenever I'm doing "Blocks vanish when alike colours meet" I tend to filter through a few times.. x=1->max, y=1->max then y=max->1, x=max->1 then again x=max->1, y=1->max The first time, you do the whole thing, then the second and third, check for "if same color as, and should be same group, but isn't!" and replace where necessary. -=-=- ''Load, Next List!''
Sun, 23 May 2010, 15:11
HoboBen	Thanks Jay! Merging the groups worked great. This horrible beast of a loop did the trick: For x = 1 to (worldW-2) For y = 1 to (worldH-2) For x2 = -1 to 1 For y2 = -1 to 1 If ((x2 <> 0) or (y2 <> 0)) then If contiguousMap[x,y] <> contiguousMap[x+x2,y+y2] then If worldTile[x,y].tileType = worldTile[x+x2,y+y2].tileType then adjust = contiguousMap[x+x2,y+y2] For x3 = 0 to (worldW-1) For y3 = 0 to (worldH-1) If contiguousMap[x3,y3] = adjust then contiguousMap[x3,y3] = contiguousMap[x,y] Endif Next Next Endif Endif Endif Next Next Next pc = ToInt((ToReal(x)/ToReal(worldW-2)) * 100) gfx_Text(4, ytext, ""+pc+"% ") wgen_DrawWorld(500, 25, 1024-25-512, 512, WGEN_PREVIEW_CONTIGUOUS) gfx_RenderCanvas() Next --v -=-=- blog \| work \| code \| more code