Quote: How can you test how collinear two segments are?

One way is to normalize them (which isn't strictly necessary, but can make the results more consistent), and then take the 'perp dot product' of the two normalized vectors. If the result is below some threshold, they can be considered colinear (what makes for a good threshold value depends on the context).

Quote: I've been playing with the switches in triangle and got this as my third try.
http://yfrog.com/10thirdtryp

I would try that again, using the original switches in the code I sent you (I'm not sure what switches you're using, but it doesn't look like you're getting a constrained triangulation).

Quote: Let's see. The graph would be a list of each triangle and the triangles each is connected to(Pointers to which ones it is connected)? The cost of the adjacent triangles would be the distance between both centers?

You can do it that way, but IMX it's more effective to place the nodes at the midpoints of unconstrained edges, rather than at the triangle centers. Using the triangle centers as nodes and applying some simple line-of-sight path smoothing once the path is constructed may be perfectly sufficient though, so you could certainly try that first and see how well it works.

Edit: Alright left image with culling(Using the perp dot product), right image without. On both I removed the vertices that were too close. I know there isn't much difference, unfortunately the more I increase the threshold the more it eats away at the geometry.
http://yfrog.com/52cullingp

The edges should be weighted according to the distance between which two node points?

[Edited by - Antonym on September 12, 2009 6:26:35 PM]

I was able to put something together although I am not sure how right I got it, trying to change a grid based pathfinding A* to a navigation mesh one.
The algorithm goes like this.
I find the triangle where the ship is and set it as the current node, then I calculate the G cost and H cost of its neighbors. G cost is the distance between the node position and the center of the triangle edge leading to the neighbor. The one with the lowest F cost becomes the new node(and the center of the edge the new node position), old triangle is added to a closed list so as to not be considered again. The process repeats until the triangle containing the target position is added to the closed list. Each node position is added to a vector(including the start and target positions). On each update a check is made to see if the ship has reached its next point in the vector, if it has it is deleted from the vector.

This was the result. Green squares mark the path.
http://yfrog.com/12navtryp

Have I missed anything? Did I misunderstand something? Suggestions? Are there better ways to get each new point along the way? Going straight for each edge center seemed to cause the ship to go an unecessary distance near the end.

[Edited by - Antonym on September 15, 2009 9:55:34 PM]

Quote: I was able to put something together although I am not sure how right I got it, trying to change a grid based pathfinding A* to a navigation mesh one.
The algorithm goes like this.
I find the triangle where the ship is and set it as the current node, then I calculate the G cost and H cost of its neighbors. G cost is the distance between the node position and the center of the triangle edge leading to the neighbor. The one with the lowest F cost becomes the new node(and the center of the edge the new node position), old triangle is added to a closed list so as to not be considered again. The process repeats until the triangle containing the target position is added to the closed list. Each node position is added to a vector(including the start and target positions). On each update a check is made to see if the ship has reached its next point in the vector, if it has it is deleted from the vector.

This was the result.
http://yfrog.com/12navtryp

I can't tell you if your implementation of A* is correct, but the path shown in your image certainly looks like it might be the shortest path (it seems the length would be similar going around the other way, but I can't tell by looking which path would be shorter).

As for the start and end points, my own approach is to temporarily add them as nodes in the graph; then, the search algorithm will just do the 'right thing' with respect to which triangle edge the first path edge connects to.

Quote: Going straight for each edge center seemed to cause the ship to go an unecessary distance near the end.

The usual solution is to apply a path smoothing algorithm of some sort once the (rough) path has been built. (The simplest such algorithm to apply would probably be line-of-sight-based node removal.)