草庐IT

javascript - 计算两点之间的最短路径

coder 2023-05-29 原文

过去几周我一直在使用 nodejs 和 websockets 开发多人 HTML5 游戏。

我已经被这个问题困住了一段时间。 想象一下，我用数组实现了这个 tilesheet map (如下所示)。

1 或 棕色瓷砖 - 路上有障碍物，玩家无法通过。

0 或 绿色瓷砖 - 是允许玩家移动的自由路径。

通过调用访问 map 上的任何图 block :

 array[x][y]

我想创建最快的算法来找出 map 两点之间的最短路线(如果有的话)。你会如何处理这个问题？我知道这是常见的问题。

示例:

位置 (1,7) 的玩家使用一些 AI 向位置 (6,0) 的敌方玩家发射子弹。 Bullet 必须计算 2 个玩家之间的最短路径，如果没有，它就会撞到墙上爆炸。

问题:

如何高效地找到两点之间的最短路径？

最佳答案

这是一个常见的 graph theory problem algorithm

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

The problem of finding the shortest path between two intersections on a road map (the graph's vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of its road segment) may be modeled by a special case of the shortest path problem in graphs.

目前存在 lot of implementations这个算法的。更简单的实现是 Dijkstra's algorithm最坏情况下的性能为 O(|E|+|V|log|V|) where

  • |V|是 Node 数
  • |E| 是边数

算法工作图解

Dijkstra 最短路径算法的定义

  • 初始 Node - 我们开始的 Node 。
  • Node Y的距离 - 是初始 Node 到Y的距离。

算法会分配一些初始距离值，并会尝试逐步改进它们:

  1. 为每个 Node 分配一个暂定的距离值:对于我们的初始 Node ，将其设置为 0，对于所有其他 Node ，将其设置为 ∞。

  2. 将初始 Node 设置为当前 Node 。标记所有其他 Node 未访问。创建一组所有未访问 Node ，称为未访问集。

  3. 对于当前 Node ，考虑其所有未访问邻居并计算它们的暂定距离。将新计算的暂定距离与当前分配的值进行比较，并分配较小的那个。

  4. 当我们考虑完当前 Node 的所有邻居后，将当前 Node 标记为已访问并将其从未访问集中删除。被访问的 Node 将永远不会被再次检查。

  5. 如果目标 Node 已被标记为已访问(当规划两个特定 Node 之间的路线时)，或者如果 未访问集 中 Node 之间的最小暂定距离为 ∞(当规划一个完全遍历；当初始 Node 和剩余未访问 Node 之间没有连接时发生)，然后停止。 算法已完成。

  6. 否则，选择暂定距离最小的unvisited Node ，设置为新的“当前 Node ”，返回步骤3。

更多 Dijkstra 算法的实现您可以在 github 存储库 mburst/dijkstras-algorithm 上找到.

例如这里是 JavaScript implementation

关于javascript - 计算两点之间的最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39256309/

javascript两点strongNodenoreferrernode.jsalgorithmmathgraph-algorithm

有关javascript - 计算两点之间的最短路径的更多相关文章

  1. ruby-on-rails - Rails 应用程序之间的通信 - 2

    我构建了两个需要相互通信和发送文件的Rails应用程序。例如，一个Rails应用程序会发送请求以查看其他应用程序数据库中的表。然后另一个应用程序将呈现该表的json并将其发回。我还希望一个应用程序将存储在其公共(public)目录中的文本文件发送到另一个应用程序的公共(public)目录。我从来没有做过这样的事情，所以我什至不知道从哪里开始。任何帮助，将不胜感激。谢谢! 最佳答案 无论Rails是什么，几乎所有Web应用程序都有您的要求，大多数现代Web应用程序都需要相互通信。但是有一个小小的理解需要你坚持下去，网站不应直接访问彼此

  2. ruby-on-rails - 使用一系列等级计算字母等级 - 2

    这里是Ruby新手。完成一些练习后碰壁了。练习:计算一系列成绩的字母等级创建一个方法get_grade来接受测试分数数组。数组中的每个分数应介于0和100之间，其中100是最大分数。计算平均分并将字母等级作为字符串返回，即“A”、“B”、“C”、“D”、“E”或“F”。我一直返回错误:avg.rb:1:syntaxerror,unexpectedtLBRACK,expecting')'defget_grade([100,90,80])^avg.rb:1:syntaxerror,unexpected')',expecting$end这是我目前所拥有的。我想坚持使用下面的方法或.join，

  3. ruby - ＃之间？ Cooper 的 *Beginning Ruby* 中的错误或异常 - 2

    在Cooper的书BeginningRuby中，第166页有一个我无法重现的示例。classSongincludeComparableattr_accessor:lengthdef(other)@lengthother.lengthenddefinitialize(song_name,length)@song_name=song_name@length=lengthendenda=Song.new('Rockaroundtheclock',143)b=Song.new('BohemianRhapsody',544)c=Song.new('MinuteWaltz',60)a.betwee

  4. ruby-on-rails - `a ||= b` 和 `a = b if a.nil 之间的区别？ - 2

    我正在检查一个Rails项目。在ERubyHTML模板页面上，我看到了这样几行:我不明白为什么不这样写:在这种情况下，||=和ifnil?有什么区别？ 最佳答案 在这种特殊情况下没有区别，但可能是出于习惯。每当我看到nil?被使用时，它几乎总是使用不当。在Ruby中，很少有东西在逻辑上是假的，只有文字false和nil是。这意味着像if(!x.nil?)这样的代码几乎总是更好地表示为if(x)除非期望x可能是文字false。我会将其切换为||=false，因为它具有相同的结果，但这在很大程度上取决于偏好。唯一的缺点是赋值会在每次运行

  5. ruby-on-rails - Rails - 使用/自定义 URL : '/dashboard' 指定根路径 - 2

    如何使此根路径转到:“/dashboard”而不仅仅是http://example.com？root:to=>'dashboard#index',:constraints=>lambda{|req|!req.session[:user_id].blank?} 最佳答案 您可以通过以下方式实现:root:to=>redirect('/dashboard')match'/dashboard',:to=>"dashboard#index",:constraints=>lambda{|req|!req.session[:user_id].b

  6. 计算机毕业设计ssm+vue基本微信小程序的小学生兴趣延时班预约小程序 - 2

    项目介绍随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱小学生兴趣延时班预约小程序的设计与开发被用户普遍使用,为方便用户能够可以随时进行小学生兴趣延时班预约小程序的设计与开发的数据信息管理,特开发了小程序的设计与开发的管理系统。小学生兴趣延时班预约小程序的设计与开发的开发利用现有的成熟技术参考,以源代码为模板,分析功能调整与小学生兴趣延时班预约小程序的设计与开发的实际需求相结合,讨论了小学生兴趣延时班预约小程序的设计与开发的使用。开发环境开发说明：前端使用微信微信小程序开发工具：后端使用ssm：VU

  7. [工业相机] 分辨率、精度和公差之间的关系 - 2

    📢博客主页：https://blog.csdn.net/weixin_43197380📢欢迎点赞👍收藏⭐留言📝如有错误敬请指正！📢本文由Loewen丶原创，首发于CSDN，转载注明出处🙉📢现在的付出，都会是一种沉淀，只为让你成为更好的人✨文章预览：一.分辨率（Resolution）1、工业相机的分辨率是如何定义的？2、工业相机的分辨率是如何选择的？二.精度（Accuracy）1、像素精度（PixelAccuracy）2、定位精度和重复定位精度（RepeatPrecision）三.公差（Tolerance）四.课后作业（Post-ClassExercises）视觉行业的初学者，甚至是做了1~2年

  8. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  9. ruby - 如何根据长度将路径数组转换为嵌套数组或散列 - 2

    我需要根据字符串路径的长度将字符串路径数组转换为符号、哈希和数组的数组给定以下数组:array=["info","services","about/company","about/history/part1","about/history/part2"]我想生成以下输出，对不同级别进行分组，根据级别的结构混合使用符号和对象。产生以下输出:[:info,:services,about:[:company,history:[:part1,:part2]]]#altsyntax[:info,:services,{:about=>[:company,{:history=>[:part1,:pa

  10. ruby - 使用 Ruby，计算 n x m 数组的每一列中有多少个 true 的简单方法是什么？ - 2

    给定一个nxmbool数组:[[true,true,false],[false,true,true],[false,true,true]]有什么简单的方法可以返回“该列中有多少个true？”结果应该是[1,3,2] 最佳答案 使用转置得到一个数组，其中每个子数组代表一列，然后将每一列映射到其中的true数:arr.transpose.map{|subarr|subarr.count(true)}这是一个带有inject的版本，应该在1.8.6上运行，没有任何依赖:arr.transpose.map{|subarr|subarr.in

随机推荐