图形算法可视化

最近看了一些和图形、算法可视化相关的文章和代码,挺有意思,于是自己也学着做了些东西。

迷宫生成算法

迷宫小时候玩过,但从来没琢磨过迷宫是怎么设计的,以为就是有人慢慢画出来的。看过网上这篇文章后,才知道,原来还可以随机生成:

Maze Generation - Visualizing Algorithms

自己找了些资料参考,试着实现了几种之后,才慢慢领会到其中的一些原理。

算法中讨论的迷宫满足一个条件:迷宫中任意两点间有且只有一条路径

要随机生成满足这样条件的迷宫,看起来很复杂啊。但是换个思路之后,就发现问题没那么复杂了。

“树”其实就满足这个条件:

  • 所有的枝叶都可以通过树枝、树干连通
  • 由于枝干不交叉,没有环,所以枝叶间连通的路径是唯一的

所以,生成随机的迷宫的问题,就转化为生成随机的树的过程。进一步,可以拆分为以下过程:

  • 在迷宫网格内随机选择一个点作为“树根”
  • 从树根开始,向随机选择的某一方向开始生长
  • 直到树的枝干通过不断生长、分叉充满迷宫的所有网格

迷宫生成的不同算法,区别主要在两点:

  • 从一个位置开始生成后一直向随机方向延伸的最大长度:有的是延伸一个网格后立即更换生长点,有的则是直到无法继续延伸后才更换生长点
  • 更换生长点时选择位置的方式:有的是记录当前枝干经过的网格,依次后退,有的干脆是完全随机选择一个有可能向外生长的点

深度优先算法

深度优先算法,也叫递归回溯算法。它会一直向随机方向生长,直到无法生成的位置,向后回退一格,继续生长,直到所有网格被填充。

深度优先算法生成的迷宫

深度优先算法生成的迷宫,会有比较明显的长路径,这是因为树在一开始生成的时候,空间比较充裕,会有一些长的枝条产生。

Prim 算法

Prim 算法不会一直沿着一条路径进行探索,而是不断尝试随机的生长点。所以 Prim 算法生成的迷宫,分叉会比较多:

Prim 算法生成的迷宫

算法实现

综合以上两种算法,我既不希望有过长的路径,也不希望有太多的分叉,所以我采用的思路的尝试沿着一条路径延伸最多一定的长度,然后再随机选择生长点执行相同的过程。

下图是在 40*40 的迷宫网格,每条枝干最多生长15个网格的效果:

迷宫生成算法 - 开始

这是执行了一段时间之后,迷宫大部分区域已经走过:

迷宫生成算法 - 执行中

这是最后的效果:

迷宫生成算法 - 完成

项目地址:luobotang/maze 在线DEMO:迷宫生成算法 - luobotang

算法可视化

上面例子中的迷宫生成算法过程,迷宫网格是通过 HTML 的 <table> 实现,相邻网格的连通效果,则是借助 CSS 的边框样式。

整个迷宫的所有网格由二维数组表示,每个网格的状态包含是否被访问、与相邻网格的连通情况等。

算法的执行过程由定时器驱动,每次执行一步,从而有动画的效果。

最短路径算法

与图相关的最短路径算法,在生活中应该是有着广泛的应用了吧,从一个位置到另一个位置,借助已有的路网,计算最短的路径。当然,还会因为路况、临时障碍,以及用户的个人偏好而产生不同结果。

对于“图”上,基本要素就是:

Dijkstra 算法

Dijkstra 算法是用于计算最短路径的比较著名的一种算法,早在1956年就发表了。

Dijkstra 算法如果看算法的详细执行过程,有点复杂,但是其基本思路在做过之后会发现,貌似很简单。

已确定 A 到 B 的最短路径,B 与 C 相连,且 A 到 B 的距离加上 B 到 C 的距离,小于当前 A 到 C 的距离,那么 A 到 B 再到 C 就是 A 到 C 的最短路径。

图示例

如上图所示,最初从 A 来看,到 C 的最短路径是 A -> C,距离是 4。但继续探索到 B 后,发现 A -> B 加上 B -> C 距离只有 3,比 A -> C 的距离要小,所以 A 到 C 的最短路径更新为:A -> B -> C。

算法实现

基本思路上面都介绍了,细节就是每次探索节点时,都选择当前未探索过的到源点距离最短的节点,这样可以源点到当前点的路径已经是最短路径。

算法可视化

图的可视化比较复杂了,只是绘制出来其实不难,但要将节点、边进行合理布局就比较麻烦,是另一个话题了。

我选择用 vis.js 提供的 Network 来绘制图形,然后通过逐步执行算法来更新图形。

