Trying to move an object in a matrix using line drawing algorithm
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:
But instead of going "in line" it goes like this:
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?
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