Using Linear Coordinates to Check Against AI

Question

I'm working on some artificial intelligence, and I want to be able for my AI not to run into given coordinates as these are references of a wall/boundary.

To begin with, every time my AI hits a wall, it makes a reference to that position (x, y). When it hits the same wall three times, it uses linear check points to 'imagine' there is a wall going through these coordinates.

I want to now prevent my AI from going into that wall again.

To detect if my coordinates make a straight line, I use:

private boolean collinear(double x1, double y1, double x2, double y2, double x3, double y3) {
    return (y1 - y2) * (x1 - x3) == (y1 - y3) * (x1 - x2);
}

This returns true is the given points are linear to one another.

So my problems are:

1. How do I determine whether my robot is approaching the wall from its current trajectory?

2. Instead of Java 'imagining' there's a line from 1, to 3. But to 'imagine' a line all the way through these linear coordinantes, until infinity (or close).

I have a feeling this is going to require some confusing trigonometry?

Answer 1

For #2, you could check if the slope between any point and one point on the wall/line you want, is the same as the slope between two points on the line.

private boolean onWall(double x, double y, double wallX1, double wallY1, double wallX2, double wallY2) {
    return (wallY1 - y) / (wallX1 - x) == (wallY2 - wallY1) / (wallX2 / wallX1);
}

So, the slopes calculated share a point, so if they're the same, they're all on the same line.

Answer 2

Interesting problem. Well two appraoches come to my mind:

• So what you can do is that, once every line is detected, store its slope m and line constatnt c as per line y= mx +c. So once you change your co-ordinate to a new co-ordinate. put your new (x1,y1) in above line equation to see if y1 == m*x1 + c. The whole operation will be computationally expensive as O(n) where n is number of lines detected for every new co-ordinate movement

You can reduce the above by clustering points and checking the line matching as per cluster rather than for every line. i.e. store what all lines pass through a cluster and check only for those lines when you are currently in the respective cluster. This should be an ideal solution

• Another solution would be to have an imaginary circle of radius r around your current point. Once the circle is obtained, find what all lines pass through the current cluster (as per explained above). For every new movement, check wall or not only for those lines. Once you move out of your cluster, draw a new circle again

I think this problem is more suitable for programmers.stackexchange.com rather than here :)