Пікірлер

• 
  @OnfeVS21 күн бұрын

  Tutorial de como usar blender please!

• 
  @darrant772323 күн бұрын

  Dijkstra: wait 19 seconds for a path, spend 35 minutes driving to destination. A*: wait 3 seconds for path, spend 1 hour 5 minutes driving to destination. I'd prefer Dijkstra, I think.

• 
  @andyrob6565Ай бұрын

  why does it flash bang me when it finds the path?

• 
  @julienboistel914Ай бұрын

  Great visu ! Do you have a Git where we can follow your work ?

• 
  @AbdulSamad-kb3smАй бұрын

  Wonderful!! Just wow ✨✨✨

• 
  @alwaysluffy.Ай бұрын

  Hello, Please can someone tell me how to do this, is there any github repo on this project, please let me know if anyone has resources on this ?

• 
  @ujjwalagrawal3669Ай бұрын

  Code please ???

• 
  @MartijnMols2 ай бұрын

  would be cool to see how you made the visualisations

• 
  @Sam-bt4fm2 ай бұрын

  Does A* have to flashbang us?

• 
  @Juni_Dingo2 ай бұрын

  That poorly-implemented A* reminds me of that ancient Intel joke: me: what's 27/14 pentium: 3 me: that's wrong pentium: maybe, but fast!

• 
  @wlockuz44672 ай бұрын

  Looking at the video description, you can implement A* with greedy-best-first search since those are two different algorithms. So this is more of a Djikstra va Greedy-best-first search.

• 
  @EdKolis2 ай бұрын

  Dijkstra: The evil empire is hunting for you. A*: The evil empire is hunting for you - and they have spies everywhere.

• 
  @Edvit402 ай бұрын

  WHY DID YOU FLASHBANG MEEEEEEEEEE

• 
  @quint3ssent1a2 ай бұрын

  Dijkstra is like doing work meticulously. A* is like doing "ehh, whatever, close enough."

• 
  @m.sierra52582 ай бұрын

  That's not true; A* also finds the best solution. It just has extra information to prevent it from walking in the wrong direction. As a sidenote: The algorithm shown in the video is not an A*, it seems to be a greedy heuristic path finding algorithm. A* is guaranteed to return the same result as Djikstra. Djikstra can actually be expressed as an A* with the "walk in the right direction" heuristic set to zero.

• 
  @LoPhatKao2 ай бұрын

  is it faster to climb straight over a mountain or go around it? the length of the path may be longer, but the amount of time it takes to traverse is shorter i submit that the a* implementation found the shortest *temporal* route the expressways and bypasses it picked _should_ be faster timewise due to their higher speed limits and lower number of traffic lights

• 
  @rubenlarochelle18812 ай бұрын

  So it comes down to: "Are you more in a rush of finding a path or to actually go there?"

• 
  @dongameleone24892 ай бұрын

  what? you are unable to at least read some english text and tell us what tf is that a* algorithm?

• 
  @andrewmerrick6012 ай бұрын

  This is not the fastest route on either one, this is a simulation of a path of least resistance (A*) and the other is a simulation of first discovery (Dijkstra) both can connect the dots, neither are exactly accurate. A* is unable to represent the speed of an object since Evey line has its own speed. Every intersection is a dilemma, and the less decisions it has to make the faster it moves. Dijkstra is unable to connect obvious paths if the map appears broken until a path that connects the two is discovered. It then automatically assumes that this is the fastest path (first discovery) as seen in the last example. Even if there is a more efficient path.

• 
  @MrGhosT29.2 ай бұрын

  Para saber realmente cual es mejor seria probandolo en la vida real los dos tipos de sistemas, teniendo en cuenta el trafico y las distintas velocidades de las vias ya que muchas veces el mas corto no es el mas rapido

• 
  @NguyenGiang_Basic3 ай бұрын

  finnally I found it, thanks <3

• 
  @KremitDeFrog4 ай бұрын

  A* is so much faster that it can afford to find a number of more paths so it can then evaluate the shortest of those.. and still likely finish processing faster than Dijkstra.. so it would be faster and very likely to provide the shortest route every time..

• 
  @JeremiahFlights5 ай бұрын

  At 2:13 the A* should never have gone to the top left of the map. Something is wrong here.

• 
  @adamschneider8685 ай бұрын

  Is it possible for Dijkstras algorithm to log all the paths to all the nodes it searched on the journey to its Destination? Then you store these for later retrieval?

• 
  @Speiger5 ай бұрын

  Fun fact. A* breaks apart when you have more then 1 target. Because it turns into O(X) while the other one stays at O(1) no matter how many targets are left.

