【记录】使用 JavaScript(Typescript) 实现AStar 寻路算法
2021/6/20 12:49:56
本文主要是介绍【记录】使用 JavaScript(Typescript) 实现AStar 寻路算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
再试着使用 JavaScript(Typescript) 实现AStar 寻路算法,在此记录一下。
export type CompareFn<T> = (a: T, b: T) => number; export function appendToOrderList<T>(orderList: T[], item: T, compare: CompareFn<T>) { if (orderList.length > 0) { if (compare(item, orderList[0]) <= 0) { orderList.splice(0, 0, item); } else { let index; for (index = 0; index < orderList.length - 1; index++) { let compareToPrev = compare(item, orderList[index]); let compareToNext = compare(item, orderList[index + 1]); if (compareToPrev >= 0 && compareToNext <= 0) { break; } } orderList.splice(index + 1, 0, item); } } else { orderList[0] = item; } } export type AStarPos = { row: number; col: number; step: number; // 0 searched: boolean; // false opened: boolean; // false closed: boolean; // false weight?: number; prev?: AStarPos; } export type AStarMap = AStarPos[][]; export const AStarConfig = { toStartWeight: 1, toEndWeight: 1 } export function findRoad(gameMap: boolean[][], startPos: [number, number], endPos: [number, number]) { // create astar map let aStarMap: AStarMap = []; gameMap.forEach((row, rowIndex) => { aStarMap[rowIndex] = []; row.forEach((col, colIndex) => { let aStarPos: AStarPos = { row: rowIndex, col: colIndex, step: 0, searched: false, // false opened: false, // false closed: !col, // false }; aStarMap[rowIndex][colIndex] = aStarPos; }); }); let aStarRoad = aStarFindRoad(aStarMap, startPos, endPos); return aStarRoad.map(aStarpos => [aStarpos.row, aStarpos.col]); } export function aStarFindRoad(map: AStarMap, [startRow, startCol]: [number, number], [endRow, endCol]: [number, number]) { let road: AStarPos[] = []; let openList: AStarPos[] = []; let testList: AStarPos[] = []; let startPos = map[startRow][startCol]; let endPos = map[endRow][endCol]; startPos.searched = true; startPos.opened = true; startPos.weight = calWeight(0, calDistance(startPos, endPos)); openList.push(startPos); let testPos = openList.shift(); while (testPos) { testPos.opened = false; testList.push(testPos); if (equalsPos(testPos, endPos)) { let roadPos: AStarPos | undefined = endPos; while (roadPos) { road.push(roadPos); roadPos = roadPos.prev; } return road.reverse(); } let notSearchedPosList = getNotSearchedPosList(map, testPos); if (notSearchedPosList.length > 0) { for (let index = 0; index < notSearchedPosList.length; index++) { let notSearchedPos = notSearchedPosList[index]; notSearchedPos.step = testPos.step + 1; notSearchedPos.weight = calWeight(notSearchedPos.step, calDistance(notSearchedPos, endPos)); notSearchedPos.prev = testPos; addToOpenList(openList, notSearchedPos); }; } else { testList.forEach(testPos => { testPos.closed = true; }); testList = []; } testPos = openList.shift(); } throw new Error("road not found"); } function calWeight(toStart: number, toEnd: number) { return AStarConfig.toStartWeight * toStart + AStarConfig.toEndWeight * toEnd; } function calDistance(pos0: AStarPos, pos1: AStarPos) { let dRow = pos0.row - pos1.row; let dCol = pos0.col - pos1.col; return Math.abs(dRow) + Math.abs(dCol); } function getNotSearchedPosList(map: AStarMap, pos: AStarPos) { let aroundPosList: [number, number][] = [ [pos.row + 1, pos.col], [pos.row - 1, pos.col], [pos.row, pos.col + 1], [pos.row, pos.col - 1], [pos.row + 1, pos.col + 1], [pos.row + 1, pos.col - 1], [pos.row - 1, pos.col + 1], [pos.row - 1, pos.col - 1], ]; let notSearchedPosList: AStarPos[] = []; aroundPosList.forEach(aroundPos => { let [row, col] = aroundPos; if ((row >= 0 && row < map.length) && (col >= 0 && col < map[row].length) && (!map[row][col].searched) && (!map[row][col].opened) && (!map[row][col].closed)) { map[row][col].searched = true; notSearchedPosList.push(map[row][col]); } }); return notSearchedPosList; } function addToOpenList(openList: AStarPos[], pos: AStarPos) { pos.opened = true; appendToOrderList(openList, pos, (pos0, pos1) => { if (pos0.weight !== undefined && pos1.weight !== undefined) { return pos0.weight - pos1.weight; } return 0; }); } function equalsPos(pos0: AStarPos, pos1: AStarPos) { return pos0.row === pos1.row && pos0.col === pos1.col; }
这篇关于【记录】使用 JavaScript(Typescript) 实现AStar 寻路算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)