这是初始状态:

Dijkstra 算法 - 开始

执行过程中,会记录节点是否被访问,以及当前的最短路径和对应的距离:

Dijkstra 算法 - 执行中

全部执行完成后,就得到了源点开始到图中所有节点的最短路径:

Dijkstra 算法 - 完成

项目地址:luobotang/graph DEMO:Dijkstra 算法 - luobotang

项目的 Github Pages 配置有点问题,只能下载到本地之后再打开页面了。

结语

其实上面这些实现起来并没有特别困难,有很多现成的资料和代码可以利用。但是不管什么饭,都得自己吃过、消化过才是自己的。所以,我把自己吸收的“营养”记录下来,如果你也有兴趣,不妨自己上手一试。

最后,感谢阅读!

原文链接:https://segmentfault.com/a/1190000016768944

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-43386.html

文章标题:图形算法可视化

相关文章
IoT实时数据可视化方案(进阶版):Worldmap Panel使用详解及使用Node-RED进行流程管理
Chap.1 万万没想到,我这一世英名葬送在了地图坑里 继上次搭建完框架得到了个粗糙的demo以后,我天真地以为我离真理的距离简直就只有一步之遥了。基本的图形组件试了个遍没什么。 想着我还有些模拟的地理数据没有做可视化,数据信息的内容放...
2018-01-03
JavaScript中数据结构与算法(二):队列
队列是只允许在一端进行插入操作,另一个进行删除操作的线性表,队列是一种先进先出(First-In-First-Out,FIFO)的数据结构 队列在程序程序设计中用的非常的频繁,因为javascript单线程,所以导致了任何一个时间段只能执行...
2017-03-25
IoT实时数据可视化方案:Grafana+InfluxDB+Telegraf+MQTT协议+Windows 10
为什么写这篇博客? 最近被论文折磨的死去活来,实时数据可视化方案是我论文的题目。 每天都被这些技术玩弄于股掌之间,靠看文档延续生命和出成果。不得不说,做完这个论文可能以后不敢乱写readme了。 由此大胆推测大家的发量问题有都是看文档时产...
2017-12-24
JavaScript实现最简单的冒泡排序算法
冒泡排序可谓是最经典的排序算法了,它是基于比较的排序算法,时间复杂度为O(n^2),其优点是实现简单,n较小时性能较好。 1)算法原理 相邻的数据进行两两比较,小数放在前面,大数放在后面,这样一趟下来,最小的数就被排在了第一位,第二趟也是如...
2017-03-17
js实现日历的简单算法
最近有用到日历可需要编辑文本的日历,为了绑定数据的方便,所以用js写了一套日历,其实思想也是很简单。 实现步骤如下: 1、首先取得处理月的总天数 JS不提供此参数,我们需要计算。考虑到闰年问题会影响二月份的天数,我们先编写一个判断闰年的自编...
2017-02-17
javascript算法题:求任意一个1-9位不重复的N位数在该组合中的大小排列序号
具体题目是这样的: 从19中选取N个数字,组成不重复的N位数,从小到大进行编号,当输入其中任何一个数M时,能找出该数字对应 的编号。如 N=3,M=213. 输出:[123(1) , 132(2) , 213(3) , 231(4...
2017-03-22
JavaScript 性能优化之算法和流程控制
循环处理是最常见的编程模式之一,也是提升性能必须关注的要点之一。 常见的优化方案有: ①JavaScript的四种循环(for、do-while、while、for-in)中,for-in循环比其他几种明显要慢。由于每次迭代操作会同时搜索实...
2017-03-17
JavaScript实现的encode64加密算法实例分析
本文实例讲述了JavaScript实现的encode64加密算法。分享给大家供大家参考。具体如下: 这段JavaScript代码可实现encode64加密算法,速度还是相当不错的。 &#x2F;&#x2F;encode64编解码 (func...
2017-03-22
JavaScript常见算法详解
阅读目录 冒泡排序 插入排序 希尔排序 归并排序 快速排序 选择排序 奇偶排序 总结 前言:在前端大全中看到这句话,以此共勉。基础决定你可能达到的高度, 而业务决定了你的最低瓶颈 其实javascript算法在平时的编码中用处不大,不过...
2017-03-15
LeetCode 算法题刷题心得(JavaScript)
花了十几天,把《算法》看了一遍然后重新 AC 了一遍 LeetCode 的题,收获颇丰。这次好好记录下心得。 我把所有做题的代码都放在 github 上以供参考。 项目地址:github.com/violetjack/… 题目地址: le...
2018-05-10
回到顶部