连接节点图的快速路径缓存生成
我正在尝试在我正在为连接节点图开发的游戏中找到更快的寻路机制。节点分为两种类型：“网络”和“路由器”。
在这张图中，蓝色圆圈代表路由器，灰色矩形代表网络。
每个网络都保存一个它所连接的路由器的列表，反之亦然。路由器不能直接连接到其他路由器，网络也不能直接连接到其他网络。
网络列出它们连接到的路由器
路由器也做同样的事情，
我需要一种算法，为每个可能的源和目标网络绘制一条路径，以穿越的网络数量来衡量，不包括源和目标是同一网络的路径。我现在有一个，但是速度慢得无法使用，大约需要两秒钟来绘制路径，这对于所有连接的玩家来说都变得非常明显。
当前的算法是深度优先的强力搜索（它在大约一个小时内拼凑在一起，以使路径缓存正常工作），它按遍历的顺序返回网络数组，这解释了为什么它如此慢。有没有更高效的算法？
附带说明一下，虽然这些示例图表有 4 个网络，但实际图表有 55 个网络和大约 20 个正在使用的路由器。不可能的路径也可能发生，并且网络/路由器图形拓扑可能随时发生变化，从而需要重建路径缓存。
什么方法/算法可能为这种类型的图表提供最佳结果？
I'm trying to get a faster pathfinding mechanism in place in a game I'm working on for a connected node graph. The nodes are classed into two types, "Networks" and "Routers."
In this picture, the blue circles represent routers and the grey rectangles networks.
Each network keeps a list of which routers it is connected to, and vice-versa. Routers cannot connect directly to other routers, and networks cannot connect directly to other networks.
Networks list which routers they're connected to
Routers do the same
I need to get an algorithm that will map out a path, measured in the number of networks crossed, for each possible source and destination network excluding paths where the source and destination are the same network. I have one right now, however it is unusably slow, taking about two seconds to map the paths, which becomes incredibly noticeable for all connected players.
The current algorithm is a depth-first brute-force search (It was thrown together in about an hour to just get the path caching working) which returns an array of networks in the order they are traversed, which explains why it's so slow. Are there any algorithms that are more efficient?
As a side note, while these example graphs have four networks, the in-practice graphs have 55 networks and about 20 routers in use. Paths which are not possible also can occur, and as well at any time the network/router graph topography can change, requiring the path cache to be rebuilt.
What approach/algorithm would likely provide the best results for this type of a graph?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
Dijkstra 的最短路径算法是经典的，但仅针对静态图而设计。
您可以尝试在网络上搜索动态最短过去算法。
这是一篇似乎相关的论文： http://www.utdallas.edu /~edsha/papers/bin/Globecom04_SPT.pdf
（并可能为您提供其他线索）。
本文描述了一个路由器网络，其中每个路由器都维护自己的最短路径表。也许你可以做类似的事情。
我建议你也看看一般的路由算法，因为采用最短路径总是可能会导致拥塞等（我在想 16 队光环！）。您可能还想合并负载平衡等。
希望它有帮助。
Dijkstra's shortest path algorithm is the classic, but is only designed for static graphs.
You can try searching the web for dynamic shortest past algorithms.
Here is one paper which seems relevant: http://www.utdallas.edu/~edsha/papers/bin/Globecom04_SPT.pdf
(and might give you other leads).
This paper describes a network of routers, where each router maintains it's own Shortest Path Table. Perhaps you can do something similar.
I suggest you also look at routing algorithms in general as taking the shortest path always might cause congestion etc (I am thinking 16 team Halo!). You might also want to incorporate load balancing etc.
Hope it helps.
您可能想看看经典网络领域。这不是确切的答案，但应该为您提供“比暴力更好”算法的起点。
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
You might want to look in the classical networking domain. This isn't the exact answer, but should give you a starting point for "better than brute force" algorithms.
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm