c# - 尝试使用画线算法移动矩阵中的对象

Question

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

但它不是“排队”，而是这样:

我在这里提出了关于这个问题的另一个问题，你告诉我使用画线算法，我这样做了，但我仍然无法让它按这个顺序移动。

关于代码的一些信息(我给你一些“背景”，这样你就不会感到困惑):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);计算对象在下一回合结束的位置(返回位置)。

现在这是我得到的代码:

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 类中的部分，以下是这些部分:

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

我告诉你的“物体”在代码中被称为myPirate，它每回合只能向一个方向移动。代码每轮都会再次运行，直到到达目标。

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

Answer 1

您应该将斜率计算为 float 或 double ，而不是整数。当你使用整数除法时，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