NPC Pathfinding Tutorial

Pathfinding (NPC Follows Player/Aggro Monsters) - How to Make a 2D Game in Java #40

AI-generated summary and notes. Check quotations, numbers, and important claims against the source video. Captions may contain errors.

Watch the source video on YouTube

Estimated reading time: 27 minutes for the text on this page.

Summary

In this video, RyiSnow demonstrates how to implement a pathfinding algorithm in a 2D game developed in Java, allowing characters to navigate towards certain locations while avoiding obstacles. The video covers three use cases: setting a location on the map for a character to reach, making an NPC follow the player, and enabling monsters to aggro and chase the player. Using the A* (A-Star) algorithm, RyiSnow simplifies the complex process of pathfinding, emphasizing implementation over theoretical explanation. This practical guide is enhanced by step-by-step coding instructions, bringing realistic NPC movements to life in your game.

Highlights

Learn to make NPCs follow players seamlessly 🚶‍♂️➡️
Monsters turn aggressive when approached too closely! 🐲🔥
A* algorithm makes pathfinding precise and efficient 💡
Coding simplified with detailed step-by-step guidance 📜
Dynamic pathfinding adds depth to 2D world exploration 🌎

Key Takeaways

Implement pathfinding for NPCs to enhance gameplay 🎮
Use A* algorithm for efficient navigation paths 🗺️
Monsters can now aggro and chase players! 👾
Create complex NPC behaviors with minimal code ✨
Boost player interaction dynamics with pathfinding 🤝

Overview

Navigating game worlds can be complex, but with RyiSnow’s tutorial, implementing a pathfinding algorithm becomes straightforward. Using Java and the A* algorithm, you’ll learn how to make NPCs move intelligently, avoiding obstacles and interacting dynamically with players. Whether you're directing an NPC to a specific location or having a monster detect and chase the player, this guide covers all you need to design engaging game interactions.

The video starts with setting up a basic node structure and progresses to creating a pathfinder class that meticulously handles path creation and navigation. By following along, developers can gain insights into integrating A* efficiently without getting bogged down by the math-heavy part of the algorithm. The tutorial focuses on practical implementation, enabling game developers to enhance their projects quickly.

Engage players like never before by integrating pathfinding that lets NPCs and monsters react to player movements. These dynamic interactions not only make the game world more immersive but also allow for scalable complexity in gameplay scenarios. Whether it’s NPCs guiding players or monsters creating unexpected challenges, mastering pathfinding in Java can significantly elevate your game’s interactivity.

Chapters

