4
\$\begingroup\$

I have a 2d square grid used for pathfinding that I wish to convert into a navigation mesh. My idea is to pluck out all of the nodes that are on the edge of walkable space, simplify the amount of data with a line reduction algorithm, then triangulate the set of points. I am stuck at the simplifying step.

To find edge nodes I use a marching squares algorithm. The downside to using marching squares is that the points are unsorted, and in order to pass the points into the Ramer-Douglas-Peucker algorithm they need to be sorted by connectivity (and separated into individual lines). I'm looking for an algorithm that can either sort my collection by connectivity or discover edge nodes in a consecutive manner.

I'm trying out Djikstra search to find a path from one point to the next. To determine if these points are connected, during path reconstruction if the parent point has a Euclidean distance greater than 1 to the current point then they are not directly connected. I might be able to get this to work but it is proving to be extremely slow.

Here are screenshots of the graph I am working with:

2d pathfinding grid: 2d pathfinding grid

unsorted edge nodes discovered via marching squares: edge nodes

\$\endgroup\$
  • \$\begingroup\$ What's too slow? Is this something that happens at runtime? Or build time? How many nodes are we talking about here? \$\endgroup\$ – MichaelHouse Sep 15 '17 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.