Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


2D Ray-casting problems, don't align correctly.


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
12 replies to this topic

#1 Moonkis   Members   -  Reputation: 273

Like
0Likes
Like

Posted 29 November 2012 - 09:30 AM

I'v been trying and studying a hell of a lot for making my 2D raycasting, I'v been visiting KahnAcademy for Trigonometry-lessons as well as reading various topics ( each with a completely different method of achieving it. )

I'v chosen to stick with the topic found here

Currently I'm just trying to get the ray-casting and movement to work, so far so good, almost.
I'm not entirely sure of how to do the casting, but I got something almost working, though it's a bit off. Here is how it looks so far:
Posted Image

The blue/magenta arrow is the direction the player will travel ( current angle ) and the white rays are supposed to be the ray-casting, as you can see it's off by quite a bit and I can't understand why.

Here is my current casting code:
  sf::VertexArray ray(sf::Lines, 2);
  const int travelingDistans = 400;
  double subsequentRayAngleIncrease = player.fov/w;
  // Start from column 0 to the X't column of the viewing plane.
  // I'm not sure what the viewing plane is but I'm guessing it's the screen.
  // Which would mean from 0 to our screens highest x, which is 800.
  // Since the resolution is 800x600
  for( int i = 0; i < w; i++)
  {
   double rayAngle = player.rot - ( (player.fov/2) + subsequentRayAngleIncrease*i );

   double rx =  player.x - travelingDistans * std::cos(Math::to_radians(rayAngle));
   double ry =  player.y - travelingDistans * std::sin(Math::to_radians(rayAngle));
   // + 5 is so it's centered of the players origin
   ray[0] = sf::Vector2f( player.x + 5 , player.y + 5);
   ray[1] = sf::Vector2f( rx + 5, ry +5 );
   ray[1].color = sf::Color(255,255,255,30);
   ray[0].color = sf::Color(255,255,255,30);
   rwind.draw(ray);
  }

What am I doing wrong?

Also a couple of side questions:

1. Why do you multiply by -d and not just d ( distance ) when calculating with sin and cos?
2. Does this technique look right considering it's supposed to transition into fake 3D using 2D raycasting ( Given that the final ray distance is determined on where it hit a wall ).

Kind regards
Moonkis


EDIT:

Realized that the offset was due to me accidentally subtracting the subsequent ray angle when calculating the offset using players FOV
Changed it from this:
double rayAngle = player.rot - ( (player.fov/2) + subsequentRayAngleIncrease*i );
into this:
double rayAngle = ( player.rot -  (player.fov/2)  ) + subsequentRayAngleIncrease*i;

