• Create Account

Calling all IT Pros from Canada and Australia.. we need your help! Support our site by taking a quick sponsored surveyand win a chance at a \$50 Amazon gift card. Click here to get started!

# Ntwiles

Member Since 27 Oct 2011
Offline Last Active Oct 05 2013 04:39 AM

### Circle vs Line Segment collision

28 September 2013 - 12:42 PM

I'm trying to implement a method to check if a circle, given a certain displacement vector, will collide with a line segment. Though I don't follow some of the math, I've managed already to get a working method to determine if a circle will collide with an infinite line, defined by a line segment:

```        public static CollisionData CircleVSLine(Vector2 position, float radius, VectorX displacement, LineSegment line)
{
CollisionData data = new CollisionData();

Vector2 line_to_circle;

VectorX line_vector = new VectorX(line.Size);
Vector2 n = line_vector.Normal;

//Shortest distance from circle's center to line - before vector is applied
line_to_circle = line.Position1 - position;
float d1 = Math.Abs(VectorX.DotProduct(line_to_circle,n));

//After vector is applied
line_to_circle = line.Position1 - position - displacement.Components;
float d2 = Math.Abs(VectorX.DotProduct(line_to_circle, n));

float t = (radius - d1) / (d2 - d1);

if (Math.Abs(d2) < radius)
{
data.Collides = true;
data.CollisionPoint = position + (displacement * t);
}

return data;
}```

And below is my attempt to check for collisions on line segments:

```        public static CollisionData CircleVSLineSegment(Vector2 position, float radius, VectorX displacement, LineSegment line)
{
VectorX line_vector = new VectorX(line.Size);
//First check if collision happened on entire length of line
CollisionData data = CircleVSLine(position,radius,displacement,line);

//Early out
if (!data.Collides) { return data; }

/* Next, get the vector form Position1 to data.CollisionPoint. If they are going in the same general direction,
* they will have a positive Dot Product, if they aren't, then the collision point must be BEHIND line_vector
* (I.E., not ON the vector, and not truly colliding.)
* http://hub.tutsplus.com/tutorials/quick-tip-collision-detection-between-a-circle-and-a-line-segment--active-10632 */

VectorX start_to_circle = new VectorX(position - line.Position1);
float dot_start = VectorX.DotProduct(line_vector.Components, start_to_circle.Components);

//Early out
if (dot_start < 0) { data.Collides = false; return data; }

if (line.Position1.X == 48 + 16)
{
//Debugger.Break();
GameStatus.Pause();
}
if (position.Y < line.Position1.Y && line.Position1.X == 48+16) Debugger.Break();

/* Next, we make sure the collision point doesn't happen after line_vector has ended. If it does, the projection
* of start_to_circle onto line_vector will exceed the length of line_vector. */

float projection = start_to_circle.ScalarProjection(line_vector);
if (projection > line_vector.Length) { data.Collides = false; }

return data;
}```

As you can see, I link to a tutorial which attempts to explain how the test is done. The algorithm treats the line segment as a vector (which I know is strange), and first tests to see if the circle is actually colliding with the line defined by our line segment BEFORE the start of said line segment.  It then tests in an entirely different way to see if the circle collides with the line at a point AFTER the vector ends. If it doesn't collide before the line segment, and it doesn't collide after the line segment, it collides on the line segment.

The logic of the first half of the test is that if two vectors (the vector defined by our line segment, and the vector from the start of that line segment to the starting position of our circle) have generally opposite directions, then the circle MUST be behind the start of our line segment vector, which makes sense to me.  The test to check if the two vectors ARE going in the same direction though, gives lots of false positives. This is my big issue. I haven't even got to the second half of the algorithm, which doesn't seem to be working either.

Can anyone help me wrap my mind around this? I'd like to repeat that I do have a working test for circles vs infinite lines, which I don't want to discard and which I feel will provide a lot of the data needed to make the more precise circle vs line segment test. Any input would be really appreciated.

### Intersection Point of two Vectors

14 September 2013 - 02:14 AM

My math is very shaky, and I'm trying to use the following tutorial to get a grasp on vectors and collision detection/response:

http://www.tonypa.pri.ee/vectors/tut05.html

I've made an example and I'll just go through the process then explain my questions.

After some research, I've learned that the t value he's using is a factor in the parametric equation of a line (x,y)=(1-t)(x1,y1)+t(x2,y2). So I need to find the ratio t of vector a at which it intersects b. Then I'll add that to the starting position of a to get the point at which the two vectors intersect.

First I find c, which is the vector between the starting points of a and b. c = (-1,-4). I can then (apparently) solve for t using the ratio of the Dot Products of the normals of my vectors (Perp Product).

t = (c * b) / (a * b).

c*b = (4*6) + (-1*1) = 24 -1 = 23
a*b = (5*6) + (4*1) = 30 + 4 = 34

t = 23/34

a*t is (46/17,-115/34). Adding that to the starting point of a, I get (80/17,-55/34)  (4.7,1.6), which looks to be right.

I have all the steps down, but I'd like to get a better understanding of the math behind it. Specifically, there's a bit of a logical leap while solving for t. I don't understand how the Perp Product gets us the ratio we need to find the intersection point, or how the vector connecting the two starting points is involved. Any explanations on that or links to theorems explaining it would be really appreciated, as well as any corrections to my explanation.

### Vector Based 2D Mapping

10 September 2013 - 03:53 AM

I'm interested in creating a 2D sidescrolling game with map design based on convex vectors instead of tiles (See "Type #4" in this article). This will be a challenge for me, and I have a few questions.

My first issue is with level design. The way I see it I'll need to do the following:

1. Design each level as a series of convex shapes for collision, overlaid with an image.

2. Save each convex shape as an array of points.

This would be very tedious, are there any map editors available that already do something like this?

My second question has to do with moving the player up and down slopes:

Collision detection and response should be no problem, but I'm not 100% sure about how a player would move up and down a slope. Currently, I would do it like this:

1. Determine if player collides with a polygon.

2. Determine between which two points of the polygon the player is colliding.

3. Modify player's Y-value based on the slope of that line segment.

Am I on the right track, or is there a better way to do this?

Would love any insight or links to articles on the topic. Thanks guys!

### Design My Game - a new kind of game project

05 September 2013 - 04:42 PM

Hi guys, I'm taking an interesting approach with my next game development project. I've decided to make it entirely community designed. I've started with the simplest shell of a 2D side-perspective game engine I could develop, and put it up online for the world to play and decide what feature needs to be added next. Step by step, we'll make a game together.

Design My Game

I would love to get some input on the idea. Things like:

- Does this idea interest you?

- Have you seen a project like this before? (If so, how did it work out?)

- Would you submit ideas to a project like this?

Thanks!

### Calculating RPG Loot Drop Chance?

14 April 2013 - 03:33 AM

I'm trying to figure out the best way to implement a loot drop system for my roguelike. I need individual enemies to have lists of items they can drop, each with different odds of dropping. Here's how I'm doing it now:

``` public static Item checkDrop(List<LootChance> loot_list)
{
if (checkLootList(loot_list))
{
float roll = (float)rand.NextDouble() * 100;
float chance_count = 0;

foreach (LootChance lc in loot_list)
{
if (roll <= lc.PercentChance)
{
return lc.Loot;
}
chance_count += lc.PercentChance;
}
}
else
{
Log.add("Loot odds exceed 100%!");
}

return null;
}
```

This works for now, but it will stop me from ever having the total odds of all possible loot items to exceed 100. I could see there being other, possibly better ways of handling this. How is this kind of thing usually calculated?

PARTNERS