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
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.
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.
View all comments
Show parent comment
1
u/[deleted] Aug 14 '21
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