It seems to work as intended now, checked using 90, 180, 270 and 360 FOV angles. ( 180 and 90 was the ones I based it on working, they looked as intended, also added some wrapping when calculated angles for the rx and ry:
if( rayAngle == 360 ) rayAngle = 0;
if( rayAngle > 360 )
{
    rayAngle = ( rayAngle - 360 );
}
if( rayAngle < 0 )
{
    rayAngle = ( 360 + rayAngle );
}

Seeing as I only like to work with the angels 0 - 359 ( sin(to_radiance(360)) and sin(to_radiance(0)) gave different angles where as 0 degrees to radians was the most correct one.

Edited by Moonkis, 29 November 2012 - 10:47 AM.


Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13934

Like
0Likes
Like

Posted 29 November 2012 - 09:50 AM

Whether you multiply by d or -d and whether you use cosine for x or for y depends on the conventions you are using. I would stick to trigonometric conventions as much as possible, where angle 0 points in the positive x direction, and angles go up counterclockwise.

I don't think you need nearly as much trigonometry as you are using. The pixel columns on your screen don't cover a constant angle: The center column covers a larger angle than the column on the far right. Imagine you have a very large screen compared to the distance you are sitting from it and it will be obvious.

The way I think about this, the player is looking in some direction (cos(player.rot),sin(player.rot)), which I'll call (x,y) for short. Now you can compute an equally-spaced sequence of points from (x,y)-K*(y,-x) to (x,y)+K*(y,-x) and launch rays in those directions. K is a constant that you can compute as tan(FOV/2).

By the way, as part of my crusade against angles, you can store the direction in which the player is looking as (x,y) directly, instead of an angle. And I even prefer to specify K directly instead of FOV. But start by getting your code working.

Edited by Álvaro, 29 November 2012 - 09:50 AM.


#3 Álvaro   Crossbones+   -  Reputation: 13934

Like
0Likes
Like

Posted 29 November 2012 - 09:57 AM

Oh, one more thing!

const int travelingDistans = 400;

You didn't post all your code, so I don't know if this is biting anywhere, but you should really use the intended type for every variable. That variable should be a double instead of an int. Getting the type wrong could result in expressions like player.fov/w being truncated, if player.fov and w happen to be integers.

#4 Moonkis   Members   -  Reputation: 273

Like
0Likes
Like

Posted 29 November 2012 - 10:22 AM

Whether you multiply by d or -d and whether you use cosine for x or for y depends on the conventions you are using. I would stick to trigonometric conventions as much as possible, where angle 0 points in the positive x direction, and angles go up counterclockwise.


Well I just based on what angles I got from 0, 90, 180 and 270, isn't this the trigonometric conventions?
// In degrees:
//		  ^ 90 deg
//		  |
// 360/0 deg| 180 deg
//    <----- ------>
//		  | a = 90 degrees delta
//		  |
//		  v 270 deg

I don't think you need nearly as much trigonometry as you are using. The pixel columns on your screen don't cover a constant angle: The center column covers a larger angle than the column on the far right. Imagine you have a very large screen compared to the distance you are sitting from it and it will be obvious.

This dosn't tell me much :/

The way I think about this, the player is looking in some direction (cos(player.rot),sin(player.rot)), which I'll call (x,y) for short. Now you can compute an equally-spaced sequence of points from (x,y)-K*(y,-x) to (x,y)+K*(y,-x) and launch rays in those directions. K is a constant that you can compute as tan(FOV/2).

I have no clue why that works. Or how it works, Or in what context to use it.

By the way, as part of my crusade against angles, you can store the direction in which the player is looking as (x,y) directly, instead of an angle. And I even prefer to specify K directly instead of FOV. But start by getting your code working.

I get that your against angles by now, but your crusade is not really helping me understand it, sorry. It just confuses me more :/
Sorry.

#5 Álvaro   Crossbones+   -  Reputation: 13934

Like
1Likes
Like

Posted 29 November 2012 - 10:33 AM

Well, the way you are increasing the angle in the code you posted, seems to indicate that each column on the screen covers an equal angle from the eye, which is not true unless you have a cylindrical screen and you sit at the axis of the cylinder (which would be totally cool ;) ). If your screen is closer to a flat surface, you should do something like what I describe.

We seem to have trouble communicating, but I can think of a way to move forward: Come up with a specific example (player is here, looking in this direction, FOV is 45 degrees... whatever). Then I can walk you through what the code should do and why.

My distaste for angles is not capricious. I actually started writing graphics programs with angles everywhere, and over the years I have learned to think in terms of vectors instead, which made my code cleaner, faster and easier to get right. I hope my crusade will actually help you. But we'll see.

#6 Moonkis   Members   -  Reputation: 273

Like
0Likes
Like

Posted 29 November 2012 - 10:47 AM

I edited my original post, I got the ray-casting aligning but I'm more than interested in getting a lesson and answers on my question, once I get into the part where my rays are supposed to render a fake 3D image I can't afford to have it done wrong in the beginning.

Okey so here is an example:

Object A is facing straight up ( towards the top of the screen ) and is currently at (400, 300) where the screen size is 800x600. Object A's FOV is 60 Degrees and needs the rays to identify whether there are objects in his line of sight.

Is this enough of information?
Also please when using tan and sin just quickly mention what it does and what it's for so I can have a context of it.

Kind regards,
Victor Karlsson

PS. I'm very glad for all your efforts on helping me!

#7 Álvaro   Crossbones+   -  Reputation: 13934

Like
0Likes
Like

Posted 29 November 2012 - 11:36 AM

You seem to be using the coordinates of the screen directly, with (0,0) being the top-left corner. Notice that in those coordinates, an increase in y goes down, while the convention used in Math is that an increase in y goes up. This explains why you need to negate the sin(...) part. The sign of the cos(...) part should be positive, but your particular test is symmetric, so you haven't noticed the problem yet.

I will use traditional Math convention for everything. I will also assume the player is at (0,0) to simplify things. If your player is facing straight up, I guess player.rot = 90 degrees. You can draw an arrow of length 1 from the origin pointing in that direction, it will have coordinates (0,1). In general the coordinates are (cos(player.rot), sin(player.rot)). The length of 1 is arbitrary. If it helps you visualize it better, you can think of it as an arrow of length 100, which would have coordinates (0,100). In the end that factor of 100 won't matter. From now on, let this vector be (x,y).

Now I am going to draw a segment that represents the screen (I assume we are viewing the whole thing from the top of the scene). It will be a segment that is perpendicular to (0,1). You can find a direction that is perpendicular to (a,b) by computing (-b,a) (that's a rotation of 90 degrees counterclockwise). In our case, we'll get (-1,0). The segment I will draw will have (0,1) as the center and the left end will be at a point (0,1)+K*(-1,0). Reminder: That notation means (0+K*(-1),1+K*0) = (-K,1). The other end will be (0,1)-K*(-1,0), which is (K,1). I don't know what K is yet, but it will depend on FOV somehow.

So let's compute K. If you have been making a drawing of this (which you should), you can look at the triangle formed by the origin (0,0), the center of my "screen segment" (0,1) and the far right end of my screen segment (K,1). This triangle is rectangle at (0,1), and I am interested in the angle at the origin, which should be FOV/2 = 30 degrees. The tangent of that angle can be computed as "opposite side / adjacent side", which is K/1. That tells me that K/1 = tan(30 degrees) = 0.57735, and that's how I compute K.

Now my code would look something like this:
double const distance_to_screen = 300.0;
  double look_angle = Math::to_radians(player.rot);
  // The next two definitions have sings different than the text, to																				
  // try to adapt to the convention that y increases going down.																					
  sf::Vector2f look_vector(distance_to_screen*std::cos(look_angle),
						   -distance_to_screen*std::sin(look_angle));
  sf::Vector2f left_vector(look_vector.y, -look_vector.x);

  double K = std::tan(0.5 * player.fov);
  sf::Vector2f far_left_end = look_vector + K * left_vector;
  sf::Vector2f one_column_increment = -2.0 * K * left_vector / w;

  sf::VertexArray ray(sf::Lines, 2);
  ray[0] = player;
  ray[0].color = sf::Color(255,255,255,30);
  ray[1].color = sf::Color(255,255,255,30);
  for (int i = 0; i < w; i++) {
	// Instead of adding +5 to x and y here, change your code so the																				
	// meaning of `player' is the center of the player																							  
	ray[1] = player + far_left_end + i * one_column_increment;
	rwind.draw(ray);
  }

I don't have a complete program to play with, so there might be mistakes in that code. If it doesn't work and it's not trivial to fix, I'll try to post a complete program, but this will probably need to wait until tonight.

Edited by Álvaro, 29 November 2012 - 11:38 AM.


#8 Moonkis   Members   -  Reputation: 273

Like
0Likes
Like

Posted 29 November 2012 - 01:10 PM

If you have been making a drawing of this (which you should), you can look at the triangle formed by the origin (0,0), the center of my "screen segment" (0,1) and the far right end of my screen segment (K,1).

How can I do that? I have no idea where the point(K,1) is? Since we haven't computed it.

Here is what I drew up until that point:
Posted Image
EDIT 2: I'm not sure if we are using cartesian-coordinate system or normal math one?

What exactly is distance_to_screen? and also your using player like a struct then telling me player is a vector representing the origin of the player?

EDIT:

On a second note maybe one thing should be clarified as well:
1. "The pixel columns on your screen don't cover a constant angle" - I'm not 100% sure I get that statement, maybe a picture ( when you have time of course! ) along with words could help straighten that out.

PS. I'm so sorry for getting this slow, and that you take a lot of time explaining it to me.

Edited by Moonkis, 29 November 2012 - 02:25 PM.


#9 Álvaro   Crossbones+   -  Reputation: 13934

Like
0Likes
Like

Posted 29 November 2012 - 02:34 PM

If you have been making a drawing of this (which you should), you can look at the triangle formed by the origin (0,0), the center of my "screen segment" (0,1) and the far right end of my screen segment (K,1).

How can I do that? I have no idea where the point(K,1) is? Since we haven't computed it.

Dude, in the next sentence after what you quote I tell you myself that we don't know what K is yet, and than I have a paragraph devoted to describing how to compute K. You need to work on your reading comprehension.

I'll try to give you an even more detailed explanation tonight.

#10 Moonkis   Members   -  Reputation: 273

Like
0Likes
Like

Posted 29 November 2012 - 04:51 PM

I'm just letting you know that I changed the degree convention, x-positive is now 0 and increase the angle y going conter-clockwise ( Which helps with just keeping it: cos(a)*d and sin(a)*d )

Also I'v been trying to adapt your code here ( since you can't multiply vectors in SFML I'm giving an alternative version a go ) it currently looks like this:
  double K = std::tan(player.fov/2);
  double distance_to_screen = 300;
  sf::Vector2f look_vector(std::cos(radians)*distance_to_screen, std::sin(radians)*distance_to_screen);
  sf::Vector2f left_vector(look_vector.x, -look_vector.y);
  sf::Vector2f far_left_end = look_vector;
  far_left_end.x + K * left_vector.x; far_left_end.y + K * left_vector.y;
  sf::Vector2f one_column_increment(-2.0,-2.0);
  one_column_increment.x * K * left_vector.x / w; one_column_increment.y * K * left_vector.y / w;
  sf::VertexArray ray(sf::Lines, 2);
  ray[0] = sf::Vector2f(player.x+5, player.y+5);
  for( int i = 0; i < w; i++ )
  {
   ray[1] = sf::Vector2f( player.x+5 + far_left_end.x + i * one_column_increment.x, player.y+5 + far_left_end.y + i * one_column_increment.y);
   rwind.draw(ray);
  }
Though I did not get it to work as intended.

By the way, don't stress man, I'm just happy that you are helping me ( Can't stress that enough ) so take your time.

Edited by Moonkis, 29 November 2012 - 05:06 PM.


#11 Álvaro   Crossbones+   -  Reputation: 13934

Like
0Likes
Like

Posted 29 November 2012 - 04:59 PM

This seems to work. See if you understand how it does everything and ask about anything that is not entirely clear.

#include <SFML/Graphics.hpp>
#include <iostream>
#include <cmath>
void draw_line(sf::RenderWindow &app, sf::Vector2f from, sf::Vector2f to) {
  app.Draw(sf::Shape::Line(std::floor(400.0f + from.x * 200.0f),
						   std::floor(300.0f - from.y * 200.0f),
						   std::floor(400.0f + to.x * 200.0f),
						   std::floor(300.0f - to.y * 200.0f),
						   1, sf::Color::White));
}
int main() {
  sf::RenderWindow app(sf::VideoMode(800, 600), "Ray casting computations");

  while (app.IsOpened()) {
    sf::Event Event;
	while (app.GetEvent(Event)) {
      if (Event.Type == sf::Event::Closed)
		app.Close();
	}
  
    app.Clear();
  
	int const width = 100;
  
	float const degrees = std::atan(1.0f)/45.0f;
	float K = std::tan(30.0f*degrees);
	sf::Vector2f position(0.0f, 0.0f);
	sf::Vector2f heading(std::cos(30.0f*degrees), std::sin(30.0f*degrees));
	sf::Vector2f left(-heading.y, heading.x);
	sf::Vector2f left_edge = position + heading + K * left;
	sf::Vector2f step = -(2.0f * K / width) * left ;
  
	for (int i=0; i<width; ++i) {
	  sf::Vector2f ray_end = left_edge + step * (i+0.5f);
	  draw_line(app, position, ray_end);
	}
    app.Display();
  }

  return EXIT_SUCCESS;
}

Edited by Álvaro, 29 November 2012 - 05:00 PM.


#12 Moonkis   Members   -  Reputation: 273

Like
0Likes
Like

Posted 29 November 2012 - 05:27 PM

Ugh, a lot of magic numbers, but the code works ( needed to make a bit conversion magic into SFML 2.0 )!
Is it okay if I respond tomorrow? It's getting quite late here :)

On the top of my head here are some questions:
void draw_line(sf::RenderWindow &app, sf::Vector2f from, sf::Vector2f to) {
sf::VertexArray line(sf::Lines, 2);
line[0] = sf::Vector2f(std::floor(400.0f + from.x * 200.0f),std::floor(300.0f - from.y * 200.0f));
line[1] = sf::Vector2f(std::floor(400.0f + to.x * 200.0f), std::floor(300.0f - to.y * 200.0f) );
app.draw(line);
}
I'm guessing 200.0f is the distance to draw the rays, 400.0f is the center of the map, and so is 300.0f?


float const degrees = std::atan(1.0f)/45.0f;
What exactly are the values used here? What does 1 and 45 represent?

float K = std::tan(30.0f*degrees);
What exactly is 30 representing in the code? Is it the same 30? for all the 30's in the code?

sf::Vector2f left(-heading.y, heading.x);
Why is the y and x inverted?

sf::Vector2f step = -(2.0f * K / width) * left ;
I have no idea what this is.

sf::Vector2f ray_end = left_edge + step * (i+0.5f);
What exactly is end here and what is the number 0.5 coming from.

Also in the drawing exercise before what coordination system are we using? Polar or Cartesian? I'd love to be able to draw It sucessfully since that might just be the key to being able to visualise it manually.

Also, great work!

#13 Álvaro   Crossbones+   -  Reputation: 13934

Like
0Likes
Like

Posted 29 November 2012 - 06:11 PM

Ugh, a lot of magic numbers, but the code works ( needed to make a bit conversion magic into SFML 2.0 )!

Yeah, that's fair criticism. I thought the origin of the numbers would be more or less obvious, but it would be better to give things names.

Is it okay if I respond tomorrow? It's getting quite late here Posted Image

Of course.

On the top of my head here are some questions:

void draw_line(sf::RenderWindow &app, sf::Vector2f from, sf::Vector2f to) {
sf::VertexArray line(sf::Lines, 2);
line[0] = sf::Vector2f(std::floor(400.0f + from.x * 200.0f),std::floor(300.0f - from.y * 200.0f));
line[1] = sf::Vector2f(std::floor(400.0f + to.x * 200.0f), std::floor(300.0f - to.y * 200.0f) );
app.draw(line);
}
I'm guessing 200.0f is the distance to draw the rays, 400.0f is the center of the map, and so is 300.0f?

400.0f and 300.0f are indeed the center of the screen. I am using coordinates like I would in Math everywhere in the program and this is the function that translates them into screen coordinates. 200.0f is a scale factor, so the window covers the interval (-2, 2) horizontally and (-1.5, +1.5) vertically.

float const degrees = std::atan(1.0f)/45.0f;
What exactly are the values used here? What does 1 and 45 represent?

The angle whose tan is 1 is 45 degrees, so by multiplying a number of degrees by this number, you turn it into radians.

float K = std::tan(30.0f*degrees);
What exactly is 30 representing in the code? Is it the same 30? for all the 30's in the code?

30.0f if half the FOV of 60 degrees.

sf::Vector2f left(-heading.y, heading.x);
Why is the y and x inverted?

I think I covered this one already: This is just a 90-degree rotation of the heading vector.

sf::Vector2f step = -(2.0f * K / width) * left ;
I have no idea what this is.

That's how much I need to advance for each pixel.

sf::Vector2f ray_end = left_edge + step * (i+0.5f);
What exactly is end here and what is the number 0.5 coming from.

I think of the ray as an arrow, with a beginning (the player's position) and an end. The 0.5 is there so the ray aims to the center of the pixel, instead of the left side.

Also in the drawing exercise before what coordination system are we using? Polar or Cartesian? I'd love to be able to draw It sucessfully since that might just be the key to being able to visualise it manually.

I have only used Cartesian coordinates everywhere. Maybe I'll try to make a picture, but it's a bit of a pain.

Also, great work!

Thanks!




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS