blocks|key|737386|text|我会尝试将网格表示为一个图形，并运行Dijkstra算法。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|737387|该图形可能需要1G或更多，但它适合于任何现代计算机中的RAM。|737388|算法复杂度为O(E+%2B+V*log(V))，即O(网格大小)。由于有10%5E8个节点，我想它一定是可行的。假设我们每个节点有1000个CPU滴答。如果我们有4G+CPU，一个滴答是2.5*10%5E-10秒，也就是说，我们有2.5*10-7秒。每个节点。对于2*10%5E8节点，我们有~1分钟的时间。|737389|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

I would try to represent the grid as a graph and run the Dijkstra algorithm. 

The graph probably takes 1G or even more, but it fits RAM in any modern computer.

The algorithm complexity is O(E + V*log(V)), i.e. O(size of the grid). Since there are ~10^8 nodes, I guess it must be feasible. Let's say we have ~1000 CPU ticks per node. If we have 4G CPU, a tick is 2.5*10^-10 sec, i.e. we have 2.5*10-7 sec. per node. For 2*10^8 nodes we have ~ 1 minute.

blocks|key|2291816|text|与2D政治龙相邻的岛屿边界|type|ordered-list-item|depth|inlineStyleRanges|entityRanges|data|2291817|将分离的政治龙的顶点(以及起点和终点)与边缘连接起来(它们不能跨越岛屿)|2291818|将A*应用于生成图|2291819|这样的图形远远小于10000x20000网格，让我们在更好的时间内找到更多真实的路径。|unstyled|2291820|更新：如果岛屿不是很大，您只需将船移向终点，并绕过它们左右边界的岛屿即可。|offset|length|style|BOLD|2291821|entityMap^0|0|0|0|0|0|2|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|R|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|S|8|@]|9|@]|A|$]]|$1|F|3|G|5|H|7|T|8|@]|9|@]|A|$]]|$1|I|3|J|5|H|7|U|8|@$K|V|L|W|M|N]]|9|@]|A|$]]|$1|O|3|-4|5|H|7|X|8|@]|9|@]|A|$]]]|P|$]]

<ol>
<li>aproximate islands' borders with 2D poligons</li>
<li>connect vertexes of separated poligons (and start and finish points) with edges (they must not cross islands)</li>
<li>apply A* to resulting graph</li>
</ol>

Such graph much less then 10000x20000 grid and let find more realistic paths in better time

Update: if islands is not big you can just move ship in direction of finish point and bypass islands on their left or right border

blocks|key|2291851|text|如果这些岛屿在大范围内相对稀疏，你可以使用我去年实现的一种算法，用于机器人在有物体可避免的环境中追逐移动的球。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2291852|我所做的就是在机器人、球和障碍物周围定义网格点，并在整个环境中添加一个稀疏的均匀网格。两个网格点之间的边界成本取决于障碍物与该边缘的距离(如果边界通过障碍物，则代价将是无限的)。然后用A*计算出最佳路线。这是在一台用Java编程的旧笔记本电脑上每秒完成40次。|2291853|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

If the islands are relatively sparse in a big see, you could use an algorithm I implemented last year for robots chasing a moving ball in an environment with objects to avoid.

What I did was define grid points around the the robot, the ball, and the obstacles, and add a sparse uniform grid over the whole environment. The cost of an edge between two gridpoints depends on how close obstacles are to this edge (if the edge goes through the obstacle cost would be infinite). Then calculate the best route using A*. This is done 40 times per second on an old laptop, programmed in Java.

blocks|key|1934909|text|与Tiendil的建议有关，LaValle的规划算法书讨论了如果岛屿是2D多边形，在用于最短路径搜索的图中包含哪些边。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1934910|entityMap|0|LINK|mutability|MUTABLE|url|http://planning.cs.uiuc.edu/node271.html^0|16|A|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

Related to Tiendil's suggestion, LaValle's Planning Algorithms book has a discussion of what edges to include in <a href="http://planning.cs.uiuc.edu/node271.html" rel="nofollow">graphs for shortest-path searches</a> if the islands are 2D polygons.

Let's say we have a rectangular sea. It's quite large - 10000x20000. 

We have islands, as well. For simplicity's sake, let's assume they are rectangular as well. We know their exact places (coordinates).

If we have a ship, somewhere on the map - (x1, y1), how can we find the shortest path to another point on the map (x2, y2) without going over any of the islands?

Update: There are no constraints so far - for the ship or for the sea. If we can simplify (and speed up) things by adding a few - this is more than welcome.

The path even doesn't have to be the best - it can be 10% off for example - perfectly acceptable.

Ship movement algorithm

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

假设我们有一个长方形的海。它很大- 10000x20000。我们也有岛屿。为了简单起见，让我们假设它们也是矩形的。我们知道他们的确切位置(坐标)。如果我们有一艘船，在地图上的某个地方- (x1，y1)，我们怎样才能找到到达地图上另一个点的最短路径(x2，y2)而不经过任何一个岛屿？更新：到目前为止还没有任何限制--无论...

问船舶运动算法
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问船舶运动算法EN