13

考虑一个矩形画布，其中包含随机大小和位置的矩形。要在这些矩形之间导航，用户可以使用四个箭头：上、下、左、右。

您是否熟悉任何可以产生相当直接的用户体验的导航算法？

我遇到了一些解决方案，但似乎都不合适。我知道没有解决方案是“理想的”。但是，我正在寻找的算法是用于仅使用箭头键在桌面上的图标之间导航的算法。

4

4 回答 4

5

[编辑 21/5/2013：正如 Gene 在评论中指出的那样，我的加权方案实际上并不能保证每个矩形都可以从每个其他矩形到达 - 只是每个矩形都会在每个方向上连接到某个其他矩形.]

一个很好的方法是使用最大加权二分匹配。

我们要做的是构建一个定义函数 f(r, d) 的表，如果用户当前位于矩形 r 并且点击方向 d（上、下、左或右），则返回用户将移动到的矩形。我们希望这个函数有一些不错的属性，例如：

  1. 必须可以从每个其他矩形到达每个矩形
  2. 按左然后右，反之亦然，或上，下，反之亦然，应该将用户留在同一个地方
  3. 按下 eg left 应该将用户带到左侧的一个矩形（这有点难以准确说明，但我们可以使用评分系统来衡量质量）

对于每个矩形，在图中创建 4 个顶点：一个顶点对应于在该矩形上可以按下的每个可能的键。对于特定的矩形 r，称它们为 r U、 r D、 r L和 r R。对于每对矩形 r 和 s，创建 4 条边：

  • (r U , s D )
  • (r D , s U )
  • (r L , s R )
  • (r R , s L )

该图有 2 个连通分量：一个包含所有 U 和 D 顶点，另一个包含所有 L 和 R 顶点。每个组件都是二分的，因为例如没有 U 顶点连接到另一个 U 顶点。实际上，我们可以在每个组件上分别运行最大加权二分匹配，尽管在分组后讨论在整个图上运行一次更容易，例如，U 顶点与 L 顶点和 D 顶点与 R 顶点。

根据这对矩形通过那对键连接起来的意义，为这些边中的每一个分配一个非负权重。您可以自由选择此评分函数的形式，但它可能应该是：

  • 与矩形之间的距离成反比（您可以使用它们中心之间的距离），并且
  • 与矩形中心之间的角度与所需的水平或垂直线的差异成反比，并且
  • 每当矩形以错误的方式定向时为零（例如，如果对于边缘 (r U , s D )，如果 r 的中心实际上在 s 的中心之上）。或者，您可以只删除这些零权重边。

此函数尝试满足顶部的要求 3。

