Trying to move an object in a matrix using line drawing algorithm

Question

I'm trying to move an object in a matrix (an array with [x,y]) using a line drawing algorithm, to help you understand what I mean I'm trying to make an object move like this:

enter image description here

But instead of going "in line" it goes like this:

enter image description here

I opened another question about this problem here, and you told me to use a line drawing algorithm, which I did, but I still can't make it move in that order.

A little bit about the code (I'm giving you some 'background' so you won't be confused): The Location variable contains a location on the matrix, it has x and y, which can be accessed like this:

Location loc = new Location(x,y);//Declaring a new location
int row = loc.Row;//Gets the x value (Row)
int col = loc.Col;//Gets the y value (Column)

The Direction variable contains a direction, there are 5 directions:

Direction.NORTH;
Direction.SOUTH;
Direction.EAST;
Direction.WEST;
Direction.NOTHING; //This direction means to stay at the same place, or not move

I think it's obvious what each of them means.

The command game.Destination(myPirate, direction); calculates where the object ends up on the next turn(returns a location).

Now here is the code that I got:

public static Direction NextDirection(Game game,Pirate myPirate,Location EndLocation)
    {
        List<Direction> westEast = new List<Direction>() { Direction.EAST, Direction.WEST };
        List<Direction> northSouth = new List<Direction>() { Direction.NORTH, Direction.SOUTH };
        int startX = myPirate.Loc.Row;
        int startY = myPirate.Loc.Col;
        int endX = EndLocation.Row;
        int endY = EndLocation.Col;
        if (startX == endX && startY == endY) return Direction.NOTHING; //If its alredy on spot return the location of the pirate;
        int dx = endX - startX;
        int dy = endY - startY;
        if (dx == 0) //The X of the end is the same as the x of the start, need to move only on the y axis;
        {
            return MyBot.GetBestDirection(game, myPirate, EndLocation);
        }
        if (dy==0) //The Y of the end is the same as the y of the start, need to move only on the x axis;
        {
            return MyBot.GetBestDirection(game, myPirate, EndLocation);
        }
        int slope = dy / dx;
        Location destination;
        double distance = MyBot.Distance(myPirate.Loc, EndLocation);
        if (slope > 1 || slope < -1)
        {
            double distance2;
            foreach (Direction dir in northSouth) //In here the algoritem decides whats the best direction (north or south);
            {
                destination = game.Destination(myPirate, dir);
                distance2 = MyBot.Distance(destination, EndLocation);
                if (distance2 < distance) return dir;
            }
            game.Debug("Couldnt find a good direction, going by the default dirction algorithem.");
            return MyBot.GetBestDirection(game, myPirate, EndLocation);
        }
        else
        {
            double distance2;
            foreach (Direction dir in westEast)//In here the algoritem decides whats the best direction (west or east);
            {
                destination = game.Destination(myPirate, dir);
                distance2 = MyBot.Distance(destination, EndLocation);
                if (distance2 < distance) return dir;
            }
            game.Debug("Couldnt find a good direction, going by the default dirction algorithem.");
            return MyBot.GetBestDirection(game, myPirate, EndLocation);
        }
    }

On some parts in the code above I'm also using parts from the MyBot class, here are these parts:

public static Direction GetBestDirection(Game game, Pirate myPirate, Location loc)//ADD: If the destination is not passable get another direction;
    {
        double distance = Distance(myPirate.Loc, loc);
        List<Direction> allDirections = new List<Direction>() { Direction.NORTH, Direction.SOUTH, Direction.WEST, Direction.EAST, Direction.NOTHING };
        Location destination;
        foreach (Direction dir in allDirections)
        {
            destination = game.Destination(myPirate, dir);
            double distance2 = Distance(destination, loc);
            if (distance2 < distance && game.IsPassable(destination)) return dir;
        }
        return Direction.NOTHING;
    }

The 'object' I told you about is called myPirate in the code, and it can only move in one direction each turn. the code run again in each turn until it gets to the target.

How can I make this program work right? What is wrong with my code?

