https://www.redblobgames.com/pathfinding/a-star/introduction.html #3

maiff · 2019-03-23T06:02:33Z

No description provided.

maiff · 2019-03-23T06:23:34Z

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8" />
  <title>Page Title</title>

  <style>
  #ul1 {
    margin: 30px auto;
    border: 1px solid black;
    border-bottom: none;
    border-right: none;
    padding: 0;
    height: auto;
    overflow: hidden;  
  }

  #ul1 li{
    list-style: none;
    border: 1px solid black;
    border-top: none;
    border-left:none;
    float: left;
  }

  #ul1 li.style1{
    /* start */
    background: red;
  }

  #ul1 li.style2{
    /* obstacle */
    background: black;
  }
  
  #ul1 li.style3{
    /* end */
    background: orange;
  }
  </style>
  
</head>
<body>

  <ul id="ul1">
  </ul>

  <center>
    <input type="button" value="start" id="btn" />
  </center>
  
</body>
<script>
  const aUl = document.getElementById('ul1')
  const aBtn = document.getElementById('btn')
  const openArr = []
  const closeArr = []
  const map = new Int8Array(400)
  map[0] = 1 // start

  map[399] = 3 //end
  const resultParent = []

  function init() {
    createMap();
    aBtn.onclick = function () {
      console.log('click')
      openFn();
    }
  }
  init()

  function getAllArray() {
    Lis = document.getElementsByTagName('li')
    beginLi = document.getElementsByClassName('style1')
    endLi = document.getElementsByClassName('style3')
  }

  
  function createMap() {
    //  aUl.innerHTML = ''
    //  openArr = []
    //  closeArr = []


    const liSize = 20;

    for(let i = 0; i < map.length; i++){
      let aLi = document.createElement('Li');
      aLi.style.width = liSize + 'px'
      aLi.style.height = liSize + 'px'
      aLi.dataset.index = i;
      aUl.appendChild(aLi)
      if(map[i] == 1){
        aLi.className = 'style1';
        openArr.push(aLi)
      }else if(map[i] == 2){
        aLi.className = 'style2';
        closeArr.push(aLi);
      }else if(map[i] ==3){
        aLi.className = 'style3';

      }

    }
    aUl.style.width = 20 * (liSize + 1) + 1 + 'px';
    getAllArray()
  }

  // 评估函数
  function fn(nowLi) {
    return g(nowLi) + h(nowLi)
  }
  function g(nowLi) {
    const a = nowLi.offsetLeft - beginLi[0].offsetLeft;
    const b = nowLi.offsetTop -beginLi[0].offsetTop;
    return a + b
  }
  function h(nowLi) {
    const a = nowLi.offsetLeft - endLi[0].offsetLeft;
    const b = nowLi.offsetTop -endLi[0].offsetTop;
    return Math.sqrt(a*a +b*b)
  }

  function showPath() {
    let lastLi = closeArr.pop();
    let iNow = 0;
    findParent(lastLi);

    const timer = setInterval(() => {
      resultParent[iNow].style.background = 'red';
      iNow++
      if(iNow == resultParent.length)
        clearInterval(timer)
    }, 500);
  }
  function findParent(li) {
    resultParent.unshift(li);
    if(li.parent == beginLi[0]) return
    findParent(li.parent);
  }

  function openFn(){
     console.log('openFn')
    let nodeLi = openArr.shift()
    if(nodeLi == endLi[0]){
      showPath()
      return
    }

    closeFn(nodeLi);
    findLi(nodeLi);

    openArr.sort((li1, li2) => {
      return li1.num - li2.num
    } )

    openFn()
  }
  
  function closeFn(nodeLi) {
    closeArr.push(nodeLi);
  }

  function findLi(nodeLi){
    const result = []

    for(let i = 0; i < Lis.length; i++){
      if( filter(Lis[i]) ){
        result.push(Lis[i])
      }
    }

    for(let i = 0; i< result.length; i ++){
      if(Math.abs(nodeLi.offsetLeft - result[i].offsetLeft) <= 21 &&
        Math.abs(nodeLi.offsetTop - result[i].offsetTop) <= 21 &&
        (nodeLi.offsetLeft == result[i].offsetLeft || 
        nodeLi.offsetTop == result[i].offsetTop
        )){
          result[i].num = fn(result[i])
          result[i].parent = nodeLi
          openArr.push(result[i])
        }
      
    }
  }

  function filter(nodeLi) {
    for(const c of closeArr){
      // console.log( nodeLi)
      if(c == nodeLi){
        return false
      }
    }
    for(const o of openArr){
      // console.log( nodeLi)
      if(nodeLi == o) return false
    }
    return true
  }

 
