Determining whether point A needs to cut a corner to get to point B

Question

I am looking for an efficient way to check if an object will cut a corner to get from point A to point B or prevent the object from moving from point A to point B if there is a diagonal unwalkable position in between.

What is known:

• Every point is a square of width and height 1
• Every point has a list of its 8 adjacent points
• A point can be either walkable or nonwalkable

Here are some examples (a is the source, b is the desination and X is an unwalkable point):

aX
 b

In the above case, a cannot walk to be because there is an unwalkable point adjacent to both point a and point b...therefore, for this current case, b becomes unwalkable from a (ie, a has to move downwards before proceeding to b)

The following is a similar case, in the sense that a cannot walk to b:

aX
Xb

---

The way I am doing it at the moment is getting the set of orthogonally adjacent points of both point A and point B and intersecting these two sets. If there are no elements in the intersected result, then point A can walk to point B.

...and it works.

But is there a, maybe, more mathematical and efficient way of achieving this?

Answer 1

I assume that you are only interested in the case where b is one of a'a neighbors, and then only diagonally adjacent. That would be

if ((abs(a.x - b.x) == 1) && (abs(a.y - b.y) == 1))

Now in this case we just need to check the two points adjacent to both.

if ((abs(a.x - b.x) == 1) && (abs(a.y - b.y) == 1)) {
   if (blocked(a.x, b.y) || blocked(b.x, a.y)) {
      // unwalkable
   } else {
      // walkable
   }
}

You can of course merge the if statements.

Answer 2

since the above answer assumes that the cells to be checked are neighbours, you can simply check whether they are diagonal to each other instead of both diagonal AND next to each other. That way you can shave off an extra comparison.

if (abs(a.x - b.x) == abs(a.y - b.y)) {

instead of

if ((abs(a.x - b.x) == 1) && (abs(a.y - b.y) == 1)) {