The player can only face in eight directions i.e. the cardinal (N, E, S, W) and ordinal (NE, SE, SW, NW) directions. This constraint is in response to the graphic art requirements; it can’t be expected that there will be animation in all possible directions. My assertion is that these eight directions will be enough, as they are for many top-down games.

To make a suitable algorithm, my idea is to break a proposed movement down into components which are directed in the eight such directions. For example, let’s say the user selects a destination about 10 steps away, slightly north of east. The player can’t move directly to that point, but you could instead make him move east for, say, 8 steps, and then north-east for, say, 2 steps and have him land on the required point.

The algorithm I designed to do this works as follows:

1. The user selects a point destination d they want the player to move to. Now imagine a single vector is drawn between the point current location c and d.

2. This single vector is now broken down into a list of component vectors s, the direction of each necessarily being one of the cardinal or ordinal compass directions, while the magnitude of each will be roughly the same (to ensure movement appears regular). The method profile will be something like:

    private LinkedList<Vector> buildVectorList (Point c, Point d)
   

   Now elect a standard length l for these component vectors. l shouldn’t be too small, otherwise the player’s movement will look abrupt, nor should it be too long, as he will deviate too far from the track. Let’s say l = 20. A method is also needed to measure the angle between c and d. I found it best to measure the angle in radians, with the y-axis being parallel to north on the map, as you’d expect. With that in mind, here are the sub-steps for creating s:

   1. Check that the distance between c and d is greater than l. If so proceed, if not, end.
   2. Get the angle a in radians between between c and d. Let’s say a is slightly larger than 0.
   3. Now find the compass direction that gives the closest approximation to a. In this example, it will be east, as east is equivalent to 0 radians on a cartesian plane.
   4. Now create a vector v and add it to your list (I think a linked list is the best data structure here, but an array list or similar would be fine). The magnitude will be l, and the direction will be east.
   5. Now create a point c1 = c + l so the c1 sits at the end of v, were v to be extended from c. Let c = c1 and discard c1.
   6. Repeat the above steps until c is within l from the d.

3. Now if you iterate s and follow the vectors sequentially tail to head, you will get the player to point d1 which approximates d. Below is an example.

   

   To get the player exactly to d, you need another method:

    private LinkedList<Vector> adjustVectors (LinkedList<Vector> s, Point c, Point d)
   

   1. Firstly, check the offset o between d and d1. Let’s say d1 is 10 pixels right and 10 pixels below d
   2. Iterate s and distribute o among the vectors vi by changing their magnitude appropriately until d1 == d. I do this with a while loop, adding or subtracting 1 to the length of vi until o == 0.

Finally we end up with a list of vectors which, if the player follows sequentially, will take him in a smooth path to the user’s elected destination.