Collision on Diagonal Line

Java 2D
#1

I want to detect the collision of a sprite with points along a diagonal line.

Can anyone give me an idea of how to best do this?

The diagonal line runs from point (0,100) to (100,0)

The sprite moves randomly and could hit any point along this line.

Thanks,

Drew

#2

Line2D.intersects(Rectangle2D) in java.awt.geom should do the trick. Otherwise, just check every point in the line to see if it’s inside the rectangle (pointx > rectx && pointy > recty && pointx < rectx+rectwidth && pointy < recty+rectheight).

#3

I’ll have to use the second method becuase I can’t use Graphics 2D for this (Java 1.1).

It’s been a long time since my high school geometry.
How do I calculate every point on the line again? (y=mx+b or such?)

Thanks,

Drew

#4

I suggest you do a search for “Bresenham” on google. You should find some good resources for line drawing.

#5

[quote]I’ll have to use the second method becuase I can’t use Graphics 2D for this (Java 1.1).

Drew
[/quote]
You may not be able to use the API method itself, but their is nothing stopping you from going into the src and copying the method (apart from the legality of such an action :D)

btw, what shape are you using as bounds for your sprite? a rectangle or circle?
it its a circle, you will want to use Line2D.ptSegDistSq or ptLineDistSq (depending upon whether its a finite, or infinite line)

#6

I would not use an algorithm like Bresenham or this. Do the math instead.

If you have a bounding box, rather than step over each pixel in the line and test if it is in the box, simply solve for the intersection of the edges of the bounding box and the original line. Then if you want even more accuracy you can just test the pixels between those intersection points to see if they collide with your sprite.

#7

Thanks for all the help!

BTW, are there any open source Java game utility libraries that would have algorithms such as Bresenham that I could use?

I would think that such utility classes would already exist since these types of problems must be common in game programming?

I guess I’ll take a look at the Graphics 2D source if I can’t find anything.

BTW, the bounding box for my sprite is a rectangle.

Drew

#8

[quote]If you have a bounding box, rather than step over each pixel in the line and test if it is in the box, simply solve for the intersection of the edges of the bounding box and the original line.
[/quote]
Sounds like a good idea.

Can you give me any more help with the math for this?

Like I said, it’s been a long while…

Thanks,

Drew

#9

When in doubt GOOGLE…

http://astronomy.swin.edu.au/~pbourke/geometry/lineline2d/
http://www.maths.abdn.ac.uk/~igc/tch/index/eg1006/notes/node23.html
http://id.mind.net/~zona/mmts/intersections/intersectionOfTwoLines1/intersectionOfTwoLines1.html

#10

I had a similar problem when writting a collision algorithm for my iso tiles. What I did was pick a point on the object, in my case it was a tile edge, and used its x,y coordinates to test them against the diagonal side of a tile. You use the y=mx + b equation. The x is from the object. The slope m is 1 in you case. The b you have to figure out. For me with a slope of -1/2 my b was
b = h + 1/2h. Since I knew my m,x, and b I could get the y value of the diagonal line at that point and check to see if my objects y was less <= the diagonal y. If it was then collision occucered.
you can email me with questions if you dont understand my explanation kommi10@hotmail.com

#11

Sweet.

I actually got this working using both methods:

  1. Using a loop to compare all the points on a subset of the line to the x,y values of my sprite.

  2. Plug in the current x value of the sprite into the slope-intercept formula and compare the result to the current y value of the sprite.

I think I’ll go with the second, it seems more elegant. :wink:

I couldn’t really tell any performance difference, but I suspect the second method is better, too.

Thanks!

Drew

p.s. I’d still like to try the Bresenham algorithm someday…
I wish we had game API’s that included cool algorithms like this.