I'm not totally sure if this is where this goes, if it's in the wrong place, I'd appreciate being told, even if it doesn't get moved [so that I don't goof up in the future] Right now my path finding system works decently well, and fill find a path along the graph nodes that doesn’t collide with any wall, doesn’t rub up against things like it’s trying to walk through them, scooting along, and has the mover continue on with purpose. The method I’m using is as follows: The map, which can be represented as mostly two dimensional [even though it’s rendered in 3d, and certain parts do overlap each other if projected onto the x/y plane] is divided up into triangles layed next to each other, marking all parts of the map that can be moved over [you cannot leave the triangles]. At each vertex of the triangles is a path-finding graph node [thus forth at every point and corner of the map]. The neighbors of a given node are every vertex of every triangle that shares a given vertex. This method though is giving a rather annoying result. First of all, it’s very common for a unit to follow walls for long distances, going down hallways, and then suddenly swerve toward the center of the hall as it approaches a doorway, and it’s very common for a unit to travel to a corner of a square [or other sided figure] room before changing course, and going through the doorway [because the room was cut up in such a way. There are no nodes in the middle of hallways, and there are no nodes in the middle of rooms. Only where corners are. This also means that If I tell a unit to enter a room, it wanders to one of the corners, then from the corner into the center. To see exactly what I’m talking about with regard to the start-end node problem. Draw a pair of triangles sharing an edge and two vertices, then draw a dot in the center of each of them, and connect them going through the nearest shared vertex. What should be a straight line, is thus a V shape. If I get a pencil and paper, I can obviously draw a more correct path, and can do this by skipping certain nodes that it chooses to follow [even though my pencil would go through nodes that it selected, it would occasionally draw a straight line between node N and node N+2, or N+3, and skip N+1 entirely]. This is a problem that needs fixed, obviously, as it ends up looking REALLY corny after a while, to have a stream of units follow one after another, touching the same stupid corner that could be entirely skipped, or all bouncing off the same doorway, crossing between the hall at the same point. The solution is obviously to either add a whole bunch more nodes [which I don’t want to do, for a reason stated below] or implement a path straightening method, which I’m really rather unsure how to approach [especially with regard to the first node, to second, or the second to last to the last node]. Any suggestions? How exactly would forcing the path to be more straight be done? Can be it be done efficiently? [given this data set described]. Would a change to my data help speed this path readjustment? I can do it, but the method that I’d use to do it is very brute-force, and isn’t very clever at all :P Get the feeling there is a better way. [ the method I would use would be a typical ray/geometry test for every node N to node N+2, if successful, node N+1 is dropped, and all the nodes are shifted down, and it starts over until a test fails, then moves along.] I know this is long, and I’m sorry for that, but people always say to give more detail, so here you go, plenty of detail! Below this point is why I don’t want to just flood the map with extra nodes, if you don’t care, then don’t read it. If it is however, the only solution that will lead to an acceptable answer, then such is what must be done. How I currently have the nodes set up, at the vertices of the triangles, assures me that I only have nodes at the edges, or more specifically, where walls intersect each other. These nodes then can include data with regard to a vector that would bisect this wall intersection, and assign it a magnitude equal to the distance away from the corner that a unit with a bounding circle of radius 1 meter would have to stand to just barely touch each of the walls. This means that I can accommodate things of varying size, and adjust the nav-points accordingly. This also means that I can pre compute the maximum size thing that can use this specific nav-point, before the nav-point ‘normal’ would force a collision against something else [a value that is one half the distance along this normal to another collision.] This allows me then to treat these nodes as choke points to large objects, and give me the ability to have large objects. Also, if I just flood-fill with nodes, the path finder will slow down [more nodes to keep track of and sort], and while that’s not a big deal right now, speed is always good. Just a last little tidbit, one optimization that I’m using right now is actually to remove every node with only two neighbors [corner nodes] from the navigation system completely, after observing that it has no effect on path-finding performance [other than to make it quicker, but it doesn’t make the path-finder run oddly in any way]. This is an option that is controlled by a variable that can be toggled, and I’ve currently noticed no difference between off and on [besides speed increase], and can’t really think of a reason to remove this optimization. Thanks for the input [or thanks for just reading this monster, even if you don’t reply], I really appreciate it.

I'd say: don't path through the vertices, path through the triangles.

First, have your triangles be the fundamental nodes, and path through them from the triangle you're in to the one you need to be in. Then, to get from one triangle to the next, aim for the median of the next triangle if it's visible, otherwise aim for the nearest point on the side that both triangles share (minus your unit's bounding radius, obviously).

You can further optimise this by scanning further ahead along the list: ie. if the median of triangle C is visible from your planned spot in triangle A, you can drop triangle B from the path since it becomes largely irrelevant (the exception being the unit radius again - a decent steering algorithm should solve that).

Convert the destination and source triangles into world coordinates x and y.
Calculate an exact straight line between them and see which triangles it passes through.
Have your units follow this line.
If the line encounters obstacles, i see no reason why you cant calculate the correct path the same way you would in a 2d rts. The tiles are triangles, which are different, but the same principles still apply!

@ Kylotan

Sounds interesting, using the triangles instead of the vertices. When i was first designing the system I’m using now, one of my concerns about doing just that was that things would refuse to walk up against walls at all, instead just walking down the middle of wide halls and through the middle of rooms, but since I'm now thinking in terms of performing a post-processing step on the path anyway to make it look more natural anyway...

Actually the original graph that I was using did use the centers of triangles, and I found it so unnatural that all the units would walk through the very center of large areas. So I changed it to the vertices, and worked with that, and found shorter paths consistently, even though the paths had occasional oddities like those described in the original post. But now that I'm going to have to process the path a second time anyway [once the best path is found, process it to remove unneeded nodes and tighten it up a bit], I'm now thinking of ways that this triangle-center method would work out a lot better. Kind of left the triangle-center method by the road side, but it looks like its the best way to go with regards to the post processing. Thanks a bunch, my brain is lit up with ideas right now [specifically regarding path post-processing]. Sounds great.

@ chosendl

Just wondering, but how does a 2D RTS do it that is different from how it's being done now? Isn't it still just a typical graph traversing path finding method? Guess I've got some reading to do on the matter, perhaps the key to my problems is in that instead. While the graph nodes don't really have any meaningful 'position' so to speak, only such as to give them a distance from each other, the reason that I try to treat it as a 3d problem is because things like bridges and multiple-floored structures aren't uncommon. Things that if projected straight against a plane would overlap. Any good articles on RTS pathing though that you happen to know of? [I’m going to be doing my own searches too, but if you happen to know of a particular diamond-in-the-rough, it would be much appreciated.]

Switching to tile based (as opposed to vertex based) pathing wont avoid the problem you're facing, since a tile must still be represented by a single state (typically the location of the centroid). I can certainly envisage very simple room geometries with tilings that meet some standard metrics that cause problems for one or the other technique (if you want some examples, holler). One can hand craft triangles to minimise the affects of path irregularities, but this solution applies equally to vertex and tile methods.

One solution is to replace the path found on the graph with a spline curve. You can use the tile centroids on the solution path as knots (control points) for a spline approximation to the optimal path. You'll need to be careful to ensure that your spline is constrained by its distance from any wall/obstacle, so as to avoid having the unit collide with corners as it attempts to round them.

Cheers,

Timkin

Hey i agree with Timkin,
Heres a nice link with some info and source code on spline curves
http://local.wasp.uwa.edu.au/~pbourke/curves/spline/

Also i you could try waiting the nodes in the path to influense the path generated by the spline cure
For example if there is a node very close to a corner it should have a high weigh so they dont walk into a wall
(the weighting would be done by including the point multiple times when generating the curve)

@ Timkin

It doesn't resolve it completely, true, but it does limit the number of possible neighbors to nodes that i can have to 3 per node [since each triangle has only 3 sides], and if i store what edge the transition goes through, i've got built in border restrictions [both vertices of the edge that it is supposed to transition though] so i can pretty easily add extra steps in the path make make sure it huge the corners effectively and so forth.

But splines, yikes!

Sure they would make it look more natural and a whole lot prettier, but in this particular situation, kinda don't think its all that necessary. Thanks for the idea though. Sounds like something for a future project when the paths need to look more natural. Right now I just need things to get to where they are going without looking too dorky.

Just thought I'd mention, I've got the new path finder up and running right now, using the center of the triangles as the nodes, and am currently testing the code to drop nodes that aren't needed, and it's hugging corners how it should. It's faster than my old code too, and hasn't even been optimized fully [i'll get to that later]

Thanks everyone for the input

If it's working and does what you want, then there's no need for further alteration. 8)