Step by Step Explanation of A* Pathfinding Algorithm in Java
Here's a step-by-step explanation of how to create an A* path search algorithm demo program in Java.
A*(star) pathfinding algorithm is widely used in video game development to let characters find their path from point A to B.
Timestamps:
0:00 Introduction
2:40 Creating a demo panel
5:01 Creating Node class
7:45 Placing nodes on the panel
9:15 Setting the start node and the goal node
13:35 Setting solid nodes
15:13 G cost, H cost and F cost
21:52 How A* algorithm evaluate nodes
27:12 Open, evaluate and check
38:15 Implementing key input
40:20 Auto-search
42:27 Backtrack the nodes and draw the path
44:03 FINAL RESULT
Пікірлер: 73
*CORRECTION* 41:44 I used the "step" variable in the search() method but it was supposed to be in the autoSearch() method! It was my silly mistake. (Thank you Aung Linn for pointing this out) Also, I realized I didn't use the checkedList at all in this video. I thought I might use it to check what nodes are checked and when I reset the search result but we can handle both with the checked boolean so the list was not really necessary :P
@user-yx5rj2jv2d
9 ай бұрын
hello maybe there are some mistakes,300steps is easily passed by,we haven't set the FPS,so one ENTER key doesn't means many times?
Theres no way, Ive been following your tutorials and just had to make my own A star pathfinding algorithm in java, I finished it yesterday and now today you upload a video on it.
Wow you are the first person to make a great algothim demo in java! Thank you so much! Your video's mean so much!
Please continue to create these amazing tutorials!
I just found your channel and I'm already a fan. I'm already arranging to watch all your videos. Thank you so much for the content, you are amazing!
@RyiSnow
2 жыл бұрын
Welcome and I'm glad you liked it!
I sincerely want to thank you very much for giving me the energy to love coding even more
Great!!! I just implemented it too... I also learned this: To move many entities, there is also the solution using Flow Fields, its algorithm is similar to A* one, I implemented it in Java recently and the performance are good. With it you have to generate just one field for all the entities, the drawback is you have to generate one vector for each tile of the map, so for big maps you have to make tradeoffs. But with many entities it should outperform A* calculation for each entity.
Heeey RyiSnow!! That's awesome. I saw that recently in my cs major, really liked to see it here. Thank you for another video!
You are a treasure for us, thanks for these tutorials
Thank you very much, I was struggling to understand A* pathfinding, but this video helped me so much and I adapted it into my project which uses MVC architecture. Great tutorial.
Just GREAT!! After a lot of searching this is far the best i have seen from all views.. GREAT JOB!
@RyiSnow
6 ай бұрын
Thank you so much 😀
This is cool! Very well done and meticulously explained.
@RyiSnow
2 жыл бұрын
Thanks Edgar, glad you liked it!
As always amazing! Worth to mention it is closely related to Breadth First Search very useful for solving programming challenges of different sort!
Really good tutorial! I'm not coding in Java but I was able to follow along just fine implementing this in a C# based project. I was quite suprised at how intuitive A* pathfinding is in terms of set up
Congrats! You are the first person to make me understand A*
@RyiSnow
2 жыл бұрын
That's great to hear!
@mousabthebest8587
2 жыл бұрын
@@RyiSnow thank you so much for your help I am making a java game and this will help me
@mousabthebest8587
2 жыл бұрын
@@RyiSnow I have searched A* in google and I didnt understand anything
Thank you man, this video is very helpful and awesome.
Great Video as always!
Hello, I am very grateful to you for this video! Thank you so much. It works; One tip for MacOS users. For me the tiles would not change color by just using the method setBackground(); For example to make the start tile blue, I had to add setOpaque(true) and setBoarderPainted(false) as follows. public void setAsStart() setBackground(Color.BLUE); setForeground(Color.WHITE); setText("S"); setOpaque(true); // ensure that the button completely covers any background behind it. setBorderPainted(false); // if set to true The button will draw its border. start = true; }
@aprilpolubiec3097
2 ай бұрын
Thank you!!!! I also had to use setFocusPainted(false); to get the button outline to go away: public Node(int col, int row) { this.col = col; this.row = row; setBackground(Color.white); setForeground(Color.black); setOpaque(true); // ensure that the button completely covers any background behind it. setBorderPainted(false); // if set to true The button will draw its border. setFocusPainted(false); addActionListener(this); }
you dont understand how badly i wanted this video
Hi, I haven't been here for a long time, but I'm slowly coming back. All I can say is that one big WOW. Both this algorithm and the trading system. This is so great, I can't wait to do it myself. Please tell us if you plan to do quests? If I can ask, I would ask for a minimap and a day and night system. And most importantly, that you develop this project. You are the best java game developer na yt: D
@RyiSnow
2 жыл бұрын
Welcome back Michał. No plan for implementing quest system but since I've received a lot of requests for that maybe I will make it once all the essential mechanics are taken care of.
i started off watching your videos but stopped and started working on my own but had a nice base to work off of, this is extremely helpful for me!!!! thank you!!!!!
Thank you very much for the video.
ayo im first and also i saw a vid of you the other day and started with the code a game series and i think you explain it very well :)
Great video!
Wow. This is perfect. This will make my pacman's ghost ai so much better. Thank you.
Thank you so much!
If I put a Thread.sleep(1000); in the autosearch metodus for presentation, the program runs but the tiles do not change. Why is this?
Amazing!
Nice job here
amazing!!
May I ask that is the coding same for Mac OS?
Such a legend
If we move diagonally how can we calculate the cost?
Yeahhh all righthhhhht You rock dude!
Thanks!
Awesome tutorial, thank you so much! I'm trying to understand the evaluation part. I tried using the H cost for checking against the distance from the goal after the F cost check. It seems to me that the algorithm is faster that way, am I missing something in the logic?
@RyiSnow
Жыл бұрын
Hmm, I tested both and both took exactly the same steps to reach the goal.
So i stored the best path into a list array and made the entity move to it every second. Now the problem is when the entity reaches the goal i want to set the start node to the goal node and set a new goal node position, how do i do that? I hope you can reply❤❤
Wow!! I have been trying to implement such an algorithm but you know, I don't understand many of them And now, you have uploaded one with full explanation. Thank you. One Thing I don't understand is why you put ' step ' variable in " search "(i mean manual search) function? Shouldn't it be in " autoSearch " function?
@RyiSnow
2 жыл бұрын
Oooops did I? Yes, the step++ should be in the autoSearch(). That's my mistake. Sorry about that and thanks for pointing this out!
what if I got a one dimensional array for nodes?
Nice.
Hey Ryi! Please make a video on how to make a grappling hook in Java. I am struggling with it for a week now. Please don't ignore this request
Hi! Can you make a video using databases(mySQL) for the game? Please!
Hi any git reference to resulting code?
Awesome tutorial, even Java begginer like me could understand the principle. I just noticed something while trying to implement it myself. The way you used the while loop and step counter doesn't really seem to handle the cases when goal is unreachable. At least it did not for me. Unreachable goal would result in index out of bounds exception. Since you placed "step ++" outside the while loop, it seems to me it can't count the repetitions. And it also seems that having "currentNode = openList.get(bestNodeIndex)" outside the forloop leads to a situaton when, at some point, all reachable tiles are checked, the openList is empty and there's nothing left to add (nothing that passes the conditions) and at this point, for loop ends (because openList size is 0) but AFTER that, program tries to get an element from this empty list, which causes the exception. So, should "step++" be inside while loop and "currentNode = openList.get(bestNodeIndex)" be inside the for loop (cause that fixed the issue for me perfectly) or am I missing something?
Hi Ryi! When i set my nodes like that, it doesn't find the shortest path. Is A* algorithm finds the shortest path or am i missing something in my code? //SET START AND GOAL NODE setStartNode(4,7); setGoalNode(11,5); //PLACE SOLID NODES setSolidNode(10,2); setSolidNode(10,3); setSolidNode(10,4); setSolidNode(10,5); setSolidNode(10,6); setSolidNode(10,7); setSolidNode(6,2); setSolidNode(7,2); setSolidNode(8,2); setSolidNode(9,2); setSolidNode(11,7); setSolidNode(12,7); setSolidNode(6,1); setSolidNode(6,2); setSolidNode(6,2); setSolidNode(6,1); setSolidNode(7,7);
@RyiSnow
Жыл бұрын
Oh, you're right. I tested that setting and the path weren't the shortest one indeed. So I guess the current method doesn't necessarily produce the shortest one. Sorry about that! To always produce the shortest path, I think you need to re-evaluate the path when you set a parent or when you trace back to the start node.
@orangomango
Жыл бұрын
@@RyiSnow you should actually check the h cost after the f cost instead of the g cost. That's why it isn't working.
@3bood_kr
Жыл бұрын
@@orangomango you are right. i just tried both and checking the h cost after the g cost was shorter.
@orangomango
Жыл бұрын
@@3bood_kr That makes more sense, because you have to reach the end so the end distance should be the shortest
@toastonastick9381
6 күн бұрын
G cost should be true distance from start node
Can you make a video for sorting algorithm as well
Can you disponibilize the code somewhere?? It's hard to follow along without it.
I think every node's cost should be recalculated every step you make, otherwise you are not finding the shortest path. Am I wrong?
🥰🥰🥰
could you post code please?
@RyiSnow Great video and it has helped me massively to understand the graph traversing. But, I think, a small correction is needed. At 36:33 while defining the best node index, we need to consider hCost and not fcost. because despite of we declaring hcost, it's not being utilized anywhere. Event at the time of comapring fCost == bestNodeFCost, we are only checking for gCost as a secondary check, Shouldn't it be a hCost(which is heuristic cost, to reach to goal?) Without hCost it will be a Dijkstra's Algorithm, with hCost, it will be an A*. Anyway, I've made a simple comparison of these both in a video. kzread.info/dash/bejne/Y6ptk5qNndPFgbA.html&ab_channel=Ashishcw Let me know your thoughts.
please give me the source code
where is GIT?