Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (497)
Games in Android Showcase (114)
games submitted by our members
Games in WIP (563)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Determining best direction to move in, to reach a specific coordinate  (Read 1102 times)
0 Members and 1 Guest are viewing this topic.
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Posted 2013-01-22 10:38:30 »

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):
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
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.

Offline ReBirth
« Reply #1 - Posted 2013-01-22 11:54:36 »

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.

Offline Roquen
« Reply #2 - Posted 2013-01-22 13:51:01 »

Quickly hacked out and untested:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
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
 }
}
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #3 - Posted 2013-01-22 21:27:01 »

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.

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
1  
return table[(value+1)&3];
aswell as
1  
return table[value ^ 2];
Why does the last one work?

There is another part where you lost me a little bit.
1  
2  
3  
4  
5  
6  
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.

Offline Roquen
« Reply #4 - Posted 2013-01-23 13:03:07 »

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.

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




Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #5 - Posted 2013-01-24 10:05:24 »

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

Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

BurntPizza (24 views)
2014-09-19 03:14:18

Dwinin (39 views)
2014-09-12 09:08:26

Norakomi (68 views)
2014-09-10 13:57:51

TehJavaDev (93 views)
2014-09-10 06:39:09

Tekkerue (47 views)
2014-09-09 02:24:56

mitcheeb (68 views)
2014-09-08 06:06:29

BurntPizza (51 views)
2014-09-07 01:13:42

Longarmx (38 views)
2014-09-07 01:12:14

Longarmx (44 views)
2014-09-07 01:11:22

Longarmx (40 views)
2014-09-07 01:10:19
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!