5
\$\begingroup\$

Pretty much whenever anyone thinks about pathfinding, they think about algorithms like A* and DFS - graph search algorithms, which also just so happen to work as pathfinding algorithms when you quantize the space you're pathing in into a graph.

What if that's not an option, though? Are there efficient pathfinding algorithms that work in space that hasn't been split in to chunks? The "left hand rule" is one example; walk forward and when you hit a wall, turn left - but there's plenty of situations where that won't ever find the target. Are there others like that?

\$\endgroup\$
2
  • \$\begingroup\$ The left hand rule, hill climbing, potential fields, etc. are all local rules that can work in a continuous space. As far as I know, none of them can guarantee a shortest path. The main reason to use the graph search is that they analyze more than just your local area. These are often combined — a very coarse global analysis with detailed paths found with local analysis. Do you have a specific type of map in mind that can't be turned into a graph? \$\endgroup\$
    – amitp
    Nov 1, 2016 at 17:30
  • \$\begingroup\$ @amitp It's mostly curiosity, although it'd be neat for building things in games like Garry's Mod where the engine's pathfinding system is inaccessible and processing power and support for complexity are very limited. I'm actually not too concerned about getting the shortest path; a path that doesn't have any obviously bizarre behavior like "walk in a circle for an hour then cross the room" would be sufficient. \$\endgroup\$
    – Schilcote
    Nov 1, 2016 at 19:59

2 Answers 2

6
\$\begingroup\$

Typically you would generate a visibility graph and perform pathfinding on that. Refer to this excellent page on map representations by amitp.

Given an open space with polygonal obstacles, the shortest path between any two points is either:

  • directly from start to finish, or
  • touches the boundaries of at least one of these obstacles

So if you generate a visibility graph, made up of the edges of all these obstacles and connected together based on visibility, any shortest path can be found using that graph. It looks something like this:

visibility graph

See how the shortest path touches some edges and corners, and the shortest path is completely within the visibility graph. This is a result that can be proven but it's pretty intuitive anyway.

\$\endgroup\$
2
  • \$\begingroup\$ What about in the case where touching an obstacle means instant death? \$\endgroup\$ Jan 20, 2020 at 0:53
  • 1
    \$\begingroup\$ @mLstudent33 The boundary doesn't have to be the exact physical point. Generally you'd take your own boundary into account too, such as by adding an offset to each of the points in the obstacle. You're completely free to increase that radius, but the premise remains exactly the same \$\endgroup\$
    – Mars
    Jan 28, 2020 at 6:49
2
\$\begingroup\$

As you suggest: Discrete (quantized) approaches like BFS, DFS, Dijkstra, A* etc. are typically used with traditional graphs, which form a discrete space.

For continuous (non-quantized) spaces, hill climbing suits better. Continuous (top) vs discrete:

enter image description here

That is, you can take a floating point space like this:

enter image description here

...and move intelligently across it, i.e. perform pathfinding, without needing individual quanta, i.e. nodes or cells. Note that the wireframe shown here exists only to indicate continuous values at that point as defined by f, not any kind of discrete topology. That is, there are infinite values available between every pair of grid lines (i.e. it is a real space).

We can see an example of hill climbing here:

enter image description here The algorithm is a simple one: find the closest point where the value is higher than the current point, and go there. This is simple enough in a static environment such a set of walls or mountains on a 2D plane.

But how does this relate to, say, seeking an enemy agent in a game? Agents can release/diffuse a scent on every update that creates a "hill" around them that follows them around, and allows others to seek them in that space. You can learn more about this by looking into collaborative diffusion.

Alternative

You can use classification, or "step" / quantise a continuous space (in 2 or 3 dimensions, this is but a 1D example):

float continuous = ...; //some floating point value in range 0..1 with precision down to n decimal places
int numSteps = 5; //some arbitrary integer value
int steppedInt = continuous * numSteps;
float steppedFloat = steppedInt / numSteps; //will be e.g. 0.0, 0.2, 0.4, 0.6, or 0.8

...Then operate on it using traditional discrete algorithms like A*.

\$\endgroup\$
2
  • \$\begingroup\$ Haven't read the link yet, but what makes hill climbing "continuous"? The image shown moves in very discrete steps, which would mean your "alternative" is more like step 1 \$\endgroup\$
    – Mars
    Jan 31, 2020 at 2:09
  • \$\begingroup\$ @Mars Read the question's requirement. Again, the point is that hill-climbing can be used in a non-quantised space by dynamically sampling points in that (2D, 3D) function. All other options are simply quantising a continuous space, which is not what was asked. \$\endgroup\$
    – Engineer
    Jan 31, 2020 at 6:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .