a星算法的原理，网络上基本都有，这里就不在介绍了，网络上的a星和例子结合的过于密切，不利于复用，如果你只需要代码，不需要了解原理，此文会对你有帮助
图片见附件,代码如下：
window.AStar = {};
(function(aStar){
//start:起始节点[i,j] ， end:最终节点[i,j] map:地图数据(2d)arr，marker:可以通过的标识（例子用的是1）
aStar.find_path = function(start,end,map,marker){
var open = [];
var close = [];
var s_p = start;
var e_p = end;
var map_arr = map;
var tra_marker = marker;
var G = 0;
var H = 0;
var F = 0;
//加入起始节点 [x, y , G ,F ,father]
open.push([s_p[0],s_p[1],0,(Math.abs(e_p[0]-s_p[0]) + Math.abs(e_p[1]-s_p[1])),null]);
return function(obj){
//重拍，取最小的一个
var count = 0;
for(var i = obj[0]-1,ilen = i+3 ; i < ilen ; i++){
for(var j = obj[1]-1,jlen = j+3 ;j < jlen; j++){
//遍历周围八节点,排除自己
if(i == obj[0] && j == obj[1])
continue;
//排除穿越的情况
if(!((i == obj[0] ) || ( j == obj[1])) && ( map_arr[i] && map_arr[obj[0]] && map_arr[i][obj[1]] != tra_marker && map_arr[obj[0]][j] != tra_marker))
continue;
if(i == e_p[0] && j == e_p[1]){
open.push([i,j,G,F,obj]);
var ways = [];
var ele = obj;
do{
ways.unshift(ele);
ele = ele[4];
}while(ele[4] != null);
return ways;
}
if(map_arr[i] && map_arr[i][j] && map_arr[i][j] == tra_marker && is_exist(open,[i,j]) == -1 && is_exist(close,[i,j]) == -1){
G = ( i == obj[0] ) || ( j == obj[1] ) ? obj[2]+1.0 : obj[2]+1.4 ;
H = Math.sqrt((e_p[0] - i)*(e_p[0] - i) + (e_p[1] - j)*(e_p[1] - j));
F = G + H;
open.push([i,j,G,F,obj]);
count++;
}
}
}
close.push(open.shift());
var o;
if(open[0] && open[0][4] == obj[4]){
o = count == 0 ? get_other(open,obj) : (arr_sort(open),open[0]);
}else{
o = (arr_sort(open),open[0]);
}
if(o){
return arguments.callee(o);
}else{
return [];
}
}(open[0])
}
//获取其他节点
var get_other = function(arr,o){
var a = [];
for(var i = 0 ; i < arr.length ; i++){
if(o && arr[i][4] == o[4]){
return arr[i];
}
}
if(o[4]){
return arguments.callee(o[4]);
}else{
return null;
}
}
//对数组进行重排列
var arr_sort = function(){
function s(a,b){
return a[3] - b[3];
}
return function(arr){
arr.sort(s);
}
}();
//数组中是否存在此元素
var is_exist = function(arr,p){
for(var i = 0 ; i < arr.length ; i++){
if(arr[i][0] == p[0] && arr[i][1] == p[1]){
return i;
}
}
return -1;
}
})(window.AStar)
测试代码
<script src="a_star.js"></script>
<link rel="stylesheet" type="text/css" href="reset.css" />
<script>
var state = 1;
var w = 20;
var h = 10;
var map_arr = [];
var start,end;
window.onload = function(){
var map = document.getElementById("map");
var arr = [];
arr.push("<table border=\"1\">");
for(var i = 0 ; i < h ; i++){
arr.push("<tr>");
if(!map_arr[i]) map_arr[i] = [];
for(var j = 0 ; j < w ;j++){
arr.push("<td id=\""+i+"-"+j+"\" style=\"width:50px;height:50px;border:1px solid #000\" onclick=\"td(" + i + "," + j + ")\"></td>");
map_arr[i][j] = 1;
}
arr.push("</tr>");
}
arr.push("</table>");
map.innerHTML = arr.join("");
}
function td(x,y){
var e = document.getElementById( x + "-" + y);
switch(state){
case 1:
start = [x,y];
e.style.backgroundColor = "#0f0";
break;
case 2:
end = [x,y];
e.style.backgroundColor = "#f00";
break;
case 3:
e.style.backgroundColor = "#000";
map_arr[x][y] = 0;
break;
}
}
function changeS(value){
state = value;
}
function find_path(){
var ways = AStar.find_path(start,end,map_arr,1);
if(ways.length == 0 ){
alert("no ways!~~~");
return ;
}
for(var i = 0;i < ways.length; i++){
var e = document.getElementById(ways[i][0]+"-"+ways[i][1]);
e.style.backgroundColor = "#00f";
}
}
</script>
<body>
<div id="map"></div>
<input type="button" onclick="changeS(1);" value="添加起始"/>
<input type="button" onclick="changeS(2);" value="添加终点" />
<input type="button" onclick="changeS(3);" value="添加障碍物" />
<input type="button" onclick="find_path();" value="生成路径" />
</body>
分享到：
相关推荐
在压缩包中的"A星寻路"文件可能包含实现A星算法的具体代码示例，通过读取栅格地图数据，计算各个节点之间的路径成本，使用A星算法找到从起点到终点的最短路径。理解并掌握这些知识点，将有助于你在实际项目中实现...
### A星算法简介 A*（A星）算法是一种广泛应用于路径寻找和图遍历的算法，能够在图中寻找从起始节点到目标节点的最短路径。虽然A*算法对于初学者而言较为复杂，但一旦掌握其核心原理，就会发现其实质上是非常直观且...
下面将详细介绍A星算法的基本原理、实现步骤以及在JAVA中的应用。 1. A星算法的基本原理： A*算法的核心在于评估每个节点的F值，F值是G值（从起点到当前节点的实际代价）和H值（从当前节点到目标节点的预估代价）...
这个"A星算法DEMO"是一个使用Java编程语言实现的示例，开发工具为NetBeans 8.1。下面将详细介绍A星算法的基本原理以及如何在Java中实现它。 1. A星算法概述： A*算法是Dijkstra算法的一个扩展，它引入了启发式信息...
A星算法的核心思想是使用一个评估函数来指导搜索方向，这个函数通常由两部分组成：g(n)表示从起点到当前节点的实际代价，h(n)是从当前节点到目标节点的启发式估计代价。综合这两个部分，我们得到f(n) = g(n) + h(n)...
A星（A*）算法是一种在图形搜索中广泛使用的路径规划算法，它的主要目标是找到从起点到终点的最短路径。A*算法结合了Dijkstra算法的全局最优性和贪婪最佳优先搜索算法的效率，通过引入启发式函数来指导搜索过程，...
A星算法结合了最佳优先搜索（BFS）和Dijkstra算法的优点，通过引入启发式函数来提高搜索效率。 A星算法的核心包括以下几个关键部分： 1. **开放列表（Open List）**：这是一个优先级队列，存储待检查的节点，根据F...
A星（A*）算法是一种在图形搜索中广泛使用的路径规划算法，它的主要目标是找到从起点到终点的最短路径。A*算法结合了Dijkstra算法的全局最优性和最佳优先搜索的效率，通过引入启发式函数来指导搜索，使得算法能够更...
A星算法简单的实现，分别使用C#、Python、JavaScript三种语言实现，通过界面10x10方格展示算法过程 思路参考于：https://blog.csdn.net/zhanghow/article/details/53585286
基于MATLAB的A星算法源码基于MATLAB的A星算法源码基于MATLAB的A星算法源码基于MATLAB的A星算法源码基于MATLAB的A星算法源码基于MATLAB的A星算法源码基于MATLAB的A星算法源码基于MATLAB的A星算法源码基于MATLAB的A星...
1. **A星算法**：A星算法的核心在于维护一个优先级队列，其中包含当前可能的最短路径节点。每个节点有一个评估函数值`f(n) = g(n) + h(n)`，`g(n)`表示从起点到当前节点的实际代价，`h(n)`是启发式估计从当前节点到...
本压缩包“易语言源码易语言A星算法源码.rar”提供了易语言实现的A星(A*)寻路算法的源代码，这对于想要了解或学习A*算法以及易语言编程的人来说是一份宝贵的资源。 A星算法是路径搜索领域中的一种非常高效的算法，...
在压缩包文件"A星算法.Q"中，可能包含了实现易语言A星算法的源代码示例，你可以通过阅读和分析代码来进一步理解其具体实现细节。此外，学习和理解A星算法的过程中，可以参考相关编程书籍、在线教程和开源项目，以便...
A星算法的核心思想是找到从起点到目标点的最小代价路径。它使用一个开放列表和一个关闭列表来存储节点。开放列表包含待检查的节点，而关闭列表则存储已检查过的节点。算法的主要步骤如下： 1. 初始化：将起点放入...
A*（发音为 "A-star"）算法是一种在图形搜索中广泛应用的路径寻找算法，它结合了Dijkstra算法和最佳优先搜索，旨在找到从起点到目标点的最短路径。A*算法以其效率和准确性而著名，特别是在游戏、地图导航和机器人...
A星算法的核心在于结合了Dijkstra算法的全局最优性和最佳优先搜索的效率。它使用一个优先队列来存储待评估的节点，根据每个节点的评估函数值F进行排序。F值由两部分组成：G值（从起点到当前节点的实际成本）和H值...
A星算法(A* Search Algorithm)是路径搜索领域中一种经典的启发式搜索算法，因其高效性和准确性而被广泛应用。这个名为"A星算法大全"的资源显然提供了深入学习和理解A星算法的全面教程，对于想在游戏中实现智能路径...
在这个"A星算法演示"项目中，我们可以通过MFC（Microsoft Foundation Classes）窗口程序来直观地理解并学习A星算法。MFC是微软提供的一种C++库，用于构建Windows应用程序，它简化了窗口、菜单、控件等元素的创建和...
2.内容：基于Qlearning算法最优路径规划算法matlab仿真,同时使用A星算法进行对比+代码操作视频 3.用处：用于Qlearning算法，A星算法编程学习 4.指向人群：本硕博等教研学习使用 5.运行注意事项： 使用matlab...