当前位置: 首页 > 科技观察

Openharmony军棋工程师寻路算法实现

时间:2023-03-14 10:21:12 科技观察

了解更多开源请访问:开源基础软件社区https://ost.51cto.com1.简介Engineer你可以在铁路线上任意行走。其他棋子在铁路线上只能直行或通过弧线,不能直角转弯。工程师像走普通路线的其他棋子一样走一格。但在轨道上,就像进入了无人区。可以在轨道上自由移动,只要不超过轨道面积,想走多远就走多远,但是如果有棋子(无论是敌是友)挡住了路线,你不能走那条路;同时我们还要找到最近的路径。二、算法分析总体要求1、工程师在从起点到终点的过程中不得被障碍物阻挡。2.如何找到最短路径?以及是否需要最快的时间。3、也有可能起点到终点是死胡同。军旗的工兵运动特别像迷宫运动。迷宫算法1.深度优先搜索(DFS)与递归检测思路基本相同,可以看作是递归方法的非递归版本。2.广度优先搜索(BFS)广度优先搜索方法利用队列的特点,逐层向外扩展,寻找可以走的方格,直到找到出口。首先找到的答案必须是最短的。3.根据特性,我们希望先找到最短的距离,所以采用bfs的方法。队列用于记录检测点;当前检测点的四个方向,可以通过的点保存在这个队列中,当前检测点被移除。从右下左上四个方向探查。使用二维数组存储x、y和检测到的点上的障碍物。letnoChessBoard:number[][]=[//a[j][h]代表j行h列数据//1,row:row2,column:columnexportconstROW=12exportconstCOLUMN=4[1,1,1,1,1],[0,0,0,0,0],[0,1,1,1,0],[0,1,1,1,0],[0,1,1,1,0],[0,0,0,0,0],[0,1,0,1,0],[0,0,0,0,0],[0,1,1,1,0],[0,1,1,1,0],[0,1,1,1,0],[0,0,0,0,0],[1,1,1,1,1]]代码实现(1)获取起点和终点的坐标。this.routeNode=this.engineerRoute(firstChess,moveChess);(2)获取迷宫标记的二维数组。二维数组就是在棋盘上记录0表示可以通过的状态,1表示不可到达的状态。默认是所有的棋盘铁轨都是0,可以通行。然后,敌方和友方都设置为Impassable1。//工程师路线搜索(bfs广度优先搜索)privateengineerRoute(start:Chess,end:Chess):RouteNode{letnoChessBoard:number[][]=[//a[j][h]代表第j行第j列h数据//1,行:第2行,列:列exportconstROW=12exportconstCOLUMN=4[1,1,1,1,1],[0,0,0,0,0],[0,1,1,1,0],[0,1,1,1,0],[0,1,1,1,0],[0,0,0,0,0],[0,1,0,1,0],[0,0,0,0,0],[0,1,1,1,0],[0,1,1,1,0],[0,1,1,1,0],[0,0,0,0,0],[1,1,1,1,1]]for(leti=0;i=0&&tx<=COLUMN&&ty>=0&&ty<=ROW&&roads[ty][tx]===0){//如果位置可以走//EnqueueLogger.d(TAG,`bfsaddtx:${tx}ty:${ty}`)lettemp=newRouteNode(tx,ty,node.step+1)temp.prev=noderouteQueue.push(temp)Logger.d(TAG,`bfsscanpush:${JSON.stringify(routeQueue)}`)roads[ty][tx]=1}}//展开后Logger.d(TAG,`bfsscanoneend...`)}returnnull}(4)本例也记录路径,使用链表数据structure每次都记录prev。现在可以追溯到整个完整的检测路线。导出类RouteNode扩展点{prev:RouteNode;//上一个节点下一个:RouteNode;//下一个节点步骤:numberconstructor(x:number,y:number,step:number){super(x,y)this.step=step}}(5)使用数组改变队列。Openharmony目前Deque和Queue有bug,无法使用;只能使用数组,如果数组的pop是最后一个,检测序列会插入到第一个。exportclassMyArrayQueue{nodes:RouteNode[]constructor(){this.nodes=newArray}push(node:RouteNode){Logger.d(TAG,`push...:${JSON.stringify(node)}`)复制代码this.nodes.unshift(node)Logger.d(TAG,`pushend.:${JSON.stringify(this.nodes.length)}`)}pop():RouteNode{returnthis.nodes.pop()}size(){returnthis.nodes.length}}第三,综上所述,直接复制代码可能不行。这篇文章也阐述了一种思路,同时也体现了openharmony的目的和能力所达到的程度。了解更多开源请访问:开源基础软件社区https://ost.51cto.com