algorithm - 如何为寻路算法优化大图？

Question

我开发了一个小程序，用户可以在其中创建一个简单的图表，其中包含用线连接的抽象 block ，例如流程图或结构图。工作说明书的条款之一是线必须绕过其他 block \线并且在移动时不要与它们相交。

插图

我尝试使用像 A* 或 Lee 算法 这样的寻路算法，并考虑像图形一样的工作空间(一个带有图表元素的窗口)——一个像素就是一个像素图节点。但是， block \线的移动会导致显着的时间延迟(例如，在大小为 500x500 的工作空间中寻路大约需要 320-360 毫秒)。对于那些算法来说，图表似乎太大了。

你能告诉我如何减少这个案例的节点数量吗？也许有办法加速这些算法或使用其他方法吗？!

Answer 1

不要将其视为图论问题，而应将其视为物理问题。

可视化如下。每个方 block 都有特定的力将其拉向最后放置的位置。线段、 block 和图形的边按照平方反比定律相互排斥(除了你画的线的末端不排斥它前面的 block )。在足够大的压力下，一条线段可以分解成更小的线段，这些线段有恢复直线的拉力。

动态很复杂，但实体的数量是您在屏幕上看到的对象数量，而不是绘制对象的像素数量。因此，您将能够相对快速地进行更新。

您需要稍微调整动态以获得良好的体验，但这应该是一种更易于处理的方法。