 |
Cheat Engine
The Official Site of Cheat Engine
|
| View previous topic :: View next topic |
| Author |
Message |
Odecey
Master Cheater
 Reputation: 1
Joined: 19 Apr 2007
Posts: 259
Location: Scandinavia
|
 Posted: Sun Aug 02, 2009 4:10 pm Post subject: [Work on hiatus]Line collision detection in C# |
 |
|
I've had this sitting in my projects folder for a while without working on it, and figured I might aswell release it (although Im not really done with it). What I'm releasing here is some classes, which deal with linesegment to linesegment collision detection. This has an amazing advantage over reactangle to rectangle collision detection, since it allows for much more freedom when creating boundaries in a game. Here you have the Wall class: | Code: | public class Wall
{
#region private variables
private Point _vector;
private Point _startPoint;
private Point _endPoint;
private double _angle;
private double _length;
#endregion
#region Constructors
/// <summary>
/// Initializes a new instance of Wall
/// </summary>
/// <param name="x1">The X coordinate of the startingpoint.</param>
/// <param name="y1">The Y coordinate of the startingpoint.</param>
/// <param name="x2">The X coordinate of the endingpoint.</param>
/// <param name="y2">The Y coordinate of the endingpoint.</param>
public Wall(int x1, int y1, int x2, int y2)
{
StartPoint = new Point(x1, y1);
EndPoint = new Point(x2, y2);
}
/// <summary>
/// Initializes a new instance of wall.
/// </summary>
/// <param name="start">The startingpoint of the wall.</param>
/// <param name="end">The endingpoint of the wall.</param>
public Wall(Point start, Point end)
{
StartPoint = start;
EndPoint = end;
}
#endregion
#region Properties
/// <summary>
/// The vector representation of wall.
/// </summary>
public Point Vector
{
get
{
return _vector;
}
}
/// <summary>
/// Start point of the wall.
/// </summary>
public Point StartPoint
{
get
{
return _startPoint;
}
set
{
_startPoint = value;
_vector = new Point(_endPoint.X - _startPoint.X, _endPoint.Y - _startPoint.Y);
_length = GetLength();
_angle = GetAngle();
}
}
/// <summary>
/// Endpoint of the wall
/// </summary>
public Point EndPoint
{
get
{
return _endPoint;
}
set
{
_endPoint = value;
_vector = new Point(_endPoint.X - _startPoint.X, _endPoint.Y - _startPoint.Y);
_length = GetLength();
_angle = GetAngle();
}
}
/// <summary>
/// Angle between the wall and a horisontal line.
/// </summary>
public double Angle
{
get
{
return _angle;
}
}
/// <summary>
/// The length of the wall.
/// </summary>
public double Length
{
get
{
return _length;
}
}
#endregion
#region Methods
/// <summary>
/// Gets the Dot product between two vectors.
/// </summary>
/// <param name="factor">The factor to multiply by.</param>
/// <returns>Dot product</returns>
public double DotProduct(Point factor)
{
return _vector.X * factor.X + _vector.Y * factor.Y;
}
/// <summary>
/// Gets the angle between the wall vector and a line which goes along the X-axis with length 1.
/// </summary>
/// <returns>Angle (Degrees)</returns>
private double GetAngle()
{
return Math.Acos( DotProduct(new Point(1, 0)) / _length)*180/Math.PI;
}
/// <summary>
/// Gets the length of the wall vector
/// </summary>
/// <param name="vector">The vector to find the length of.</param>
/// <returns>Length</returns>
private double GetLength()
{
return Math.Sqrt(_vector.X * _vector.X + _vector.Y * _vector.Y);
}
/// <summary>
/// Tries to parse the input string to Wall.
/// </summary>
/// <param name="input">The string to parse.</param>
/// <returns>Wall</returns>
/// <exception cref="System.ArgumentException"></exception>
public static Wall FromString(string input)
{
if (Regex.Match(input, @"{?X\=\s?\d+\s?\,Y\=\s?}{X\=\d+\s?\,Y\=}?\s*") != Match.Empty)
{
MatchCollection buf = Regex.Matches(input, @"\d+");
return new Wall(new Point(int.Parse(buf[0].Value), int.Parse(buf[1].Value)), new Point(int.Parse(buf[2].Value), int.Parse(buf[3].Value)));
}
throw new ArgumentException("The input string was in the wrong format.");
}
#endregion
} |
This class is used to store the information of a single boundary line. The line collision and collsion info classes: | Code: | class LineCollision
{
public Point VectorToMove(Point intendedVector, Rectangle movingObject, List<Wall> walls)
{
Rectangle bufferObject = new Rectangle(movingObject.X + intendedVector.X, movingObject.Y + intendedVector.Y, movingObject.Width, movingObject.Height);
if (IsColliding(movingObject, walls))
{
if (IsColliding(bufferObject, walls))
return new Point(0, 0);
else
return intendedVector;
}
else
{
List<CollisionInfo> infoBuffer;
if ((infoBuffer=CollisionPoints(bufferObject, walls)).Count != 0)
{
if (CollisionInfo.SingleWall(infoBuffer))
{// Incomplete. The idea: Move movingObject up to collision point with original vector, then move in the direction of the wall vector for the remaining distance.
return new Point(0, 0);
}
else
{
return new Point(0, 0);
}
}
else
return intendedVector;
}
}
/// <summary>
/// LTLCT Wrapper for hittesting between rectangle and walls
/// </summary>
/// <param name="rect"></param>
/// <param name="walls"></param>
/// <returns></returns>
public bool IsColliding(Rectangle rect, List<Wall> walls)
{
int[] c = {0, 0, 1, 1, 0, 0};
foreach (Wall wall in walls)
for (int i = 0; i < 4; i++)// Iterate through rectangle sides
if (LTLCT(c[i+1] * rect.Width + rect.X, c[i]* rect.Height + rect.Y, c[i+2] * rect.Width + rect.X, c[i+1] * rect.Height + rect.Y, wall.StartPoint.X, wall.StartPoint.Y, wall.EndPoint.X, wall.EndPoint.Y))// Collision check between rectangle side and a wall.
return true;
return false;
}
public List<CollisionInfo> CollisionPoints(Rectangle rect,List<Wall> walls)
{
List<CollisionInfo> collisionPoints = new List<CollisionInfo>();
Point buffer = new Point();
int[] c = {0, 0, 1, 1, 0, 0};
foreach (Wall wall in walls)
for (int i = 0; i < 4; i++)// Iterate through rectangle sides
if ((buffer = CollisionPoint(c[i + 1] * rect.Width + rect.X, c[i] * rect.Height + rect.Y, c[i + 2] * rect.Width + rect.X, c[i+1] * rect.Height + rect.Y, wall.StartPoint.X, wall.StartPoint.Y, wall.EndPoint.X, wall.EndPoint.Y) )!= Point.Empty)
collisionPoints.Add(new CollisionInfo(walls.IndexOf(wall),i+1,new Point(buffer.X, buffer.Y)));
return collisionPoints;
}
/// <summary>
/// Linesegment to linesegment collision test. Returns true if the two line segments are colliding, otherwise false.
/// </summary>
/// <param name="x1_"></param>
/// <param name="y1_"></param>
/// <param name="x2_"></param>
/// <param name="y2_"></param>
/// <param name="x3_"></param>
/// <param name="y3_"></param>
/// <param name="x4_"></param>
/// <param name="y4_"></param>
/// <returns></returns>
private bool LTLCT(int x1_, int y1_, int x2_, int y2_, int x3_, int y3_, int x4_, int y4_)
{
float r, s, d;
//Make sure the lines aren't parallel
if (((x2_ - x1_) == 0) && ((x4_ - x3_) == 0))
{
//Parallel
}
else
{
d = (((x2_ - x1_) * (y4_ - y3_)) - (y2_ - y1_) * (x4_ - x3_));
if (d != 0)
{//Not parallel
r = (((y1_ - y3_) * (x4_ - x3_)) - (x1_ - x3_) * (y4_ - y3_)) / d;
s = (((y1_ - y3_) * (x2_ - x1_)) - (x1_ - x3_) * (y2_ - y1_)) / d;// Make sure that the collision occurs on the linesegments
if (r >= 0 && r <= 1)
if (s >= 0 && s <= 1)
{// Collision occurs on the linesegments. To find the collision point, do:
// Point intersectionPoint = new Point( x1_ + r * (x2_ - x1_), y1_ + r * (y2_ - y1_));
return true;
}
}
}
}
return false;
}
private Point CollisionPoint(int x1_, int y1_, int x2_, int y2_, int x3_, int y3_, int x4_, int y4_)
{
float r, s, d;
if (((x2_ - x1_) == 0) && ((x4_ - x3_) == 0))
{}
else
{
d = (((x2_ - x1_) * (y4_ - y3_)) - (y2_ - y1_) * (x4_ - x3_));
if (d != 0)
{
r = (((y1_ - y3_) * (x4_ - x3_)) - (x1_ - x3_) * (y4_ - y3_)) / d;
s = (((y1_ - y3_) * (x2_ - x1_)) - (x1_ - x3_) * (y2_ - y1_)) / d;
if (r >= 0 && r <= 1)
if (s >= 0 && s <= 1)
{
return new Point((int)Math.Round(x1_ + r * (x2_ - x1_), 0), (int)Math.Round(y1_ + r * (y2_ - y1_), 0));
}
}
}
return Point.Empty;
}
}
public class CollisionInfo
{
#region Private variables
private int _wallID;
private int _sideNum;
private Point _coordinates;
#endregion
#region Properties
public int WallID
{
get
{
return _wallID;
}
set
{
_wallID = value;
}
}
public Point Coordinates
{
get
{
return _coordinates;
}
set
{
_coordinates = value;
}
}
public int SideNumber// 1 = Top, 2 = Right, 3 = Bottom, 4 = Left
{
get
{
return _sideNum;
}
set
{
_sideNum = value;
}
}
#endregion
#region Constructor
public CollisionInfo (int id, int sideNum, Point coordinates)
{
_coordinates = coordinates;
_wallID = id;
_sideNum = sideNum;
}
#endregion
#region Methods
public static bool SingleWall(List<CollisionInfo> collInfo)
{
int id = collInfo[0].WallID;
foreach (CollisionInfo coll in collInfo)
if (coll.WallID != id)
return false;
return true;
}
public static bool SingleSide(List<CollisionInfo> collInfo)
{
int side = collInfo[0].SideNumber;
foreach (CollisionInfo coll in collInfo)
if (coll.SideNumber != side)
return false;
return true;
}
#endregion
} |
As mentioned in one of the comments, the original idea for VectorToMove was something like this:
1. Check that the angle between the movement vector and the wall vector aren't 90 degrees, and if so:
2. Set the moving objects position along the movement vector so that it is as close as possible to the wall without colliding with it, and:
3. Move the object along the wall vector for the total movement distance minus the distance from the original point of the object to the point it was set to in step 2.
This would allow the object to "slide" along the wall as long as it isn't hindered by other boundaries, instead of being simply put to a halt. Unfortunately I haven't found a good way to do this, so for now the rect parameter will simply not change location if it collides with anything when moved.
I've provided a project which shows how these classes can be used: Download
Picture of the GUI:Picture
Controls:
To set wall starting point, press the left mouse button.
To set the ending point, click again.
To remove the last created wall, press the right mouse button.
To clear the wall list, press space.
To toggle wall creation, press E.
To bring the log window to focus, press L. (Will create a new instance if the window was closed)
To adjust the rectangle size, use + and -.
To get collision info, press enter.
If you are wondering about the mathematics behind CollisionPoint(), you can take a look here:Click.
Any feedback is as always very much appreciated ^_^.
_________________
Never confuse activity with productivity. You can be busy without a purpose, but what's the point?- Rick Warren |
|
| Back to top |
|
 |
Odecey
Master Cheater
Reputation: 1
Joined: 19 Apr 2007
Posts: 259
Location: Scandinavia
|
| Posted: Wed Aug 05, 2009 11:11 am Post subject: |
|
|
How come no one has commented on this?
_________________
Never confuse activity with productivity. You can be busy without a purpose, but what's the point?- Rick Warren |
|
| Back to top |
|
|
iGod
Grandmaster Cheater
![]() Reputation: -1
Joined: 31 Jan 2009
Posts: 621
Location: Manchester, uk.
|
| Posted: Wed Aug 05, 2009 11:20 am Post subject: |
|
|
| Odecey wrote: | | How come no one has commented on this? |
Because most people dont understand it.
|
|
| Back to top |
|
|
Odecey
Master Cheater
Reputation: 1
Joined: 19 Apr 2007
Posts: 259
Location: Scandinavia
|
| Posted: Wed Aug 05, 2009 1:36 pm Post subject: |
|
|
| iGod wrote: | | Odecey wrote: | | How come no one has commented on this? |
Because most people dont understand it. |
Are you saying that I did a poor job describing what this is, and what it does? If so I guess I could revise it to something more readable. If not, then what do you mean?
_________________
Never confuse activity with productivity. You can be busy without a purpose, but what's the point?- Rick Warren |
|
| Back to top |
|
|
dnsi0
I post too much
![]() Reputation: 0
Joined: 04 Jan 2007
Posts: 2674
|
| Posted: Wed Aug 05, 2009 3:34 pm Post subject: |
|
|
| Odecey wrote: | | iGod wrote: | | Odecey wrote: | | How come no one has commented on this? |
Because most people dont understand it. |
Are you saying that I did a poor job describing what this is, and what it does? If so I guess I could revise it to something more readable. If not, then what do you mean? |
I think he means that this is too advanced for people to know.
|
|
| Back to top |
|
|
hcavolsdsadgadsg
I'm a spammer
![]() Reputation: 26
Joined: 11 Jun 2007
Posts: 5801
|
| Posted: Wed Aug 05, 2009 4:12 pm Post subject: |
|
|
| Odecey wrote: | | How come no one has commented on this? |
I could have sworn I did... maybe I just opened the tab then forgot.
The code seems simple enough at first glance, but I always hate reading through all the math unless I'm the one writing it.
Maybe you should look into quad-trees. They work very well with collision detection since you can intelligently determine what needs to be checked instead of just brute force plowing through the entire scene.
|
|
| Back to top |
|
|
Drkgodz
Flash moderator
 Reputation: 2
