- 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,
and B is a new boundary
between, I don't know,
300,
300.
No, 300, 100,
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)