寻路算法小游戏
寻路算法小demo
寻路算法有两种，一种是dfs 深度优先算法，一种是
dfs 深度优先算法
深度优先搜索的步骤分为 1.递归下去 2.回溯上来。顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标。这里称之为递归下去。
否则既没有达到目标又无路可走了，那么则退回到上一步的状态，走其他路。这便是回溯上来。
bfs 广度优先搜索
广度优先搜索较之深度优先搜索之不同在于，深度优先搜索旨在不管有多少条岔路，先一条路走到底，不成功就返回上一个路口然后就选择下一条岔路，而广度优先搜索旨在面临一个路口时，把所有的岔路口都记下来，然后选择其中一个进入，然后将它的分路情况记录下来，然后再返回来进入另外一个岔路，并重复这样的操作。
数据结构上的运用
DFS用递归的形式，用到了栈结构，先进后出。
BFS选取状态用队列的形式，先进先出。
<html><head><title>寻路算法</title>
</head><body><div class="body"><div class="body-content1"><div class="dfs-title">寻路算法</div><div id="dfs-content" class="dfs-cell"></div><div id="btn-list"><div id="btn-start-dfs" class="btn-start">dfs</div><div id="btn-start-bfs" class="btn-start">bfs</div><div id="btn-reset">重置</div></div></div><div class="body-content2"><div class="dfs-title">.</div><div class="start-point point">开始坐标：<input id="start-point-x" type="number" placeholder="行" /><input id="start-point-y" type="number" placeholder="列" /></div><div class="target-point point">终点坐标：<input id="target-point-x" type="number" placeholder="行" /><input id="target-point-y" type="number" placeholder="列" /></div></div></div>
</body>
<script>let count = 0; //步数计数//迷宫地图let map = [[0, 0, 1, 0, 0, 0, 0, 0],[0, 0, 0, 0, 1, 0, 0, 0],[1, 0, 0, 0, 0, 1, 0, 0],[0, 0, 0, 0, 1, 0, 1, 0],[1, 0, 0, 0, 1, 0, 0, 0],[0, 0, 1, 0, 1, 0, 0, 0],[0, 1, 0, 0, 1, 1, 0, 1],[0, 0, 1, 1, 1, 0, 0, 0],[0, 0, 1, 0, 0, 0, 0, 0],[0, 0, 0, 0, 1, 0, 0, 0],[1, 0, 0, 0, 0, 1, 0, 0],[0, 0, 0, 0, 1, 0, 1, 0],[1, 0, 0, 0, 1, 0, 0, 0],[0, 0, 1, 0, 1, 0, 0, 0],[0, 1, 0, 0, 1, 1, 0, 1],[0, 0, 1, 1, 1, 0, 0, 0],];let cellSize = 20; //px单元格大小let startX = 0, //开始坐标startY = 0;let targetX = 15, //结束坐标targetY = 7;let canFind = false;//遍历方向let dx = [0, 1, 0, -1],dy = [1, 0, -1, 0];let flag = new Array(map.length); //dfs标记走过的路径for (let i = 0; i < flag.length; i++) {flag[i] = new Array(map[i].length).fill(false);}//能否到达let findFlag = false;let step = new Array(map.length); //bfs标记走过的路径for (let i = 0; i < step.length; i++) {step[i] = new Array(map[i].length).fill(Infinity);}//单元格点击事件function cellClick(e) {let wFlag = 0;let classList = [...e.classList];if (classList.includes("now-in")) return;if (classList.includes("wall")) {e.classList.remove("wall");e.classList.add("space");} else if (classList.includes("space")) {e.classList.remove("space");e.classList.add("wall");wFlag = 1;}let id = e.id.split("-");let x = id[2],y = id[3];map[x][y] = wFlag;// console.log(map[x][y], x, y);}//初始化页面function init() {initPage();initData();}function initData() {const startPointX = document.getElementById("start-point-x");const startPointY = document.getElementById("start-point-y");const targetPointX = document.getElementById("target-point-x");const targetPointY = document.getElementById("target-point-y");startPointX.value = startX;startPointY.value = startY;targetPointX.value = targetX;targetPointY.value = targetY;startPointX.addEventListener("change", (e) => {if (e.target.value < 0 ||e.target.value >= map.length ||map[e.target.value][startY] == 1) {alert("非法坐标，请重新输入");startPointX.value = startX;return;}startX = parseInt(e.target.value);initPage();});startPointY.addEventListener("change", (e) => {if (e.target.value < 0 ||e.target.value >= map[0].length ||map[startX][e.target.value] == 1) {alert("非法坐标，请重新输入");startPointY.value = startY;return;}startY = parseInt(e.target.value);initPage();});targetPointX.addEventListener("change", (e) => {if (e.target.value < 0 ||e.target.value >= map.length ||map[e.target.value][targetY] == 1) {alert("非法坐标，请重新输入");targetPointX.value = targetX;return;}targetX = parseInt(e.target.value);initPage();});targetPointY.addEventListener("change", (e) => {if (e.target.value < 0 ||e.target.value >= map[0].length ||map[targetX][e.target.value] == 1) {alert("非法坐标，请重新输入");targetPointY.value = targetY;return;}targetY = parseInt(e.target.value);initPage();});}function initPage() {let innerHtml = ``;count = 0;findFlag = false;for (let i = 0; i < map.length; i++) {for (let j = 0; j < map[i].length; j++) {flag[i][j] = false;innerHtml += `<div id="${"dfs-id-" + i + "-" + j}" class="${map[i][j] == 0 ? "space" : "wall"} cell" style="width:${cellSize}px;height:${cellSize}px;" click="cellClick"></div>`;}}let dfsContent = document.getElementById("dfs-content");dfsContent.style.width = map[0].length * (cellSize + 2) + "px";dfsContent.innerHTML = innerHtml;let startCell = document.getElementById("dfs-id-" + startX + "-" + startY);startCell.classList.add("now-in");let targetCell = document.getElementById("dfs-id-" + targetX + "-" + targetY);targetCell.classList.add("target-in");let cell = document.getElementsByClassName("cell");for (let i = 0; i < cell.length; i++) {cell[i].addEventListener("click", () => {cellClick(cell[i]);});}}function dfs(x, y) {const dx = [1, 0, -1, 0],dy = [0, 1, 0, -1];if (x < 0 || y < 0 || x >= map.length || y >= map[0].length) return;if (map[x][y] == 1 || flag[x][y] || findFlag) return;let startCell = document.getElementById("dfs-id-" + x + "-" + y);startCell.classList.add("now-in");if (x == targetX && y == targetY) {findFlag = true;startCell.innerHTML = `<div style="font-size:small;text-align: center;">${count}</div>`;canFind = true;return;}for (let i = 0; i < 4 && !findFlag; i++) {flag[x][y] = true;startCell.innerHTML = `<div style="font-size:small;text-align: center;">${count}</div>`;count++;startCell.classList.add("pass");startCell.classList.remove("now-in");if (!findFlag) dfs(x + dx[i], y + dy[i]);if (!findFlag) flag[x][y] = false;if (!findFlag) startCell.innerHTML = "";if (!findFlag) count--;if (!findFlag) startCell.classList.remove("pass");}}function bfs() {let quene = [[startX, startY]];step[startX][startY] = 0;// console.log("开始bfs");let res = [];flag[startX][startY] = true;while (quene.length) {let p = quene.shift();res.push(p);let x = p[0],y = p[1];if (x == targetX && y == targetY) break;let f = false;for (let i = 0; i < 4; i++) {let nx = x + dx[i],ny = y + dy[i];if (nx < 0 || nx >= map.length || ny >= map[0].length || ny < 0) {continue;}if (map[nx][ny] == 1 || flag[nx][ny] == true) {continue;}flag[nx][ny] = true;step[nx][ny] = step[x][y] + 1;quene.push([nx, ny]);if (nx == targetX && ny == targetY) {f = true;canFind = true;break;}}if (f) break;}if (canFind) bfsDrawRoad();}//绘制路线function bfsDrawRoad() {let road = [[targetX, targetY]];while (road[0][0] != startX || road[0][1] != startY) {let x = road[0][0],y = road[0][1];for (let i = 0; i < 4; i++) {let nx = x + dx[i],ny = y + dy[i];if (nx < 0 || ny < 0 || nx >= step.length || ny >= step[0].length)continue;if (step[x][y] == step[nx][ny] + 1) {road.unshift([nx, ny]);break;}}}for (let i = 0; i < road.length; i++) {let startCell = document.getElementById("dfs-id-" + road[i][0] + "-" + road[i][1]);if (i != road.length - 1) {startCell.classList.add("pass");} else {startCell.classList.add("now-in");}startCell.innerHTML = `<div style="font-size:small;text-align: center;">${i}</div>`;}}//页面初始化init();//开始dfslet startBtnDfs = document.getElementById("btn-start-dfs");startBtnDfs.addEventListener("click", () => {canFind = false;init();dfs(startX, startY);// console.log(canFind);if (!canFind) alert("无法达到");});//开始bfslet startBtnBfs = document.getElementById("btn-start-bfs");startBtnBfs.addEventListener("click", () => {canFind = false;init();bfs();// console.log(canFind);if (!canFind) alert("无法达到");});//重置页面let resetBtn = document.getElementById("btn-reset");resetBtn.addEventListener("click", () => {init();});
</script>
<style>.body {display: flex;margin: auto;}.body-content1 {flex: 1;}.body-content2 {flex: 1;}.point {margin-top: 1rem;}.dfs-cell {display: flex;flex-wrap: wrap;margin: auto;}.dfs-cell>.cell {border: 1px solid gray;cursor: pointer;}.dfs-cell>.wall {background-color: black;}.now-in {background-color: yellow;}.target-in {background-color: rgb(245, 162, 9);}.pass {background-color: yellowgreen;}.dfs-title {text-align: center;margin: 2rem;}#btn-list {display: flex;justify-content: space-between;width: 20rem;margin: auto;}.btn-start {padding: 1rem;margin: auto;margin-top: 2rem;text-align: center;background-color: violet;width: 2rem;cursor: pointer;}#btn-reset {padding: 1rem;margin: auto;margin-top: 2rem;text-align: center;background-color: violet;width: 2rem;cursor: pointer;}
</style></html>
相关文章：
寻路算法小游戏
寻路算法小demo 寻路算法有两种，一种是dfs 深度优先算法，一种是 dfs 深度优先算法 深度优先搜索的步骤分为 1.递归下去 2.回溯上来。顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标。这…...
CSS基础 知识点总结
一.CSS简介 1.1 CSS简介 ① CSS指的是层叠样式表，用来控制网页外观的一门技术 ② CSS发展至今，经历过CSS1.0 CSS2.0 CSS2.1 CSS3.0这几个版本，CSS3.0是CSS最新版本 1.2 CSS引入方式 ① 在一个页面引入CSS，共有三种方式 外部…...
自动执行探索性数据分析 （EDA），更快、更轻松地理解数据
一、说明 EDA是 exploratory data analysis (探索性数据分析 )的缩写。所谓EDA就是在数据分析之前需要对数据进行以此系统性研判，在这个研判后，得到基本的数据先验知识，在这个基础上进行数据分析。本文将在R语言和python语言的探索性处理。 摄…...
【自定义系统服务】【android13】添加自定义java系统服务
背景 在平时的业务开发中，我们往往需要开发自定义的系统服务来处理自己特殊的需求，这里介绍的是添加自定义的Java系统服务，可以在系统App中直接调用 定义aidl Binder默认可以传输基本类型的数据，如果要传递类对象，则这个类需要实现序列化。我们先定义一个序列化的自定义…...
【Sklearn】基于随机梯度下降算法的数据分类预测（Excel可直接替换数据）
【Sklearn】基于随机梯度下降算法的数据分类预测（Excel可直接替换数据） 1.模型原理2.模型参数3.文件结构4.Excel数据5.下载地址6.完整代码7.运行结果1.模型原理 随机梯度下降（Stochastic Gradient Descent，SGD）是一种优化算法，用于训练模型的参数以最小化损失函数。在分…...
44、TCP报文（二）
接上节内容，本节我们继续TCP报文首部字段含义的学习。上节为止我们学习到“数据偏移”和“保留”字段。接下来我们学习后面的一些字段（暂不包含“检验和”的计算方法和选项字段）。 TCP首部结构（续） “数据偏移”和“保…...
目标检测（Object Detection）
文章目录 1. 目标检测1.1 目标检测简要概述及名词解释1.2 IOU1.3 TP TN FP FN1.4 precision（精确度）和recall（召回率） 2. 边框回归Bounding-Box regression3. Faster R-CNN3.1 Faster-RCNN：conv layer3.2 Faster-RCNN&…...
vue中实现文字检索时候将搜索内容标红
实现结果 html： <div class"searchBox"><span class"bt">标  题</span><div class"search"><div class"shuru"><!-- <span class"title">生产经营<…...
PCL protocol composition logic
PCL 协议组合逻辑 一 主体（principal）和线程（thread）的区分 1.主体：指 **协议的参与者，用X^来表示。**每个主体可以扮演一个或多个角色，如 InitCR和RespCR ； 2.线程：主…...
聊聊看React和Vue的区别
Vue 更适合小项目，React 更适合大公司大项目； Vue 的学习成本较低，很容易上手，但项目质量不能保证...... 真的是这样吗？借助本篇文章，我们来从一些方面的比较来客观的去看这个问题。 论文档的丰富性 从两个…...
OSPF在广播类型的网络拓扑中DR和BDR的选举
指定路由器（DR）： 一个网段上的其他路由器都和指定路由器（DR）构成邻接关系，而不是它们互相之间构成邻接关系。 备份指定路由器（BDR）： 当DR出现问题，由BDR接…...
系统学习Linux-Mariadb高可用MHA
概念 MHA（MasterHigh Availability）是一套优秀的MySQL高可用环境下故障切换和主从复制的软件。 MHA 的出现就是解决MySQL 单点的问题。 MySQL故障切换过程中，MHA能做到0-30秒内自动完成故障切换操作。 MHA能在故障切换的过程中最大程度上…...
慢SQL的原因
如何排查慢SQL问题 识别慢SQL：使用数据库性能监控工具，如慢SQL日志，识别耗时较长的查询。执行计划分析：使用数据库提供的分析工具，例如EXPLAIN来查看查询的执行计划，判断是否存在全表扫描，索引…...
php正则替换文章的图片
要使用正则表达式替换文章中的图片链接，可以按照以下步骤进行操作： 1. 获取文章内容：首先，你需要获取包含图片链接的文章内容。你可以从文件中读取文章，或者从数据库中检索文章内容。 2. 使用正则表达式匹配图片链接…...
57 | TAPTAP客户端分析
TAPTAP客户端分析 一、用户群分析 首先，TapTap用户群可分为三大类： 游戏爱好者游戏发烧者游戏开发者（次要用户，有开发者后台，可以显示数据，不重点分析）注：爱好者与发烧者区别在于，前者是用空余时间来玩游戏，时间不如后者充足，且后者更执着于游戏，游戏种类更多。 …...
开源了一套基于springboot+vue+uniapp的商城，包含分类、sku、商户管理、分销、会员、适合企业或个人二次开发
RuoYi-Mall-JAVA商城-电商系统简介 开源了一套基于若依框架，SringBoot2MybatisPlusSpringSecurityjwtredisVueUniapp的前后端分离的商城系统， 包含分类、sku、商户管理、分销、会员、适合企业或个人二次开发。 前端采用Vue、Element UI（ant…...
Android进阶之多级列表
遇到一个需求需要显示多级列表，因为界面是在平板上的，所以层级是从左向右往下排的，类似于 我当时的写法是在xml布局里一个个RecyclerView往下排的 当然前提是已经规定好最大的层级我才敢如此去写界面，如果已经明确规定只有两级或…...
Stochastic: Distribution-Expectation-Inequalities
见：https://www.math.hkust.edu.hk/~makchen/MATH5411/Chap1Sec2.pdf...
Java算法_ 二叉树的最大深度(LeetCode_Hot100)
题目描述：给定一个二叉树 ，返回其最大深度。root 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 获得更多？算法思路:代码文档，算法解析的私得。 运行效果 完整代码 /*** 2 * Author: LJJ* 3 * Date: 2023/…...
行业追踪，2023-08-18
自动复盘 2023-08-18 凡所有相，皆是虚妄。若见诸相非相，即见如来。 k 线图是最好的老师，每天持续发布板块的rps排名，追踪板块，板块来开仓，板块去清仓，丢弃自以为是的想法，板块去留让…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板，载入页面后，会显示引导弹窗，适用于引导用户使用页面，点击完成后，会显示下一个引导弹窗，直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包：import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序（自然排序和定制排序）Arrays.binarySearch()通过二分搜索法进行查找（前提：数组是…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装；只需暴露 19530（gRPC）与 9091（HTTP/WebUI）两个端口，即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
论文解读：交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架（一）
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读：交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架（一） 论文解读：交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上，所以报错，到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本，cu、torch、cp 的版本一定要对…...
VM虚拟机网络配置（ubuntu24桥接模式）：配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式，然后找到相应的网卡（可以查看自己本机的网络连接） windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置，选择刚才配置的桥接模式 静态ip设置： 我用的ubuntu24桌…...
【MATLAB代码】基于最大相关熵准则（MCC）的三维鲁棒卡尔曼滤波算法（MCC-KF），附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则（MCC）的三维鲁棒卡尔曼滤波算法（MCC-KF），针对传感器观测数据中存在的脉冲型异常噪声问题，通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现，验证了后者在状态估计鲁棒性方面的显著优…...
R 语言科研绘图第 55 期 --- 网络图-聚类
在发表科研论文的过程中，科研绘图是必不可少的，一张好看的图形会是文章很大的加分项。 为了便于使用，本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中，获取方式： R 语言科研绘图模板 --- sciRplothttps://mp.…...
在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率：以冒泡排序为例
目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码：冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...
yaml读取写入常见错误 (‘cannot represent an object‘, 117)
错误一：yaml.representer.RepresenterError: (‘cannot represent an object’, 117) 出现这个问题一直没找到原因，后面把yaml.safe_dump直接替换成yaml.dump，确实能保存，但出现乱码： 放弃yaml.dump，又切…...