Get a points coordinate

Started by
14 comments, last by P0jahn 11 years, 4 months ago

Look at these three pictures:

[attachment=12966:example1.png]

[attachment=12967:example2.png]

[attachment=12968:example3.png]

So the red object is some sort of watcher. It watches the green object. However, I do not want the coordinates of the green object, but the black circle. Is there any way to calculate this?

Some more info about my game, the top left corner is point 0,0, x increases while moving to the right and y is increasing when moving down, just like any other java coordinate system. The black circle is always going to be at the edge of the map.

Advertisement

So you want the direction to the green object from the red object?


direction = normalize(greenPos - redPos)

Then you can multiply the direction by the distance from the red object to the black circle. So if you wanted the black circle to appear 10 units away from the red object you would write:



blackCirclePos = direction * 10

Does that answer your question or have I misunderstood?

Well, I am afraid he doesn't know the distance to the black circle a priori. The black circle is wherever the ray intersects the edge of the map.

Consider a structure called a "ray" that contains the position of the red dot (the ray's "origin") and the direction (as defined in Nyssa's post). You can find a point along the ray as ray.origin + t*ray.direction. I would write a function that finds the intersection of a ray with a line, and returns the value of the parameter t where the intersection happens (use the dot product for this). Then call it four times for the edges of the map and pick the lowest non-negative value of the parameter. That should give you the position of the black dot.

I may post some easy-to-read C++ code to solve this later.

The black circle is always going to be at the edge of the map.

Ah, right, missed that bit. Thanks for clearing that up Alvaro.

Here's some C++ code to solve the problem. I tried to not use references or static variables, to not confuse matters. But I couldn't get myself to not overload a few operators... Let me know if you have a hard time understanding what it's doing. But the function find_black_dot() is the key to it all, and it should be fairly easy to follow.
#include <iostream>
#include <cmath>
struct Vector {
  float x, y;
 
  Vector(float x, float y) : x(x), y(y) {
  }
};

Vector operator*(Vector v, float s) {
  return Vector(v.x*s, v.y*s);
}

float dot_product(Vector v, Vector w) {
  return v.x*w.x + v.y*w.y;
}

Vector normalize(Vector v) {
  return v * (1.0 / std::sqrt(dot_product(v, v)));
}

struct Point {
  float x, y;
 
  Point(float x, float y) : x(x), y(y) {
  }
};

std::ostream &operator<<(std::ostream &os, Point p) {
  return os << '(' << p.x << ',' << p.y << ')';
}

Vector operator-(Point p, Point q) {
  return Vector(p.x-q.x, p.y-q.y);
}

Point operator+(Point p, Vector v) {
  return Point(p.x+v.x, p.y+v.y);
}

struct Ray {
  Point origin;
  Vector direction;
 
  Ray(Point origin, Vector direction) : origin(origin), direction(direction) {
  }
};

// If dot_product(p-origin,normal)==constant, p is in the line
struct Line {
  Vector normal;
  float constant;
  
  Line(Vector normal, float constant) : normal(normal), constant(constant) {
  }
};

float find_intersection_parameter(Ray ray, Line line) {
  return (line.constant - dot_product(ray.origin-Point(0.0f,0.0f), line.normal))
    / dot_product(ray.direction, line.normal);
}

Point find_black_dot(Point red_point, Point green_point) {
  Line lines[4] = {
    Line(Vector(1.0f,0.0f), 0.0f),
    Line(Vector(1.0f,0.0f), 30.0f),
    Line(Vector(0.0f,1.0f), 0.0f),
    Line(Vector(0.0f,1.0f), 20.0f)
  };
 
  Ray ray(red_point, normalize(green_point-red_point));
  double min_non_negative_intersection_parameter = 1.0e20f;
  for (int i=0; i<4; ++i) {
    float intersection_parameter = find_intersection_parameter(ray, lines[i]);
    if (intersection_parameter >= 0.0f
        && intersection_parameter < min_non_negative_intersection_parameter)
      min_non_negative_intersection_parameter = intersection_parameter;
  }
 
  return ray.origin + ray.direction * min_non_negative_intersection_parameter;
}

int main() {
  Point red(16.5,10.5);
  Point green(11.5,15.5);
 
  std::cout << find_black_dot(red, green) << '\n';
}

I would use the Pythagorean theorem and slope, however I'm just now getting into linear algebra tongue.png.

I'm a game programmer and computer science ninja !

