Determining best direction to move in, to reach a specific coordinate

Game Mechanics
#1

Well, what the title says. I have no need for advanced pathfinding - my enemies shall be dumb for now.

I really want to keep my DIRECTION enum used, and not just hardcode xc and yc according to direction.

This is what I’m currently doing (…and I’m ashamed of myself, indeed):


public DIRECTION moveTowards(int x, int y) {
		float north = 
				distanceBetween(
						this.getX() + DIRECTION.NORTH.getXC(),
						this.getY() + DIRECTION.NORTH.getYC(),
						x,
						y
				);
		float south = 
				distanceBetween(
						this.getX() + DIRECTION.SOUTH.getXC(),
						this.getY() + DIRECTION.SOUTH.getYC(),
						x,
						y
				);
		float east = 
				distanceBetween(
						this.getX() + DIRECTION.EAST.getXC(),
						this.getY() + DIRECTION.EAST.getYC(),
						x,
						y
				);
		float west = 
				distanceBetween(
						this.getX() + DIRECTION.WEST.getXC(),
						this.getY() + DIRECTION.WEST.getYC(),
						x,
						y
				);
		
		if (north < south 
				&& north < west 
				&& north < east) {
			return DIRECTION.NORTH;
		} else if (east < south 
				&& east < west 
				&& east < north) {
			return DIRECTION.EAST;
		} else if (south < east 
				&& south < west 
				&& south < north) {
			return DIRECTION.SOUTH;
		} else if (west < south 
				&& west < west 
				&& west < north) {
			return DIRECTION.WEST;
		} else {
			return DIRECTION.NOWHERE;
		}
	}
	
	public float distanceBetween(int x1, int y1, int x2, int y2) {
		return Math.abs(x1 - x2) + Math.abs(y1 - y2);
	}

The code should be selfexplanatory in what it aims to do - the process of achieving that is just utterly terrible at the moment. It also doesn’t work as intented. Meh.

#2

So you want to know the direction of click (x, y) in “this”'s point of view?

If yes, I would do this by comparing (x1-x2) dan (y1-y2) and return the enum based on it.

#3

Quickly hacked out and untested:


public enum DIRECTION 
{
  E(0),
  N(1),
  W(2),
  S(3),
  ;
  public final int value;
  
  private static final DIRECTION[] table;
  
  static {
    table = new DIRECTION[4];
    table[0] = E;
    table[1] = N;
    table[2] = W;
    table[3] = S;
  }
  
  DIRECTION(int v) { value = v; }
  
  public DIRECTION getTurnL()    { return table[(value+1)&3]; }
  public DIRECTION getTurnR()    { return table[(value-1)&3]; }
  public DIRECTION getOpposite() { return table[value ^ 2]; }
  
  
  public static DIRECTION getDirection(int x0, int y0, int x1, int y1)
  {
    int dx = x1-x0;
    int dy = y1-y0;
    int ax = Math.abs(dx);
    int ay = Math.abs(dy);
    
    if (ax != ay || ax != 0) {
      if (ax > ay)
        return table[(dx >> 31) & 2];
      
      return table[((dy >> 31) & 2) + 1];
    }
   
    return null; // whatever for the points being the same
  }
}
#4

That is exactly what I had already done, however it is really horrible to look at and it doesn’t work. I’m sure it could work this way, but this is most likely an ancient problem and someone is bound to have figured out a nice way to solve it.

@Roquen
That is really a lot better, and it’ll probably work. I assume you know what you’re doing with bitwise operators.
I am not yet entirely comfortable with them. Would you mind explaining to me the logic behind the “&3” part of

return table[(value+1)&3];

aswell as

return table[value ^ 2];

Why does the last one work?

There is another part where you lost me a little bit.

if (ax != ay || ax != 0) {
      if (ax > ay)
        return table[(dx >> 31) & 2];
      
      return table[((dy >> 31) & 2) + 1];
}

I don’t quite understand the returning-part of that code.

Even if you don’t want to elaborate, I thank you for taking time to reply to me in such an extensive way.

#5

Sure. First the ordering. East is chosen to be zero simply because that matches the (most) standard mathematical notion…but any would do. Next the remaining are chosen in a counter-clockwise order, again to match convention. So the we have:

E=0, N=1, W=2, S=3. These four values fit exactly in 2-bits: 00, 01, 10, 11. Any direction counter-clock wise is +1 from the current and clockwise is -1. The catch is that we need to keep the values in the legal range. You could use an ‘if’, but the properties of 2s complement integers allow us to simply restrict the result to 2-bits and everything works out. So the AND-masking of 3 (the lower 2-bit set) restrict us to that range: 3+1 = 4 (11+01=100), 4 & 3 = 0 (100 & 011 = 0) and likewise 0-1 = -1 (00-01=11111111111111111111111111111111), -1 & 3 = 3 (111…11 & 11 = 11). These properties hold regardless the number being added or subtracted…you’re moving ‘n’ steps in one direction or the other.

Now for the opposite version: we could turn twice CC: (value+2)&3, or twice clockwise: (value-2)&3 and get the same result. But consider the values: N <-> S & E <-> W, or the values (in binary): 01 <-> 11 & 00 <-> 10. So the opposite direction is simply flipping the value of the 2nd bit. The “why” of this is a bit long winded (stuck below). Notice that this means that x+2 and x-2 have identical meaning (results) in 2-bit numbers. Moving on to 3, you’d find that (x+3)&3 = (x-1)&3 and (x-3)&3 = (x+1)&3.

Next I’m computing the offsets (or vector if you wish) between the two points, then compute the magnitude of each component. The comparison: (ax != ay || ax != 0), say that if the magnitudes are different then do the block OR if they aren’t both zero then do the block. This could have been written as (dx != 0 || dy != 0)…the reason that I didn’t make that choice is because the likelihood of needed to perform two 'if’s is drastically higher.

Inside that block I choose the direction with the greatest difference (arbitrary choosing N/S if the two deltas are equal in magnitude). Given an integer ‘x’, then (x>>31) = -1 (all bits set) if x is negative, otherwise it’s zero. Anding that with ‘2’ gives a 2 if negative, otherwise zero. So if (ax > ay) then we want to move either E or W and if ‘dx’ is negative then we need to go W, which is 2 and otherwise E which is 0. Likewise for N/S except we need to add 1 to get ‘3’ for negative and otherwise ‘1’.

Long winded why (x+2)&3 = x^2. Given integers ‘x’ & ‘y’, then:
x + y = ((x & y) + ( x | y)) = ((x ^ y) + ((x & y)<<1))

Taking the second, plug in the ‘2’ and applying the mask:
(x + 2) & 3 = ((x ^ 2) + ((x & 2)<<1)) & 3

Although AND doesn’t generally distribute over addition, (x+y)&3 = ((x&3)+(y&3))&3 is always true, so:
(x + 2) & 3 = ((x ^ 2)&3 + ((x & 2)<<1)&3) & 3

And since ‘x’ is limited to [0,3], then (x^2)&3 = (x^2) and ((x & 2)<<1)&3 = 0, therefore:
(x + 2) & 3 = (x ^ 2)

Subtracting ‘2’ is similar. Note that the ‘xor’ formulation of addition is why the black-magic averaging of two integers without over/under-flow works.


public static final int signedAverage(int x, int y)
{
  return (x & y) + (x ^ y) / 2;  // division is removable...for clarity
}
#6

Thanks a ton. That was quite insightful. I will edit this post as soon as I get to implement this into my game. :slight_smile: Thanks again.