Programming Algorithm

wolfcomm · 2007-11-05 04:36:50

I'm programming a strategy game, and I'm making an AI algorithm that will move units to their destinations. I need to make sure that units won't run into walls though.

So I need a function (parameters: origin x, origin y, destination x, destination y, object x1, object y1, object x2, object y2). The object in this case would be a wall with two points (x1, y1, x2, y2). The function needs to return a boolian (true/false) if the wall intersects the path. As in, does it cross between the origin and destination. In other words, we have two finite lines (path of movement and wall), and I need to know if they cross.

How do I do that?

Thanks in advance!

TheDude · 2007-11-05 05:58:15

Find the point on the grid where the 2 lines would intersect and determine if that point is between the origin and the destination. Here's how I would do it in C:

bool func(double originx, double originy, double destx, double desty, double objx1, double objy1, double objx2, double objy2)
{
bool pathInf = false, wallInf = false;
if (destx == originx)
{
pathInf = true;
}
if (objx2 == objx1)
{
wallInf = true;
}
if (pathInf && wallInf)
{
if (originx != objx1)
{
return false;
}
if ( (originy <= objy1 && originy >= objy2) ||
(originy <= objy2 && originy >= objy1) ||
(desty <= objy1 && desty >= objy2) ||
(desty <= objy2 && desty >= objy1) )
{
return true;
}
return false;
}
double slopePath, slopeWall, interceptPath, interceptWall;
if (!pathInf)
{
slopePath = (desty - originy) / (destx - originx);
interceptPath = originy - (slopePath * originx);
}
if (!wallInf)
{
slopeWall = (objy2 - objy1) / (objx2 - objx1);
interceptWall = objy1 - (slopeWall * objx1);
}
if (!pathInf && !wallInf)
{
if (slopePath == slopeWall)
{
if (interceptPath != interceptWall)
{
return false;
}
else
{
if ( (originy <= objy1 && originy >= objy2) ||
(originy <= objy2 && originy >= objy1) ||
(desty <= objy1 && desty >= objy2) ||
(desty <= objy2 && desty >= objy1) )
{
return true;
}
return false;
}
}
else
{
double x = (interceptWall - interceptPath) / (slopePath - slopeWall);
if ( (x <= originx && x >= destx) ||
(x <= destx && x >= originx) )
{
return true;
}
return false;
}
}
if (pathInf)
{
if ( (originx <= objx1 && originx >= objx2) ||
(originx <= objx2 && originx >= objx1) )
{
return true;
}
return false;
}
else
{
if ( (objx1 <= originx && objx1 >= destx) ||
(objx1 <= destx && objx1 >= originx) )
{
return true;
}
return false;
}
}

This function will return true if the paths collide and false if they do not. Note that this function (should) determine if 2 line in the xy-plane will collide. I made no assumptions about the ability of the units in your game to move. For example, if your units can only move up/down and left/right then a lot of this code is unnecessary. If that's the case then you should be able to remove a lot of the code, particularly everything dealing with slope. If they are points that can move anywhere in the xy-plane, though, this should work.

wolfcomm · 2007-11-10 10:26:45

I program in Basic (small basic to be precise). Can you explain this in english? It doesn't have to be so comprehensive, I just need to know what to look out for, and I can program it myself.

Thanks again.

mathsyperson · 2007-11-10 11:31:27

He said what you had to do at the start of his post.

TheDude wrote:

Find the point on the grid where the 2 lines would intersect [if they were infinite] and determine if that point is between the origin and the destination.

(italics are mine, for clarity)

Because you're interested in two lines, there's only one place they could possibly cross (unless they're parallel, in which case they never will).
You just need to find that point, and then check whether the point is in both the path of movement and the wall. If it's in both then you've got a collision, if it's not then you don't.

Spirinus · 2007-11-11 02:33:32

I have devised a problem: one must term a problem which resolve by maximal quantity of algorithm! All your ideas please post here.

wolfcomm (author) · 2007-11-11 23:28:38

mathsyperson wrote:

He said what you had to do at the start of his post.
TheDude wrote:
Find the point on the grid where the 2 lines would intersect [if they were infinite] and determine if that point is between the origin and the destination.
(italics are mine, for clarity)
Because you're interested in two lines, there's only one place they could possibly cross (unless they're parallel, in which case they never will).
You just need to find that point, and then check whether the point is in both the path of movement and the wall. If it's in both then you've got a collision, if it's not then you don't.

This is exactly what I need to know how to do. How do I find the point on the grid where the 2 lines would intersect?

TheDude · 2007-11-12 03:11:03

Ok, that's an easier question to answer. All straight lines can be written in the form

where m is the slope of the line and b is the y-intercept. To find the slope, use the equation
Note that if then m is infinite. This means that the line goes straight up and down, and the line's equation is of the form
where c is the x-intercept.
After you find m, calculate b with the equation
Now, after you find m and b for both lines (the wall and the path) you can solve for where they meet with the simultaneous equations

Then just plug x into either of the equations to solve for y. This will be the point where they intersect. Note that if the slopes for both lines are equal then they are parallel and will never intersect, unless they also have the same y-intercept (b), in which case they are the same line and intersect at every point.

Math Is Fun Forum

#1 2007-11-05 04:36:50

Programming Algorithm

#2 2007-11-05 05:58:15

Re: Programming Algorithm

#3 2007-11-10 10:26:45

Re: Programming Algorithm

#4 2007-11-10 11:31:27

Re: Programming Algorithm

#5 2007-11-11 02:33:32

Re: Programming Algorithm

#6 2007-11-11 23:28:38

Re: Programming Algorithm

#7 2007-11-12 03:11:03

Re: Programming Algorithm

Board footer