寻路算法小游戏
寻路算法小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排名，追踪板块，板块来开仓，板块去清仓，丢弃自以为是的想法，板块去留让…...
js将项目中的图片上传到服务器
项目上有时候会有奇怪的需求，比如前端有一些示例，想点击按钮就能上传图片，而这个图片是在前端的项目中的，如果不上传吧，又获取不到一些业务数据的id，但后端又不想为这块功能做特殊的处理，这时想通过前端直接上传到后端，需要file对象才可以。 这个时候我们需要将img转换…...
【C语言】指针的进阶
目录 一、字符指针 二、指针数组 三、数组指针 1.数组指针的定义 2.&数组名和数组名区别 3.数组指针的使用 四、数组参数与指针参数 1.一维数组传参 2.二维数组传参 3.一级指针传参 4.二级指针传参 五、函数指针 六、函数指针数组 七、指向函数指针数组的指针…...
【Windows系统编程】03.远线程注入ShellCode
shellcode：本质上也是一段普通的代码，只不过特殊的编程手法，可以在任意环境下，不依赖于原有的依赖库执行。 远程线程 #include <iostream> #include <windows.h> #include <TlHelp32.h>int main(){HANDLE hPr…...
第1天----验证一个字符串是否是另一个字符串的子串
本文我们将学习如何去验证一个字符串是否是另一个字符串的子串。 一、小试牛刀： 题目描述 输入两个字符串，验证其中一个串是否为另一个串的子串。 输入格式 两行，每行一个字符串。 输出格式 若第一个串 s 1 是第二个串 s 2 的子串，…...
项目实战第四十三讲：使用模版模式优雅实现财务编辑费用
项目实战第四十三讲：财务编辑费用 本文是项目实战第43讲：使用模版模式优雅实现财务编辑费用。支持查看司机填写费用信息，并且附件管理支持展示司机上传费用照片。 文章目录 项目实战第四十三讲：财务编辑费用1、项目背景2、主要技术3、项目职责4、项目实现4.1、表结构4.2、流…...
[JavaWeb]【六】web后端开发-请求响应
前言：请求响应 目录 一 引子 二 请求 2.1 Postman 2.1.1 安装 2.1.2 创建工作空间 2.1.3 添加接口 2.2 简单参数 2.2.1 原始方式（不推荐） 2.2.2 SpringBoot方式-GET(参数名与形参变量名相同) 2.2.3 SpringBoot方式-POST(参数名与形参…...
uniapp websocket机制 心跳 重连
在开发程序过程中通信功能还是比较常用到的，本文主要介绍的是uniapp中websocket的使用 websocket建立连接后，断开、心跳机制重新链接的一个过程。 关于uni.connectSocket可仔细阅读uniapp官网中的uni.connetSocket以及连接socket创建的实例SocketTask …...
labelme安装以及标注自己的目标检测数据集
目录 一、labelme安装指令 二、使用教程 三、 快捷键 一、labelme安装指令 winR之后在弹出的对话框中输入cmd按回车进入终端 conda activate 虚拟环境名称 pip install labelme -i https://pypi.tuna.tsinghua.edu.cn/simple/ 二、使用教程 安装成功之后在终端输入label…...
归并排序JS
当然，下面是使用JavaScript编写的归并排序的示例代码。归并排序是一种分治算法，其基本思想是将数组分成两半进行排序，然后将排序后的结果合并在一起。 function mergeSort(arr) {if (arr.length < 1) {return arr;}const middle Math.fl…...
matlab 计算点云平均密度
目录 一、算法原理二、代码实现三、结果展示四、C++版计算结果本文由CSDN点云侠原创，爬虫自重。如果你不是在点云侠的博客中看到该文章，那么此处便是不要脸的爬虫。 一、算法原理 采样设备不同、设备距离场景远近不同，会使点云密度产生差异。现有的对点云密度的估算方法有基…...