# Play with pathfindingApril 24, 2013 6:39 AM   Subscribe

An interactive demonstration of different algorithms for finding the shortest path from one point to another on a uniform grid.

Includes the following algorithms:
posted by Jpfed (42 comments total) 59 users marked this as a favorite

I couldn't figure out the best way to include this in the post, but here is a fantastic description of how Dijkstra's algorithm works:
Think of what would happen if you "spill water" in the source vertex s. Water would start spreading simultaneously along the edges emanating from S. Let the amount of time it takes a water drop to cross an edge be proportional to its weight (that is - interpret the edge weights as "distances" and assume drops move at a constant speed). Then, for each vertex, the information you would like to have is "when did water first arrive here and where did it come from".

This is what Dijkstra's algorithm simulates. Think of the (continuous) water flow processs I described and consider the events of type "water gets to a certain vertex for the first time". These events can be ordered by their time of occurrence. There are |V| such events (assuming the graph is connected). Each iteration of Dijkstra's algorithm celebrates one such event. Ordering the vertices by the number of the iteration where they where extracted from Q and added to S is the same as ordering them by the "time when water first arrived".
posted by Jpfed at 6:42 AM on April 24, 2013 [3 favorites]

MOST BORING TOWER DEFENSE EVER!
posted by Samizdata at 6:48 AM on April 24, 2013 [5 favorites]

Seriously, pretty cool.
posted by Samizdata at 6:48 AM on April 24, 2013 [1 favorite]

The idea of representing a vertex's distance with ∞ caused me to wonder: how do people represent infinity computationally? Is there a meaningful way to express the concept of infinity to a computer? Other than as some foo where foo + n = foo for all values of n?

Hooray for this post I love it
posted by Eideteker at 6:57 AM on April 24, 2013 [1 favorite]

Never heard of Jump Point Search; skimmed the article. on a network laid out like a grid on the linked Javascript sample, it looks like magic compared to the old standards. I wonder how it deals with networks that aren't laid out as two-dimensional grids.
posted by Yowser at 7:04 AM on April 24, 2013 [2 favorites]

Jump-point search is a beast! I had not seen that one before.
posted by burnmp3s at 7:04 AM on April 24, 2013

The idea of representing a vertex's distance with ∞ caused me to wonder: how do people represent infinity computationally? Is there a meaningful way to express the concept of infinity to a computer? Other than as some foo where foo + n = foo for all values of n?

Here is an explanation of how infinity is commonly represented in computers. Well, at least it explains what bit patterns are used for "infinity"; making that bit pattern "act like" infinity is normally the responsibility of the ALU (the part of the processor that just cares about doing math, rather than figuring out what to do next or shuttling bits around between registers/cache/main memory), but if the ALU doesn't support floating-point operations they can be emulated in software.
posted by Jpfed at 7:06 AM on April 24, 2013 [1 favorite]

It's also amazing how the old standbys look like so-called "flood fills" on a network set up as a two-dimensional graph. Of course, setting up a two-dimensional graph network in the first place strikes me as a special case, I've never conceptualized a network in this way to be honest and it strikes me as a rarity in the real world.
posted by Yowser at 7:07 AM on April 24, 2013

And of course, by network, I mean graph. I think social media has ruined me for Comp Sci.
posted by Yowser at 7:09 AM on April 24, 2013

Of course, setting up a two-dimensional grid network in the first place strikes me as a special case, I've never conceptualized a network in this way to be honest and it strikes me as a rarity in the real world.

It's certainly common enough in video games to be of interest. Also, note that the only algorithm here that actually requires a uniform-cost grid is jump-point; there's some interesting discussion in the last link about generalizing jump-point to other regular lattices.
posted by Jpfed at 7:12 AM on April 24, 2013

This is very cool. Great find.
posted by three blind mice at 7:20 AM on April 24, 2013

At a higher level, representing infinity as "some foo" works fine. Many programming languages define custom results for mathematical operations -- so [thing of type foo] + [thing of type bar] can be handled by a special function that knows how to add foo and bar. Then you can create a special object named Infinity, which defines what its results should be for various mathematical operations.

For example, here's a quick session in javascript -- you can follow along at home by hitting Ctrl-shift-J in Chrome if you want to see what else Infinity can do:
> i=Infinity // Infinity is just an object, so we can copy it to a variable called "i" for easy typing

> i*10
Infinity

> i/i
NaN