Here's my 2D RPG-Ish Platformer Programmed in Python + Pygame, with a Custom Level Editor and Rendering System!

Here's my Custom IDE / Debugger Programmed in Pure Python and Designed from the Ground Up for Programming Education!

Want to ask about Python, Flask, wxPython, Pygame, C++, HTML5, CSS3, Javascript, jQuery, C++, Vimscript, SFML 1.6 / 2.0, or anything else? Recruiting for a game development team and need a passionate programmer? Just want to talk about programming? Email me here:

hobohm.business@gmail.com

or Personal-Message me on here !

You don't really need the Pythagorean theorem for this, and the method I proposed is also kind of overkill.

This is much simpler code that does the same thing. I should probably posted this solution before:
#include <iostream>

struct Point {
  float x, y;

  Point(float x, float y) : x(x), y(y) {
  }
};

Point find_black_dot(Point red_point, Point green_point) {
  float vertical_intersection_time = 1.0e20f;
  if (green_point.x > red_point.x)
    vertical_intersection_time = (30.0f-red_point.x)/(green_point.x-red_point.x);
  else if (green_point.x < red_point.x)
    vertical_intersection_time = (0.0f-red_point.x)/(green_point.x-red_point.x);

  float horizontal_intersection_time = 1.0e20f;
  if (green_point.y > red_point.y)
    horizontal_intersection_time = (20.0f-red_point.y)/(green_point.y-red_point.y);
  else if (green_point.y < red_point.y)
    horizontal_intersection_time = (0.0f-red_point.y)/(green_point.y-red_point.y);

  float time = std::min(horizontal_intersection_time,vertical_intersection_time);
  return Point(red_point.x + time * (green_point.x-red_point.x), red_point.y + time * (green_point.y-red_point.y));
}

int main() {
  Point red(16.5,10.5);
  Point green(11.5,15.5);

  Point black = find_black_dot(red, green);
  std::cout << '(' << black.x << ',' << black.y << ")\n";
}
Thanks Alvaro. May I ask what type of data the returned point actually contains? If it is the black circle as you described, how can it find it without knowing the dimension of the map?
Also, can you suggest some sort of professional name for this method? :)

I didn't understand what you did the second time there (I need to copy it into SciTE and look at it more closely), but this is what I came up with (just because I like messing with this kind of problem).


struct Vector2 {
  int x;
  int y;
};

Vector2 findTargetAlignedBoundaryIntersection(Vector2 obsever, Vector2 target) {
  Vector2 targetDelta = { //vector to the target from the obserer
    target.x - observer.x,
    target.y - observer.y
  };
  
  //position of the relevant boundaries (will also be abused as a retval later)
  //start by assuming max bounds (lower right)...
  Vector2 boundary = {
    X_MAXIMUM_BOUND,
    Y_MAXIMUM_BOUND
  };
  //and then correct by axis when wrong
  if(targetDelta.x < 0) {boundary.x = X_MINIMUM_BOUND;}
  if(targetDelta.y < 0) {boundary.y = Y_MINIMUM_BOUND;}
  
  //vector from observer to relevant map corner
  Vector2 boundaryDelta = {
    boundary.x - observer.x,
    boundary.y - observer.y
  };
  
  //find ratio of boundary vs target deltas per-axis
  //(Edit - corrected against div-by-zero)
  //(Note - behavior is undefined if observer and target are equal)
  float xRatio = std::numeric_limits<float>::max();
  if(targetDelta.x) {xRatio = (float)(boundaryDelta.x) / targetDelta.x;}
  float yRatio = std::numeric_limits<float>::max();
  if(targetDelta.y) {yRatio = (float)(boundaryDelta.y) / targetDelta.y;}
  
  if(xRatio > yRatio) { //slope collides with y bound first
    boundary.x = observer.x + (targetDelta.x * yRatio);
  }
  else { //slope collides with x bound first
    boundary.y = observer.y + (targetDelta.y * xRatio);
  }
  
  return boundary;
}

Edit - Ah, I see. Same solution. Cool.

@P0jahn - He's just using 30.0f and 20.0f as map bounds there. You'd have to fill in the actual bounds where he uses the constants.

void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

I guess 30.0f is the width and 20.0f is the height? So what is vertical_intersection_time and horizontal_intersection_time?

And as I am not a C++er, I guess std::min is Math.min in java?

This topic is closed to new replies.

Advertisement