[beautifully solved]extrapolating a line to screen edge, origin is center screen

[suicidal pencil]

Now, I am willing to admit that my math sucks. Pretty bad, but almost every math problem I encounter I can usually work through by bashing my head against it. This problem, so seemingly simple, has made my procedure end in a concussion, instead of success.

here's a visual representation of what I'm doing:


Let me explain:

• The intersection of the blue dashed lines is the origin of every line (400, 300)
  
• The red lines represent the known line
  
• The yellow lines represent the extrapolated path of the red lines
  
• Where the red lines turn into yellow lines is the location of a mouse click
  
• The end of the extrapolated line will always be at the screen edge, never farther.
  

The issue I'm having is accurately extrapolating that line. My first attempt at a solution was relatively simple: get the slope, increment/decrement x which changes y, and keep going until I hit an edge. Slow and time consuming, but at the time I was just looking to brute force it so I could continue on other stuff (optimization comes later). However, the results are far from accurate. Depending on where the click happens, the end of the extrapolated line is in the thousands, or it's a location in the completely wrong direction.

Could someone advise me on what I've done wrong? Code below.

Code: ags

  function ExtrapolateShot(float x1, float y1, float x2, float y2)
  {
    //x1 and y1 represent the origin
    //using floats for accuracy
    float rise;
    float run;
    int xdirection = 1; //which way x is going to move, 1 = positive
    
    //debugging...
    DL7.Text = String.Format("x1 %f y1 %f x2 %f y2 %f", x1, y1, x2, y2);
    
    if(x1 > x2)
    {
      run = x1-x2;
      xdirection = 0;
    }
    else run = x2-x1;
    if(run == 0.0) return 0; //just catching the error, to be removed
    
    if(y1 > y2) rise = y1-y2;
    else rise = y2-y1;
    
    float slope = rise/run;
    float eX = x2;
    float eY = y2;
    String EdgeCoor;
    
    while(eX > 0.0 && eX < 800.0)
    {
      if(eY < 0.0 || eY > 600.0)
      {
        EdgeCoor = String.Format("%f %f", eX, eY);
        DL8.Text = String.Format("%f %f y", eX, eY); //debug
        return EdgeCoor; //I'm aware that I can't return strings, this is just to show where the function can escape
      }
      
      if(xdirection == 1) eX += 1.0;
      else eX -= 1.0;
      
      eY = eX*slope;
    }
    
    EdgeCoor = String.Format("%f %f", eX, eY);
    DL8.Text = String.Format("%f %f x", eX, eY); //debug
    return EdgeCoor;
  }

I'm also trying to keep the code flexible so that the origin can move around the screen (instead of being stuck at 400,300), but while the code doesn't work this is of little concern.

[Gilbert]

Edited: Swapped back x and y for the correct order.

I'm halfway through your codes, not finish reading it yet, but one obvious problem is that you calculate the slope wrongly.

No matter what (x1, y1) and (x2, y2) are, the slope is defined by: (y2-y1)/(x2-x1) (or (y1-y2)/(x1-x2), which is essentially the same thing). Note that if you subtract x1 from x2 in the denominator, then you have to subtract y1 from y2 in the numerator, that is, the numbers in the numerator and the denominator have to be subtracted in the same order.

In your codes you choose to use x2-x1 or x1-x2 according to which is larger. This is fine, but the y's in the numerator should be subtracted in the same order, not according to which of the y's is larger, so this part:

Code: ags

    if(y1 > y2) rise = y1-y2;
    else rise = y2-y1;
    
    float slope = rise/run;

should probably should be

Code: ags

    if(positive) slope = (y2-y1)/run;
    else slope = (y1-y2)/run;
    

There may be other errors in the remaining codes but I'm in a hurry atm.

[monkey0506]

I haven't worked with graphs in years, but unless I'm mistaken you should be able to find the edge-collision pretty easily as soon as you know the slope.

Code: ags

