Hi, welcome to this third video in our pathfinding series. This is our project four,
and in this video, we're going to be looking at
how do we access neighbors? This is, again, a recurring topic, something that we covered in different
places throughout this course. But we're going to revisit it because it's
a kind of fundamental computation that we need to undo in order to kind of
do the pathfinding project, right? So finding neighbors in this case is
going to be when we have a start node or a particular node. We're going to start with the mouse so
to make sure that actually it works. For every location in the grid, each cell should have information
of adjacent cells, right? So if you think of this as a graph, each cell should have a connecting kind
of information to other cells, right? So that means that the cell
needs to understand its own position in a collection. So we're going to be passing information
to the cell itself to be able to understand this information, right? The kind of equation that
we want to calculate, especially when we're looking at
this nested list configuration, is that your neighbor above you,
it's going to be a y-1. On the left is going to be x-1, below is
going to be y+1, and on the right, x+1. Understanding that the x and
y is the coordinate that we're sampling, meaning the point,
let's say in this case, the mouse, right? So whenever we have those
neighbors available to us, we will append them to a list of
neighbors, and we want to be able to have each cell in the system
have this information,, right? What I was mentioning is that
we could start thinking and reflecting on how the system could be
extrapolated also to other kind of data structures, or think of not necessarily
a grid, but perhaps a graph. We are looking at a grid as a graph,
and how those neighbors are kind of connected to each other,
which are the edges on a graph system, is the way in which you can access
this neighborhood relationship, right? But you could have a graph
that is much more arbitrary, that doesn't have
necessarily four neighbors. There could be more neighbors,
there could be less neighbors. There could be no neighbors on some nodes,
right? So I wanted you to start thinking of
how this algorithm could be used in different contexts. And many times when you
kind of research pathfinding, you'll see that it's actually
explained through graphs. In our case,
it's going to be a bit more graphing and straightforward to do it within this grid,
right? But let's start writing this kind
of neighborhood calculation, especially looking at how a tile would
actually get the information we need. So we're going to jump into the code. We are continuing with
the code that we have started, which is we have
a customizable environment, something that we can paint with our
left mouse and also delete walls. And I wanns go back all
the way to the tile here. Currently, the tile knows
very little about the world. It knows its own position. It knows which size it has and
its own type. But let's expand the information
that the tile has. Because if you think about it,
a neighbor for a tile first needs to be in
awareness that, hey, well, maybe I need to know how many columns and
rows are in the world, or maybe, which is my position in that world,
right? And also what is the total
collection of tiles, right? So let's just provide this information. If we realize that some of that
information is not necessary, we can backtrack and delete that. But let's think that we want to
provide the information of columns, The information of rows, right? I'm going to call x and y. It's going to be the current
index of the tile, so the tile should know its own index,
and all_cells, right? So the constructor of our tile
has changed quite drastically, has a lot more information. Let's just create local variables for those. Right, so we have cells,
columns, rows, ,x and y, right? So these are all the new
pieces of information. If we would try to run this, we're
going to run into an error because our environment, it constructs the cells
right here, new_tile = tile. It just provides three arguments. So let's provide the arguments
that were missing, right? So we do have self.columns, self.rows as the columns and
rows of the system. We also have, in the loop,
we know that i and j refer to the index of that
cell in the collection. And finally, self.cells are basically
all the other cells, right? So in order to access the list, a tile would have to go through
this collection, right? So knowing your index, most importantly,
knowing your index and the cells, you could kind of derive
your index plus 1, minus 1, and so on. So we can actually
calculate the neighbors. These columns and
rows is just to know that we are within the bounds of the world or
kind of how big the grid is. So let's go back into the tile. I mean, and
here you could have thought, well, could I do this calculation
from the environment? It could be done, but I like thinking
from the perspective of the cell, really kind of thinking bottom-up. Like, what would be the capacity of
one cell to identify its neighbors? So let's write a get_neighbors function, so get_neighbors. And in the get_neighbors, we're going to
create an empty list of neighbors. And we are going to first review if the self.x is bigger than 0, right? Because we want to make sure that
the index, we're checking these indices against the size of the world,
zero being the lowest there is, right? So let's just basically want to append to this empty list. What do we want to append? We want to append one entry, another node, basically self.all_cells,
which is from the list. So we access the list now
that we have access to. And if we would say x, or sorry, [self.x], [self.y], that index is who we are as a cell, right? So the neighbor in x needs to be
a -1 in this direction, right? Because by definition,
the cell in which we are working, right, its own index is defined by x and y,
and the collection is all_cells, right? So the x and y index would
represent who we are as a cell. The -1 would represent
our adjacent neighbor. So let's copy this line and
let's go one by one checking the four neighbors that we want to evaluate for
this situation, right? So the x in the second one needs
to be smaller than the columns, the number of columns, so self.cols. And we're going to do -1 here
because we want to make sure that it's not the size of the world. As you can see here,
we're doing bigger than 0. In the size of the world, we want to do smaller than
the number of columns minus 1. And here the neighbor in this
case would be a plus 1, right? Because this plus 1,
we need to stop one short and ask for a neighbor to the right, and
that could give us our rightmost neighbor. Understanding that the last cell on
the row would not have a neighbor to the right, right, because we ran
out of neighbors in that direction. Let's copy the first one, which is a little bit more closer
to what we're going to write now. The next one has to do with y. So if self.y is bigger than 0, we will append, The y-1 neighbor, right? So this is the neighbor above us. And then finally,
I'm going to copy the second line, which is closer to what we're
going to write for the final line. If the y is smaller than the number of rows minus 1, let's append the neighbor that has y+1, right? So again, the diagram here suggests
that we have four neighbors. All of them are based on their indices,
right? So the neighbors are defined
by their index numbers. So let's return, This new list, Of neighbors, right? Yeah, so this is great. Now, each cell can calculate some
neighbors based on indices, right, and we should be able to draw them
somehow in the screen, right? So how would we access the neighbors? Well, let's create a function from
the environment that we can call. So similarly to how we were painting
a cell, we can do a function that would be like, let's draw,
let's paint the neighbors, right? Collect the neighbors and draw them in the screen somehow, right? We could do them up here as well. I think that we are leaving
behind this calculation. So let's just do here a function
that we're going to be able to call from the mouse. So draw_neighbors, (self.x,y). So this is going to be testing with
the mouse position, first of all. So, What we want here is first collect the cell,
right? Let's collect the cell, self.get_cell. So this is going to be the, The cell
that we are kind of highlighting, right? And it would be nice to
have a way of drawing the cells with a particular color, right? Like what if the cells would
have a method that would draw themselves in a way but
similar to the display function? So something like display, but maybe
when we want to highlight them, right? So let's do that. It's kind of a very simple function, but I realized that it's
actually pretty useful, which I'm going to call
define display_highlight. And with this function,
we can provide a color. How do you want to highlight this cell? We can say the fill,
it's going to be the color provided. And the display is basically
the same display that we have been using in the display function, right? So what this display highlight is kind
of a temporary function to highlight some data, right, would allow us to
pass a color, say color blue, and paint this cell blue or red or whatever
color we want just when we need it, right? And we're not going to be executing it for
all cells at all times, but it's incredibly useful to be able to
highlight or draw them differently. So let's use this function
that we just created here. So if I get the cell,
which is the mouse cell, let's create a color. We're going to do the color. Let's do a red color just to
see if this function works. And the cell that we got,
which is where the mouse is holding, let's do this function,
display_highlight with the color, right? So we haven't drawn the neighbors yet. We're first getting the cell
where the mouse is, right? We're going to draw
the neighbors in a minute. Now, just to check if we're not running
into errors, let's call this function. Let's remove these comments. For a moment, I'm going to,
Comment out our capacity to paint walls just to kind of
test our neighbor calculation. So my_environment, .draw_neighbors(mousex, mousey), right? So let's see what we have so far. All right, we're running into an error, let's see. Okay, so
there was a problem with indentation. But as you can see, we press now and
we can highlight a cell, right? So that's pretty useful. The neighborhood,
basically we get the cell, but now we actually have the function
to pick the neighbors as well. So what would be the neighbors? So we have neighbors, = cell.get_neighbors. We know that's a list. The returning value from that calculation
is a list of up to four neighbors, right? So let's say for n, or short for neighbor, in neighbors. Let's do the same thing that
we did to this cell here. Let's display it with a highlighted color,
right? So in this case,
the cell in question is n, which is the entity within
the neighbor's collection. And let's just do a different color. Let's do blue. Right, so we're saying display
the cell you're on top of as a mouse, right, and display your four neighbors. And there we go. So this is kind of a very slow and kind of
way to kind of double-check that we are, in fact, doing a neighbor
calculation that works, right, that we can not only grab a cell,
but grab the neighbor cells. And that basically this is telling
us that the cell has access or information about its neighboring cells. And this is going to be
the foundation of the algorithm. So with this in mind and having this
working well, we'll leave it here and I'll see you in the next video.