So I'm trying to create my own navmesh right now for fun. I've been able to construct a heightmap where each cell stores whether it's walkable(blue) or unwalkable(red).
What I need to do now is actually generate the boundaries of the blue regions as an ordered list of vertices so I can use them in a Douglas-Peucker algorithm and a CDT. Right now I know which cell belongs to region and am able to get all the cells in that region that are on some sort of boundary whether inner or outer.
First off how would I able to be separate these boundary cells into ones that create holes in the region and the cells that define the overall shape(concave hull) of the region?
Then how would I take that information and convert it into an ordered list of vertices? I want to be able to draw along the edges of the cells instead of from the center as well to support places where the width of a walkable region is just 1.?
This is the topview of the same geometry. I've been looking into image segmentation techniques to accomplish this as it seems applicable in this case but I just can't get anything working past determing which region a cell belongs too and if a cell is a on a boundary or not.
I've seen this post: Finding Edges and Vertices Within Heightmap Array but it doesn't mention anything about how to draw along the edges of cells and deal with holes right now which is my biggest struggle.
Also maybe it's a misnomer to describe what is being displayed as a heightmap anymore because it has been simplified into a binary value of 0 or 1 after doing all the heightmap calculations/filtering but this is new territory so yea.
Starting with a bit mask image of walkable pixels, this task is pretty straightforward:
Scan all the pixels in the image from top to bottom (major) and left to right. Consider the top edge of the pixel and the pixel above.
When you encounter a boundary (pixel is different from the one above) that hasn't been traced already, trace the outline of the connected shape using length-1 segments. Always trace in a clockwise direction around the filled region. When you start tracing at a top boundary, it's an object. Orient to the right. When you start tracing at a bottom boundary, it's a hole. Orient to the left.
When you start tracing a hole, look up from the bottom boundary you started at to find the hole or object boundary above it. This will already have been traced, and is part of the same object. Group paths for the same object together.
To "trace around a boundary", imagine standing on the walkable pixel with your left hand on the boundary, and then:
Do this until you come around to the same position and direction that you started at.
A reasonably efficient implementation of all this uses a matrix of integers that keeps track of which object, if any, every horizontal boundary belongs to.
Implementation in python:
walkableMask = [
" ",
" ### ",
" ### ##### ",
" ###### ",
" ### ### ",
" ###### ",
" ###### ",
" ### #### ",
]
# Test to see if a pixel is walkable
def isWalkable(mask, x, y):
if x < 0 or y < 0 or y >= len(mask) or x >= len(mask[y]):
return False
return mask[y][x] == "#"
# Trace a boundary and return a list of coordinates on the boundary
def traceBoundary(
mask,
trackmatrix, # trackMatrix[y][x] is object owning top boundary of (x,y)
x,y, # starting position inside walkable object
dir, # starting direction - number of left turns from right-facing
objectid # object id of the boundary
):
# boundary start - position, by direction
BSX = [0,0,1,1]
BSY = [0,1,1,0]
# coordinate changes for directions
DX = [1,0,-1,0]
DY = [0,-1,0,1]
# initial boundary point
startx = x + BSX[dir]
starty = y + BSY[dir]
# start result list
ret=[(startx,starty)]
while True:
dx = DX[dir]
dy = DY[dir]
# mark boundary owner
if dir == 0:
trackmatrix[y][x] = objectid
elif dir == 2 and y+1 < len(trackmatrix):
trackmatrix[y+1][x] = objectid
# check pixel in front
if (isWalkable(mask, x+dx, y+dy)):
# check forward and left
if (isWalkable(mask, x+dx+dy, y+dy-dx)):
# boundary turns left
x = x+dx+dy
y = y+dy-dx
dir = (dir+1) % 4
else:
# move forward
x += dx
y += dy
else:
# boundary turns right
dir = (dir+3) % 4
# start point of new boundary segment
bx = x + BSX[dir]
by = y + BSY[dir]
if bx == startx and by == starty:
break
ret.append((bx,by))
return ret
# get a list of objects in the mask
# each object is a list of paths
# each path is a list of coordinates
def getObjects(mask):
hei = len(mask)
wid = len(mask[0])
# track matrix - object id for boundary above each pixel. -1 for no object
# add an extra row for bottom-most boundaries
trackmatrix = [[-1]*wid for y in range(hei+1)]
objects = []
# iterate over all pixels
for y in range(hei+1):
for x in range(wid):
# check boundary above x,y
if trackmatrix[y][x] >= 0:
continue
wup = isWalkable(mask, x, y-1)
wdown = isWalkable(mask, x, y)
if wdown and not wup:
# start of object
objectid = len(objects)
path = traceBoundary(mask, trackmatrix, x, y, 0, objectid)
objects.append([path])
elif wup and not wdown:
# hole in object
ty = y-1
while trackmatrix[ty][x] < 0:
ty -= 1
if ty < 0:
raise "Impossible error"
objectid = trackmatrix[ty][x]
path = traceBoundary(mask, trackmatrix, x, y-1, 2, objectid)
objects[objectid].append(path)
return objects
# render an object list in ASCII
def renderObjects(objects):
output = []
def setOutput(x,y,c):
while len(output) <= y:
output.append([])
while len(output[y]) <= x:
output[y].append(" ")
output[y][x] = c
for obji in range(len(objects)):
obj = objects[obji]
objchar = str(obji % 10)
for path in obj:
for x,y in path:
setOutput(x*3,y*2,objchar)
for pathi in range(len(path)):
x1,y1 = path[pathi]
x2,y2 = path[(pathi+1)%len(path)]
if y1 == y2:
setOutput(min(x1,x2)*3+1,y1*2,"-")
setOutput(min(x1,x2)*3+2,y1*2,"-")
if x1 == x2:
setOutput(x1*3,min(y1,y2)*2+1,"|")
for s in output:
print("".join(s))
objects = getObjects(walkableMask)
renderObjects(objects)
Output:
0--0--0--0
| |
0--0--0 0--0--0 1--1--1--1--1--1
| | | |
0--0--0--0 1--1--1--1 1--1--1
| |
1--1 1--1--1--1 1--1--1
| | | |
1--1--1 1--1--1--1 1--1
| |
1--1--1--1 1--1--1--1
| |
1--1 1--1--1--1 1--1--1--1
| | | |
1--1--1--1 1--1--1--1--1