Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Titandrake]

It doesn't look like BFS because some nodes towards the end aren't expanded as much, but the heuristic used doesn't seem that good either.

[eHalcyon]

I won a Snapfish 5x7" Photo Book at McDonald's Monopoly.  I have no desire to get a photo book.  Does anyone want it?  This is Canadian, so you might have to be Canadian to redeem it...

[florrat]

Similar animation for different heuristics:

No weights (Dijkstra's algorithm)


Euclidean distance


Inconsistent heuristic. Fast, but finds solution which is not optimal.

[blueblimp]

Euclidean distance is a weird heuristic to pick if your moves are compass directions and diagonals. Maximum of absolute coordinate distances would make more sense, since that's what the distance would be if there are no obstacles. Edit: Never mind, I didn't realize that the moves were being costed by their Euclidean distance. Still, a tighter heuristic would be  sqrt(2)*min + (max - min).

[heron]

Fun fact: In my mind, pacovf is pronounced pakov-vee.

[AndrewisFTTW]

Fun fact: In my mind, pacovf is pronounced pakov-vee.

That fact was not as fun as I hoped it'd be.

[Dsell]

I won a Snapfish 5x7" Photo Book at McDonald's Monopoly.  I have no desire to get a photo book.  Does anyone want it?  This is Canadian, so you might have to be Canadian to redeem it...

Give it to a family member who's in to that sort of thing. My mom makes Shutterfly (a competitor with a similar product) books all the time and loves them. They're really cool for documenting trips or occasions or just a year in the life. They're basically digital scrapbooks.

[pacovf]

Fun fact: In my mind, pacovf is pronounced pakov-vee.

That fact was not as fun as I hoped it'd be.

But it is random!

[Witherweaver]

Fun fact: In my mind, pacovf is pronounced pakov-vee.

In my mind, it's Pavlov.

[Tables]

Inconsistent heuristic. Fast, but finds solution which is not optimal.

Why is this non-optimal? It looks like it's the shortest distance to me, assuming we're counting distance in number of points not in actual line length.

[GeoLib]

Inconsistent heuristic. Fast, but finds solution which is not optimal.

Why is this non-optimal? It looks like it's the shortest distance to me, assuming we're counting distance in number of points not in actual line length.

It's counting actual distance. If you look at the description "The graph is created by uniform square discretization of a 2-dimensional planar region, placing a node in each discretized cell, and connecting each node with its 8 neighbors using bidirectional edges. Cost of edges are same as their Euclidean lengths."

[eHalcyon]

Fun fact: In my mind, pacovf is pronounced pakov-vee.

In my mind, it's Pavlov.

Whenever pacovf hears a bell, he feels the need to feed a dog.

[ashersky]

How awesome is falafel?

[AHoppy]

How awesome is falafel?

It has nothing on the kebab

[Kirian]

Similar animation for different heuristics:

[images]

So the bottom one gets an answer that's suboptimal by about 5%, but only takes 30% as long to complete... isn't that the one to go with so long as you don't need a perfectly optimal path?

[eHalcyon]

How awesome is falafel?

Well, it's not awful.

[WalrusMcFishSr]

How awesome is falafel?

There was a restaurant a block away from my college house which was open until 3 AM and had $2 falafel sandwiches...so awesome

[GeoLib]

Similar animation for different heuristics:

[images]

So the bottom one gets an answer that's suboptimal by about 5%, but only takes 30% as long to complete... isn't that the one to go with so long as you don't need a perfectly optimal path?

Given your assumption, yes. Approximation techniques are extremely powerful. If you're willing to settle for something a little bit less than optimal, then all kinds of problems become far more tractable (e.g. polynomial-time solutions for NP-hard problems).

Sometimes you really do want the very best solution though, and computers are so fast that it is also quite frequently worth it to use an algorithm that gives the optimal. Path finding is very much polynomial.

It depends on what you care about and what your constraints are.

[Titandrake]

I can't tell if my internet is dead and I'm seeing cached content or if it's just really slow, the forum still loads so here's a test post.

Edit: have confirmed that I can load this page and someone who hasn't been to the forum can load this page, but literally no other site is loading, so it's not a speed issue...

Edit 2: Somehow the DNS server was completely dead, except for on this site, which also explains why Hearthstone + Skype were still working. Pointing at Google's DNS, all good now, thank you for taking part in this real-time blogging of technical issues.

[pacovf]

I can't tell if my internet is dead and I'm seeing cached content or if it's just really slow, the forum still loads so here's a test post.

Edit: have confirmed that I can load this page and someone who hasn't been to the forum can load this page, but literally no other site is loading, so it's not a speed issue...

Edit 2: Somehow the DNS server was completely dead, except for on this site, which also explains why Hearthstone + Skype were still working. Pointing at Google's DNS, all good now, thank you for taking part in this real-time blogging of technical issues.

3/5 stars. Intense and suspenseful with a nice plot twist, but on the short side. Might watch again.

[Tables]

Inconsistent heuristic. Fast, but finds solution which is not optimal.

Why is this non-optimal? It looks like it's the shortest distance to me, assuming we're counting distance in number of points not in actual line length.

It's counting actual distance. If you look at the description "The graph is created by uniform square discretization of a 2-dimensional planar region, placing a node in each discretized cell, and connecting each node with its 8 neighbors using bidirectional edges. Cost of edges are same as their Euclidean lengths."

Right, okay. I thought that might be it but the use of dots made me suspect otherwise (and people are often bad at noticing in the kind of geometry where you move along a grid orthogonally or diagonally that zig-zagging is just as fast as a straight line).

[soulnet]

Sometimes you really do want the very best solution though, and computers are so fast that it is also quite frequently worth it to use an algorithm that gives the optimal. Path finding is very much polynomial.

Minimum path is actually linear. However, sometimes linear is not enough. Just imagine the number of nodes in the graph used to search for directions in Google Maps when entering addresses in different continents.

[Kuildeous]

Smashed my pinkie in a door that we move around on stage. Thankfully, the door's been redesigned so that that shouldn't happen again, but the damage has been done. I'll just be grateful that it wasn't too damaging.

Still not as bad as the time I did a stage fight and sliced my thumb on a rusty sickle. That was worrisome.

[silverspawn]

Smashed my pinkie in a door that we move around on stage.

[GeoLib]

Sometimes you really do want the very best solution though, and computers are so fast that it is also quite frequently worth it to use an algorithm that gives the optimal. Path finding is very much polynomial.

Minimum path is actually linear. However, sometimes linear is not enough. Just imagine the number of nodes in the graph used to search for directions in Google Maps when entering addresses in different continents.

Right, linear⊆polynomial, but I didn't go into specifics since it's linear wrt to edges, not nodes and a few other things depend on your implementation (which in turn probably depends on how complete you think your graph is). Certainly there are many cases where you'd like the speed, which is why I said sometimes. I think google does something where they break the world into chunks and work on the smaller sub-graphs and then cleverly stitch them together if necessary.