[EDIT #2 24/5/2013：在下面添加了一个示例函数。]

这是满足这些属性的示例函数的 C-ish 伪代码。它取 2 个矩形的中心点和矩形 1 的方向（矩形 2 的方向始终与此方向相反）：

const double MAXDISTSQUARED = /* The maximum possible squared distance */;
const double Z = /* A +ve number. Z > 1 => distance more important than angle */

// Return a weight in the range [0, 1], with higher indicating a better fit.
double getWeight(enum direction d, int x1, int y1, int x2, int y2) {
    if (d == LEFT  && x1 < x2 ||
        d == RIGHT && x1 > x2 ||
        d == UP    && y1 < y2 ||
        d == DOWN  && y1 > y2) return 0;

    // Don't need to take sqrt(); in fact it's probably better not to
    double distSquared = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    double angle = abs(atan2(x1 - x2, y1 - y2));   // 0 => horiz; PI/2 => vert
    if (d == UP || d == DOWN) angle = PI / 2 - angle;
    return 1 - pow(distSquared / MAXDISTSQUARED, Z) * (2 * angle / PI);
}

现在运行最大加权二分匹配。这将尝试找到具有最高总权重的边集，使得每个顶点（或至少尽可能多的顶点）都与所选边相邻，但没有顶点与多于一条边相邻。（如果我们允许一个顶点与多个边相邻，这意味着在该矩形处按下该键会将您带到多个目标矩形，这是没有意义的。）此匹配中的每条边对应到一对双向按键，以便按下例如向上然后向下将返回到您所在的位置，自动满足顶部的要求2。

到目前为止，这种方法没有自动满足的唯一要求是重要的第 1 个要求：它不一定保证每个矩形都可以到达。如果我们只使用“原始”质量分数作为边缘权重，那么这实际上可能发生在某些配置中，例如，当屏幕的 4 个角各有一个矩形，再加上一个在中心的矩形时，中心的一个可能是遥不可及。

[编辑 2013 年 5 月 21 日：正如 Gene 所说，我提出的新加权方案满足属性 1 的说法是错误的。在许多情况下，每个矩形都是可达的，但一般来说，您需要解决 NP-hard Hamiltonian Cycle 问题来保证这一点。我会留下解释，因为它让我们了解了一些情况。无论如何，只要检测到子周期，就可以通过向上调整连接组件之间的权重来破解它。]

为了保证匹配算法总是返回每个矩形都可达的匹配，我们需要调整边权重，以使匹配永远不可能比具有更多边的匹配得分更高。这可以通过将评分函数缩放到 0 和 1 之间，并将矩形的数量n 添加到每条边的权重来实现。这是有效的，因为完整匹配的得分至少为 4n^2（即，即使质量得分为 0，边缘本身的权重为 n，并且有 4n 个），而任何具有较少边缘的匹配最多得分4(n-1)(n+1) = 4n^2 - 4，严格来说是更少。

于 2013-05-16T00:49:08.930 回答
3

不言而喻，对于一个拿着锤子的人来说，一切看起来都像钉子。最短路径算法在这里是一个明显的工具，因为最短距离看起来很直观。

然而，我们正在设计一个 UI，其中逻辑距离比物理距离更重要。

因此，让我们尝试不同的想法。

一个限制是重复点击向上（右、下或左）箭头最终应该循环通过所有矩形。否则可能会出现一些无法访问的“孤儿”。使用基于物理 (2d) 距离的算法来实现这一点很困难，因为 2d 中最近的项目可能在对应于正在使用的箭头对的 1d 投影中处于错误的方向。即点击向上箭头可以轻松选择当前下方的框。哎哟。

所以让我们采用一个极其简单的解决方案。只需在其质心的 x 坐标上对所有矩形进行排序。按此顺序点击左右箭头在矩形中循环：从右到下一个最高的 x，从左到下一个最低的 x。包裹在屏幕边缘。

也对 y 坐标执行相同的操作。按此顺序使用向上和向下循环。

成功的关键（双关语）是在循环时向屏幕添加动态信息，以向用户展示正在发生的事情的逻辑。这是一个建议。其他是可能的。

在第一次垂直（向上或向下）键时，矩形上方会出现浅色半透明覆盖。它们以由质心的 y 坐标交替的模式着色为淡红色或蓝色。整个窗口还有匹配颜色的水平哈希标记。使用两种颜色的唯一原因是提供线条和矩形之间对应关系的视觉指示。当前选择的矩形是非半透明的，并且井号比其他所有的都亮。当您继续按向上或向下键时，突出显示的框会按照质心 y 顺序发生变化，如上所述。当半秒左右没有按下箭头键时，覆盖消失。

如果按下水平键，则会出现非常相似的叠加层，只有垂直哈希标记和 x 顺序。

作为用户，我真的很喜欢这个方案。但是YMMV。

实现这一点所需的算法和数据结构是显而易见的、微不足道的，并且可以很好地扩展。将努力使叠加层看起来不错。

NB 现在我已经完成了所有的绘图，我意识到在每个盒子的质心放置一个正确颜色的点来显示哪条线与其相交是一个好主意。下面是一些说明性图表。

裸盒

裸箱

使用向上或向下箭头进行选择

使用向上或向下箭头进行选择

使用左箭头或右箭头进行选择

用左箭头或右箭头选择

于 2013-05-15T17:22:07.170 回答
2

如下构建运动图怎么样：

  • 对于任何方向，尝试在给定方向上找到最近的矩形，其中心点是当前矩形边的中间。
  • 尝试消除循环，例如从 A 移动“右”应该尝试产生与从 A 移动“右上”不同的矩形。例如在这个图中，从绿色的“右”应该是橙色，即使粉红色是最近的中点
  • （感谢 biziclop）：如果在图中无法访问任何矩形，则重新映射相邻的矩形之一以到达它，可能是误差最小的一个。重复直到所有矩形都可以到达（我认为该算法将终止......）

然后存储图形并仅使用它来导航。您不想在会话中间更改方向。

于 2012-11-16T16:49:28.710 回答
0

这个问题可以建模为一个graph问题，并且algorithm of navigation可以作为一个shortest path routing.

这里是建模。

每个矩形都是图中的一个顶点。从每个顶点（又名矩形），您有四个选项 - 上、下、左、右。因此，您可以达到四个不同的矩形，即该顶点将有四个邻居，并且您将这些边添加到图形中。

我不确定这是否是问题的一部分——“可以​​使用特定操作（例如向上）从一个矩形到达多个矩形”。如果没有，上面的建模就足够了。如果是，则添加所有此类顶点作为该顶点的邻居。因此，您可能不会得到一个 4 正则图。否则，您会将问题建模为 4 正则图。

现在，问题是how do you define your "navigation" algorithm。如果您不想区分您的动作，即如果上、下、左和右都相等，那么您可以将权重 1 添加到所有边。

如果您决定赋予特定动作比其他动作更高的优先级，例如比其他动作up更好，那么您可以将向上运动产生的边缘的权重设置为 1，将剩余的边缘设置为 2。这个想法是通过分配不同的权重，您可以区分您将行驶的边缘。

如果您确定所有up边不相等，即 A 和 B 之间的向上距离小于 C 和 D 之间的向上距离，那么您可以在图形构建过程中相应地为边缘分配权重。

这里是路由

现在如何查找路线——您可以使用它dijkstra's algorithm来查找给定顶点对之间的最短路径。如果您对多条最短路径感兴趣，可以使用k-shortest path算法找到k一对节点之间的最短路径，然后选择您的最佳路径。

请注意，您最终得到的图不一定是有向图。如果您更喜欢有向图，您可以在构建边时为其指定方向。否则，您应该很好地使用无向图，因为您只关心使用一条边从另一个边到达顶点。此外，如果A使用upfrom rectangle 可以到达 rectangle B，那么rectangle B可以使用downfrom rectangle到达A。因此，如果您出于其他原因不需要它们，方向真的无关紧要。如果你不喜欢我刚才所做的假设，那么你需要构造一个有向图。

希望这可以帮助。

于 2013-05-15T00:59:09.900 回答