Hi, welcome to this new week. We're going to continue
working on a new project. This is going to
be our Project 4, and we're going to be working
on a pathfinding system. We are going to be understanding first what a
pathfinding system is. A pathfinding, it's a
computational problem solving approach where we
would actually have agreed. In this case, as you
can see on the right, we're going to
have a start note, and we're going to try to
figure out what would be the path that would take us
to an end node or a target. That maybe straightforward
if we're doing it visually, but we want to
calculate what would be the optimal path
between these units, e specially if we
consider things like obstacles or certain tiles
that might not be accessible. It's a really interesting
algorithm that might able to solve a labyrinth
or something like that, but it has a whole
range of applications. Also, we learned that there's different computational
techniques of how to solve this problem. Some of them are maybe
more brute force, and they actually take a lot of time to
actually calculate, and some others actually taking consideration some
methods that may speed up the computation
and make it to a solution very quickly. There's a whole range
of interesting ideas that could be learned
from this project. We will start in the
first few lessons, building an environment
that we can customize, something that we could actually
adapt, paint, and draw. It's very similar to what
we've been doing with grits. But we're going
to be structuring that as an environment
in which we could use as a playground for our
pathfinding algorithm to play and execute. Let's start building
it up from scratch. I'm going to jump
into our code here. I'm starting from
an empty project. As you can see here, we have mostly our template
starting point. We have been using
this template before, and I'm going to
start with a new tab, which I'm going to call tiles. Let's import randomness. This is going to be a class, but it's going to
be a class called tile and it's going
to be a constructor. Basically, what the tile is is each cell in the grids
going to be a tile. It's going to be useful to
have this tile because we can embed information
like, are you a wall? Are you a floor? Are you a resource?
Are you water? We might not use
all those types, but we could actually
start thinking, oh, this could be actually a
tiling system as it's been used in video games or
other environments. Some of those tiles might
have a property of being an obstacle or not
being an obstacle, being something that
you can walk on. We will eventually be able to store data
in this file like, has this style been visited
or not, or things like that. Let's just start this constructor
by defining a position. What's going to be important? We're going to define a
cell size and a type. For now, that type might
be just two types, but we might have
different ones. Self taught position
equals position. It's a cell size. That's two types. Here, I'm going to
create a variable of the possible types, and I'm going to define
that as a tuple. Types plural, we're
going to say this could be floor or this
could be a wall, or this could be a resource, or this could be water
just to give some ideas. Again, if you think again of a 2D overview of an environment, you could start
imagining all tile types that you might
want to have here. What we're going to call
the self.current_type. It's going to be provided
by the constructor. Type is going to be the current type of
tile that we're using. If we say zero, it's
going to be floor, if we say one, it's going
to be wall, and so on. Let's also anticipate that we're going to be using
this a bit later, but we're going to
say is obstacle. This is going to be a Boolean, we're going to say it false
at the moment. That's it. We're going to continue
adding some variables to this class later
down the line. But I think for something
that we could actually see in the screen, this
should be enough. Let's just do one function
that will run the tiles. The run function as we have
been doing for many others. I'd like here using
this as an outline of the functions that
I'm going to be using. I'm going to just use
self taught display, which is a function
that we don't have yet, so let's just write it. So def display. Here, what we want
to do is just to have a very simple distinction. We want to do a rectangle. Most grid systems actually
operate with a rectangle. I mean, you could be thinking
of an hexagonal grid. I mean, this algorithm
should be able to work with any kind of
grid configuration, and it could actually work for any kind of graph configuration. We'll see that if
you have a graph, we can think of this
grid as a graph. You could also think
of the algorithm running in a graph as long as you have sales or entities notes
that have neighbors. This should actually
be possible. Let's just say self.
position.x, self. position.y. Self.cell_ size and self size. We're drawing the rectangle, but we want to differentiate
it maybe just a feel. First is to a stroke of 0,50, which is zero black
50 transparency. You might want to
increase this a little bit if you want more contrast. But let's say if the self. types, because we're checking the types, self.current type. The current type is an index. It's an index to the different typologies
of tiles that we have. We're going to say
it's equals to floor, are we equal to floor? Then the feel will be white. Here we could say else. But I would like to
do an elif statement. Let's just copy
paste this because I think that this is something
that could be expanded. We might not expand
it too much here, but it's something that
I want to leave open for you to explore, if you want to expand
different tile types drawings. If the current type, in this case is wall. The wall, we're going to
draw them as a black tile, meaning that there's
kind of some visibility of the wall system. You could invert that
relationship if you want, if you're going to change
the color scheme to black over white,
that's your choice. We have a class, which is
our tile that is ready to be used by a system
or a environment. We're actually going to create a second class that's going to control and create a grid out
of a series of these tiles. We're going to create
that. Let's save, make sure that we're
saving what we're doing. We're going to create another
tab called environment. The environment is going to
be yet again another class. Let's import a randomness first. We are also going to be importing the tile because we're going to use the
tile for the grid. Let's just do that right away. From tiles. Remember that we call the file
tiles and the class tile. From tiles, it's
important class tile. Let's create our
class environment. This class, if you've
gone through this course, you know that we
have constructed things like this before. It's going to have a columns and rows and some reference
to the world, so we know how we can match our grid size to the
entirety of the screen. Let's start with self. We're going to need columns,
going to need rows, and we're going to
need a reference to the world size in x, and the world size in y. Now we can use prepare
those variables. Here, this is a very
important variable that it doesn't necessarily need
to come from the constructor, but we're going to
create our cells. The cells, it's going to be representing the list
of all the tiles. We can call them cells,
we can call them nodes. But for now, it's going
to be a single array, but we're going to use
slightly different structure from what we've been doing in the vector field exercise
where we were actually doing a flat array or flight list for the
entirety of the vectors. We're going to be
using a nested list. That's really to practice different forms of organizing
the data structure, and I think that it's going
to become a little bit more intuitive when we start doing a lot of work with neighbors. Hopefully, that serves for practicing different
ways of organizing agreed. I think we've covered
this difference, but I just wanted
to make sure that we have some explicit
description of that. In the self-run, we're
going to write the run I just always write
this function by default here. What
do we want to do? We want to basically
run the tiles, right? So we'll need a
function for that. But let's just come back
to this in a moment. I think I'm getting
ahead of myself. The first thing we need to do is make a function that
would initiate the cells. Because that cell array or
that cell list is empty. Let's just create that function. Initiate the cells. As we have done before, we need to do a four loop or a nested four loop that goes through egg columns and rows. But what would be useful here is to calculate the cell size. Let's start by that.
The cell size. It's going to do a float we're going to take a float version
of the size of the world, and we're going to divide it
by in the number of columns. I'm going to assume at this
point that the ratio of the screen and it's going to allow us to
do a square grid, you'll see that
we could actually have the tiles be asymmetric, but I'm going to work
with square tiles. Again, the system could be
a bit better prepared to do non-symmetrical tiles
or not square tiles. But for now, I think I'm
going to just stick to that. I'm only going to
calculate the cell size for one of the axes. So the world x divided
by the number of column. So we're dividing the size of the screen by the
number of columns we have, in range, so we're going to look
through the number of columns that we have as
create a bit more space here. In range, so self dot spend. We're going to append
an empty list. Here, instead of just going
through the loop twice, we're going to inside firstly, we're going to append
an empty list, and now we're going to do for range rose. The position, it's
going to be P vector. The vector that we really want to for the position of the tile, we have to think that it's
going to be in x j in y. But both of those ones to be
multiplied by the cell size. Because we want to give some separation
between those tiles. That's the position of the tile. Now we can actually construct the new tile. We
can say new tile. Because we've imported the
class tile, we can use it. So I say tile. If you remember the
constructor of the tile, requires a position a cell size, which we already
calculated here. Also requires a type. We're going to say zero for now. Because remember that
the type is an index, zero stands for the floor
and one stands for the wall. Let's just finally
say self.cells [i]. append new tile. What we're doing here is saying, from this entry list that we
created within the columns, we are going to be appending an entry that is going
to be one of the rows. In this way, what
we're going to end up having is that
we're going to have two indices and the first index is accessing within the row, and the next one
is for the column, and then the next
one for the row. That would actually make
it a lot simpler to start looking at neighborhood calculations,
neighbor calculations. But let's see if this
is actually working. We're going to be calling
this initiate cells. Let's just call
it this function. Call it straight from
the constructor here. Initiate cells. Now, the only thing that
we're actually missing. Let's imagine that is
all working perfectly. We have initiated the cells, and now we want every
frame in processing, draw those cells
into the screen. Let's just do def run_tiles. Run cells. I think that
I'm using interchangeably. Cells and tiles. You might want to be a bit
more rigorous in your naming, but what we want to do, this type we have a
nested, at least, so for column in self.cells. The cell list contains, first of all, what we're
going to call a column, which is a list and
for cell in column. Within that column,
which is a list, we have entities that we would
call cells and cell.run. This would be finally
be this line here. Let's just execute the
running of the tiles. I think at this point, we
might have everything we need, we initiate the cells
using this empty list. Then every frame we
execute the run function, which is, if you remember here, is basically just their
display function, but we might be adding
more execution here later. In order to see if
this would work, let's just first of
all, import here. From environment,
import environment. We're going to call this
to global my environment. My environment, let's create
a new environment that is the environment of how
many columns, 120 by 60. I'm using basically one fraction of the size of the screen, just to have a good
match between those two. Here we can actually use the
variables of Canvas width, which is the size of the wall, Canvas width and Canvas height. I think that's everything
that the environment requires really to operate. Now, within the run, we can basically just
run the environment. Let's see where we
wrote some errors. We have some errors. Let's just figure those out. Yeah, so I found I think the errors were in
a couple of typos. I think that we had
misspelled here cells. It should be columns. The second one was here in I
think we're missing the Z. We had something like that. Finally, I did a small
change to the stroke transparency 50-150
just to make sure that we have some
visibility of the grid. Here, this is the environment. The resolution of this
environment now could change if you want
to use half of the resolution you
want to use and will be changing this resolution. It should always to
match the screen size. We're going to be
learning how to customize this environment further and start running the algorithm
in the videos that come. I'll see you in the next video.