String ExtrapolateShot(float x1, float y1, float x2, float y2) // defining String as the return type means you CAN return a String (not a string though)
{
  float rise = (y2 - y1);                                                              // rise
  float run = (x2 - x1);                                                               // run
  float xedge = IntToFloat(System.ViewportWidth);                                      // positive run heads toward right of screen
  float yedge = 0.0;                                                                   // positive rise heads toward top of screen
  if (rise < 0.0) yedge = IntToFloat(System.ViewportHeight);                           // negative rise heads toward bottom of screen
  if (run < 0.0) xedge = 0.0;                                                          // negative run heads toward left of screen
  float xsteps = 0.0;                                                                  // account for undefined slope (run == 0.0)
  if (run > 0.0) xsteps = ((xedge - x1) / run);                                        // the number of steps in the X-direction before we hit an edge
  if (xsteps < 0.0) xsteps = -xsteps;                                                  // make sure the number of steps is positive
  float ysteps = 0.0;                                                                  // account for 0 slope (rise == 0.0)
  if (rise > 0.0) ysteps = ((yedge - y1) / rise);                                      // the number of steps in the Y-direction before we hit an edge
  if (ysteps < 0.0) ysteps = -ysteps;                                                  // make sure the number of steps is positive
  if ((xsteps == 0.0) && (ysteps == 0.0)) AbortGame("Invalid coordinates specified."); // prevent invalid coordinates
  float steps = xsteps;                                                                // get minimum number of steps before we hit an edge
  if ((ysteps != 0.0) && (ysteps < xsteps)) steps = ysteps;                            // if fewer Y-steps, use those
  xedge = (run * steps) + x1;                                                          // get X-edge coordinate
  yedge = (rise * steps) + y1;                                                         // get Y-edge coordinate
  return String.Format("%f,%f", xedge, yedge);                                         // return coordinates of edge collision
}

There might be a way to simplify this even further, so one of the math buffs might be able to help out more, but I've tested this with several values and the resultant slope matches the specified slope as far as I can tell.

Seems to me that you should be able to determine from the rise and run how many steps you need to take before you hit an edge, and then you can extrapolate the resultant edge coordinate from there.

Edit: Changed static 800.0 and 600.0 values to something more dynamic for other resolutions..

Edit 2: Modified the code to prevent divide-by-zero errors. Thanks for pointing that out Pencil. I've called AbortGame if both the rise and run are undefined (both coordinates passed in are the same), but you might want to handle it differently, it's up to you. Of course you shouldn't run into that I would assume, but it could be handled nicer if you need it for some reason.

[suicidal pencil]

Not only did I learn from my mistake, I learned something new  

Thank-you both, I understand a bit more now and your code works perfectly, monkE3y. I only had to change one line outside that function for it to fit. The only problem your code has is when it divides by zero    Whenever the mouse is perfectly in line horizontally or vertically with the origin, run and rise respectively end up being zero. I can take it from here, thank-you again =D

(I'm going to be honest, I'm going to go through your code on paper so I know exactly what's going on. I can't really do math in my head very well, but I have no issues with it on paper.)

[monkey0506]

Thanks for pointing out that divide-by-zero error. It should be corrected now.

As for my code, the basic idea is this..

The "edges" are defined as (0,0) to (0,600), (0,600) to (800,600), (800,600) to (800,0), and (800,0) to (0,0). So any point along an edge will be at (0,Y), (800,Y), (X,0), or (X,600). Anything else wouldn't be on the edge.

From there, we already have the rise and run (slope), and two definite points (whether either is the origin or not is actually irrelevant now). We actually only need one point since we know the slope, and know where the line is going to go from that point. So, depending which way the slope of the line is heading, we can determine which two of the edges we need to take into consideration.

If the line is heading up-right, then we need to look at the top and right edges, heading down-right we need to look at the bottom and right edges, heading up-left we need to consider the top and left edges, and heading down-left it's the bottom and left edges. If there's no slope, or an undefined slope, then we only have to look at one edge.

Regardless of how many edges we are looking at (whether it's one or two), we can take the difference between the edge and the first point along each axis, which will allow us to determine (based on the rise or run, depending on the axis), how many steps it will take to get from that first point to the edge. If we're looking at more than one edge, then whichever one has the fewest steps is the one the line will reach first.

From there we just calculate, again based on the rise and run, what the other coordinate will be when we finally hit that edge.

Hopefully that helps explain it somewhat better.

[suicidal pencil]

Thanks for pointing out that divide-by-zero error. It should be corrected now.

I won't lie, I'm being a bit lazy right now (watching a 3 1/2 hours movie), which means I didn't get to analyzing the code on paper or writing in the handling of the divide-by-zero, but I've tested both iterations of your code and the latest has another tiny problem...

Okay, that's a euphemism. The function is borked. The extrapolated line goes past the top edge, any location in the bottom left quadrant is a set (400,300), and any location in the top left quadrant causes AbortGame to be called. I commented it out and tested it, and the result is the same as the bottom left. Bottom right works fine, and so does top left (if the extrapolated line doesn't cross the top edge).

