# "Trivial" Navigation Mesh Generation (not PandAI)

Hello there,

I am trying to make my own generation of a navigation mesh (as PandAI not suits my needs and Recast/Detour hasn’t a working Python wrapper). I follow an very interesting article: gameschoolgems.blogspot.de/2009/ … ion-i.html

The algorithm I implemented works not like it should and I can’t find the solution. Here is a small snippet:

``````        blocked = []
##        blocked.append(((0.5, 0.5), (1.5, 16.5), (0.5, 16.5)))
##        blocked.append(((0.5, 0.5), (1.5, 0.5), (1.5, 16.5)))
blocked.append(((1.5, 2.5), (1.5, 4.5), (2.0, 4.5)))
for i in range(len(blocked)):
a, b, c = blocked[i]
line1 = Edge(a, b)
line2 = Edge(b, c)
line3 = Edge(c, a)
for edge in list(self.edgeContainer):
intersection = lineLineIntersection(line1, edge)
if intersection:
first = Edge(edge.getFirstPoint(), intersection)
second = Edge(intersection, edge.getSecondPoint())
for tri in list(edge.getTris()):
left = tri.getEdgeLeftOf(edge)
right = tri.getEdgeRightOf(edge)
same = Edge(first.getSecondPoint(), tri.getUnconnectedPoint(edge))
Triangle(first, left, same)
Triangle(second, right, same)
#removeTris.append(tri)
tri.selfDestruct()
removeEdges.append(edge)
intersection = lineLineIntersection(line2, edge)
if intersection:
first = Edge(edge.getFirstPoint(), intersection)
second = Edge(intersection, edge.getSecondPoint())
for tri in list(edge.getTris()):
left = tri.getEdgeLeftOf(edge)
right = tri.getEdgeRightOf(edge)
Triangle(first, left, Edge(first.getSecondPoint(), tri.getUnconnectedPoint(edge)))
Triangle(second, right, Edge(first.getSecondPoint(), tri.getUnconnectedPoint(edge)))
#removeTris.append(tri)
tri.selfDestruct()
removeEdges.append(edge)
intersection = lineLineIntersection(line3, edge)
if intersection:
first = Edge(edge.getFirstPoint(), intersection)
second = Edge(intersection, edge.getSecondPoint())
for tri in list(edge.getTris()):
left = tri.getEdgeLeftOf(edge)
right = tri.getEdgeRightOf(edge)
Triangle(first, left, Edge(first.getSecondPoint(), tri.getUnconnectedPoint(edge)))
Triangle(second, right, Edge(first.getSecondPoint(), tri.getUnconnectedPoint(edge)))
#removeTris.append(tri)
tri.selfDestruct()
removeEdges.append(edge)
for i in range(len(removeEdges)):
try:
self.edgeContainer.remove(removeEdges[i])
except: pass``````

This is just the main part of my algorithm, I have a small math lib for it. You can get the source and media at GitHub: github.com/JoernSchoenyan/pyrdacor
The code snippet is in pyrdacor.py and the math lib is pyrmath.py