</script>
</html>

maiff · 2019-03-23T07:00:26Z

<html>
<head>
  <meta charset="utf-8" />
  <title>tank</title>
<style>
  html,
  body {
    height: 100%;
    width: 100%;
    margin: 0;
    padding: 0;
  }

  #point{
    position: absolute;
    top:10%;
    left:50%;
  }
</style>
</head>
<body>
  <canvas id="canvas"></canvas>
  <p id="point">0</p>
</body>
<script>

let canvas = document.getElementById('canvas')
let ctx = canvas.getContext('2d');
let tank_2;
function addVoice(src){
  var audio = document.createElement("audio")
  audio.src = src;
  audio.play();
}

const baseNum = 10;

let point = 0;
const bullets = [];
function resizeCanvas(){
  console.log('resize')
  canvas.width = window.innerWidth;
  canvas.height = window.innerHeight;
}
window.addEventListener("resize",resizeCanvas,false)
resizeCanvas()

class Rect{
  constructor(x, y, w, h, color) {
    this.x = x;
    this.y = y;
    this.w = w* baseNum;
    this.h = h* baseNum;
    this.color = color;

  }
  draw() {
    // console.log(this.x, this.y)
    ctx.beginPath();
    ctx.fillStyle = this.color;

    ctx.rect(this.x, this.y, this.w, this.h);
    ctx.fill();
    ctx.stroke();
  }
}
// function updatePoint(){
// const p = document.getElementById('point')
// p.innerText = point
// }


class Bullet extends Rect{
  constructor(x,y,w,h,color,d){
    super(x,y,w,h,color)
    this.direction = d
    this.show = true
  }
  draw(){
    if(this.show)
      super.draw()
  }

  move(){
    if(!this.show)return
    //  if(isHitEnemy()){
    //  point+=1
    //  updatePoint()
    //  addVoice('./Explosion.wav')
    //  }
    switch (this.direction) {
      case 0:
        this.x -= this.w
        break
      case 1:
        this.y -= this.h
        break
      case 2:
        this.x += this.w
        break
      case 3:
        this.y += this.h
        break
    }
    if (this.x >= canvas.width || this.x < 0 ||
        this.y >= canvas.height || this.y < 0) {
          this.show = false
      }
  }
}
class Tank{
  constructor(x, y, w, h, img){
    this.x = x * baseNum;
    this.y = y * baseNum;
    this.w = w * baseNum;
    this.h = h * baseNum;

    this.img = img;

    this.direction = 0 // 0 left 1 up 2 right 3 left

  }
}

function newImage(src) {
  var img = new Image();
  img.src = src;
  return img;
}

const direction = ['l', 'u', 'r', 'd'];
const tankList = [];
for(let i = 0; i < 4; i++){
  tankList.push(newImage('./tank'+direction[i]+'.png'))
}; 
class Player extends Tank{
  draw(isLoad=false){
    if(isLoad){
      ctx.drawImage(this.img[this.direction], 
      this.x, this.y, this.w, this.h)
    }else{
      this.img[this.direction].onload = () => {
        ctx.drawImage(this.img[this.direction], 
        this.x, this.y, this.w, this.h)
      }
    }

  }

