- Hello, and welcome
to a coding challenge: 2D raycasting. (dinging) So, what you're about to watch is an edited version of what I did on last week's live stream. This is the result of
the example that I made, but before I get started with the coding, let me talk to you a little bit about where I got this idea. So, a lot of people shared with me a recent YouTube video
from Sebastian Lague about the 2D raymarhing algorithm. This is part of his
coding adventure series. The video's really wonderful, and goes through the basic 2D algorithm and gets into also some
crazy 3D rendering stuff. So, I want to explore that
algorithm in a later video, but I wanted to start
with something simpler, and I looked back and
Brenda Dowd, back in 2016, posted a suggestion for
me to do 2D raycasting. So, about 3 years later,
I'm getting to it. So, I've been looking for inspiration and I found inspiration in one of my favorite internet artists, indie game creator, Nicky Case. So, Nicky Case made a game
called Nothing To Hide, and also an accompanying
explorable explantation that describes the process of creating this really beautiful 2D
shadow effect in the game. So, I encourage you to
check out Nicky Case's work, all of their explorable explanations, but in particular, down
the middle of this page is an example of exactly,
basically, what I tried to make in the coding challenge. There's also, from Red
Blob Games, Amit Patel. A wonderful interactive essay, explorable explanation, again, if you will of a 2D visibility, and
there's a source code and a variety of different languages and a whole bunch of interactive demos. So, this is what I wanted to make. I kind of got there. There's so much further it could be taken by you, the viewer, and I hope you make your own creative version of this and share it with me at TheCodingTrain.com So, I hope you enjoy
this coding challenge. (train whistling) Let's get started with,
actually, the coding of this. In JavaScript, using the p5.js library. So, let me map out what
I think I need, first. So, what I want to have, is I want to have two classes where I can make two kinds
of objects in my world. I want to have a boundary. This idea of a boundary, and the boundary really
just is line segments between two points, A
and B, or start and end, however I want to consider that. Then, I also want to
have an idea of a ray, and a ray has a position,
and then maybe a direction. So, presumably, if this was the ray at this position, with this direction, I need a function to tell me, where does this ray hit the boundary. So, two questions: One, does it hit the boundary? Yes or no. If it does hit the boundary, give me that point. If no, then just say no. So, this is what I need to do. If I can create this basic
ray class, a boundary class, I can have every ray find
its point on the boundary. Then all of those things
that I just showed you I should be able to create. I want to mention one other
reason why I'm doing this, and it might take me a
while to get to this, but in a future video, what
I intend to use this for, is also if I have a vehicle, I want to use this in an A.I. application. If I have a vehicle that's trying to drive
along some type of path, if I can give it sensors,
which are like rays that allow it to see
out from in front of it, the readings of those sensors, where those sensors, how far they are from the path's boundary could be inputs into a neural network
that would then determine which direction the vehicle should turn. So, this is where I'm also
going with this, eventually. But right now, in this
video, I just want this ray and this segment. Here I am with the code. So, I have three JavaScript files. I have sketch.js with my,
sort of, meme stuff in it set up in Draw. I have ray.js, where I
want to create a ray class, and boundary.js, where I want
to create my boundary class. So, let's do the boundary first. Class boundary, and then I need a constructor. And basically, I want two points. A equals createVector and B equals createVector. So, this is the idea of the boundary. I have two points. I could have them be separate variables. This.x1, this.y1, this.x2, this.y2, but I'm going to use A and B. Oh, but wait! Yeah, as vectors. So, A and B each get their own X and Y. Ha, okay. But maybe what I'll do
is I'll initialize it with four arguments, which
are the raw coordinate values. I might regret this later, but
let's see what happens here. Then, let me write a
function just to draw it. So, if were to draw it, all I want to do is say draw line from a.x, a.y, to b.x, b.y, and say stroke 255, okay. This is good. So, this is when things just
work out so specifically. So now, in sketch, I'm going to say, let's start with just one boundary. I'm going to call it B, and I'm going to say createCanvas 400, 400, and B is a new boundary between, I don't know, 300, 300, 300. No, 300, 100, 300, 300, and then background zero and b.show. Okay. Alrighty. Alrighty, alrighty, alrighty. (comical music) You'd think by now I
wouldn't have this problem. This comes from 15 years
of programming in Java before JavaScript, wasn't
that many years, maybe 10? There we go, look! Yay, I have a boundary! (trumpets blaring) Now, let's make the ray class. So, I'm going to say class ray, and, oh, there's so many
ways I could do this. I definitely need a constructor, and I want a position, which is going to be a createVector, and this a little bit. This is a little bit
silly, because ultimately, what is a ray but a vector? What I'm saying, though,
is that for my purposes, I want the ray to be a
vector that emminates from a particular location. So, instead of just
using P5 vector directly, I'm going to make my own ray
class, which wraps a P5 vector with a P5 vector, that's position. So, the ray will be initialized
at an X, Y location, and then its direction, I'm just going to hard
code that right now. CreateVector zero comma one, and then
what I'm going to do is write a draw function and I will say same thing, stroke 255. Let's translate to the position,
that'll make things easier. Translate to this.pos, I
didn't forget this time. This.pos.y, and then draw
a line from zero, zero to direction.x, direction.y, and pop. Maybe what I'll also do. So. If I make the vector that
size, it's going to be one pixel of length, which means draw, which is fine for just
knowing the direction. It's a unit vector, but for
drawing it, it's kind of tiny. So, I don't know, this is very silly, but I'm just going to multiply it by 10 just so I can sort of see it right here. There's other more thoughtful
ways I could do this, but this will work. All right, let's go here. Oh, now I need to make a ray. So, now I'm going to say let R. Let's call this bound,
let's call this ray. Let's call this wall, let's call that ray. So, wall is a new boundary, wall.show. Ray is a new ray, and I will put this at, you're going to be surprised
about this location. (laughing) 100, 200, 100, 200, and then I'm
going to say ray.show. Okay, ah! Dir is not defined. This dot, this dot, I was so close to not forgetting my this dots. Oh, what? No! (coughing) Oh yeah, I want to point it to the right. So, there we go. X is the first component. Yes, okay, look at this! Oh, have I set myself up for
an exciting situation or what? So, if all goes according to plan, all I need to do now is write a function that says ray dot check wall. Ray.checkWall, that function
should either return maybe null or undefined if it doesn't intersect, or the point at which it
intersects if it does intersect. In other words, I want
to say let pt for point equal ray.intersect or cast. Let's call it cast against
the wall, I know it's weird, and then if point exists,
let's draw a point at point.x, point.y. We'll make this white
and maybe we'll make it, actually, an ellipse. So, this is the idea. I have a wall, I have a ray, and I'm going to cast
the ray towards the wall, and if I get a point back,
I'm going to draw it. So, in the ray class, I'm going to write a function called cast, and it's going to receive a
boundary, or I can call it wall. In order to do this, I need math. Right, I need to learn about
how do I determine if a line and another line are intersecting, and what's that point of intersection? There is a library, I'm
being told from the chat, called p5.collide2D that offers a lot of functionality for these types of geometry operations. Line-line intersection. You know, line-circle intersection. Circle-rectangle intersection. So, I could go and use that library and maybe it might be useful to do that and I'll come back to that
at the end of this video. I am, however, going to enjoy
looking at a Wikipedia page called line-line intersection
and finding the formula that I can use to apply to do
this math myself in the code. So, one thing I want to emphasize is that I mentioned
there's actually two steps. The first step is just to determine if it's even intersecting at all. Is it intersecting the line segment or no? And only if it is, then find that point. And so, in order to do this, and I'll go to the Wikipedia page itself, there's actually two values
that I need to calculate. One called T, and one called U. If T is between zero and one, and U is greater than zero, then the answer is yes. Both of these have to be true. Once the answer to that is yes, I can use T and U to then
calculate the actual point itself. I'm going to let you enjoy this. You can pause and read this
whole Wikipedia page yourself, but I'm going to scroll
down to the important part, and that is right here. The intersection point falls
within the first line segment if T is between zero and
one, and falls within the second line segment if
U is between zero and one. So, this is different
than what I said, right? Because, the thing is, that Wikipedia page is describing the point of intersection between two line segments. This boundary is an actual line segment. It has a start and an end. It's only this segment. The ray, however, is not
really a line segment the way I'm thinking of it. It is just an infinite line that goes off in both directions. So, this is why if T is for this boundary, then I know if this point is
really within this boundary if T is between zero and one, but for U, I just want to know
that the intersection point is on the positive side of the ray and not if the ray was
pointing in this direction on the negative side. So, this is my modification of that math on the Wikipedia page. So, let's calculate T and U. So, one thing you're looking
in this formula here, is this is the formula for T, and this is the formula for U. You'll notice that the denominator of both of these fractions
is exactly the same. So, let me first, in my code. I'm going to, just to reduce confusion, I'm going to say x1 is wall.a.x, just so I can use the same notation that's on that Wikipedia page, and I'll skip through this more quickly. (calming music) So, the wall's start and end points are x1, y1, x2, y2. (calming music) And now, for the next. So, this one line segment
between x1, y1, x2, y2. Between the other line
segment x3, y3, x4, y4, I have the position of the ray and then the endpoint of the endpoint of that line segment, which is the position of the ray plus the direction of the ray. So, I'm making a line segment by saying here's the position of the ray, this is the direction vector. So, I have x3, y3, and
then this point right here is x4, y4. So, now that I've kind
of renamed all of this, and I could do the actual
math with vector operations and just keep these variable names, but this going to let me make sure that the Wikipedia formula matches exactly what I'm doing here. So, the first thing is to
calculate the denominator. Can I remember this? X1, x2, y3, y4, y1, y2, x3, x4. (calming music) Now, this is the formula
implemented as the denominator. Now, an interesting tidbit that
you might've noticed here is wow, the denominator is the
thing you're dividing by. What if it's zero? This could be zero. Well, guess what? If the value of that is zero, that means that the boundary and the ray are perfectly parallel, meaning
they would never intersect, even if you stretch them out
infinitely in both directions. So, that's something that I
need to look at right here, which is just to say if denominator equals zero, return null. So, this is, or just return,
I'll just say return. Get out of here if that's a zero. I'm done! I'm done with this, check. Now, I want to calculate T. So, T is going to be this x1, x3, y3, y4, y1, y3, x3, x4. (calming music) All right, now I've got T, the numerator divided by that denominator
I calculated above. Now, it's time for me to get U. X1, x2, y1, y3, y1, y2, x1, x3. This is actually the
same, it's just a two. (calming music) This is close, but if you're
not looking carefully, there is a nice little negative there, so I've got to also add that in for U. People in the chat are asking about these pipe symbols, what they mean. That means its the
determinate of a matrix. So, I've got a lot of different videos about matrix math beyond the scope of what I'm doing here right now, but that's certainly
something you could look into, and I'll try to include some resources in the video's description. But, what am I doing right now? Remember, I said. Right, what did I say? I said I was checking now if
T is between zero and one, and if U is greater than zero. So, let's try that. Let's just say if T is greater than zero,
and T is less than one, and U is greater than zero, than return. I'll just say return true. Otherwise, return. So now, in theory, if
the lines are parallel, I'll return there. If there is an intersection point, I'll return true. If there isn't, then I'll
just return nothing again. So, I haven't calculated
the point of intersection. Right now, this is just testing if there's a point of intersection. Let's see if that even works. So, back to sketch.js, and then if point. Actually, let's just comment this out. Console.log point. Let's see what we get. True! There is a point of intersection, yay! So, this is working. Now, will I get false? (dinging) So, the chat is pointing
out that I can just return the bullion result of that, and I would do that if this
was all that I want to do, but ultimately, if that's true, then I want to go and calculate
the actual point itself. So, that's why I'm breaking this out into a large if statement. Now. I need to do something where I actually set the direction of the ray. So, let me add a function called set. I'm just going to call
it update, I don't know. Or set, I don't know, set direction, and I'm going to give it an X and a Y, and I'm going to say this.dir equals, this.dir.x equals X minus this.pos.x. This.dir.y equals Y, minus this.pos.y, and then this.dir normalize. So, I'm just creating a vector that's pointing towards. This is kind of like, so let's actually make this
function called lookAt. I want to look at this particular point, and then in draw, what I can do is I can say ray look at mouseX, mouseY. So, now, let's see what happens. So, true, true, true, but
if I point up, undefined. Right here, it starts
being true, true, true. Undefined, undefined, undefined. So, this looks to me like it's working. I'm getting true when
I'm pointing at the wall and getting undefined
when I'm pointing away. That's a good sign. So, now, all I need to
do is get that point. So, right here, I want to create a vector. I want to create a vector and eventually, I want to say the X
value of that vector is, back to my Wikipedia page. Here, I can use either T
or U to find that point. I don't know that it really matters. Let's use T. X1 plus T times x2 minus x1. X1 plus T times x2 minus x1. And then the Y is Y1 plus T times y2 minus y1. Y1 plus T times y2 minus y1, and then I can say return that point. So now, I should be able to go back here, and I should be able to add this. And here we go. Look, I'm casting my ray
all the way up to the edge. So, you might rightfully be wondering is this really working? I mean, I kind of set this up
in a really simple scenario where the line is perfectly vertical and the ray is right here positioned so that it's kind of
pointed directly at it from an obvious location. So, to know if this is really working, I might want to move the
line around, skew it, move the ray around. But ultimately, what I want to do, is I want to create something
like what Nicky Case has on their page, and I want to create a
world of many boundaries and an object that I can move
around and shoot rays out in all directions. So, I could approach that
by first setting rays out in all directions. Let's do that. Let's send rays out in all directions. This might be a little bit overkill, but I think I'm going
to make a particle class just to be the thing that's
moving around the screen. I don't really need that right now, but it's going to set me
up better for the future if I want to do raycasting from multiple vehicles driving around. So, let's make a particle class. I'm just going to give it. I'm just going to give it a position. This dot position equals createVector, and I'm going to put it
squarely in the center of the canvas, and then I'm going to create an array of rays. So, I'm going to say for let I equal zero, I is less than 360, I plus equal 10. So, I'm just going to think about the rays as every 10 degrees from zero to 360, and I am going to say this.rays equals a new ray position.x, position.y, and then I'm going to give it an angle. So, I am now going to, when
I create this.rays, index I. I'm going to make it
so when I create a ray, I give it, in addition to its position, I give it its angle. Actually, if all of the
rays are going to move as the particle moves, then, to be honest, it would make much more sense for me to actually just pass in the vector reference itself, and have the rays point to it, I don't even need to make
a copy of that vector. So, I could change the angle
mode to degrees, by the way, but I kind of like using radian, so I'm going to just use the
radians function to convert it, but I wanted to think in
degrees when doing the loop. So, if I go back to ray, I
need to change the constructor. So, the constructor now expects
a position and an angle. So, I can say this.position
just equals that position, and the angle, now,
equals p5.Vector.fromAngle angle. So, this is a function
in the P vector class. A static function that
allows me to create a vector pointing in the direction of an angle. So, now that I have that, I have my particle. I'm going to say let particle. Particle equals a new particle. There's no individual ray, anymore. I'm going to say particle.show, and in particle.show, I am going to comment all this out. In particle.show, I am going to say first fill
255, let's draw the particle, which is an ellipse at pos.x,
pos.y with, I don't know, 16, and then, I'm going to
say for let I equal zero, I is less than rays.length,
I plus plus, ray.show. So, let's look at this, now. Particle is not defined because
I forgot to include it as a file reference in my HTML. Pos is not defined because
I almost definitely forgot this dot everywhere. And then, actually, I
don't know what I'm doing with this loop here. I can just say for let ray of this.rays. Pos is not defined. Where was this.pos? There we go. Cannot read property show of
undefined at particle.show. Oh, this is terrible! This.rays, I didn't mean to do that. This is why I shouldn't
have called that I. This is really the angle, and what I want to do is just add a ray. So, I don't need to keep
track of the number of rays. So, there we go. I just want to use push
because I is not an index here. There we go, so you can
kind of see it there. Those are all the rays shooting out. Let's draw this smaller. So, you can see there they are. That's a little dot with
all the rays shooting out. Next step is to actually
find if any of those rays intersect the boundary. So, I have this cast function. So, I should be particle look. Look, I'll call it particle.look, and I need to give it the wall. Not sure if this is the smartest object-oriented structure,
but this will work. So, look at a wall, and
then I'm going to say, once again, I'm going
to look at all the rays, and I'm going to have every ray. When I say check, what is it called? In cast. Cast wall. Okay, let's try this and see what happens. So, what happens in cast? It does this. Oh, it returns the point. Okay. So now. Okay, so it returns the point. So, let const point equals ray.cast if point exists. Now, I want to draw a line
from this.pos.x, this.pos.y to point.x, point.y. There we go, you can
see those are the rays that intersect the wall. Now, if I, oh, this is the exciting part! If I say particle.update mouseX, mouseY, and in the particle, I add
a function called update with an X,Y, and I can
just say this.pos.set X,Y. Now, I can move this around and you can see that
it's showing me the rays that hit this boundary. Let's make sure this
works with the boundary being in a completely different location. So, now, the boundary could be 100, 100 to 200, 300. Right, still works. I could move over here. So, these rays are hitting that boundary from wherever they are. I could draw the non-hitting
rays with a alpha. That could be kind of interesting. Just all the way. I could also add boundaries to the edge of the window, but what happens now. The real thing is to
have multiple boundaries. So, let's make multiple boundaries. I'm going to make it called walls, which is an array, then I'm going to say for let I equal zero, I is less
than five, I plus plus, and I'm going to say walls
index I is a new boundary, and let's, I don't know. This is probably a terrible idea, but let's make some random boundaries. Y1, Y2, height. Height. X1, Y1, X2, Y2. Then I need to show for let wall of walls show all the walls, and let's
comment out this look, now. All right, so this is what we get if I make five random boundaries. I probably should be more thoughtful about how I'm setting them up, but this should work, anyway. So, let's let this. Let's let this go. So, right now, if I were to just say look walls index zero, this should work with
just one of the walls, but what I want is for now this ray to stop here and not go to the next one. So, I need to check the ray
against every single wall and find the one that's closest. In other words, if I have
this wall and this wall, and I have a ray here,
extending this ray out, I get these two intersection points, but all I need to do is figure
out which one was closer, and that's the one that I
choose to draw the ray to, and then I sort of ignore this part. If this were a light source, the shadow would be cast there, but the light would arrive over here. So, you can see how
this idea of raycasting is related to how light
is sent out into a scene and shapes and shadows are rendered. So, if I change the particle look function and give it walls. Now, I can go in here and I can say, let ray of this.rays, and I can then say for
let, and this is walls, let wall of walls, and I want to find the record distance. So, if I start with infinity, and I look for that point, and then I say let's get the distance. The distance between this.pos and point. Right, this the p5.Vector function, and then I say D equals the minimum, whichever's smaller between
the distance and the record. Sorry, the record is that. The record is whatever's smaller between the new distance I've
found and the record. All of this I can only do if
point, if there is a point, then I need to keep track of the record point. So, I'll call this closest equals null, and if point, and if point. Oh, I really should check
if its a new record. So, I might as well just do here. There might be a better way to do this. If distance is less than the record, then the record equals distance, and the closest is that point. Oops, I typed closet instead of closest. So, now, if closest is a thing, then now, I'm going to draw that line from this.pos.x, this.pos.y, to closest.x, closest.y. So, this is now the same exact algorithm, but for each ray instead of
seeing if there is a point. For each ray, I'm
finding is there a point, and is it the closest one? So, let's see if that works. Yeah this, oh no. So, why do I have a bug here? Ah, here we go, this is the problem, thank you to the chat.
(dinging) The record is a thing that
I need to keep track of while I'm looking at every wall. So, I'm re-setting the record to infinity. That's not going to work. So, the record needs
to be set to infinity, and now I start checking all the walls. So, that should do the trick. There we go. So, we can see, now, my
beautiful raycasting is working. I'm going to do one more thing to this. This is really done. There's so much more that
can be done with this, and I'm really having a hard time stopping myself, but I'm going to do one thing. I want to let it just
move without the mouse, and the way that I'm going to do that is I am going to just use Perlin noise. So, let's say X offset and Y offset, and I know, I know there
was a whole long discussion about what's Perlin noise versus Simplex versus OpenSimplex. Let me just say Perlin noise. Please, please, let me just say it. You can find those videos if you want, and then I am going to
say particle.update, noise X offset times width, noise Y offset times height, and then I will increase X
offset by some small amount, and also Y offset by some small amount. That's going to move on the
diagonal if I don't start Y offset in a different place, and there we go. So, I just want it to move automatically, which I think is a little bit
more interesting to watch. Also, oh, there we go. Here's a nice configuration of boundaries. So, there we go! Now we have raycasting from a particle moving with Perlin
noise throughout a space in all 360 directions, only drawing the rays where
it actually hits a boundary. (dinging) (train whistling) There is so much you can do with this. I am going to return to do a video where I take this idea
and then render the view. So, a couple things I want to do. One is, I want these to be
sensors to a neural network. So, I want this object to
learn how to move about a space based on its ability to see
the boundaries around it. Another thing that I want to do is see if I can take this
and then render the view of a 3D scene. This is the kind of
classic DOOM or Wolfenstine Wolfenstine 3D, right,
one of those things. (chuckling) Effects. Stop me for a second, here. People are asking me to put
boundaries along the edges. So, why not? I'll fast-forward this for you. (calming music) Okay, so, here are four boundaries,
if I did this correctly. The top wall, the right
wall, the bottom wall, and the left wall. Let's see what that looks like. So, now you can see the rays
are always going to go out in every single direction. Alternatively, I kind of like it better without it casting
everything out to the walls. So, here is that again, and the chat is saying,
"More rays, please". More rays? So, let's add that. So, particle right now, I
made a very arbitrary decision to have the angle
increments at 10 degrees. If I change this to one. There we go, this feels
much more like light, right? You can almost, sort of, get the sense. Again, the boundaries are in
a sort of weird place here, but you can get the sense
of this casting of shadows. Oh, now I should put the walls back in, and maybe, just maybe, I might like to draw the ray. Just maybe I'd like to draw these lines with a stroke weight of, let's actually just give it an alpha. A little bit of transparency? And let's see what happens. There we go, ooh, I like that! So, yeah, so now you really
see it's like a light source that's just casting its light everywhere, and you can see where the shadows are. Thank you for watching this
raycasting coding challenge. This one was a lot of fun to do, and I think there are a lot
of creative possibilities that you could explore
building on top of this very basic example that I've made. I haven't added color to this, the boundaries are just
in random locations. They could be drawn by a user, they could be part of
some generative pattern. How the actual light source
moves about the space doesn't have to be by a user
interaction or Perlin noise. There could be multiple light sources, there could be different
kinds of boundaries. There are so many things you could do. I'm sure there are things you could do that I'm not even thinking of. There are a whole bunch
of follow-up videos I could also do exploring
this topic further. So, the first thing that
I want to try to tackle is just exploring this idea of raytracing. Could I render, sort of
like a 3D view of the scene from this little point of light
that's moving about a space? There's also another technique
for doing essentially the same exact thing, called raymarching. There's a wonderful coding adventure video by Sebastian Lague that I referenced at the beginning of this video that you should check out, and I'm going to come
back and do my own version of that raymarching in
2D algorithm as well. So, thanks for watching, and see you in a future coding challenge. (train whistling) (bright pop music)
