代码之家 › 专栏 › 技术社区 › Relequestual

我的随机漫游算法怎么了?

path algorithm java

Relequestual · 技术社区 · 15 年前

我为我在Java中创建的游戏世界创建了一个2维的网格。我创建的“漫游”模式算法有问题。

我注意到一个问题,即对象似乎倾向于网格的右下角。我改变了算法,认为它是固定的。

今天,当压力测试时,我注意到问题并没有得到解决,现在漫游的对象倾向于网格的左上角,但是在这个区域漫游需要更长的时间。

该算法的工作原理如下: 1.获取人员职位的当前值 2。将半径为3个块的所有方块放入链接列表中三。随机化列表 4。从列表中选择一个随机值 5。将该值设置为下一个目标

下面是代码段:

 Point personAt = this.getTopLeftPoint();
    personAt = Game.getGame().screenToGame(personAt);
    LinkedList<Point> thisSet = new LinkedList<Point>();
    for (int x = personAt.x - 2; x < personAt.x + 3; x++) {
    for (int y = personAt.y - 2; y < personAt.y + 3; y++) {
        if (!(x == personAt.x && y == personAt.y)) {
        //TODO: Clean up the next line of code.
        if (x > 0 && y > 0 && !Board.getBoard().getSquare(x, y).getSquareType().equals(SquareType.path)) {
            if (!Game.getGame().getMap().blocked(x, y)) {
            thisSet.add(new Point(x, y));
            }
        }
        }
    }
    }
    Collections.shuffle(thisSet);
    //Random random = new Random();
    //Integer randomNo = random.nextInt(thisSet.size());
    setNextTarget(thisSet.get(0));

我这里有什么东西不见了吗?

我很困惑为什么它们仍然会出现在网格的左上角。

编辑: 我完全移除了随机物体, as suggested by Don .结果还是一样的。

编辑:更新代码以修复问题的一部分,因此现在只忽略人员当前所在的方块,而忽略当前x或y坐标上的所有方块。按照RSP的建议。

7 回复 | 直到 15 年前

user85421 15 年前

很难在代码中找到任何问题,但您调用了该代码之外的许多方法。从gettopleftpoint()开始,我的第一个疑点是,您确定要对坐标使用相同的引用吗?如果gettopleftpoint()返回最左边、最上面的点,但setNextTarget设置了中间点,那么我们就有问题了!

下一步:screentogame()还会更改坐标…也可能是问题的根源。

如果部分正确的话

!Board.getBoard().getSquare(x, y).getSquareType().equals(SquareType.path)

你只能走一条不是小路的广场?(与问题无关…)

另一个:blocked()不确定realy做了什么。如果所有的方块都在人的右侧和侧面被阻挡,他将在左上角结束。

最后一个几乎与第一个相同:setNextTarget()与screentogame()具有相同的坐标引用?

总结:最好创建一些单元测试来测试没有这些“噪声”的随机漫游算法。
我这样做得到了很好的结果(没有阻塞,没有路径)。每个角落的人访问次数几乎相同。

还有一点:我更喜欢使用随机列表,而不是把所有的列表都洗掉,只得到其中的一个元素…

Dónal 15 年前

一些要点,其中一些是在其他答案中提出的:

与以往一样,只创建 Random() . 我怀疑这是答案的一部分-很少有关于堆栈溢出时随机数的问题不是与此相关:)
你为什么要洗牌? 和随机元素?只需选择一个随机元素。
不对称的一点:您正在检查x>0和y>0(顺便问一下,不是大于等于0?)但你不需要检查x和y是否在棋盘的上界内。如果 Board.getSquare() 解决这个问题,您真的需要>0支票吗?

Stefan Kendall 15 年前

只初始化一次随机。你反复地重新测试随机生成器,破坏了随机性。

最好使用整个应用程序的工厂来创建随机的单例。

public class RandomFactory
{
    private Random random;
    public Random getRandom()
    {
       if( random == null ){ random = new Random(); }

       return random;
    }
}

Dónal 15 年前

假设 shuffle() 方法是无偏见的,没有理由需要在洗牌后随机选择元素,您可以简单地选择第一个元素。换言之,替换:

Collections.shuffle(thisSet);
Random random = new Random();
Integer randomNo = random.nextInt(thisSet.size());
setNextTarget(thisSet.get(randomNo));

用:

Collections.shuffle(thisSet);
setNextTarget(thisSet.get(0));

Brienne Schroth 15 年前

正如其他人所说,您应该只实例化一次随机对象,然后重用它,shuffle()调用意味着您根本不需要使用随机对象。但是对于bug的根本原因,每次调用它时,它都会在这里初始化。getTopLeftPoint(),所以我不知道它如何不总是转到左上角。我认为您应该在角色的实际位置(而不是左上角)实例化它。

rsp 15 年前

你说你把周围所有的点都放在列表中,但是你的代码排除了水平线和垂直线,所以你的对象倾向于只沿对角线方向移动,这可能解释了对左上角的偏好。

顺便说一句,您的条件可以放得更可读一些,这样可以节省一些不必要的执行过程:

for (int x = personAt.x - 2; x < personAt.x + 3; x++) {
  if (x > 0 && x != personAt.x) {
    for (int y = personAt.y - 2; y < personAt.y + 3; y++) {
      if (y > 0 && y != personAt.y) {

         if (!Game.getGame().getMap().blocked(x, y) &&
               !Board.getBoard().getSquare(x,y).getSquareType().equals(SquareType.path)) {

            thisSet.add(new Point(x, y));
         }
      }
   }
}

Dolphin 15 年前

Person对象列表的顺序是什么(您正在运行此代码)?如果你按照预先设定的顺序迭代它们,那么你可能会在那里引入一个偏差,因为第一个结果会对第二个结果产生影响(等等)。

在处理人员列表之前,您可以尝试对其进行洗牌。