Any angle path finding.

Does anyone have a bead on a canned any angle path finding routine? (A* project looks great but is not any angle)

I have a 2D map that changes over time, and am looking for optimal paths between waypoints.

Thanks.

There is no such thing, because it’s an NP hard problem.

All pathfinding algorithms have to consider space in discrete units to be able to explore it (basically turn space into a topology, a graph). And obviously it’s very important that this graph can be tiled, so this is why we use grids.

Now if you have specific constraints, no one says it has to be a square grid, it could be hexagonal, or triangular, or smaller, but making the grid smaller would only deteriorate the performance without any significant benefit. Making it bigger, on the other hand, would make it unable to find the narrow passages between the obstacles, so this is really a natural constraint on the algorithm itself.

A* is the severe optimization technique for the more general Dijkstra’s algorithm, and its result can be refined to suit your needs. And this is exactly what navmeshes do secretly as well.

The basic approach is to let A* do its job, then take the result and scan the segments point by point, determining whether there is line of sight between them, and pruning points that are redundant, giving you the end result that is practically gridless and angle-free.

Because your map is changing over time, consider navmeshes that allow for dynamic obstacles, or write the algorithm yourself. But it simply has to be A* or a variant thereof.

A* don’t have to be a grid, but since you are asking it mean you don’t have the skills, it’s better you follow the advice above.

I do not understand the answer. There are any angle algorithms, some of them based on A*, some of them not.

The constraint of a square grid is not a problem. The problem is that classic A* creates paths that are limited to 8 directions from each node. Theta* is one such algorithm that “prunes as you go” as you mentioned, and creates any angled paths that are closer to optimal, but there are many others.

I’m looking for a canned version of one of these if it exists.

Thanks.

Nothing you said counters my arguments.
Theta* is the same thing as A* and the main difference, as I’ve already explained in my last two paragraphs, is this

WP article even explicitly states this being the main difference

So, once again, true any-angle algorithm doesn’t exist. All of them refine the result of A* or its variants, and in practice there are only few of them worth mentioning. If an algorithm optimizes this inside the main loop, that doesn’t make it any more any-angle than A*, it just subsumes this constraint into the algorithm’s critical path, in order to do everything in one pass.

That’s not true. Classic A* operates on a graph, any graph at all, except the open one (you use D* or a variant for exploring unknowable graphs). And because of this can be used in other applications, such as AI, not just pathfinding.

Hmm, I am not sure why taking what seems to be a combative tone.

RRT algorithms are not based on A*. Visibility graphs result in true any angle pathfinding that is optimal. ANYA as well.

I am looking for a canned algorithm, similar to Theta* (or perhaps Theta* or one of its variants) that gives any angle pathfinding, is not limited to next neighbors as A*, and is canned. A good description of some of the variants can be found here.

https://en.wikipedia.org/wiki/Any-angle_path_planning
https://github.com/Ohohcakester/Any-Angle-Pathfinding

Theta* tends to give more optimized paths than A* with post smoothing.

If the form of the question continues to bother you, you may assume for the moment I am asking for a canned Theta* implementation.

1 Like

Yes, but on a rectilinear grid, as occurs in many games, classic A* produce graphs based on its closest neighbors. Whereas some other algorithms do not.

sorry about that, didn’t mean to come across as combative.
I’m just cutting to the point.

no, obviously not every algorithm is based on A*, but every single algorithm out there has to use some sort of spatial discretization. I’m just stuck with trying to explain this part, but now I see that you simply ask for a proven any angle algorithm that you can use in your project.

I honestly don’t know about any, except Unity’s navmeshes, which are similar to how theta* works, from what I’ve seen. I don’t know if they support dynamic obstacles though.

My point was that you shouldn’t take this into consideration at all. You don’t care how games use the A*. I’ve used A* differently in my projects. Your nodes can be entire rooms and corridors, not tiles. And you could build your own heuristic and describe the penalties differently from what is typically used. The general-purpose A* has nothing to do with rectilinear grids, this is just how people typically use it.

1 Like

As I said, you could describe your topology with irregular hexagons or voronoi cells, and have an A* interpret the shortest path, admittedly it would be a weird one, but it’s technically any-angle, right?

Actually the voronoi cells idea is very very interesting, now that I’ve mentioned it, I never thought about that one.

Yes. Sunday morning easy questions. :slight_smile:

When I last revisited this, Navmeshes got baked and weren’t suitable for dynamic obstacles. I’ll revisit this.

Appreciate the replies. This particular game is fairly straightforward rectilinear grid based. The canned A* projects I have seen generate the grid in the background away from user intervention. If need be, I’ll reinvent the wheel, but was simply doing project planning and hoping this part of the project could be sped up with existing assets.

