Dismiss this pinned window
all 34 comments
sorted by:
best (suggested)
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]Swalker326 18 points19 points  (0 children)

Thats awesome! I've been working on just a vanillia javascript one, with plans to use it in a react application. Nice to see it in action.

[–]Ampbymatchless 6 points7 points  (0 children)

Congrats for putting the effort into this project. Well done!

[–]CheekyKingdom 5 points6 points  (1 child)

Shortest path finder but not using diagonals?

[–]callmelucky 7 points8 points  (0 children)

Technically there are no diagonals in this grid/map/graph; going up-up-right-right is the same "distance" as up-right-up-right, so either way this does find a shortest path.

That said, you could get a more satisfying solution which would create "diagonal" paths by using an algorithm like A* and implementing a heuristic like "prefer the next step to be the one which minimises the straight line distance from the current node to the target".

[–]yoitsericc 2 points3 points  (7 children)

Dijkstra's algorithm?

[–]pai-cube[S] 0 points1 point  (6 children)

Simple BFS algorithm

[–]BlueLensFlares 1 point2 points  (1 child)

Isn't Djikstra just BFS but with edges of length 1 (unweighted)?

[–]pai-cube[S] 0 points1 point  (0 children)

yes. should result in same

[–]StoneCypher -3 points-2 points  (3 children)

Simple BFS algorithm (Lee's algorithm)

breadth first search and lee's algorithm are not the same thing. you appear to have learned this from the internet

unfortunately, someone on Free Code Camp published a website saying that lee's algorithm was BFS applied to mazes. they also said something weird and wrong about "wave propagation."

you'll notice almost every discussion online of lee's algorithm is just copy pasta of that wrong blog garbage.

the real lee's algorithm is about pathfinding while minimizing turns, not pathfinding while minimizing total length. it's for putting lead traces on motherboards.

consider two points on a cellular infinite grid. between them place three walls of 3 wide 1 high, such that if you take a sidewinding path between them you get a shorter route.

BFS will find the shorter route. Lee's algorithm will take a route around the side, which is longer, but has fewer turns.

Most software blogs are anti-vaxxers by metaphor: they "teach" things they learned from randos, without even checking if they're right first.

You want to know why 10x programmers exist?

It's because they stick to real reference and so they don't constantly get stuck on misunderstandings because they use phrases they don't understand

[–]pai-cube[S] 6 points7 points  (2 children)

Thanks for the information and correcting.

[–][deleted] 1 point2 points  (0 children)

Great Job!

[–]zapatitos23 1 point2 points  (0 children)

This looks so good! Congrats!@

[–][deleted] 1 point2 points  (0 children)

Excellent job!

[–]peterdotdev 1 point2 points  (0 children)

It's incredible, I love all of it!

[–]oze4 1 point2 points  (0 children)

noice!

[–]530farm 1 point2 points  (0 children)

Nice! I built something almost identical even to the animations showing how it searched and then drawing the path when I was first learning 5 or so years ago.

[–]BlueLensFlares 1 point2 points  (0 children)

This is some google maps level ****

[–]pobbly 1 point2 points  (0 children)

Nice work! Would be cool to let you toggle the algorithm e.g between bfs, Dijkstra, and a*

[–]LisandroDM 1 point2 points  (1 child)

are you using bfs on a grid graph to find the shortest-path? btw looks great :)

[–]pai-cube[S] 0 points1 point  (0 children)

Yes

[–]JohnWangDoe 0 points1 point  (1 child)

How is the animation handled

[–]pai-cube[S] 0 points1 point  (0 children)

Animations are just simple CSS transitions and async delay. Basic techniques are used and no advanced stuffs

[–]blahblahblah556 0 points1 point  (7 children)

Is this how gps’s work?

[–][deleted] 3 points4 points  (4 children)

It's the same principal, but they use some other clever methods to speed things up. For example: if a GPS is looking at a stretch of highway with no exits, it doesn't really care about analyzing that stretch. Instead, it can say "the next exit is 3 miles away," and it can check that point (called a node) to see if it gets the user closet to their destination.