• 
  @arikontinen76885 ай бұрын

  Fun fact. A* does not break with multiple goals if you know what you are doing. Just search in reverse. Make the original start the goal and all the original goals as open nodes and it trivially finds the closest goal in a single search. It also works just fine with multiple goals if you just make the heuristic be the euclidian distance to the nearest goal. It will take longer than the reverse search but it will still give you the shortest path with only a single search. The only thing that breaks A* is wormholes(nodes with a cost of zero in between them). For all other problems you might encounter while using A* there is a simple solution if you know what you are doing.

• 
  @Speiger5 ай бұрын

  @@arikontinen7688 It breaks apart because the computational cost becomes just that much worse, while Dijkstra's algorithm stays the same. Ofc you can try to optimize the way you aproach it, but A* stays always in the multiplier cost and sadly that's not avoidable :) Also you can optimize Dijkstra's algorithm to be a lot quicker. If your target is rather close and you know the distance you can simply stop nodes from scanning if their total travel distance exceeded the furthest target distance reached. And you can keep track if all targets were found :)

• 
  @arikontinen76885 ай бұрын

  @@Speiger Yeah sorry to tell you this but you are just wrong. A* will always be the same or fewer operations than dijkstra no matter what you are doing. Does not matter if you have multiple targets or not. If you only need to find the best path to any one of the targets A* will be better. If you need a path that visits all the targets then use A* to find distances between each pair and after that solve for the traveling salesman problem. If you try to use dijkstra to find a path that visits all targets directly without first working out the distance between pairs etc it will scale O(X^X) and you will regret your decision to even attempt doing it that way. And if you are not trying to solve the traveling salesman problem you should never need to find a path to all the targets. Just the closest one. If your implementations show a different result then you implemented A* wrong or your graph is too small that the difference gets lost in the noise. Also dijkstra is not O(1). Both dijkstra and A* scale with the size of the graph. A* however scales a lot better. If someone claims there is a situation where dijkstra scales better than A* they do not know what they are talking about.

• 
  @Speiger5 ай бұрын

  ​@@arikontinen7688 You misunderstood the problem. Lets take for example Oxygen not included (ONI) Which is a game where a dupe (character) can walk to a resource and pick it up. The problem is that there can be hundreds or thousands of resource objects laying around. When you use A* to calculate paths you either have to do each one one by one, which technically you could multithread. Or you could use dijkstra to simply scan the entire map and have paths to every single one in 1 rush. The traveling merchants problem has nothing to do with dijkstra's strengths, its an entirely different problem because it assumes 1 starting point and you want to visit all targets in the fastest order, while dijkstra's strength is: I want to find X and i have 500 possible connections, which one is the closest or which are the paths to all of them. Edit: Knowing all paths can be also useful because you can simply cache them and update them as you walk so you don't have to path again. A* will simply break by the amount of overhead due to duplicated work since it can't really keep existing work and unless all paths have 0 overlap you are a lot faster with dijkstra then with A* To go back to ONI, you will have a ton of duplicated pathing which means dijkstra's algorithm will simply outperform A* by miles. If you can't see that in this scenario which is really common in building games then i am sorry you have no idea you are talking about. Now to make concessions: dijkstra isn't the perfect algorithm that beats everything. It is really good if you have a ton of targets or don't know where your targets are like you can not calculate a "distance" at all. But the moment either of these are not a factor it breaks apart and is really slow. A* on the other hand is really good if you have information about distance and you have single targets. Which a TON of cases have. Then A* is really hard to beat. But A* isn't as perfect as people make it out to be. Know the cons and strengths of your algorithms.

• 
  @arikontinen76884 ай бұрын

  @@Speiger No. You misunderstood the solution. A* does not need to do any duplicated work. In your ONI example with A* you would put all the resources as open nodes(starting postitions) and the dupe as the goal. Initiate the search and it will find the closest resource to the dupe faster than dijkstra with a single search no duplicate work needed. Or if you want to search from the dupe to the resources, your heuristics is the distance to the resource closest to the node but that is the slower approach as your heuristic function becomes quite slow. You do not do them one by one. You add them all at the same time and the algorithm searches from the best candidates first. If you actually understood how these algorithms work you would have known that. Dijkstra is just A* with a heuristic of 0. Which means that no matter what as long as the heuristic is admissible(the guessed distance to the goal is always smaller or equal to the real distance) then at the worst case scenario A* matches dijkstra and on average it always beats it. It only breaks if the graph contains nodes with a cost of 0 or lower between them because that forces the guess to always be zero which effectively forces it to perform the same as dijkstra. This is a fact and no matter how you try to define the problem it will not change. If your heuristic is admissible A* will never search a node that dijkstra does not search. If the heuristic is admissible then there is no problem where A* would search more nodes than dijkstra. It is simply impossible. Any time you think you have found a case where dijkstra is better than A* you have just implemented A* wrong.