> 10/i
0

> i*i
Infinity

> i/0
Infinity
Maybe this is doing what Jpfed describes under the hood; I'm just poking at the surface. But what I'm describing works as a general concept -- if you wanted to do more complex math with the concept of infinity than was supported by your hardware, you could define your own thing named "Infinity" with other things it knew how to do.
posted by jhc at 7:22 AM on April 24, 2013

Jump point is basically A* plus this:

prune the set of immediate neighbours around a node by trying to prove that an optimal path exists from the parent of the current node to each neighbour and that path does not involve visiting the current node.

So trim out any nodes from the search which would lead straight back to the current node. Duh. These things always seem so obvious, after somebody else discovers them...
posted by ook at 7:38 AM on April 24, 2013 [5 favorites]

how do people represent infinity computationally?

There's also the complicated explanation. Even simple arithmetic in computers can be deceptively tricky (which is why this guide exists).

That's why I avoid the whole issue and just use INT_MAX.
posted by RobotVoodooPower at 7:48 AM on April 24, 2013

Eideteker: " how do people represent infinity computationally?"

Infinity is one part of a larger class in computing that represents DEEP HURTING for the uninitiated and unwary:

What does -1.#IND mean? (indefinite Not-A-Number)

How do I access the magic IEEE floating point values like NaN in code? (internals, but also don't do that.)

What does 1#J mean? A strange corner case of the printing of special values (What happens when you treat infinity like a countable number?)
posted by boo_radley at 8:20 AM on April 24, 2013 [6 favorites]

RobotVoodooPower: "That's why I avoid the whole issue and just use INT_MAX."

And for those of you picking things up, RobotVoodooPower is joking with one of those DEEP HURTING examples.
posted by boo_radley at 8:29 AM on April 24, 2013 [1 favorite]

I now want someone to make a Dwarf Fortress importer for this, so I can see why it takes my dwarves so freaking long to get across the fortress, what areas I need to mark as high-cost, etc.

Also I would love to see some face offs between the different algorithms on some huge fortresses.

That said, I noticed a way to break all of them in this implementation: Enable diagonals. Now create a structure that has the end point in it, and all surrounding squares as barriers except one of the corners. It won't find that diagonal path inwards. However, if I remove one of the barriers adjacent to that corner, it will then use that corner to make the shortest path.

Something like: (o = open, *=wall, x = goal)

o**
*x*
***

Will never be found, but
oo*
*x*
***

Works just fine, and uses the corner diagonal as the shortest path.
posted by Canageek at 8:47 AM on April 24, 2013 [2 favorites]

Path finding is still a remarkably hard problem for games. A lot of games pre-calculate shortest paths for every point on the map, units can use those to find their way.

There's a lot of great path finding resources on Amit Patel's game programming site. That site deserves a whole MeFi post of its own, lots of great content hidden in there.
posted by Nelson at 8:55 AM on April 24, 2013 [1 favorite]

That site deserves a whole MeFi post of its own, lots of great content hidden in there.

For some time I've been hoping to include it in a more detailed (Rhaomi-style) game programming FPP at some point in the future, which is why I didn't link to it in this post.
posted by Jpfed at 8:58 AM on April 24, 2013

Hmm, so I guess the only way to perform operations or represent different levels of infinity is to essentially use an object. So in terms of a computer "understanding" infinity, they "can't"—but then again, neither can we—other than as a set of rules governing its behavior under sets of specific circumstances.

This is all very helpful/informative. I really appreciate it, and hope it's not too big of a derail. I'm trying to teach myself some basic computer science (beyond just "programming languages"), so I'm just starting to enjoy things like pathfinding and sorting algorithms (I'm more of a pencil+paper computer scientist, at this point. Graph paper, that is (♥graph paper♥)).
posted by Eideteker at 9:12 AM on April 24, 2013

That said, I noticed a way to break all of them in this implementation: Enable diagonals. Now create a structure that has the end point in it, and all surrounding squares as barriers except one of the corners. It won't find that diagonal path inwards.

More generally, it will not take any diagonal path whose next step could not be reached by an orthogonal path.
posted by Jpfed at 9:35 AM on April 24, 2013