You didn't need to go to the trouble of handling the divide by zero, but I'm thankful you have. As well, your description did help my understanding   Still going to look at it on paper just so I'm 100% confident that I know how it works  


I wish this scripting language looked and worked more like Perl...if to name only one advantage, regular expressions =) but I know that Perl would make no sense as the scripting language...maybe for a MUDD based adventure game

[Khris]

So, is this solved yet?

If no:

Code: ags

String ExtrapolateShot(float x1, float y1, float x2, float y2) {

  float xs1 = (x2 - x1), ys1 = (y2 - y1);                                
  float xedge = IntToFloat(System.ViewportWidth), yedge = IntToFloat(System.ViewportHeight);                                  

  float w = xedge, h = yedge, k;

  if (xs1 < 0.0) xedge = 0.0;                                
  if (ys1 < 0.0) yedge = 0.0; 

  // xedge
  float d = - xs1*h;
  if (d != 0.0 && -d != 0.0) {   // yup
    k = (ys1*(xedge-x1) - xs1*(-y1))/(-d);
    if (k >= 0.0 && k <= 1.0) return String.Format("%f,%f", xedge, k*h);
  }

  // yedge
  d = ys1*w;
  if (d != 0.0) {
    k = (ys1*(-x1) - xs1*(yedge-y1))/(-d);
    return String.Format("%f,%f", k*w, yedge);
  }
  return "FAIL";
}

[suicidal pencil]

So, is this solved yet?

Technically yes, the first code segment monkE3y posted that had the divide by zero error (seen below) worked perfectly (except when rise or run were 0, of course). I still need to check how accurate it is, but it should be no more complicated then just drawing that line.

Code: ags

  String ExtrapolateShot(float x1, float y1, float x2, float y2) // defining String as the return type means you CAN return a String (not a string though)
  {
    
    float rise = (y2 - y1);                                    // rise
    float run = (x2 - x1);                                     // run
    float xedge = IntToFloat(System.ViewportWidth);            // positive run heads toward right of screen
    float yedge = 0.0;                                         // positive rise heads toward top of screen
    if (rise < 0.0) yedge = IntToFloat(System.ViewportHeight); // negative rise heads toward bottom of screen
    if (run < 0.0) xedge = 0.0;                                // negative run heads toward left of screen
    float xsteps = ((xedge - x1) / run);                       // the number of steps in the X-direction before we hit an edge
    if (xsteps < 0.0) xsteps = -xsteps;                        // make sure the number of steps is positive
    float ysteps = ((yedge - y1) / rise);                      // the number of steps in the Y-direction before we hit an edge
    if (ysteps < 0.0) ysteps = -ysteps;                        // make sure the number of steps is positive
    float steps = xsteps;                                      // get minimum number of steps before we hit an edge
    if (ysteps < xsteps) steps = ysteps;                       // if fewer Y-steps, use those
    xedge = (run * steps) + x1;                                // get X-edge coordinate
    yedge = (rise * steps) + y1;                               // get Y-edge coordinate
    return String.Format("%f,%f", xedge, yedge);               // return coordinates of edge collision
  }
  

Still, I tested your code. The data it's giving me isn't correct, not quite as wild as my original attempt but just as weird. X equals either 0 (when mouse is left of origin) or 800 (when mouse is right of origin) and never anything else. Y on the other hand is accurate only when the extrapolated line hits the x edges.

edit: I checked the accuracy of monkE3y's function (the first one...) and it's perfect.

[Khris]

I tested my code and it worked perfectly fine.
Just to make sure, you're calling it like this, right?

Code: ags

  Display(ExtrapolateShot(400.0, 300.0, IntToFloat(mouse.x), IntToFloat(mouse.y)));

X equals either 0 (when mouse is left of origin) or 800 (when mouse is right of origin) and never anything else. Y on the other hand is accurate only when the extrapolated line hits the x edges.

That's the expected result if the mouse is sufficiently off-center horizontally.
Are you saying that my function fails if the mouse is closer to the upper or lower screen edge?

I went ahead and tested my function in a 800x600 game. Works flawlessly.

[suicidal pencil]

Just to make sure, you're calling it like this, right?

Code: ags

  Display(ExtrapolateShot(400.0, 300.0, IntToFloat(mouse.x), IntToFloat(mouse.y)));

The function is called like this:

Code: ags

String ShotEnd = ExtrapolateShot(IntToFloat(FiringX), IntToFloat(FiringY), IntToFloat(AimX), IntToFloat(AimY));

The data is printed on a gui label just before returns. The only time this function gets called is on left mouse click.

