A* pathfinding and navigation mesh #3

Here is a little demonstration of A* pathfinding and navigation mesh. The first part of the video shows how I'm generating the navigation mesh and nodes for pathfinding using my editor, and the second part shows A* algorithm in action:

I have already described how most of it works in my previous posts:
http://antonior-software.blogspot.hr/2015/04/a-pathfinding-and-navigation-mesh.html
http://antonior-software.blogspot.hr/2015/04/basic-path-smoothing.html
http://antonior-software.blogspot.hr/2015/09/a-pathfinding-and-navigation-mesh-2.html

Clipper library is used to get the shape of the mesh by making holes where the obstacles are. Clipper supports vertex offsetting which I use so the nodes are placed a bit away from the obstacles, so the entities don't collide with them when they travel between nodes. Nodes are placed only in the concave vertices of the outer shell(orange) and convex vertices of the holes(yellow):

 
Poly2Tri is used to triangulate the mesh. Nodes are connected if they form the edge of a triangle, forming a tree structure.

Triangles are also used in real-time to connect the start and end points to the nodes in the tree;
- First I check inside what triangles the start and end points are (I'm using Box2D for this; triangles are bodies with a polygon fixture and I'm using a custom query callback just like when using a mouse joint to pick bodies in the testbed),
- then I create temporary start and end nodes and connect them to the nodes in the triangle's vertices,
- then I calculate the path using A* algorithm (white line in the video),
- then I optimize the path using visibility between the nodes (red line in the video(part with the tanks)).

For that "path smoothing" thing from the second link I also use Box2D, this time for ray casting. Instead of ray casting in the actual Box2D world where the game entities are, I use the outer shell of the navmesh and the holes to make bodies with chain fixtures(black lines), which serve as obstacles:

 
Vertices of those obstacles need to be offset using Clipper. If you look in the image above, the vertices of the obstacles for ray casting (black lines) are between the actual wall and the navmesh, so the entities don't cut corners while following the new path(see picture below), and that adjacent nodes can actually see each other:

 This is all probably very confusing... at least I tried :/

A* pathfinding and navigation mesh #2

I was generating the graph for pathfinding by triangulating the navigation mesh. Every vertex of the mesh was one node, and the edges of the resulting triangles would be used to connect the nodes.

If you remove the nodes on the convex vertices of the outer shell of the mesh, and nodes on the concave vertices from the holes of the mesh, you can get an optimized graph, since no shortest path will ever go trough those nodes.

Before: 882 nodes, 3522 connections

After: 439 nodes, 1226 connections