1 00:00:07,129 --> 00:00:09,758 Hi, welcome to this new video on our pathfinding series. 2 00:00:09,758 --> 00:00:14,362 We're going to continue our pathfinding simulation working with the code that 3 00:00:14,362 --> 00:00:16,497 we've done in the past few videos. 4 00:00:16,497 --> 00:00:17,340 And in this video, 5 00:00:17,340 --> 00:00:20,252 we're going to be looking at how do we consider obstacles, right? 6 00:00:20,252 --> 00:00:23,990 We currently have a flood fill simulation that grows and 7 00:00:23,990 --> 00:00:28,138 obstructed by any kind of wall or anything, any kind of tile. 8 00:00:28,138 --> 00:00:32,961 But we would like to make this simulation grow differently if 9 00:00:32,961 --> 00:00:34,956 it reaches an obstacle. 10 00:00:34,956 --> 00:00:38,916 That's why we have an environment where we can customize and draw obstacles for it. 11 00:00:38,916 --> 00:00:44,496 So this is going to be giving us a lot of really opportunities 12 00:00:44,496 --> 00:00:49,613 to see how this algorithm really can become smart and 13 00:00:49,613 --> 00:00:54,513 figure out a path through a challenging setting. 14 00:00:54,513 --> 00:00:59,483 What we're going to be doing is rather simple, but we need to make sure that 15 00:00:59,483 --> 00:01:03,973 we are preparing the data to have the right information, right? 16 00:01:03,973 --> 00:01:07,429 Our flood fill, the only variation that we're going to have, 17 00:01:07,429 --> 00:01:12,169 is if you see towards the end of it, when we're checking if a tile has been visited, 18 00:01:12,169 --> 00:01:15,518 we're also going to check if it's not an obstacle, right? 19 00:01:15,518 --> 00:01:18,828 So if it's an obstacle, it won't add it to the stack. 20 00:01:18,828 --> 00:01:23,028 Therefore, the stack cannot grow towards in an area that it's an obstacle, right? 21 00:01:23,028 --> 00:01:25,431 Sounds simple, Let's add it to the code, but 22 00:01:25,431 --> 00:01:28,943 let's make sure that we're actually providing the information of 23 00:01:28,943 --> 00:01:33,504 what is an obstacle in a manner that actually makes sense for this algorithm. 24 00:01:33,504 --> 00:01:35,560 So we're here, this is what we have so far. 25 00:01:35,560 --> 00:01:37,596 We have a flat field calculation that starts automatically. 26 00:01:37,596 --> 00:01:43,117 We're going to change that as well, so that we can actually decide, give 27 00:01:43,117 --> 00:01:49,576 ourselves a little bit of time to draw the environment before we actually execute. 28 00:01:49,576 --> 00:01:53,095 So if you remember, if we go into the tile, if you remember, 29 00:01:53,095 --> 00:01:56,002 we have a variable called is_obstacle, right? 30 00:01:56,002 --> 00:01:59,501 And we have it by default, false. 31 00:01:59,501 --> 00:02:06,496 So let's just say that when you create the tiles or when you paint the tiles, 32 00:02:06,496 --> 00:02:12,963 you're changing the tile type from floor to wall, and so on, right? 33 00:02:12,963 --> 00:02:18,563 We would like to specify that if a tile is 34 00:02:18,563 --> 00:02:24,690 of a particular type, we will convert it. 35 00:02:24,690 --> 00:02:26,611 We're going to decide if it's an obstacle, right? 36 00:02:26,611 --> 00:02:30,954 So we could decide, well, look, maybe wall and water are obstacles, right? 37 00:02:30,954 --> 00:02:36,141 So let's just create a function that filters through the data, and 38 00:02:36,141 --> 00:02:41,510 allows us to say, well, if you are giving me specific type of change, 39 00:02:41,510 --> 00:02:46,348 I'm going to make this property of being an obstacle being true. 40 00:02:46,348 --> 00:02:52,362 So let's say defined 41 00:02:52,362 --> 00:02:59,424 change_type, right? 42 00:02:59,424 --> 00:03:05,184 So the change_type, currently we are doing it very manually. 43 00:03:05,184 --> 00:03:09,380 The environment sets the type of the tile to be zero or to be one. 44 00:03:09,380 --> 00:03:15,705 Now, they're going to have to go through this function, right? 45 00:03:15,705 --> 00:03:19,488 So that's the opportunity for 46 00:03:19,488 --> 00:03:24,442 us to say self.current_type = type. 47 00:03:24,442 --> 00:03:26,951 So that's what we have been doing before. 48 00:03:26,951 --> 00:03:28,634 But let's add a bit more to that. 49 00:03:28,634 --> 00:03:36,239 We could say if (type equals 1 or 50 00:03:36,239 --> 00:03:40,589 type equals 3). 51 00:03:40,589 --> 00:03:45,925 So 1 and 3 refers to, if you look at the indices, 52 00:03:45,925 --> 00:03:48,732 1 is wall and 3 is water. 53 00:03:48,732 --> 00:03:54,098 And this is, again, you could add more tiles that represent obstacles. 54 00:03:54,098 --> 00:04:00,851 We could say self.is_obstacle 55 00:04:00,851 --> 00:04:04,472 = true, right? 56 00:04:04,472 --> 00:04:10,474 Else, self.is_obstacle equals false, right? 57 00:04:10,474 --> 00:04:17,402 So now, if we would like to change the type of a tile, 58 00:04:17,402 --> 00:04:22,450 we go through this function, right? 59 00:04:22,450 --> 00:04:24,508 So where are we changing the tile type? 60 00:04:24,508 --> 00:04:26,856 We are doing that into the paint. 61 00:04:32,627 --> 00:04:33,346 Where do we have it? 62 00:04:33,346 --> 00:04:35,577 Paint_cell, right? 63 00:04:35,577 --> 00:04:43,605 Here, we are using this line that says current_type = type. 64 00:04:43,605 --> 00:04:45,509 That's kind of something that we don't want to do anymore. 65 00:04:45,509 --> 00:04:51,020 We want to say cell.change_type(type) 66 00:04:51,020 --> 00:04:56,076 specify in the argument here, right? 67 00:04:56,076 --> 00:04:58,999 So we're going to be saying change it into a wall. 68 00:04:58,999 --> 00:05:01,159 And when that change happens, 69 00:05:01,159 --> 00:05:07,067 the tile will automatically define if it's an obstacle or not an obstacle, right? 70 00:05:07,067 --> 00:05:10,278 So let's check that this is running. 71 00:05:10,278 --> 00:05:11,434 It still should work. 72 00:05:11,434 --> 00:05:14,834 We can paint our obstacles, but as you can see, 73 00:05:14,834 --> 00:05:19,944 our obstacles are not by any way affecting the growth of the algorithm. 74 00:05:19,944 --> 00:05:24,597 The second thing I want to do before I include the obstacle 75 00:05:24,597 --> 00:05:29,349 calculation into the system is, as I mentioned before, 76 00:05:29,349 --> 00:05:34,111 I would like to make that the running starts being false. 77 00:05:34,111 --> 00:05:37,573 Are we running this flat fill? 78 00:05:37,573 --> 00:05:38,770 We're not, right? 79 00:05:38,770 --> 00:05:40,121 We're not trying to run it. 80 00:05:40,121 --> 00:05:42,223 It's going to be false. 81 00:05:42,223 --> 00:05:46,973 But I would like to add a way of making it true, right? 82 00:05:46,973 --> 00:05:50,383 So let's just here in create a bit more interactivity here. 83 00:05:50,383 --> 00:05:57,141 We're going to say if(keyPressed), 84 00:05:57,141 --> 00:06:04,540 if the key that we're pressing is 's'. 85 00:06:04,540 --> 00:06:12,392 Or if the key that we're pressing is capital 'S'. 86 00:06:12,392 --> 00:06:19,065 Oops, capital 'S', then 87 00:06:19,065 --> 00:06:27,970 my_environment.running = true. 88 00:06:27,970 --> 00:06:33,786 So that means that if we press the key s in our keyboard now, 89 00:06:33,786 --> 00:06:37,480 we can start the execution, right? 90 00:06:37,480 --> 00:06:43,397 That gives us time to customize our environment, paint some walls, 91 00:06:43,397 --> 00:06:49,528 and paint some regions, and then execute the running of the flat fill. 92 00:06:49,528 --> 00:06:51,149 So that's great. 93 00:06:51,149 --> 00:06:57,416 Finally, let's just add that in a flat fill algorithm here, in this line here. 94 00:06:57,416 --> 00:07:01,589 If the neighbor that we're evaluating is not visited, 95 00:07:01,589 --> 00:07:03,996 what else do we want to add there? 96 00:07:03,996 --> 00:07:08,307 We want to check if it's not an obstacle, right? 97 00:07:08,307 --> 00:07:12,587 So we also want to say and 98 00:07:12,587 --> 00:07:16,012 not neighbor dot, 99 00:07:16,012 --> 00:07:22,012 what is the name of the variable? 100 00:07:22,012 --> 00:07:25,105 Let's just double-check. 101 00:07:25,105 --> 00:07:28,690 The variable name is obstacle, right? 102 00:07:28,690 --> 00:07:31,124 Let's just make sure we are using the same variable name here. 103 00:07:31,124 --> 00:07:36,555 If the neighbor is not obstacle, right? 104 00:07:36,555 --> 00:07:42,389 We could say if neighbor obstacle equals true, but we're using the node, 105 00:07:42,389 --> 00:07:47,945 meaning if the neighbor has not been visited and it's not an obstacle, 106 00:07:47,945 --> 00:07:52,501 then we can continue growing our stack in that direction. 107 00:07:52,501 --> 00:07:54,434 So let's see if this works. 108 00:07:54,434 --> 00:07:59,536 So now, we have the time to kind of create some kind 109 00:07:59,536 --> 00:08:07,439 of environment that would make this flat fill maybe grow at a different pace. 110 00:08:07,439 --> 00:08:14,235 So now the growth, as you can see, doesn't go through the walls. 111 00:08:14,235 --> 00:08:21,717 It's actually being kind of limited by the walls that we created. 112 00:08:21,717 --> 00:08:27,710 And of course, if we want to create a region that is unaccessible, 113 00:08:27,710 --> 00:08:32,640 the algorithm shouldn't be able to reach the target. 114 00:08:32,640 --> 00:08:36,972 So therefore, it would actually feel everything, but 115 00:08:36,972 --> 00:08:39,551 it will not reach the target, but 116 00:08:39,551 --> 00:08:44,633 it would actually cover everything outside the target, right? 117 00:08:44,633 --> 00:08:51,276 So yeah, that's how we have obstacles being taken in consideration. 118 00:08:51,276 --> 00:08:53,993 So with this in mind, we have included obstacles in the calculation. 119 00:08:53,993 --> 00:08:58,088 Now, we're going to be able to kind of start kind of understanding what would be 120 00:08:58,088 --> 00:08:59,098 the optimal path. 121 00:08:59,098 --> 00:09:02,757 Now that we've done this algorithm, if we have to backtrack, 122 00:09:02,757 --> 00:09:06,079 what would be the best path to go from the start to the end? 123 00:09:06,079 --> 00:09:08,591 So there's a lot of interesting calculations that we can do on 124 00:09:08,591 --> 00:09:09,133 top of this. 125 00:09:09,133 --> 00:09:10,374 So I'll see you in the next video.