(I'm more of a pencil+paper computer scientist, at this point. Graph paper, that is (♥graph paper♥)).

The head of the CS department at the school I went to told us all on the first day of his programming languages course that he hadn't coded anything for at least twenty years, so in that regard you're not in bad company.
posted by invitapriore at 9:44 AM on April 24, 2013

Eideteker: "Hmm, so I guess the only way to perform operations or represent different levels of infinity is to essentially use an object."

More generally, you agree on a value -- objects came later.

Here's a basic puzzle to highlight the example: A pointer is usually sized to a word or a dword. What's the value of a NULL pointer? What does NULL guarantee? How does the value of NULL fulfill that guarantee?
posted by boo_radley at 9:51 AM on April 24, 2013

So in terms of a computer "understanding" infinity, they "can't"—but then again, neither can we—other than as a set of rules governing its behavior under sets of specific circumstances.

By the way, this is a very important realization in math. Knowing "what infinity really is" (whatever that really means) is not much use; what's needed to produce proofs of interesting facts and execute and design useful algorithms like those in the post is exactly knowing the "rules governing behaviour". And this has nothing to do with infinity; the same is true for, say, "understanding what a number really is", even though plain old numbers don't have infinity's reputation of being an unusually difficult or problematic concept. A big part of an undergraduate education in math is breaking the student's attachment to the everyday idea of "understanding" and building up a new attitude toward understanding, in which knowing the rules is not opposed to understanding, or independent, or complementary, but actually foundational. (Terry Tao on this subject.) (This is also discussed in Tim Gowers' A Very Short Introduction to Mathematics — paraphrasing a point made there about the imaginary numbers, we could say that most of the difficulties with concepts like infinity evaporate once we take the attitude that all that matters is which deductive steps are permissible and which are impermissible.)

I think folklore has it that this realization historically appeared as a result of trying to prove the parallel postulate in Euclidean geometry — or more precisely, trying to assimilate the discovery that it was impossible to prove it — but I don't know the actual history.
posted by stebulus at 10:00 AM on April 24, 2013 [7 favorites]

"Knowing "what infinity really is" (whatever that really means) is not much use"

Well, I'm a writer, first and foremost; always have been. Even in my deepest explorations of physics, mathematics, and philosophy. So I suppose the question as framed in my mind was: "How would I explain the concept of infinity to a computer?" treating it like a conversation or even a first-contact type of situation with any kind of machine intelligence. The fundamentals of mathematics and communication (or even communication through mathematics), a la the prime number sequence signaling in Contact, is something deeply fascinating to me. (I'm also prone to more abstract arguments like how exactly is Lt. Cmdr. Data's subjective experience of an emotion any different from an "actual" emotion; since, after all, an emotional response is just a specific set of signals—at some point, I'll find a way to unify my various backgrounds in psychology, [machine] intelligence and learning, mathematics, and philosophy (esp. epistemology) into something meaningful and useful to humanity. Should be easy, right?)

Again, this is really just a roundabout, chatty, and narcissistic way of saying I love this thread. <3
posted by Eideteker at 10:40 AM on April 24, 2013

The fundamentals of mathematics and communication (or even communication through mathematics), a la the prime number sequence signaling in Contact, is something deeply fascinating to me.

I have to get to work, but let me make one quick response to this — I think you might like Ted Chiang's short story "Story of Your Life", if you haven't read it already.
posted by stebulus at 10:57 AM on April 24, 2013 [1 favorite]

The example maps in the jump-point example are pretty sweet. Though it seems a little deceptive, visually, to pretend the pruned squares are 100% skipped-over.

The cool thing is, it finds corners! It makes me think you could make a pretty cute pre-calculated algorithm by finding all the corners, and then all paths become straight line walks from corner to corner (or from start to corner, or from corner to goal) as waypoints. One side effect would be more 'natural' paths of direct lines instead of arbitrary diagonal jooking to orthogonal alignment.
posted by fleacircus at 10:58 AM on April 24, 2013

I suppose the question as framed in my mind was: "How would I explain the concept of infinity to a computer?" treating it like a conversation or even a first-contact type of situation with any kind of machine intelligence.

When you start writing infinity down you usually have stopped talking about numbers and concrete values and I guess you're probably talking about the nature of a function as part of it goes off without bound or under some other process. (How did you explain the concept of variables to the machine intelligence?) Before, you were saying x=2+1 and now you're saying x=squirrel+1, so maybe the hard part is not explaining 'squirrel', but explaining what you now mean by +, =, and 1. Or maybe somebody already explained all that to the machine, and it's way ahead of you and would like to tell you that (1-1+1-1+1 ...) = cantaloupe.
posted by fleacircus at 11:32 AM on April 24, 2013

And BAM! then you've reimplemented YACC.
posted by boo_radley at 1:08 PM on April 24, 2013 [1 favorite]

Without thinking too much about it, I think the reason jump point search works so dramatically on the sample data is that the points in the search space a) have lots of neighbors and more importantly b) neighboring points share neighbors. This means that the pruning step tends to remove a lot. If you were searching on something that locally looked like connected braids or a branching tree, presumably there'd be less of an improvement.
posted by PMdixon at 2:51 PM on April 24, 2013

