집 > 기사 > 웹 프론트엔드 > JavaScript를 사용하여 웹 페이지에 8자리 휴리스틱 A* 알고리즘 애니메이션 효과를 구현하는 그래픽 및 텍스트 코드 소개

JavaScript를 사용하여 웹 페이지에 8자리 휴리스틱 A* 알고리즘 애니메이션 효과를 구현하는 그래픽 및 텍스트 코드 소개

黄舟원래의: 2017-04-18 09:49:583253검색

이 글에서는 주로 JavaScript를 사용하여 8자리 휴리스틱 A* 알고리즘 애니메이션 효과를 웹 페이지에 구현하는 방법을 소개합니다. 필요한 친구는

최근 인위적인 스마트클래스 선생님께서 8자리 실험을 준비하셨는데요. 인터넷에서 8자리 휴리스틱 A* 알고리즘을 많이 보았으나 대부분 C나 C++를 사용하여 콘솔에서 구현한 것이었기 때문에

js를 웹페이지에 구현하기 위해 .

먼저 8자리 숫자는 9개의 정사각형 격자 안에 공백이 하나 있고 나머지 8개의 해당 숫자는 1~8입니다.

다음과 같이 마지막

상태 가 정렬되도록 공백을 이동합니다.

휴리스틱 알고리즘은 휴리스틱

을 사용하는 것을 말합니다. 문제의 풀이 공간을 줄이기 위해 제거할 때 규칙을 따르지 않는 풀이 노드를 제거하는 함수가 있습니다.

A* 알고리즘은 평가 함수를 사용하는 휴리스틱 알고리즘입니다. 이 예에서는 현재 노드 상태와 최종 노드 상태가 다른 그리드 수를 사용하여 노드의 품질을 평가합니다. 상위 노드는 저장되었다가 나중에 하위 노드를 확장하고 폐기합니다.

이를 달성하려면 먼저 그림과 같이 html에 9개의 입력 텍스트 상자를 추가하세요.

그림은 디지털 그리드

페이지 코드는

<!DOCTYPE html>
<html lang="en">
<head>
 <meta charset="UTF-8">
 <title>八数码</title>
 <style type="text/css">
 #result input{
  display: inline-block;
  font-family:"微软雅黑";
  font-size: 60px;
  font-weight: 900;
  text-align: center;
  width:100px;
  height:100px;
  background:url(images/0.png);
  background-size:cover;
 }
</style>
</head>
<body>
 <p id="result">
  <input type="text" id="r1">
  <input type="text" id="r2">
  <input type="text" id="r3"><br>
  <input type="text" id="r4">
  <input type="text" id="r5">
  <input type="text" id="r6"><br>
  <input type="text" id="r7">
  <input type="text" id="r8">
  <input type="text" id="r9"><br>
 </p>
 <button onclick="run()">求解</button>
</body>
</html>

이고 javascript를 사용하여 입력값을 가져와서

2차원 배열

var startArray=[[8,1,3],[0,2,4],[7,6,5]];//初始化八数码数组
   //获取输入的初始状态
   var cpic=1;
   for(var i=0;i<N;i++){
    for(var j=0;j<N;j++){
     var rid=&#39;r&#39;+cpic++;
     var inputValue=getId(rid).value;
     if(inputValue==""){inputValue=0;}
     startArray[i][j]=parseInt(inputValue);
     getId(rid).value="";
    }
   }
var startGraph=new Graph(startArray);
var endArray=[[ 1,2,3],[ 8,0,4 ],[ 7,6,5 ]];
var endGraph=new Graph(endArray);//目标节点
evaluateGraph(startGraph,endGraph);
showGraph(startGraph);

에 저장합니다. 그래프 클래스는 상태 노드 관련 데이터를 저장하는 데 사용됩니다:

//节点类
  var Graph = function(formData){
   this.form=formData;
   this.evalue=0;
   this.udirect=0;
   this.parent=null;
  };

showGraph() 함수를 구현하여 8자리 상태를 표시합니다.

function showGraph(graph) {
   var c=1;
   for(var i=0;i<N;i++){
    for(var j=0;j<N;j++){
     var s=&#39;r&#39;+c++;
     getId(s).style.backgroundImage="url(images/"+graph.form[i][j]+".png)";
    }
   }
  }

평가 함수를 사용하여 평가 그래프()를 평가합니다. 현재 노드와 대상 노드 사이의 간격 값

//评估函数
  function evaluateGraph(theGraph, endGraph){
   var differ = 0;//差距数
   for (var i = 0; i<N; i++)
   {
    for (var j = 0; j<N; j++)
    {
     if (theGraph.form[i][j] != endGraph.form[i][j]){differ++;}
    }
   }
   theGraph.evalue = differ;
   return differ;
  }

moveGraph() 함수를 사용하여 새 노드를 이동하고 반환합니다.