Also it would help immensely to read the list in this article, entry by entry.
You can see that all the algorithms either operate as D* or A*, the only difference being in how greedy they are.
Regarding RRTs, it’s an algorithm for the actual construction of the graph in higher-dimensions (because spatial discretization becomes a problem), so it simply adds a zeroth step.

I’m nitpicky at this moment, but none of these are truly any-angle, it’s just the techniques to get something smoother that what is prescribed by the initial discretization, or the discretization itself is irregular to begin with.

1 Like

sadly, this is why I’m not sure if it helps you at all. I simply don’t bother with navmeshes exactly for this reason, all my games tend to be procedurally generated, so baking is a no go for me.

I’ve considered the A* project in the past, but it looked as an overkill in many regards, and its most sought features are behind a paywall anyway, and this is why I rolled my own.

A* in itself is very simple, you can check out Amit’s tutorials on A*
that should be enough. however, when it comes to pruning, maybe check out that theta* pseudo on wp, it should be sufficient. the whole business isn’t that hard to implement from scratch.

maybe there is something on github, but I wouldn’t know about that. haven’t looked it yet.
sorry if I’m choking you with the answers you didn’t need.

depending on what you want exactly, you can also consider the flow fields, I forgot the exact name of the algorithm, but it’s what planet coaster does with the crowds. and I think supreme commander used that as well. but in both games, obstacles aren’t exactly dynamic (though they implement flocking behavior and prevent actor collisions), so you’re either supposed to smartly rebake the flow fields locally, or to abandon idea and go for the actor-oriented pathfinding.

if I stumble upon anything else useful, I’ll drop by and paste it here, I’m interested in the subject for the same reasons that you highlighted. i.e. prototyping and quick assemblage of the foundational assets.

1 Like

A* is independent of the graph shape. It doesn’t necessarily have to a rectangular grid.

Unity’s NavMesh uses A*, but is not rectangular.

I’m not sure which project you mean by “A* Project”, but if you mean “Aron Granberg’s A* Pathfinding Project”:
https://arongranberg.com/astar/

This one has both rectangular graphs, mesh graphs, and point graphs (point graphs are where you set up your own graph point by point… so really ANY shape you want).

But yeah, A* is completely independent of the graph shape. All it needs to know if what nodes exist, and what are the neighbours (connections) between those nodes. It could be N-dimensional and it’ll still work.

Many people implement their simple A* hard coded with a grid graph. But it’s not necessary.

Case in point… here’s my implementation of A*:

Not one mention of a grid in it.

Rather it takes the graph in the shape of my IGraph interface:

And as you can see my graphs are defined only as a collection of nodes and a way to find the neighbours of the nodes:

    public interface IGraph<T> : IEnumerable<T>
    {

        int Count { get; }

        IEnumerable<T> GetNeighbours(T node);
        int GetNeighbours(T node, ICollection<T> buffer);
        bool Contains(T node);

    }

Here’s a gridgraph:

Here’s a hexgraph:

Here’s an arbitrary linked node graph:

Yes, perhaps a more precise wording would be “any angle constrained to rectilinear nodes”.

1 Like

Not at all. I’ve rolled by own A* in the past. As you noted, it is not that difficult. This is meant to be a fast project though (dev time not run time) and I was hoping to find something akin to the A* project for “any” angle paths.

1 Like

Great example there, but the real thing that is missing, is a good pruning technique which can be applied to A* result (to make it appear gridless, or “any angle”). Do you know about any?

Are you referring to aron granberg’s a*? Cause if not, I really suggest you check it out as a quick pick up and use system. It’s powerful and ready to use out of the box:
https://arongranberg.com/astar/

Pruning? What do you mean?

I feel like this thread is full of misplaced terminology. Like OP conflating A* with the graph, and ambiguously referring to some “A* project” like there’s only one “A* project” out there despite that A* is a long standing algorithm established in the 60’s completely independent of gaming and spatial pathfinding but has more to do with graph traversal in the sense of “graph theory”.
https://en.wikipedia.org/wiki/A*_search_algorithm

Do you mean path smoothing? Like taking the resulting path coming from A* and smoothing out the sharp angles that come from moving linearly from node to node?

I again point back to Aron Granberg’s project that has a path smoothing component with multiple path smoothing algorithms.

…

With that said I’ve done numerous kinds of smoothing before.

Like once when working on our stupid manatee puzzle game where a manatee trudged along in the water. We used a grid graph but didn’t go node to node. Rather instead we heading in the general direction of the next node until we were sufficiently close and trudged to the next node.

But also tacked on some collision detection slightly larger than our character. We casted this out ahead of the character to see if it bumped into things before moving… and if it did we averaged out heading that avoided the contact points.

It worked to create what looked like a lumbering fat manatee trudging through the water.

https://www.youtube.com/watch?v=2W6H6p2JzOY