When you start writing infinity down you usually have stopped talking about numbers and concrete values ...

While that's true, what's surprising is that once you write down $\sqrt{2}$ you're already a few steps away from simple concrete values.
posted by benito.strauss at 3:35 PM on April 24, 2013

the nature of a function as part of it goes off without bound or under some other process.

In calculus, for example, that's very usual, that we treat statements involving infinity as shorthand for more complicated statements about limits, but in algorithms like those in the post, I don't think that manoeuvre is useful. I haven't studied all the algorithms here, but often the only relevant property of "infinity" is that it's an upper bound for everything, i.e., "x≤∞" is true no matter what x is. (This is why using INT_MAX can actually work.) For instance, Dijkstra's algorithm maintains a table giving the distance from the origin to other points (as far as it knows at each step), and it's tidier if all points can go in that table, even points that the algorithm hasn't found any path to at all yet. Putting as-yet-unfound points in the table with distance ∞ is a convenient device, and no limits are needed to justify or understand it.
posted by stebulus at 5:15 PM on April 24, 2013 [1 favorite]

That jump-point search looks pretty nifty and, according to the linked article, it doesn't require pre-processing. It looks pretty new, though. Does anyone know if this has made it into current game programming technology yet?
posted by mhum at 6:23 PM on April 24, 2013

I'm more of a pencil+paper computer scientist, at this point.

Computer Science is no more about computers than astronomy is about telescopes.
posted by 23 at 6:54 PM on April 24, 2013

once you write down $\sqrt{2}$

Holy crap, my browser supports MathML!
posted by stebulus at 7:44 PM on April 24, 2013 [2 favorites]

I know, right!?!? And I was guessing that MetaFilter was going to strip out the markup. I foresee lots of abuse creative uses.
posted by benito.strauss at 9:21 PM on April 24, 2013

Wikipedia says support is pretty uneven, and the cited info for Chrome 25 says they disabled it in that release because of "a high severity security issue" in the WebKit implementation. And the old school HTML fallback strategy of ignoring unknown tags means, I imagine, that lots of people see you saying that 2 is not a concrete value...
posted by stebulus at 9:51 PM on April 24, 2013

... 2 is not a concrete value...

I'll just refer them to this.
posted by benito.strauss at 10:04 PM on April 24, 2013 [1 favorite]

This infinity question is basic computer algebra stuff. When building computer algebra systems, you have lots of different kinds of objects (natural numbers, complex numbers, matrices, group elements, monoid elements, polynomials, polynomials over finite fields, etc etc etc), and really just need to define how things get combined (ie, added and multiplied) in different contexts. So you could do something like define a class with a name like extended_integers including the usual integers and an infinity object. The addition and multiplication methods are then trivial to write.

(Or at least, that's how we do things in Sage.)
posted by kaibutsu at 11:30 PM on April 24, 2013

If you like jump point search, you'll love Contraction Hierarchies. Geisberger's thesis is really quite readable, and the speedups are amazing! (Of course, a lot of pre-processing is required; there are techniques which require much less less preprocessing).
posted by novalis_dt at 4:03 AM on April 25, 2013 [1 favorite]

"Computer Science is no more about computers than astronomy is about telescopes."

Yah, but I didn't want to sound all smug and condescending (comp sci hipster?) because I'm still deep in n00b territory—I'm not better or worse for it, but I definitely prefer the pencil and paper aspects of CS. But for the sake of nerdly camaraderie, hands up everyone who's played Conway's Game of Life with pencil (or pen!) and paper. o/

reams and reams of notebook paper alongside/crammed into my copy of Gödel, Escher, Bach
posted by Eideteker at 8:48 AM on April 25, 2013

Now I really want to write that Roguelike.
posted by Artw at 9:34 AM on April 25, 2013

« Older Hooray a new friend!   |   Our Fair City Newer »