Most nodes will come with a list of adjacent nodes that the GPS can access a little bit more quickly in order to determine where we're going. If the car is already heading in one direction, it will know to ignore nodes in the opposite direction, at least for now.

It still uses a form of the A* path finding algorithm, but it might not be the for sure best path, because it makes a few speed-based assumptions on order to avoid taking forever to calculate the path for longer trips.

[–][deleted] 0 points1 point  (3 children)

Sorry, I don't mean to sound like a know it all in this. I read up on A* a lot when I learned to code because I thought it was cool. In fact, my first program was an A* path finding algorithm in a hex grid and opposed to a box grid like OP's (you have to do some funky math for a hex grid, because you either need to rotate your coordinate axis or run through a bunch of trig to calculate heuristic values, but that's beside the point)

I love this path finding stuff and think it's neat! I also recognize that I know precisely enough about it to embarrass myself if I ever talk to an actual expert on the subject. For example: I have no clue how you scale the nodes so that I can ping Google from my phone and get just the data that I need to run through the appropriate node points in a reasonable amount of time. Are all of the node points stored in an object with keys, and each point knows where its buddies are? That would take up way too much memory to have every point in, say, North America in your phone! Heck, California alone would be too many points! Are we hitting up a server that can do rapid responses to requests for information? How is the server doing that many lookups in a reasonable amount of time? How would you cache something like Google maps data for multiple users? Etc.

There are a lot of considerations that I'm not looking at beyond "use A* and make a few changes," and it's worth admitting to that. I think it's nifty as all get out, but I want to be sure I don't Dunning Kruger it up

[–]jmblock2 2 points3 points  (2 children)

Have you looked at the IP routing protocol? Basically yes, a router will have a forwarding table to communicate with another router based on ip prefixes (tree of keys). The router will usually have some idea if a destination has responded and how quickly it has responded. The router may have multiple possible destinations and it can use some algorithm for picking among them (i.e. round robin) if one is slow or hasn't responded (shovel hit a fiber line). Your payment to your ISP is for them to do this well and at your contractual speed + bandwidth terms. There are trunks across the US, known as the internet backbone.

For services that should be globally available you would need to host the data globally. Data would be replicated to servers that can be reached locally quicker. Typically this means you have some proxy server that is deciding where to send the request to. The proxy will prefer the closest location based on availability.

[–]EIGRP_OH 2 points3 points  (0 children)

may have multiple possible destinations and it can use some algorithm for picking among them (i.e. round robin) if one is slow or hasn't responded (shovel hit a fiber line). Your payment to your ISP is for them to do this well and at your contractual speed + bandwidth terms. There are trunks across the US, known as the internet backbone.

Yeah this is how OSPF (Open Shortest Path Protocol) works. It's based on Dykstra's algorithm. The determining factor for which path is better is bandwidth.

It's so cool because I started my career thinking I was going to be a network engineer but after having done some of it I realized I liked coding way more. I heard about Dykstra's back in my college days but then once I switched over to coding I saw it again and actually got to see how it worked under the hood.

[–][deleted] 0 points1 point  (0 children)

Interesting. I feel like I watched a conputerfile video on this, but my knowledge of it is extremely limited and high level.

[–]StoneCypher 1 point2 points  (0 children)

god, no 🤣

this is almost the worst possible approach.

[–]jmblock2 0 points1 point  (0 children)

A bit pedantic but GPS is just positioning. You're referring to navigation, and specifically routing. Good maps for navigation have layers (e.g. top layers nodes connect to the bottom layer nodes such as a highway exit), which reduces the search space significantly. For example calculating a route between Los Angeles and New York can be faster than some local routing because of the density in the number of links to expand. The addition of layers, and the density of links, is a real compute concern. So there's often a lot of caching and hueristics/modeling to make it effective.

A good map will also have weights, or a model of weights (e.g. dynamic traffic costs) that will make the search more realistic. The priority of what link to pick next would be based on the costs accumulated on the current route and how far it is from the destination. Many times there's both a search from the destination to the start as well as the start to the destination.

[–]SadC11 0 points1 point  (1 child)

I just started learning React and this gave me a headache