  move(direction){
    // ctx.clearRect(0, 0, canvas.width, canvas.height);
    switch(direction){
      case 0:
        this.x -= this.w
        break;
      case 1:
        this.y -= this.h
        break;
      case 2:
        this.x += this.w
        break;
      case 3:
        this.y += this.h
        break;
    }
    
    if(this.x >= canvas.width || this.x < 0 || 
    this.y >= canvas.height || this.y < 0){
        switch(direction){
            case 0:
              this.x += this.w
              break
            case 1:
              this.y += this.h
              break
            case 2:
              this.x -= this.w
              break
            case 3:
              this.y -= this.w
              break
          }
        return
    }
    this.direction = direction
  }
}

const enemy = newImage('./enemy.png')
const enemies = []
// function isHitEnemy(){
// for(let s = 0; s < enemies.length; s++){
//       for(let b = 0; b < bullets.length; b++){
//         let BoneX =  bullets[b].x
//         let BoneY =  bullets[b].y

//         let BtwoX =  bullets[b].x + bullets[b].w
//         let BtwoY =  bullets[b].y

//         let BthreeX =  bullets[b].x 
//         let BthreeY =  bullets[b].y + bullets[b].h

//         let BfourX =  bullets[b].x + bullets[b].w
//         let BfourY =  bullets[b].y + bullets[b].h

//         let ex = enemies[s].x
//         let ex_e = enemies[s].x + enemies[s].w

//         let ey = enemies[s].y
//         let ey_e = enemies[s].y + enemies[s].h


        
//         if((BoneX >= ex  && BtwoY>= ey && 
//             BoneX <= ex_e  && BtwoY <= ey_e)||

//             (BtwoX >= ex  && BoneY>= ey && 
//             BtwoX <= ex_e  && BoneY <= ey_e)||

//             (BthreeX >= ex  && BthreeY>= ey && 
//             BthreeX <= ex_e  && BthreeY <= ey_e)||

//             (BfourX >= ex  && BfourY>= ey && 
//             BfourX <= ex_e  && BfourY <= ey_e)

//         ){
//           enemies.splice(s, 1)
//           bullets.splice(b, 1)
//           return true
//         }
//       }
      
//     }
//     return false
// }
class Enemy extends Tank{
  draw(isLoad=false){
    if(isLoad){
      ctx.drawImage(this.img, 
      this.x, this.y, this.w, this.h)
    }else{
      this.img.onload = () => {
        ctx.drawImage(this.img, 
        this.x, this.y, this.w, this.h)
      }
    }
  }
}

const tank_1 = new Player(0,0,5,5,tankList)
tank_1.draw()

document.onkeydown = function (e) {
  switch (e.keyCode) {
    case 37: //left
      tank_1.move(0)
      
      break;
  
    case 38: //up
      tank_1.move(1)
      
      break;
    case 39: //right
      tank_1.move(2)
      
      break;
    case 40: //down
      tank_1.move(3)
      
      break;
    case 32:
      addVoice('./Fire.wav')
      const bullet = new Bullet(tank_1.x,tank_1.y,5,5,'black',
      tank_1.direction)

      bullets.push(bullet)



      break;

  }
  tank_1.draw(true)
  e.preventDefault();
// ctx.clearRect(0, 0, canvas.width, canvas.height);
  
}

var timer = setInterval(() => {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  tank_1.draw(true)
  for(const b of bullets){
    b.move()
    b.draw()
  }
  for(const e of enemies){
    e.draw(true)
  }
  const random_enemy = getRandomEnemy()
  if(random_enemy){
    enemies.push(random_enemy)
  }
}, 100);

function randomBetween(min, max) {
  return Math.round(min + Math.random() * (max - min))
}
function getRandomEnemy(){
  if(enemies.length > 10) return null
  let isOnTank = true;
  while(isOnTank){
    isOnTank = false

    let enemyX = randomBetween(0, canvas.width / baseNum - 1);
    let enemyY = randomBetween(0, canvas.height / baseNum - 1);

    tank_2 = new Enemy(enemyX,enemyY,5, 5,enemy)
    if (tank_2.x == tank_1.x && tank_2.y == tank_1.y) {
          isOnTank = true
    }
  }
  return tank_2
}