//移动数码组
  function moveGraph(theGraph, direct){
   var HasGetBlank = 0;//是否找到空格位置
   var AbleMove = 1;//是否可移动
   var i, j, t_i, t_j;
   //查找空格坐标i,j
   for (i = 0; i<N; i++)
   {
    for (j = 0; j<N; j++)
    {
     if (theGraph.form[i][j] == 0)
     {
      HasGetBlank = 1;
      break;
     }
    }
    if (HasGetBlank == 1)
     break;
   }
   t_i = i;
   t_j = j;
   //移动空格
   switch (direct)
   {
    case 1://上
     t_i--;
     if (t_i<0)
      AbleMove = 0;//移动超过边界
     break;
    case 2://下
     t_i++;
     if (t_i >= N)
      AbleMove = 0;
     break;
    case 3://左
     t_j--;
     if (t_j<0)
      AbleMove = 0;
     break;
    case 4://右
     t_j++;
     if (t_j >= N)
      AbleMove = 0;
     break;
   }
   //Direct方向不能移动，返回原节点
   if (AbleMove == 0)
   {
    return theGraph;
   }
   //向Direct方向移动，生成新节点
   var ta=[[0,0,0],[0,0,0],[0,0,0]];
   var New_graph = new Graph(ta);
   for (var x = 0; x<N; x++)//复制数码组
   {
    for (var y = 0; y<N; y++)
    {
     New_graph.form[x][y] = theGraph.form[x][y];
    }
   }
   //交换
   New_graph.form[i][j] = New_graph.form[t_i][t_j];//交换空格和移动方向上的数字
   New_graph.form[t_i][t_j] = 0;
   return New_graph;
  }

마지막으로

검색이 있습니다. 초기 노드부터 시작하여 대상 노드에 도달할 때까지 계층별로 아래쪽으로 검색하는 함수입니다. 하위 노드로 돌아가서 하위 노드부터 계층별로 상위 노드를 역추적하여 솔루션 경로를 찾습니다:

//搜索路径
  function Search(beginGraph, endGraph){
   var g1, g2, g;
   var Step = 0;//深度
   var Direct = 0;//方向
   var i;
   var front=-1,rear=-1;
   g1=beginGraph;//初始八数码节点
   while (g1)//队列不空,从close队列中拿出一个节点
   {
    for (i = 1; i <= 4; i++){//分别从四个方向推导出新子节点
     Direct = i;
     if (Direct == g1.udirect)
      continue;//跳过屏蔽方向
     g2=moveGraph(g1,Direct);
     if (evaluateGraph(g2,g1)!=0){//数码组是否可以移动
      evaluateGraph(g1,endGraph);
      evaluateGraph(g2,endGraph);//评价新的节点
      if (g2.evalue <= g1.evalue + 1)//利用评估值判断是否为优越节点
      { //若为优，将g2的父节点指向g1
       g2.parent = g1;
       //设置屏蔽方向，防止往回推
       switch (Direct){
        case 1://上
         g2.udirect = 2;
         break;
        case 2://下
         g2.udirect = 1;
         break;
        case 3://左
         g2.udirect = 4;
         break;
        case 4://右
         g2.udirect = 3;
         break;
       }
       Qu[++rear]=g2;//把优越节点放到close队列
       if (g2.evalue == 0)//为0则搜索完成
       {
        g = g2;
        break;
       }
      }
      else{g2 = null;}//抛弃劣质节点
     }
    }
    //搜索完成，继续退出
    if (typeof g !== &#39;undefined&#39;)
    {
     if (g.evalue == 0)
     {
      break;
     }
    }
    Step++;//统计深度
    if (Step>Max_Step){
     alert("超过搜索深度！");
     break;}
    g1=Qu[++front];//从close队列中拿出一个节点继续下一轮展开
   }
   return g;
  }

마지막으로 솔루션 경로 노드를 순서대로 스택에 푸시하고 매초마다 하나의 노드를 팝업하여 애니메이션을 표시하고 형성합니다.

var top=-1;
   var G;
   G = Search(startGraph, endGraph);
   //解序列存入堆栈
   var P=G;
   while (P != null)
   {
    top++;
    St[top] = P;
    P = P.parent;
   }
   //动画执行
   var si=setInterval(function () {
    if (top>-1)
    {
     showGraph(St[top]);
     top--;
    }else {
     clearInterval(si);
    }
   },1000);
  }

위 내용은 JavaScript를 사용하여 웹 페이지에 8자리 휴리스틱 A* 알고리즘 애니메이션 효과를 구현하는 그래픽 및 텍스트 코드 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명：

이전 기사：프론트엔드 실시간 검색 기능을 구현하기 위한 JavaScript용 코드 공유(그림)다음 기사：프론트엔드 실시간 검색 기능을 구현하기 위한 JavaScript용 코드 공유(그림)