Are you programming robot of some kind? Then you have to build path first and then try to follow it. E.g. you can define line as `y = kx + b` or as `x += dx` and `y += dy` (up to you), then on every iteration of path building (finding coordinates of next cell, which is not current by increasing shorter to move: `x` or `y`) see where you have to go (N, S, E, W) and do step. — Sinatr, Apr 24 '15 at 15:11
`int slope = dy / dx;` and `(slope > 1 || slope < -1)` imply that slope must be 2 or more to go north or south. That's a gradient over 66%, otherwise it's going horizontal. Even if you just worked out the tangent quadrant and followed that you'd get a more gradual line. To get the line you want you need the start location. Then the next square is which ever the line passes into from the original location — James, Apr 24 '15 at 15:18
@Sinatr it does not work that way, the code runs 1 time per turn, for exapmle: turn 1: my bot is playing, then the code stops and bot 2 is playing, the code runs and stops. all the variable are getting wiped from the memory and in turn 2 it starts over, so i dont think your method will work. — Shaked Dahan, Apr 24 '15 at 16:20

Douglas Zare · Accepted Answer · 2015-04-24T18:15:58.427

You should compute the slope as a float or double, not as an int. When you use integer division, 1/2 is 0, and of course when the slope is 0 you are moving to the right. This means if you go from (0,0) to (20,10) you would have to start with 10 (1,0) steps if you are using integer division, and that is not the best behavior.

If you set a fixed threshold for the (floating point) slope, such as if the slope is less than 1.0 then go right, then you will not follow a line closely at all because you will move due right until you get to a point where the slope is greater than the threshold. So, don't use a fixed threshold.

A quick-and-dirty method is to randomize the threshold so that it causes you to move in the right direction on average. I'll assume dx>0 and dy>0. You can handle the other quadrants by symmetry. To move in the right direction on average, you can choose a random integer from [0,dx+dy-1]. If it is less than dx, then take a step in the x direction. If it is greater than or equal to dx, take a step in the y direction. Equivalently, choose a random double in [0,1] and if it is lower than dx/(dx+dy), take a step in the x direction, otherwise take a step in the y direction.

If you don't like the randomization, then you can derandomize this. Instead of picking a fixed threshold, you can choose a pseudo-random function of (dx,dy,x,y). For example, you could compare dx/(double)(dx+dy) with (2^((dx+3*dy)%28) mod 29)/29.0. This sets the threshold from 1/29 to 28/29 in a roughly uniform manner.

Edit: Here is some untested code.

// assume dx>0, dy>0
int linearMod28 = (dx + 3*dy) % 28; // 0 through 27
int pseudorandomMod29 = (1 << linearMod28) % 29; // 1 through 28
double threshold = pseudorandomMod29/29.0; // 1/29 through 28/29
if (dx/(double)(dx+dy) < threshold)
    // take a step in the x direction
else
    // take a step in the y direction

I didnt not understand what you meant in the last 4 lines. could you show me a code example of what you meant? (something small) — Shaked Dahan, Apr 24 '15 at 18:03
THANK YOU!!! thats the first thing that actually worked! but i did not understand 2 things, why do %28 and %29? i mean why those numbers and not 52 or 36? — Shaked Dahan, Apr 24 '15 at 19:06
I used a little number theory. Since 29 is prime, and one of the primitive roots is 2, the powers of 2 cover all of the possibilities mod 29 except for 0, repeating every 28. So, 2^0 mod 29=1, 2^1 mod 29=2, 2^2 mod 29=4, ... 2^27 mod 29=15, 2^28 mod 29=1. The powers of 12 would not be a good choice, since these would only hit a few possibilities before repeating, since 12^4 mod 29 = 1. Since the powers of 2 repeat every 28, you only have to keep track of the exponent mod 28, and reducing to a number from 0 through 27 means you can compute 2^k using the shift operator. — Douglas Zare, Apr 24 '15 at 22:35
You could do something other than take powers of a number mod 56 to get a sequence of numbers from 1/56 through 55/56. It would probably be fine, but it might be slightly more complicated. Initially I planned to use 1/1007 through 1006/1007, but I couldn't do those with just shifts. — Douglas Zare, Apr 24 '15 at 22:43
thank you very much! if ill win the competition ill give you some of its prize ;) — Shaked Dahan, Apr 25 '15 at 11:47

Trying to move an object in a matrix using line drawing algorithm

1 Answers1