在 2D 板上随机生成实体，避免碰撞
Randomly generate entity on 2D board avoiding collisions
我正在尝试制作一条蛇的克隆体，我希望这条蛇有 5 个像素左右的宽度，并且以 1 个像素的增量移动。这意味着蛇可以比一条蛇宽度更接近自身。这在随机生成食物时使事情变得复杂，食物将是 5x5 像素的正方形。我需要/想要一种算法，将随机生成减少到不包含蛇的 5x5 方块。
部分问题在于，由于食物是 5x5，因此必须针对食物内的每个像素检查碰撞检测，以查看蛇是否部分位于食物内。这给我留下了两个问题
问题
随机生成食物时如何减少搜索space？
我想过做一个四叉树，细分 space 直到划分小于我想要放置的食物。我还考虑过使用 awt 的 Rectangle，并确定食物的生成位置是否包含在构成播放器的矩形列表中。
我能想到的最好的解决方案是生成一个二维数组，包含所有可能的矩形，以它们的左上角作为索引值。然后生成另一个二维数组，将每个像素映射到包含它的每个矩形，甚至只是起点，不需要整个矩形（每个 25 个）。然后在每次移动之后，更新头部和尾部的角映射，标记它所占据的每个映射矩形。然后使用映射角数组进行更简单的随机搜索（这将其减少为 1x1 像素搜索 space）。
我试图避免的主要问题是，当蛇填满 90% 的可玩空间时 space，任何基本的搜索-失败-重复系统都将花费大量时间才能完成，最糟糕的是case，永远不要生成食物方块。
7个月后我找到了解决方案。我还没有测试这个，因为我还得实现它。
我处理蛇体的方式是通过左上角的 X、Y 坐标、宽度和高度定义的矩形列表。
我能做的是从整个棋盘开始创建一棵8阶树，然后将每个蛇部分放入树中，左上角偏移苹果的大小。放置零件后，我可以根据蛇的 4 个角、4 条边和中心将板分成 9 个部分。忽略包含蛇的板件和尺寸 <= 0 的板件，我可以将它们放入树中。
由于蛇的部分已经根据苹果的大小进行了调整，因此未占用的叶节点内的任何点都可用于放置苹果
我正在尝试制作一条蛇的克隆体，我希望这条蛇有 5 个像素左右的宽度，并且以 1 个像素的增量移动。这意味着蛇可以比一条蛇宽度更接近自身。这在随机生成食物时使事情变得复杂，食物将是 5x5 像素的正方形。我需要/想要一种算法，将随机生成减少到不包含蛇的 5x5 方块。
部分问题在于，由于食物是 5x5，因此必须针对食物内的每个像素检查碰撞检测，以查看蛇是否部分位于食物内。这给我留下了两个问题
问题
随机生成食物时如何减少搜索space？
我想过做一个四叉树，细分 space 直到划分小于我想要放置的食物。我还考虑过使用 awt 的 Rectangle，并确定食物的生成位置是否包含在构成播放器的矩形列表中。
我能想到的最好的解决方案是生成一个二维数组，包含所有可能的矩形，以它们的左上角作为索引值。然后生成另一个二维数组，将每个像素映射到包含它的每个矩形，甚至只是起点，不需要整个矩形（每个 25 个）。然后在每次移动之后，更新头部和尾部的角映射，标记它所占据的每个映射矩形。然后使用映射角数组进行更简单的随机搜索（这将其减少为 1x1 像素搜索 space）。
我试图避免的主要问题是，当蛇填满 90% 的可玩空间时 space，任何基本的搜索-失败-重复系统都将花费大量时间才能完成，最糟糕的是case，永远不要生成食物方块。
7个月后我找到了解决方案。我还没有测试这个，因为我还得实现它。
我处理蛇体的方式是通过左上角的 X、Y 坐标、宽度和高度定义的矩形列表。
我能做的是从整个棋盘开始创建一棵8阶树，然后将每个蛇部分放入树中，左上角偏移苹果的大小。放置零件后，我可以根据蛇的 4 个角、4 条边和中心将板分成 9 个部分。忽略包含蛇的板件和尺寸 <= 0 的板件，我可以将它们放入树中。
由于蛇的部分已经根据苹果的大小进行了调整，因此未占用的叶节点内的任何点都可用于放置苹果