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

집

웹 프론트엔드

JS 튜토리얼

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

黄舟

Apr 18, 2017 am 09:49 AM

이 글에서는 주로 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명

본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

관련 기사

JavaScript 데이터 유형 : 브라우저와 Nodejs 사이에 차이가 있습니까?May 14, 2025 am 12:15 AM

JavaScript 코어 데이터 유형은 브라우저 및 Node.js에서 일관되지만 추가 유형과 다르게 처리됩니다. 1) 글로벌 객체는 브라우저의 창이고 node.js의 글로벌입니다. 2) 이진 데이터를 처리하는 데 사용되는 Node.js의 고유 버퍼 객체. 3) 성능 및 시간 처리에는 차이가 있으며 환경에 따라 코드를 조정해야합니다.

JavaScript 댓글 : / / * * /사용 안내서May 13, 2025 pm 03:49 PM

javaScriptUSTWOTYPESOFSOFCOMMENTS : 단일 라인 (//) 및 multi-line (//)

Python vs. JavaScript : 개발자를위한 비교 분석May 09, 2025 am 12:22 AM

Python과 JavaScript의 주요 차이점은 유형 시스템 및 응용 프로그램 시나리오입니다. 1. Python은 과학 컴퓨팅 및 데이터 분석에 적합한 동적 유형을 사용합니다. 2. JavaScript는 약한 유형을 채택하며 프론트 엔드 및 풀 스택 개발에 널리 사용됩니다. 두 사람은 비동기 프로그래밍 및 성능 최적화에서 고유 한 장점을 가지고 있으며 선택할 때 프로젝트 요구 사항에 따라 결정해야합니다.

Python vs. JavaScript : 작업에 적합한 도구 선택May 08, 2025 am 12:10 AM

Python 또는 JavaScript를 선택할지 여부는 프로젝트 유형에 따라 다릅니다. 1) 데이터 과학 및 자동화 작업을 위해 Python을 선택하십시오. 2) 프론트 엔드 및 풀 스택 개발을 위해 JavaScript를 선택하십시오. Python은 데이터 처리 및 자동화 분야에서 강력한 라이브러리에 선호되는 반면 JavaScript는 웹 상호 작용 및 전체 스택 개발의 장점에 없어서는 안될 필수입니다.

파이썬 및 자바 스크립트 : 각각의 강점을 이해합니다May 06, 2025 am 12:15 AM

파이썬과 자바 스크립트는 각각 고유 한 장점이 있으며 선택은 프로젝트 요구와 개인 선호도에 따라 다릅니다. 1. Python은 간결한 구문으로 데이터 과학 및 백엔드 개발에 적합하지만 실행 속도가 느립니다. 2. JavaScript는 프론트 엔드 개발의 모든 곳에 있으며 강력한 비동기 프로그래밍 기능을 가지고 있습니다. node.js는 풀 스택 개발에 적합하지만 구문은 복잡하고 오류가 발생할 수 있습니다.

JavaScript의 핵심 : C 또는 C에 구축 되었습니까?May 05, 2025 am 12:07 AM

javaScriptisNotBuiltoncorc; it'SangretedLanguageThatrunsonOngineStenWrittenInc .1) javaScriptWasDesignEdasAlightweight, 해석 hanguageforwebbrowsers.2) Endinesevolvedfromsimpleplemporectreterstoccilpilers, 전기적으로 개선된다.

JavaScript 응용 프로그램 : 프론트 엔드에서 백엔드까지May 04, 2025 am 12:12 AM

JavaScript는 프론트 엔드 및 백엔드 개발에 사용할 수 있습니다. 프론트 엔드는 DOM 작업을 통해 사용자 경험을 향상시키고 백엔드는 Node.js를 통해 서버 작업을 처리합니다. 1. 프론트 엔드 예 : 웹 페이지 텍스트의 내용을 변경하십시오. 2. 백엔드 예제 : node.js 서버를 만듭니다.

Python vs. JavaScript : 어떤 언어를 배워야합니까?May 03, 2025 am 12:10 AM

Python 또는 JavaScript는 경력 개발, 학습 곡선 및 생태계를 기반으로해야합니다. 1) 경력 개발 : Python은 데이터 과학 및 백엔드 개발에 적합한 반면 JavaScript는 프론트 엔드 및 풀 스택 개발에 적합합니다. 2) 학습 곡선 : Python 구문은 간결하며 초보자에게 적합합니다. JavaScript Syntax는 유연합니다. 3) 생태계 : Python에는 풍부한 과학 컴퓨팅 라이브러리가 있으며 JavaScript는 강력한 프론트 엔드 프레임 워크를 가지고 있습니다.

See all articles