</script>
</html>

maiff · 2019-03-23T08:24:11Z

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8" />
  <title>Page Title</title>

  <style>
  #ul1 {
    margin: 30px auto;
    border: 1px solid black;
    border-bottom: none;
    border-right: none;
    padding: 0;
    height: auto;
    overflow: hidden;  
  }

  #ul1 li{
    list-style: none;
    border: 1px solid black;
    border-top: none;
    border-left:none;
    float: left;
  }

  #ul1 li.style1{
    /* start */
    background: red;
  }

  #ul1 li.style2{
    /* obstacle */
    background: black;
  }
  
  #ul1 li.style3{
    /* end */
    background: orange;
  }
  </style>
  
</head>
<body>

  <ul id="ul1">
  </ul>

  <center>
    <input type="button" value="start" id="btn" />
    <input type="button" value="choose start" id="btnStart" />
    <input type="button" value="choose obstacle" id="btnObs" />
  </center>


  
</body>
<script>
  const aUl = document.getElementById('ul1')
  const aBtn = document.getElementById('btn')
  const btnStart = document.getElementById('btnStart')
  const btnObs = document.getElementById('btnObs')

  let openArr = []
  let closeArr = []
  const map = new Int8Array(400)
  map[0] = 1 // start

  map[399] = 3 //end
  let olderstart = 0
  let olderend = 399
  let nowChoose = 2 // 2 obstacle 1 start 3 end
  btnStart.onclick = () =>{
  	nowChoose = 1
  }
  btnObs.onclick = () => {
  	nowChoose = 2
  }



  const resultParent = []

  function init() {
    createMap();
    aBtn.onclick = function () {
      console.log('click')
      openFn();
    }
  }
  init()

  function getAllArray() {
    Lis = document.getElementsByTagName('li')
    beginLi = document.getElementsByClassName('style1')
    endLi = document.getElementsByClassName('style3')
  }
 
  
  function createMap() {
     aUl.innerHTML = ''
     openArr = []
     closeArr = []


    const liSize = 20;

    for(let i = 0; i < map.length; i++){
      let aLi = document.createElement('Li');
      aLi.style.width = liSize + 'px'
      aLi.style.height = liSize + 'px'
      aLi.dataset.index = i;
      aUl.appendChild(aLi)
      if(map[i] == 1){
        aLi.className = 'style1';
        openArr.push(aLi)
      }else if(map[i] == 2){
        aLi.className = 'style2';
        closeArr.push(aLi);
      }else if(map[i] ==3){
        aLi.className = 'style3';

      }

    }
    aUl.style.width = 20 * (liSize + 1) + 1 + 'px';
    getAllArray()
  }

  // 评估函数
  function fn(nowLi) {
    return g(nowLi) + h(nowLi)
  }
  function g(nowLi) {
    const a = nowLi.offsetLeft - beginLi[0].offsetLeft;
    const b = nowLi.offsetTop -beginLi[0].offsetTop;
    return a + b
  }
  function h(nowLi) {
    const a = nowLi.offsetLeft - endLi[0].offsetLeft;
    const b = nowLi.offsetTop -endLi[0].offsetTop;
    return Math.sqrt(a*a +b*b)
  }

  function showPath() {
    let lastLi = closeArr.pop();
    let iNow = 0;
    findParent(lastLi);

    const timer = setInterval(() => {
      resultParent[iNow].style.background = 'red';
      iNow++
      if(iNow == resultParent.length)
        clearInterval(timer)
    }, 50);
  }
  function findParent(li) {
    resultParent.unshift(li);
    if(li.parent == beginLi[0]) return
    findParent(li.parent);
  }

  function openFn(){
     console.log('openFn')
    let nodeLi = openArr.shift()
    if(nodeLi == endLi[0]){
      showPath()
      return
    }

    closeFn(nodeLi);
    findLi(nodeLi);

    openArr.sort((li1, li2) => {
      return li1.num - li2.num
    } )

    openFn()
  }
  
  function closeFn(nodeLi) {
    closeArr.push(nodeLi);
  }

  function findLi(nodeLi){
    const result = []

    for(let i = 0; i < Lis.length; i++){
      if( filter(Lis[i]) ){
        result.push(Lis[i])
      }
    }

    for(let i = 0; i< result.length; i ++){
      if(Math.abs(nodeLi.offsetLeft - result[i].offsetLeft) <= 21 &&
        Math.abs(nodeLi.offsetTop - result[i].offsetTop) <= 21 &&
        (nodeLi.offsetLeft == result[i].offsetLeft || 
        nodeLi.offsetTop == result[i].offsetTop
        )){
          result[i].num = fn(result[i])
          result[i].parent = nodeLi
          openArr.push(result[i])
        }
      
    }
  }

  function filter(nodeLi) {
    for(const c of closeArr){
      // console.log( nodeLi)
      if(c == nodeLi){
        return false
      }
    }
    for(const o of openArr){
      // console.log( nodeLi)
      if(nodeLi == o) return false
    }
    return true
  }

  aUl.onclick = (e) => {
  	if(e.target.tagName == 'LI'){
  		
  		map[e.target.dataset.index] = nowChoose
  		if(nowChoose == 1){
  			map[olderstart] = 0
  			olderstart = e.target.dataset.index
  		}
  	}
  	createMap()
  }


 
