On-the-floor

On the Floor

How to calculate the point of intersection between a line and a bounding box

I've been doing a ton of iOS development lately, and out of curiosity I started playing around with Cocos2d, which is an excellent library for building 2d games.

Utilizing a tutorial from the awesome Ray Wenderlich site, I started building a simple game based on a game concept from my college days, which is going back around 12 years or so now. Unfortunately, I rather quickly ran into a problem that took me quite a while to solve, so I'm going to share the solution in the hopes that it helps someone else out.

Suppose that you have a situation where you control an object on the screen, which I will call the "hero". The hero can fire projectiles. Firing projectiles is caused by the user tapping on locations on the screen.

In Cocos2d, the movement of objects, such as projectiles, is caused by an action called CCMoveTo. The argument to this method that we are interested in is the position argument, which indicates where you wish the object to move to.

In the case of a projectile, however, you do not want the projectile to move to the position that the user tapped. That would cause the projectile to travel to the tap location and then stop. Instead, you want the projectile to move through the position of the tap and then travel off the edge of the screen (unless it hits something on the way, which I won't be discussing in this post).

This means that you must calculate the point at which a line, drawn from the hero through the tap and onwards, intersects with the edges of the screen (which I will now refer to as the "bounds").  This point, which I call the intercept point, has the position you must provide to CCMoveTo.

This sketch illustrates the issue:

In this sketch, the hero is at the center-left side of the screen, and three taps around the hero's position indicate we must find three intercept points.  This is easy to sketch, but not quite as easy to determine mathematically.

The tutorial demonstrates a basic way of calculating the intercept point, but it is not robust (it lacks handling of edge cases, like when the tap is directly vertical or horizontal from the hero) and does not handle situations where the hero can be at any point on the screen and the tap can be on any point.

I ended up developing a robust solution to this problem utilizing linear algebra. In my solution, I define a line that travels through both points in y = mx + b format.

Each of the edges of the bounds can be thought of as a line, as well, except that the line either has infinite slope (in the case of vertical edges) or zero slope (in the case of horizontal edges). The simple definition of each of those lines, if the bounds are 1024x768, is that the two vertical edges can be defined as:

x = 0
x = 1024

And the two horizontal edges can be defined as:

y = 0
y = 768

I then substitute these values into my line equation to determine the corresponding intercept points. Additionally, I handle all edge cases, and determine the intercept point based on the intended direction of the projectile.

You can find my solutions on Github. I have provided solutions in Ruby and in Objective-C.

Comments

There are no comments to display.