00:00 - 00:30: Introduction to Pathfinding The chapter titled 'Introduction to Pathfinding' introduces the concept of implementing a pathfinding algorithm, which allows characters to navigate to a specified location while avoiding obstacles. The video tutorial presented by Rice Knope covers three examples: setting a goal point on a map for a character to reach, programming a character (referred to as 'the old man') to follow a player character, and a third example not completely described in the transcript.
00:30 - 01:00: Examples of Pathfinding Implementation The chapter titled 'Examples of Pathfinding Implementation' discusses the concept of pathfinding in programming, specifically focusing on how monsters chase player characters in a game. Although pathfinding is an advanced programming technique and was not initially planned, due to popular demand, it was included in the roadmap. The chapter focuses on the A* search algorithm, which is a popular method for pathfinding, and mentions the availability of a tutorial video on this topic.
01:00 - 01:30: A* Pathfinding Algorithm This chapter focuses on the implementation of the A* Pathfinding Algorithm within a 2D game setting. The speaker assumes that the audience is already familiar with the basic concepts of the A* algorithm and has referred to a previous video for foundational knowledge. The explanation is targeted towards understanding how to practically apply the algorithm rather than explaining its fundamental mechanics.
01:30 - 03:00: Setting Up the Node Class In the chapter titled 'Setting Up the Node Class,' the task is to implement the A* algorithm in a game. It starts with creating a package, naming it 'ai,' and then defining a class called 'Node.' In this class, several essential variables are declared, including 'node' and 'parent.' This section lays the groundwork for integrating the A* algorithm into the project by preparing the necessary data structures.
03:00 - 04:30: Creating the Pathfinder Class In this chapter, the focus is on creating the Pathfinder class. Various public methods and constructors are introduced, which facilitate the initialization and manipulation of nodes. The chapter highlights the use of boolean variables, the integration of costs (g, h, f costs), and how they are essential components in the Pathfinder class. This implementation is crucial for achieving optimal pathfinding in the respective application. Specific attention is given to the proper initialization of variables and how they contribute to the overall functionality of the class.
04:30 - 05:00: Open and Check Nodes Methods The chapter introduces a class designed to handle the pathfinding in a game. The class is named 'Pass Finder Game Panel.'
05:00 - 05:30: Tracking Path Method The chapter titled 'Tracking Path Method' discusses the concept of a node array list and the use of open and public released node lists in the context of path tracking. It likely explores algorithms or methods to efficiently manage and track paths using these lists.
05:30 - 06:30: Assigning Path to NPCs In the chapter titled 'Assigning Path to NPCs', the focus is on the technical aspects of assigning paths to Non-Playable Characters (NPCs) in game development. It begins with the introduction of the concept of 'nodes', where a current node is referred to as 'reached recall first'. This sets the stage for understanding how NPCs navigate within the game environment. The concept of a step is introduced, likely referring to the movement or progression from one node to another. The chapter then discusses the constructor, which is a fundamental part of programming that initializes objects. Finally, it introduces the 'public path finder', a method or function that interacts with the game panel, presumably to determine or display the paths for NPCs. The chapter is technical, aimed at those with programming and game development knowledge.
06:30 - 08:00: NPC Follows the Player In this chapter titled 'NPC Follows the Player', the focus is on implementing a system where an NPC (Non-Playable Character) can effectively follow the player within a game environment. The process begins with instantiating nodes, specifically using shading nodes and incorporating a new node, referred to as node recall. Additionally, a maximum border core is being utilized to ensure efficient functioning of these nodes. The chapter seems to delve into technical aspects of game development, particularly within the context of programming or scripting the behaviors of NPCs to interact with the player's movements dynamically.
08:00 - 09:00: Monsters Get Aggro In 'Monsters Get Aggro,' the chapter delves into the mechanics of the world law, where methods are employed from constructors to manage behaviors. It illustrates the process within a game scenario, utilizing while loops to control actions, reflecting on the strategies that lead to gains and losses, thereby engaging readers with a complex, detailed analysis of game dynamics that involve 'max world law' tactics.
09:00 - 10:30: Additional Features and Testing The chapter 'Additional Features and Testing' begins with the concept of creating a node for every tile on the map, indicating a programming or game development context. Further explanations on the implementation details are not provided in the transcript.
10:30 - 11:00: Conclusion In the conclusion, the focus is on resetting nodes for pathfinding in the game. It is emphasized that each time pathfinding is performed, previous results must be cleared to ensure the algorithm functions correctly. To achieve this, a secondary loop is used to reset all node data.

Pathfinding (NPC Follows Player/Aggro Monsters) - How to Make a 2D Game in Java #40 Transcription