Joined: 17 Jul 2006
Posts: 2997
Location: Houston
|
| Posted: Fri Aug 21, 2009 9:39 am Post subject: |
|
|
So this is basically for using boundary lines (like edges of shapes) and checking to see if it intersects with any of the boundaries of what you're collision testing it against?
_________________
|
|
| Back to top |
|
|
Jorg hi
I post too much
 Reputation: 7
Joined: 24 Dec 2007
Posts: 2276
Location: Minnesota
|
| Posted: Sat Aug 22, 2009 12:29 pm Post subject: |
|
|
Very good! I don't have time to look through all the code but does this support circular collisions?
_________________
CEF will always stay alive. |
|
| Back to top |
|
|
Odecey
Master Cheater
Reputation: 1
Joined: 19 Apr 2007
Posts: 259
Location: Scandinavia
|
| Posted: Wed Aug 26, 2009 12:01 am Post subject: |
|
|
slovach: I took a quick glance at quad trees, but I don't quite see how this is usable with lines, especially if the lines won't be stationary from one colllision test to another. What exactly do you suggest that I do?
Drkgodz: If I understood your question correctly, yes.
Jorg hi is back: No, it does not. Thanks for the compliment.
I've gotten a bit further on this, so I just might finish it sometime soon.
_________________
Never confuse activity with productivity. You can be busy without a purpose, but what's the point?- Rick Warren |
|
| Back to top |
|
|
hcavolsdsadgadsg
I'm a spammer
![]() Reputation: 26
Joined: 11 Jun 2007
Posts: 5801
|
| Posted: Wed Aug 26, 2009 12:55 am Post subject: |
|
|
| Odecey wrote: | slovach: I took a quick glance at quad trees, but I don't quite see how this is usable with lines, especially if the lines won't be stationary from one colllision test to another. What exactly do you suggest that I do?
|
You traverse the tree to determine if a line is actually worth running a collision check on. This is probably -the- optimization to make for such a routine if you need to speed it up.
|
|
| Back to top |
|
|
ChainRule
Cheater
![]() Reputation: 1
Joined: 21 Jan 2008
Posts: 40
|
| Posted: Fri Nov 06, 2009 5:25 pm Post subject: |
|
|
Yeah, a quad tree would definitely speed it up.
You can also speed it up by using two control points; Usually those points should be at the end of a line segment; namely your x1, y1; x2, and y2. Since a line is straight, if none of the control points are inside a shape, then there is no point testing it. It is relatively easy to test if a point is inside a triangle by using Dot Product. If a control point is inside, then you can use further test to determine specific collision spot.
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
