# Path finding straightness suggestions.

This topic is 4346 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

##### Share on other sites
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).

##### Share on other sites
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.
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!

##### Share on other sites
@ 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.]

##### Share on other sites
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

##### Share on other sites
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)

##### Share on other sites
@ 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

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

1. 1
2. 2
Rutin
22
3. 3
JoeJ
18
4. 4
5. 5

• 17
• 40
• 23
• 13
• 13
• ### Forum Statistics

• Total Topics
631726
• Total Posts
3001910
×