</script>
</html>

maiff · 2019-03-23T08:47:46Z

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8" />
  <title>Page Title</title>

  <style>
  #ul1 {
    margin: 30px auto;
    border: 1px solid black;
    border-bottom: none;
    border-right: none;
    padding: 0;
    height: auto;
    overflow: hidden;  
  }

  #ul1 li{
    list-style: none;
    border: 1px solid black;
    border-top: none;
    border-left:none;
    float: left;
  }

  #ul1 li.style1{
    /* start */
    background: red;
  }

  #ul1 li.style2{
    /* obstacle */
    background: black;
  }
  
  #ul1 li.style3{
    /* end */
    background: orange;
  }
  </style>
  
</head>
<body>

  <ul id="ul1">
  </ul>

  <center>
    <input type="button" value="start" id="btn" />
    <input type="button" value="choose start" id="btnStart"/>
    <input type="button" value="choose obstacle" id="btnObs"/>
    <input type="button" value="choose end" id="btnEnd"/>
  </center>
  
</body>
<script>
  const aUl = document.getElementById('ul1')
  const aBtn = document.getElementById('btn')
  const btnStart=document.getElementById('btnStart')
  const btnObs=document.getElementById('btnObs')
  const btnEnd=document.getElementById('btnEnd')

  let openArr = []
  let closeArr = []
  const map = new Int8Array(400)
  map[0] = 1 // start

  map[399] = 3 //end

  let olderstart=0
  let olderend=399
  let nowChoose=2
  const resultParent = []
  btnStart.onclick=()=>{
    nowChoose=1
  }
  btnObs.onclick=()=>{
    nowChoose=2
  }

  btnEnd.onclick=()=>{
  nowChoose=3
  }
  


  function init() {
    createMap();
    aBtn.onclick = function () {
      console.log('click')
      openFn();
    }
  }
  init()

  function getAllArray() {
    Lis = document.getElementsByTagName('li')
    beginLi = document.getElementsByClassName('style1')
    endLi = document.getElementsByClassName('style3')
  }

  
  function createMap() {
     aUl.innerHTML = ''
     openArr = []
     closeArr = []


    const liSize = 20;

    for(let i = 0; i < map.length; i++){
      let aLi = document.createElement('Li');
      aLi.style.width = liSize + 'px'
      aLi.style.height = liSize + 'px'
      aLi.dataset.index = i;
      aUl.appendChild(aLi)
      if(map[i] == 1){
        aLi.className = 'style1';
        openArr.push(aLi)
      }else if(map[i] == 2){
        aLi.className = 'style2';
        closeArr.push(aLi);
      }else if(map[i] ==3){
        aLi.className = 'style3';

      }

    }
    aUl.style.width = 20 * (liSize + 1) + 1 + 'px';
    getAllArray()
  }

  // 评估函数
  function fn(nowLi) {
    return g(nowLi) + h(nowLi)
  }
  function g(nowLi) {
    const a = nowLi.offsetLeft - beginLi[0].offsetLeft;
    const b = nowLi.offsetTop -beginLi[0].offsetTop;
    return a + b
  }
  function h(nowLi) {
    const a = nowLi.offsetLeft - endLi[0].offsetLeft;
    const b = nowLi.offsetTop -endLi[0].offsetTop;
    return Math.sqrt(a*a +b*b)
  }

  function showPath() {
    let lastLi = closeArr.pop();
    let iNow = 0;
    findParent(lastLi);

    const timer = setInterval(() => {
      resultParent[iNow].style.background = 'red';
      iNow++
      if(iNow == resultParent.length)
        clearInterval(timer)
    }, 500);
  }
  function findParent(li) {
    resultParent.unshift(li);
    if(li.parent == beginLi[0]) return
    findParent(li.parent);
  }

  function openFn(){
     console.log('openFn')
    let nodeLi = openArr.shift()
    if(nodeLi == endLi[0]){
      showPath()
      return
    }

    closeFn(nodeLi);
    findLi(nodeLi);

    openArr.sort((li1, li2) => {
      return li1.num - li2.num
    } )

    openFn()
  }
  
  function closeFn(nodeLi) {
    closeArr.push(nodeLi);
  }

  function findLi(nodeLi){
    const result = []

    for(let i = 0; i < Lis.length; i++){
      if( filter(Lis[i]) ){
        result.push(Lis[i])
      }
    }

    for(let i = 0; i< result.length; i ++){
      if(Math.abs(nodeLi.offsetLeft - result[i].offsetLeft) <= 21 &&
        Math.abs(nodeLi.offsetTop - result[i].offsetTop) <= 21 &&
        (nodeLi.offsetLeft == result[i].offsetLeft || 
        nodeLi.offsetTop == result[i].offsetTop
        )){
          result[i].num = fn(result[i])
          result[i].parent = nodeLi
          openArr.push(result[i])
        }
      
    }
  }

  function filter(nodeLi) {
    for(const c of closeArr){
      // console.log( nodeLi)
      if(c == nodeLi){
        return false
      }
    }
    for(const o of openArr){
      // console.log( nodeLi)
      if(nodeLi == o) return false
    }
    return true
  }

  aUl.onclick=(e)=>{
    if (e.target.tagName=='LI') {
      map[e.target.dataset.index]=nowChoose
      if(nowChoose==1){
        map[olderstart]=0
        olderstart=e.target.dataset.index
      }
      if(nowChoose==3){
      map[olderend]=0
      olderend=e.target.dataset.index
      }

      
    } 
    createMap()
  }

 
</script>
</html>

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

https://www.redblobgames.com/pathfinding/a-star/introduction.html #3

https://www.redblobgames.com/pathfinding/a-star/introduction.html #3

maiff commented Mar 23, 2019

maiff commented Mar 23, 2019

maiff commented Mar 23, 2019

maiff commented Mar 23, 2019

maiff commented Mar 23, 2019

https://www.redblobgames.com/pathfinding/a-star/introduction.html #3

https://www.redblobgames.com/pathfinding/a-star/introduction.html #3

Comments

maiff commented Mar 23, 2019

maiff commented Mar 23, 2019

maiff commented Mar 23, 2019

maiff commented Mar 23, 2019

maiff commented Mar 23, 2019