00:00 - 00:30 hi guys this is rice knope in this video we will implement a pathfinding algorithm so the characters can walk to a certain location while avoiding solid tiles i will show you three examples the one is setting a point on the map as a goal and let the old man moves to it and the second example is making the old man follow the player character and the third example is making these
00:30 - 01:00 monsters agro so they start chasing the player character programming algorithm is kind of an advanced technique so this was not in my original road map but pathfinding was one of the top requests that i've received so i decided to add it we use an algorithm called a star search and recently i uploaded a tutorial video
01:00 - 01:30 about it and explained its fundamental mechanics in details so if you have no knowledge of a star pathfinding i recommend you to check my a star video first and run its basics so just so you know i will not explain about the algorithm itself in this video my explanation here will be focused on its implementation to this 2d game ok so from here i assume you already
01:30 - 02:00 know how a star algorithm works so let's implement it into our game they first create our package and name this like ai then create a class node class will declare some crosshand variables node parent
02:00 - 02:30 public print call public hint allow int g cost h cost into f cost and the boolean solid furlium open boolean checked the constructor public node and get call and allow
02:30 - 03:00 that oh no okay so this class is done then create a class to handle the pathfinding i'm going to name this pass finder game panel
03:00 - 03:30 and the node array list yeah open list also another list and this is public released node pass list node start
03:30 - 04:00 or node current node called reached recall first and also step okay that's it then constructor okay public pass finder and we receive game panel
04:00 - 04:30 and then we're going to instantiate this node instant shade nodes and node recall new node we're going to use this max border core uh max
04:30 - 05:00 world law and also here let's call this method from this constructor then create while loop marks all all and loss gp.max world law
05:00 - 05:30 okay so basically we create a node for every tile on the map okay then create another method
05:30 - 06:00 called reset nodes in the actual game we do this pathfinding again and again so every time we do it first we need to reset the previous result otherwise the algorithm doesn't work so we create another while loop and reset all the node data
06:00 - 06:30 node call solid equal first and also after this loop
06:30 - 07:00 so we're gonna reset this open list clear so we're gonna clear this open list and also this past list clear and uh call reached boolean is false and the step is zero so we reset everything then we create a method
07:00 - 07:30 called set nodes as the parameters we receive start call start cloud call call or allow and entity and the first we call this set nodes method and reset everything
07:30 - 08:00 and this is where we set the current node settings so we set the start core and solid to node and also set g h and f cost on each node so start node is node start call start log then current node so we set this start node as a current
08:00 - 08:30 node or node is called and after that we only add the current node to this open list and then create another while loop
08:30 - 09:00 and first we need to know which node should be solid so we can get a solid info from our tile class or other entity class so hint tile num equal gp.tile manager dot map tile num
09:00 - 09:30 and the gp.com and we're gonna pass this call and allow okay then we call this a tile array in the style manager and put this style number and check if collision status is true or not
09:30 - 10:00 and if it's solid then we set this nodes solid to status to true and we check the interactive tiles too for example if you have placed these dry trees we need to set the corresponding nodes solid so we scan the itil array
10:00 - 10:30 gp dot i tile one dot length and i press plus so make sure to add this dimension number and then check if beta type tile dot gp dot current map and index i
10:30 - 11:00 is distractible so if it's true then uh it is a solid object so i t call call gp dot i type gp dot current map x i dot world x divided by tile size so we can get the column number
11:00 - 11:30 and also love just copy and this time worldwide and we're gonna use this color on the love to set this node straight through yeah like this ah and also we need to check
11:30 - 12:00 not equal null otherwise we can get more pointer error so make sure to check if it's not equal no yep okay then we set cost on this node so we're gonna call this get cost method and pass node now
12:00 - 12:30 and so now we're going to create this get custom method so public or we don't get cost receive node and first we get g cost so we can get the g cost
12:30 - 13:00 then h cost page cost all right let's copy and this time not start nor but goal node or node so h cost is and finally f cost so the most important one so of course is
13:00 - 13:30 okay that's it so the node settings are done so now search the pass public boolean the search file call reached call first and also we set some limit so like step 500
13:30 - 14:00 and okay into all call current node dot cor into allow call current node dot love a current node dot checked equal to open list dot remove current node
14:00 - 14:30 and then open the up node if log minus one script away equal to zero so we're gonna open this node called lao minus one we're gonna create this method a bit later
14:30 - 15:00 okay so this time we're gonna use this max wall now max world hall okay let's create this open node method and if note that open equal first
15:00 - 15:30 and uh node that checked recall first and uh node.solid recall first then we can open this node for evaluation and also set current node as its parent and also we're gonna
15:30 - 16:00 add this to this open list so we can compare and so we can scan the nodes in the open list and find the best one and for loop so open list dot size
16:00 - 16:30 if open list dot get i dot f cost is smaller than best node f cost then we're gonna update this best node index and also best node f cost
16:30 - 17:00 and if f cost is key core check the g cost if open list dot get i thought g cost is smaller than this start to get a best node index
17:00 - 17:30 g cost so this time also we're gonna update this best node index if there is no node in the open list then we end this group so if open list dot size
17:30 - 18:00 is zero then we're gonna end this loop okay so current node open list that get best node index and if current node is call node
18:00 - 18:30 then a call reached recall true then we're gonna call track the path method that we're gonna create after this and also in every this while loop we're gonna increase this step and also finally so since this is a boolean so we're going to return boolean
18:30 - 19:00 return core reached and okay so let's create this method node current call call node the file current is not we call start node so we're gonna backtrack from the goal node to the start node
19:00 - 19:30 so this time we're gonna put these nodes to this path list so hot zero current one by one current equal current dot parent so we're gonna update the current node so this past list is pretty important with this list any pcs or monsters can track the path
19:30 - 20:00 okay so this pathfinder class is also done so now open this entity class and at the boolean public boolean home pass or something like that and we're going to use this old man npc class so for example let's change it so when you talk to this old man
20:00 - 20:30 she starts moving to a specific location when you play games this kind of thing often happens like when you talk to an npc he says just follow me or something like that and so he starts walking to the next town or nearby cave or something like that so when we talk to him we're gonna set his own path to true and then inside of this set action is we're gonna add an if statement
20:30 - 21:00 if on path equal true and so we're gonna put the rest in this else like this and what we do here is set its goal as coron the law
21:00 - 21:30 and the passes to a method called search pass that we will create after this let's assume this is the old man's home and when we talk to him he starts walking to this location okay let's get so call 12 under round nine so we're gonna set number gold core is
21:30 - 22:00 12 allow is nine then go back to the entity class and uh create this such path method so receive call call and call now but before working on this method we create another method and call the
22:00 - 22:30 public void check call region and we're gonna move this collision checking stuff in the update method to this new method and we just call this method from here because you know we need to check collision as we track the path and i thought having this collision checking stuff in a
22:30 - 23:00 separated method is more convenient so we don't need to type the same thing again okay first let's install j class in this game panel a public pass finder ap finder or something new find uh this
23:00 - 23:30 okay now let's work on this such path method here we get the start call and the log so start call and start law and this is where this entity is so world x plus solitary x divided by tile size so we can get a
23:30 - 24:00 call number of this entity okay so now we know start call start allow and call call goal now so next we're gonna call this signals method gp dot pe finder set nodes and the path start call start allows call call goal log and this is entity so
24:00 - 24:30 we're gonna pass this so we have passed necessary data to run the passage so we call this search method and check if it returns true so if gp.p finder dot such and so if it return true that means it has found a path so we can
24:30 - 25:00 guide this entity to the goal and the past data is in this path list and we check what node is in it certain number 0 and which is next to the start node and that's where this entity should go next and we get its word x and worldwide
25:00 - 25:30 next word x and the word y so i'm going to name this simply next x equal gp dot p finder so we're gonna call this pass list and get index zero call times tile size so we're gonna get its world x and the next y
25:30 - 26:00 is gp.p finder dot plus list dot get index zeros log times tile size then we also get these entities current solid areas positions okay i'm gonna name this n and left x and it is left x
26:00 - 26:30 equal a world x plus solid area.txt entities write x equal alt x plus solid edit or text plus solid area dot twist and entities top y equal or y
26:30 - 27:00 plus solid area dot y and entities bottom y equal worldwide plus solid area that y plus solid period height yep then we're going to use these numbers and compare these word x and the word y
27:00 - 27:30 and these entities word x and worldwide and decide a direction of this entity we're going to create a lot of if statements here to make sure this entity won't get stuck so this was pretty tricky and it took me a while to make it work and i don't think this is the only way but among many methods that i tried this worked good for me so i'm gonna show you how i did it
27:30 - 28:00 so we're gonna check entities top y is greater than next y and entities left x is greater or equal to next x and entities write x is smaller than next x plus g p dot tile size
28:00 - 28:30 so if these conditions are matched this entity can go up okay copy and paste and receive so we're going to check the opposite so top y is smaller than next y and these are the same so in this case this entity can go down
28:30 - 29:00 and as if entities top y is greater or equal to next y and entities bottom y is smaller than next y plus tile size and toy
29:00 - 29:30 and in that case this entity can go either left or right so we're gonna check that so if entities left x is greater than next x then direction should be left and if entities left x is
29:30 - 30:00 smaller than next x then direction should be right so with this we can cover most of the case but still there are some situations that none of these conditions are matched so we need to take care of other exceptions okay so tell us if a entity stop y is
30:00 - 30:30 greater than next to y and entities left x is greater than next x why i always type toy to y so in this case direction is either up or left because this entity's y position is below the next tile and also this entity is on
30:30 - 31:00 the right side of the next tile so yeah so the direction should be up or left so we set direction to up for now but we are not so sure maybe there is a collision tile above him so we're gonna call that check collision method and if collision
31:00 - 31:30 is true then direction is left and the next one is let's see if some entity top top y is greater than next y and this time entity left x is smaller than next
31:30 - 32:00 x then in this case direction should be up or right so first set direction to up and okay check collision and if collision is true then direction is right and two more there's if this time entity top y is
32:00 - 32:30 smaller than next y and entity left x is greater than next x in this case direction should be down or left so first set direction to down then
32:30 - 33:00 then check origin and if collision is true direction is left and a copy and paste and this time this entity left x is smaller than next x then uh
33:00 - 33:30 direction is down or right so change this to right okay yeah that's everything okay also if you want to stop the entity when it reaches the goal then so we need next call and next love
33:30 - 34:00 maybe we could have created this earlier love so if next call equal call and next love equal or love
34:00 - 34:30 then we're gonna set this on pass too fast so as long as this old man is on path it keeps calling this such pass method and getting the next tire information until it reaches a goal so i think it works now so let's check
34:30 - 35:00 all right talk to old man and then now he starts walking so he's going back to his home slowly though yeah yep yep yep so he's safely backing his home so the npc found the path and moved to
35:00 - 35:30 the goal location and we can also display his path on the screen in this title manager class click on volume draw path and they go through and here in this draw method so if draw paths go true
35:30 - 36:00 so basically we're gonna draw some rectangles and i'm gonna choose red half transparent thread and for loop we're gonna scan that path list and we need to get its screen x on the screen y so okay let's copy this
36:00 - 36:30 and the paste and the wall x is the gp.p finder dot list dot get index i dot co times time size so we get the word x and uh okay order y is
36:30 - 37:00 low times time size then we're gonna fill it and the screen next green y and type size all right let's check and okay let me change old man's walking speed a little bit so yeah yeah like this
37:00 - 37:30 so now we can see his path so he's tracking the path like this okay it's working good so next let's make him follow the player and it's actually pretty simple so we just change this call call and call love to
37:30 - 38:00 players position so change this to player that word x plus player that solid area dot x not to default x and so we're gonna divide it by tile size so we're gonna get the call number and okay so log is
38:00 - 38:30 worldwide why okay also yeah we need to disable this because if the player is a goal the old man instantly reaches a goal when we talk to him and the old man just stops following us so disable this okay and let's check
38:30 - 39:00 all right let's talk to him alright so now he starts following us yep so he automatically finds the shortest path to the player
39:00 - 39:30 yep okay i think so now the final part so monsters getting aggro and start attacking you or chasing you so let's open this slime class and this set action method is basically the same as the hold man so i think we can just copy
39:30 - 40:00 and paste copy paste okay so the goal is player and okay and so yeah this project dial so let's change this rhyme shoots locks only when you know they are grow
40:00 - 40:30 like when when it starts shooting rocks then we know they are angry or they are aggro so we can move in this one pass and probably we can increase the percentage more than 197 or something and now we decide conditions that this monster gets aggro and you can choose any conditions that you want and so here's an example i'm
40:30 - 41:00 gonna set two conditions the one is when player attacks this slime then it gets aggro 100 percent and the other one is when player gets close to it you know when when he gets in a certain distance so first one we can take care inside of this damaged reaction so instead of moving away from the sprayer when it
41:00 - 41:30 receives damage we set on pass to true so it instantly becomes aggro so right now they are passive but if you attack it then suddenly it becomes aggro and starts changing player all right and let's take care of the
41:30 - 42:00 other one as a condition so let's say if player gets close to this rhyme you know like within five tiles then it can get aggro and to handle that we override the update method fabric void update and first we gonna call update in its superclass because we
42:00 - 42:30 still need to handle the normal update stuff but after this we check the distance between player and this rhyme so we get the total distance as uh tile size so tile distance equal x distance plus
42:30 - 43:00 y distance divided by tide size and if so on path is false and uh tile distance is less than five then we can just set this on pass through here but i think i wanna randomize it a little bit so
43:00 - 43:30 i'm going to use london class and if i is greater than 50 or something so 50 percent of the time it becomes aggro because i thought it would be a bit uh robotic if you know slime always gets aggro 100 percent so i wanted to
43:30 - 44:00 randomize it a little bit and if you like you can also set the condition that this rhyme abandoned the chase like if you take 20 tiles distance then the slime gives up chasing you or something like that like pass if it's already on pass but the title distance is
44:00 - 44:30 greater than 20 or something then on passes files or something i'm i'm not gonna use this in this demo but uh yeah this is also another example okay i think that's everything all right let's check hope this works so if you're getting within
44:30 - 45:00 getting a five tile distance then i think that frame is aggro now so yeah so it starts shooting the lock okay let's pull more shrines and yeah now what okay let's talk to
45:00 - 45:30 old men to you follow me oh this looks pretty crazy all the slimes are chasing us what are we gonna do old man
45:30 - 46:00 oh they they are coming now they're here oops i died no i feel like i need a shield [Music] [Music] yep so now the slime gets aggro when
46:00 - 46:30 player gets too close to it so the battle suddenly becomes more challenging we've implemented a star pathfinding algorithm so now npcs and the monsters have an ability to find a path and get to the assigned goal so this definitely helps to create more complicated game mechanics so please utilize it however you want and make your game more interesting
46:30 - 47:00 thanks for watching and until next time [Music] you