• 
  @johndeleon87415 ай бұрын

  Either that A* is not properly implemented or they're using a Potato as heuristic.

• 
  @uwuowo48565 ай бұрын

  Singapore research !

• 
  @marcomaltschik69515 ай бұрын

  A* is optimized dijkstra. If yout set the weight of the cost funtion to zero in A*, you basically only the path information(Dijkstra).

• 
  @klimmesil95855 ай бұрын

  Fix the title this is not A* it's just A

• 
  @flippert05 ай бұрын

  Of course it starts in Rome. All roads lead to Rome.

• 
  @josiahjack4555 ай бұрын

  Turns out one cannot simply use the Manhattan distance in Manhattan.

• 
  @JordanMcCaughey5 ай бұрын

  A* is not implemented correctly. Why bother looking for a first arbitrary path solution, we want the shortest.

• 
  @thesimpilot20225 ай бұрын

  Is it possible to merge the intentions of both algorithms to find a partially efficient path while also ensuring there’s a lesser time for the algorithm to calculate?

• 
  @thesimpilot20225 ай бұрын

  I read through like 5 comments and I figured out they were people with an intellectual level 10 times higher that my standard 9th grade A scoring self right when I saw heuristic checking as a term

• 
  @Karak-_-5 ай бұрын

  In a way, yes. What they claim is "A*" is not really A* it's Greedy-Best-First Search. When make a path, Dijkstra makes decisions based on distance from start to the next step, while Greedy-Best-First Search makes decisions based on distance it (inaccuraty) guesses (that's the heuristic) there is between the next step. A true A* combines both aproaches and makes decision based on the sum of both.

• 
  @henrykkaufman14885 ай бұрын

  Those algos might seem similar to unexperienced programmers, but they are diffirent things and serve diffirent purposes. A* is a pathfinding algorithm and Djkstra is a mapping algorithm. Therefore it processes much more data than A* given the same dataset. For example, in a game, use djkstra to map information on the game envirnoment for AI, and use A* for player controlled entities.

• 
  @blissful49925 ай бұрын

  No. A* is an extension of Dijkstra's algorithm. A* achieves better performance by using heuristics to guide its search.

• 
  @ailst6 сағат бұрын

  @@blissful4992 I think you misunderstood the guy you replied to. Dijkstra isn't about finding the fastest path. It's about generating a map of all pathes to all possible destinations. If you use A* to map, that map would be incomplete as pathes that won't lead to your destination will not be further investigated. So you use A* if you know where you want to go and just want the fastest path and Dijkstra to get an idea of everywhere you could be going. For example in a game that simulates tactical combat of ranged units there are a lot of aspects of how to evaluate the usefulness of a specific tile. I want to compare all of my options and thus also need the path-length to all of them. Dijkstra populates the pathing-distances for every single tile of my game-map with a single function-call.

• 
  @blissful49926 сағат бұрын

  @@ailst False. The entire point of the Dijkstra algorithm is finding the shortest path between two nodes in a weighted graph. E. W. Dijkstra outlined this when he published his algorithm in "A note on two problems in connexion with graphs" in Numerische Mathematik. Its the entire point of Dijkstra's algorithm, the A algorithm, and A-star algorithm. Your statement is completely deranged. Dijkstra's algorithm comes from a solution proposed to the second problem in his article "Problem 2. Find the path of minimum total length between two given nodes P and Q [in a weighted graph]."Numerische Mathematik l, 269- 27I (l 959) Furthermore Dijkstra's algorithm and the A* algorithm both guarantee finding the shortest path (A* depending on the heuristic). The A algorithm however does not. A* is a variation of the A algorithm where h(n) <= h*(n), h(n) being the heuristic cost to the goal, and h*(n) the actual cost to the goal.

• 
  @llejk5 ай бұрын

  I think you used a bad heuristic for A* . I was yelling “Manhattan Distance” at my screen, i bet that would work really well in NY example. Edit: Remembering A*, the heuristic works best if it (almost) always better than the real path. So euclidian distance at 60mph should work. Curious what you used?

• 
  @blissful49925 ай бұрын

  This isn’t A*. Look at the description

• 
  @speedstyle.5 ай бұрын

  Euclidean distance _is_ a heuristic, you didnt write a greedy algorithm (which would be Dijkstra's). And it is an admissible heuristic, even with obstacles, as it always underestimates (you can't go shorter than a straight line).

• 
  @abdulrahmanabunabhan49195 ай бұрын

  What was the heuristic function used in this implementation?

• 
  @blissful49925 ай бұрын

  They didnt use A*. They used Greedy-Best-First Search.

