尝试使用画线算法在矩阵中移动对象

Question

我正在尝试使用画线算法在矩阵（带有 [x,y] 的数组）中移动一个对象，以帮助您理解我的意思我正在尝试让一个对象像这样移动:

但不是 "in line" 它是这样的：

我在这里开了另一个关于这个问题的问题，你告诉我用画线算法，我照做了，但我还是不能让它按那个顺序移动。

关于代码的一点点（我给你一些 'background' 所以你不会混淆）： Location 变量包含矩阵上的一个位置，它有 x 和y，可以这样访问：

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)

Direction变量包含一个方向，有5个方向：

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

我认为它们各自的意思很明显。

命令game.Destination(myPirate, direction);计算对象在下一回合结束的位置（returns一个位置）。

现在这是我得到的代码：

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);
        }
    }

在上面代码的某些部分，我也使用了 MyBot class 中的部分，这里是这些部分：

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;
    }

我跟大家说的'object'在代码里叫myPirate，一圈只能往一个方向移动。每回合再次输入代码运行，直到到达目标。

我怎样才能让这个程序正常工作？我的代码有什么问题？

Answer 1

您应该将斜率计算为浮点数或双精度数，而不是整数。当您使用整数除法时，1/2 为 0，当然当斜率为 0 时您正在向右移动。这意味着如果您从 (0,0) 到 (20,10)，如果您使用整数除法，则必须从 10 (1,0) 步开始，这不是最佳行为。

如果您为（浮点）坡度设置了一个固定的阈值，例如如果坡度小于 1.0 则向右走，那么您根本不会紧跟一条线，因为您会向右移动直到您到达斜率大于阈值的点。所以，不要使用固定的阈值。

一种快速而肮脏的方法是随机化阈值，使您平均向正确的方向移动。我假设 dx>0 且 dy>0。您可以通过对称处理其他象限。要平均向正确的方向移动，可以从 [0,dx+dy-1] 中选择一个随机整数。如果小于dx，则在x方向上走一步。如果大于等于dx，就往y方向走一步。等价地，在[0,1]中随机选择一个double，如果低于dx/(dx+dy)，就往x方向走一步，否则往y方向走一步。

如果您不喜欢随机化，那么您可以取消随机化。您可以选择 (dx,dy,x,y) 的伪随机函数，而不是选择固定阈值。例如，您可以将 dx/(double)(dx+dy) 与 (2^((dx+3*dy)%28) mod 29)/29.0 进行比较。这以大致统一的方式将阈值设置为从 1/29 到 28/29。

编辑：这是一些未经测试的代码。

// 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

尝试使用画线算法在矩阵中移动对象

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

c#

algorithm

matrix

line-drawing