寻路算法小游戏
寻路算法小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排名，追踪板块，板块来开仓，板块去清仓，丢弃自以为是的想法，板块去留让…...
多云管理“拦路虎”：深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言：多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时，基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套：跨云网络构建数据…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令： return <value>;在收到客户端连接后，立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量（如 $time_iso8601、$remote_addr 等）&a…...
＜6＞-MySQL表的增删查改
目录 一，create（创建表） 二，retrieve（查询表） 1，select列 2，where条件 三，update（更新表） 四，delete（删除表…...
Spring AI 入门：Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天，Spring AI 作为 Spring 生态系统的新生力量，正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务（如 OpenAI、Anthropic）的无缝对接&…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会，玩音乐的本质就是玩电网。火电声音偏暖，水电偏冷，风电偏空旷。至于太阳能发的电，则略显朦胧和单薄。 不知你是否有感觉，近两年家里的音响声音越来越冷，听起来越来越单薄？ —…...
快速排序算法改进:随机快排-荷兰国旗划分详解
随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...
k8s从入门到放弃之Pod的容器探针检测
k8s从入门到放弃之Pod的容器探针检测 在Kubernetes（简称K8s）中，容器探测是指kubelet对容器执行定期诊断的过程，以确保容器中的应用程序处于预期的状态。这些探测是保障应用健康和高可用性的重要机制。Kubernetes提供了两种种类型…...
PLC入门【4】基本指令2(SET RST)
04 基本指令2 PLC编程第四课基本指令(2) 1、运用上接课所学的基本指令完成个简单的实例编程。 2、学习SET--置位指令 3、RST--复位指令 打开软件(FX-TRN-BEG-C)，从 文件 - 主画面，“B: 让我们学习基本的”- “B-3.控制优先程序”。 点击“梯形图编辑”…...
SpringCloud优势
目录 完善的微服务支持 高可用性和容错性 灵活的配置管理 强大的服务网关 分布式追踪能力 丰富的社区生态 易于与其他技术栈集成 完善的微服务支持 Spring Cloud 提供了一整套工具和组件来支持微服务架构的开发，包括服务注册与发现、负载均衡、断路器、配置管理等功能…...
生产管理系统开发：专业软件开发公司的实践与思考
生产管理系统开发的关键点 在当前制造业智能化升级的转型背景下，生产管理系统开发正逐步成为企业优化生产流程的重要技术手段。不同行业、不同规模的企业在推进生产管理数字化转型过程中，面临的挑战存在显著差异。本文结合具体实践案例，分析…...