• 
  @omkarbhale4425 ай бұрын

  I just got flashbanged a few times

• 
  @aric77265 ай бұрын

  Why don't the source and target actually line up with the map

• 
  @TheMasonX235 ай бұрын

  Cool, but A* and Dijkstra should return the same shortest path

• 
  @myithspa255 ай бұрын

  Why is that?

• 
  @Zeos-pk3wh5 ай бұрын

  @@myithspa25because if implemented correctly, both algortihms should return the single shortest path, of which there is only one

• 
  @blissful49925 ай бұрын

  @@Zeos-pk3wh Not necessarily only ONE, but only one length yes

• 
  @mx.olydian21115 ай бұрын

  Nope, Dijkstra searches all directions evenly whereas A* is weighted by the "as the crow flies" distance to the objective Dijkstra always find the shortest path, A* compromises that goal to prioritise minimising search time, they behave totally differently

• 
  @tylerbakeman5 ай бұрын

  A* is fast, but it’s weakness is obvious: moving backwards as part of the solution

• 
  @camelotenglishtuition63945 ай бұрын

  Beautifully animated

• 
  @tvguyofnature5 ай бұрын

  This is wild but the location you chose on the new york map is my house

• 
  @FutureAIDev20155 ай бұрын

  Dijkstra's algorithm looks like how a slime mold navigates toward food.

• 
  @nabeelsherazi88606 ай бұрын

  your description says you used “greedy best first logic” - that is not A* which is why you don’t get the optimal solution

• 
  @SebastianPuertaCO6 ай бұрын

  Can you make a tutorial of how make this?, this is incredible

• 
  @BooleanDisorder6 ай бұрын

  Imagine an AI enhanced A* algorithm that has been trained on billions of these examples.

• 
  @nicolasmeddour89206 ай бұрын

  And your source of inspiration : kzread.info/dash/bejne/dZuLkqqJeNSsdZs.html&ab_channel=onesandzeros ;)

• 
  @Squirrel-zq6oe6 ай бұрын

  You could have shortened this video by probably at least a minute by not pausing so long dude.

• 
  @blissful49925 ай бұрын

  ... and implementing A* correctly

• 
  @0MVR_06 ай бұрын

  a star assumes to always know the absolute distance

• 
  @blissful49925 ай бұрын

  no, thats a heuristic, not the algorithm itself

• 
  @0MVR_05 ай бұрын

  @blissful4992 actually that is a part of the algorithm. A heuristic can have a portion of total knowledge, rather than exclusively local vantage. A star is only more efficient because the bird's eye distance of each node to the destination is known, which is a form of optimal selection filtering. edit: literally called a star because "true north" is calculable

• 
  @blissful49925 ай бұрын

  @@0MVR_0 False. Multiple heuristics exist that aren’t purely based on distance. Different distance heuristics exist aswell, like Euclidean and Manhattan.

• 
  @0MVR_05 ай бұрын

  @@blissful4992 pedantic and irrelevant. a star utilizes absolute meter which is the critical factor for its optimality

• 
  @jakobseitz11766 ай бұрын

  Nice video, even though its not really a fair race since dijkstra needs no information about the location of the goal but a* does. They are not built to solve the same problem but rather for different scenarios

• 
  @blissful49925 ай бұрын

  A* doesn't necessarily need the location of the goal. You are referring to a specific heuristic (that calculates distance for example) used in tandem with A*. Dijkstra is A* with a uniform heuristic. A* is Dijkstra with admissible heuristics.

• 
  @zeroanims41135 ай бұрын

  @@blissful4992 and what do you think is needed by the heuristic used by A* to calculate distance? exactly, an information about the location of the goal (e.g. coordinates) just like the commenter said.

• 
  @blissful49925 ай бұрын

  @@zeroanims4113 Please go educate yourself on A-star. Distance isn’t necessarily required to make a heuristic for A-star. In a map application scenario you can use: road length, traffic, steepness, narrowness, among other things. A-star doesn’t calculate distance by default. It’s the addition of a heuristic that allows it to do so.

• 
  @zeroanims41135 ай бұрын

  @@blissful4992 and isn't road length, traffic, steepness, narrowness, etc... an extra information required by a*? that's the point of the original comment, and my reply is just another example of extra information a* might use (distance). Again, the only point we're making here is that dijkstra uses no other information, but a* does. Do you agree?

• 
  @blissful49925 ай бұрын

  @@zeroanims4113 No, it’s not required by A*. Actually if you give a heuristic of a constant value to A-star it behaves exactly like Dijkstra. That’s the point and it’s why you’re wrong. Sorry. A-star doesn’t need extra information, it just performs better with it.