In my game all objects are facing right direction by default but they can be rotated and one of my object (let's call it "shooter") needs to know if any object is on its line of fire. If so, it shoots... The most basic idea that comes to my head is to calculate the equation of a straight line, given the left bottom corner of the "shooter" and its right bottom corner. Then I could check if left top corner of some object is above the line and if its right bottom corner is beneath the line. If so, I'd say that it's on the "shooter's" line of fire. But I suppose that this could be done in a much simpler but maybe a little sophisticated manner. Unfortunately I'm not sure how... I would be grateful for offering some better approach!

Here's the drawing for clarity ^^: enter image description here

  • $\begingroup$ Can you draw it? $\endgroup$ – luka5z Aug 7 '14 at 18:54
  • $\begingroup$ Are the targets always convex polygons? $\endgroup$ – Hagen von Eitzen Aug 7 '14 at 19:09
  • $\begingroup$ The objects aren't always convex polygons but I don't need a pixel perfect test for this, so a simple bounding box would be sufficient I guess. $\endgroup$ – Savail Aug 7 '14 at 19:12

You have the right idea. Generally, you would check every point of the target object to see which side of the line it lies on. If you get points that lie on both sides, then the object intersects the line. This applies only if your object is formed by straight line segments. If your object is a circular disk, then you can either discretize it into a polygon or calculate the distance from the center of the circle to the line and compare it against the radius.

The check to see which side of a line a point is on, is called the orient2d test. In floating point, it's quite hard to do it precisely, but there is very reliable code here. It assumes the line is specified by two points it passes through ($a$ and $b$, and the point you are testing is $c$). A positive number means $c$ is on the left of the line, look from $a$ towards $b$.

  • $\begingroup$ Well, I think that for Joe average's shooter game, a slightly imprecise determinant is good enough except in the most horrific melee scenarios ... $\endgroup$ – Hagen von Eitzen Aug 7 '14 at 19:13
  • $\begingroup$ thanks for the info, I'll check this out. Would upvote but my rep is too low...:P $\endgroup$ – Savail Aug 7 '14 at 19:14
  • $\begingroup$ Yeah, I realize that's overkill, but I think it's the right way of thinking about it. And imprecise collision detection is often extremely frustrating for players, so there is value in taking extra precautions. $\endgroup$ – Victor Liu Aug 7 '14 at 19:26
  • $\begingroup$ Aactually I really like the fastOrient2D solution given in your link. It's very simple, short and even works. I've just implemented it and seems to be fine despite the possible loss of data $\endgroup$ – Savail Aug 8 '14 at 6:34

A quick and easy test is as follows (I understand you mostly want it quick and easy, maybe do a more precise test and calculation if the preliminary test triggers), assuming you can approximate your objects with circles (or have "bounding disks" instead of bounding boxes): Assume your shooter is at $(a,b)$ and shoots to $(c,d)$ (and beyond). You want to know if you hit the disk of radius $r$ around $(x,y)$.

  1. First, if $(a-x)^2+(b-y)^2< r^2$, the you doo have a hit - in fact you fire from within the disk!

  2. Otherwise test if the object is ahead of the shooter at all: Caclculate the scalar product $(c-a,d-b)\cdot (x-a,y-b)$. If the result is positive, the object is in front. (If the result is $\le 0$, the object is behind or besides the shooter and a hit would have been detected by the first test).

  3. But if the object is in front of you, you still haven't hit it yet. Compute $|(d-b,a-c)\cdot (x-a,y-b)|$. If the result $<r\cdot \sqrt{(c-a)^2+(d-b)^2}$, we have a hit.

  • $\begingroup$ hmm shouldn't it be in point 2. and 3. y - b instead of y - a? $\endgroup$ – Savail Aug 8 '14 at 10:52
  • $\begingroup$ @Savail Yes, of course. Edited, thank you $\endgroup$ – Hagen von Eitzen Aug 8 '14 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.