That's the expected result if the mouse is sufficiently off-center horizontally.
Are you saying that my function fails if the mouse is closer to the upper or lower screen edge?

When the extrapolated line is to intersect the upper or lower edges before the left or right edges, Y is supposed to stay at 0 or 600 respectively. If the extrapolated line is to intersect the left or right edges before the upper or lower edges, X is to be 0 or 800 respectively. When I tested your code Y constantly changed when it was supposed to stay at 0 or 600, and X was either 0 or 800, and not the in between values when it is supposed to be.

[Khris]

When the extrapolated line is to intersect the upper or lower edges before the left or right edges, Y is supposed to stay at 0 or 600 respectively. If the extrapolated line is to intersect the left or right edges before the upper or lower edges, X is to be 0 or 800 respectively.

This is exactly the result I get when using my code. Not sure what you're doing on your end but since monkey's code does what you need let's leave it at that

[monkey0506]

Okay I've done some testing, and I've made some more modifications. I didn't test the changes I made before when I tried to fix the divide-by-zero error..but there was actually quite a few things that I messed up:

Code: ags

String ExtrapolateShot(float x1, float y1, float x2, float y2) // defining String as the return type means you CAN return a String (not a string though)
{
  float rise = (y2 - y1);                                                              // rise
  float run = (x2 - x1);                                                               // run
  float xedge = IntToFloat(System.ViewportWidth);                                      // positive run heads toward right of screen
  float yedge = IntToFloat(System.ViewportHeight);                                     // positive rise heads toward bottom of screen
  if (rise < 0.0) yedge = 0.0;                                                         // negative rise heads toward top of screen
  if (run < 0.0) xedge = 0.0;                                                          // negative run heads toward left of screen
  float xsteps = 0.0;                                                                  // account for undefined slope (run == 0.0)
  if (run != 0.0) xsteps = ((xedge - x1) / run);                                       // the number of steps in the X-direction before we hit an edge
  if (xsteps < 0.0) xsteps = -xsteps;                                                  // make sure the number of steps is positive
  float ysteps = 0.0;                                                                  // account for 0 slope (rise == 0.0)
  if (rise != 0.0) ysteps = ((yedge - y1) / rise);                                     // the number of steps in the Y-direction before we hit an edge
  if (ysteps < 0.0) ysteps = -ysteps;                                                  // make sure the number of steps is positive
  if ((xsteps == 0.0) && (ysteps == 0.0)) AbortGame("Invalid coordinates specified."); // prevent invalid coordinates
  float steps = xsteps;                                                                // get minimum number of steps before we hit an edge
  if (((ysteps != 0.0) && (ysteps < xsteps)) || (xsteps == 0.0)) steps = ysteps;       // if fewer Y-steps, use those, but only if there are any Y-steps, OR if there are no X-steps
  xedge = (run * steps) + x1;                                                          // get X-edge coordinate
  yedge = (rise * steps) + y1;                                                         // get Y-edge coordinate
  return String.Format("%f,%f", xedge, yedge);                                         // return coordinates of edge collision
}

I've tested this with various coordinates in every quadrant, as well as various coordinates along each axis, and it should be fixed now.

[Dualnames]

On a totally unrelated note, hey suicidal pencil, welcome back, we missed you!! 

[suicidal pencil]

On a totally unrelated note, hey suicidal pencil, welcome back, we missed you!! 

lol, thanks    My hiatus was partially due to laziness, but when my laptop was stolen with my unfinished Guitar Hero clone, it took me quite a while to get the drive to program back. I had just finished the song editor, too 

This is actually one of two projects I'm working on at the moment. Might resurrect AGS:GH, but not after I finish this ^_^

And MonkE3y, that code works as perfectly as the first iteration, without that error of course  Much appreciated.

[monkey0506]

Yeah, once I actually tested the modified version of the original code, I realized just how borked it was. :

Glad I got the error actually fixed for you though. Can I ask what this is for?

[suicidal pencil]

Glad I got the error actually fixed for you though. Can I ask what this is for?

You may  

It's one half of my attempt to implement hitscan in a birds-eye view styled shooter. Next is collision detecting!

Even if I gave the project 6 hours of attention a day, it'll probably still take a solid month or two to finish  

edit: If you want to get an idea for the feel of the game, here's a sample of the music I'll be using (shamelessly ripping...hey, I'm terrible at graphic design and creating music, give me a break  ). Thinking about it, the picture describes it pretty well too. I'm pretty sure I can get away with it, seeing as I don't expect anyone to pay to play, and the source will be available when it's done   And of course, anything in it that is not my own creation will be credited