php 解迷宫之H最小 可刷新运行 刷新

A*搜索算法。目前只保证了H是最小,所以F有可能不是最短的。 F = G + H 。G = 从起点 A 移动到指定方格的移动代价,H = 从指定的方格移动到终点 的估算成本。

代码:

<?php

$n=20;
$positions=[];
for ($i=0;$i<=$n;$i++){
    for ($j=0;$j<=$n;$j++){
        $positions[] =[$j,$i] ;
    }
}

//开始的点
$startDot=[0,0];
//已经放置的点
$placedDot=[];
//不可放置的点
$notPlacedDot=notPlacedDot($positions,$n);
$placedDot[]=$startDot;



//所有穿过的点
list($lineDot,$finishDot)=line($positions,$startDot,$placedDot,$notPlacedDot,$n);

//平面上的所有迷宫点
$mazePositions=mazePosition($positions,$lineDot);


//查找最小的点
$line=[];
$canReOpen=[];//库存
$startDot=[0,0];//开始的点
$line[]=[0,0];
$shortLine=getShortLine($line,$canReOpen,$startDot,$mazePositions,$notPlacedDot,$finishDot,$n);
echo "解迷宫";
echo getHtml($positions,$lineDot,$shortLine,$n);
echo "<br>";
echo "迷宫路线";
echo getAllHtml($positions,$lineDot,$n);



function line($positions,$startDot,$placedDot,$notPlacedDot,$n){
    
    $dotWrapper=GetDotWrappers($startDot);
    $key=rand(0,3);
    $nextDot =  $dotWrapper[$key];

    $i=0;
    $notPlacedDotAll =array_merge($notPlacedDot,[]);
    while (in_array($nextDot,$placedDot)||in_array($nextDot,$notPlacedDotAll)){

        $i++;
       if(badDot($nextDot,$placedDot,$notPlacedDot,$n)){//是否是坏点

           $notPlacedDotAll[]=$nextDot;

          $startDot=$placedDot[count($placedDot)-1];
           $dotWrapper=GetDotWrappers($startDot);
           $key=rand(0,3);
           $nextDot =  $dotWrapper[$key];

          if(badDot($startDot,$placedDot,$notPlacedDotAll,$n)){//本身是否是坏点
              $notPlacedDotAll[]= array_pop($placedDot);

              $startDot=$placedDot[count($placedDot)-1];
              $dotWrapper=GetDotWrappers($startDot);
              $key=rand(0,3);
              $nextDot =  $dotWrapper[$key];

          }

        }else{
            $key=rand(0,3);
            $nextDot =  $dotWrapper[$key];

        }
        if($i>4&&count($placedDot)>1){//循环大于3次 还没找到去除该点
            $i=0;
            $notPlacedDot[]= array_pop($placedDot);
            $startDot=$placedDot[count($placedDot)-1];
            $dotWrapper=GetDotWrappers($startDot);
            $key=rand(0,3);
            $nextDot =  $dotWrapper[$key];


        }

    }


    $placedDot[]=$nextDot;

   if($nextDot[0]>=$n&&$nextDot[1]>0&&$nextDot[1]<=$n){
       return [$placedDot,$nextDot];
   }
   return line($positions,$nextDot,$placedDot,$notPlacedDot,$n);
}

function mazePosition($positions,$lineDot){
    $mazePositions=[];
    foreach ($positions as $position){

            if(in_array($position,$lineDot)){
                $mazePositions[]=$position;
            }
    }
    return $mazePositions;
}

function getShortLine($line,$canReOpen,$startDot,$mazePositions,$notPlacedDot,$endDot,$n){

    if($startDot==$endDot){
//        echo(json_encode($line));
        return $line;
    }

    $dotWrapper=GetDotWrappers($startDot);

    $allOpen = array_reduce($canReOpen, 'array_merge', array());

    $arr=[];

    foreach ($dotWrapper as $dot){

        if(in_array($dot,$mazePositions)&&!in_array($dot,$line)&&!in_array($dot,$allOpen)&&!in_array($dot,$notPlacedDot)){

            $arr[distance($dot,$endDot)][]=$dot;
        }


    }

    if(empty($arr)){//死点
        $notPlacedDot[]=$startDot;//这个点不能放
        array_pop($line);//去除这个点

        $length=count($line);
        $dot=$line[$length-1];//去除上面这个点的最后一个点
        $dotWrapper=GetDotWrappers($dot);//这个点周围的点

        if(!empty($canReOpen)){//库存中是否有点
            $reOpen = array_pop($canReOpen);//取出库存中最后一个库存
            $ifIntersect=false;
            foreach ($reOpen as $open){
                if(in_array($open,$dotWrapper)){//有交集,说明最后一个库存可用
                    $ifIntersect=true;
                    break;
                }
            }
            if($ifIntersect){//可用的库存
                $nextStartDot=array_shift($reOpen);//库存中的第一个点默认是最短距离的
                array_push($line,$nextStartDot);
                if(!empty($reOpen)){//没用完,再放进去
                    array_push($canReOpen,$reOpen);
                }
            }else{//不可用。把库存再放进去
                array_push($canReOpen,$reOpen);
                $nextStartDot = $dot;
            }
        }else{
            $nextStartDot = $dot;
        }
    }else{
        ksort($arr);//按距离大小升序排序

        $arr = array_reduce($arr, 'array_merge', array());
//        echo json_encode($arr);
//        echo "<br>";
        $nextStartDot=array_shift($arr);//取出最小距离的作为开始点

        array_push($line,$nextStartDot);
        if(!empty($arr)){//还有可用的点,放进库存
            $canReOpen[] = array_values($arr);
        }
    }



    return getShortLine($line,$canReOpen,$nextStartDot,$mazePositions,$notPlacedDot,$endDot,$n);

}


function getAllHtml($positions,$lineDot,$n){
    $str="<table border='1'>";

    foreach (array_chunk($positions,$n+1) as $row){
        $str.="<tr>";
        foreach ($row as $tr){
            if(in_array($tr,$lineDot)){

                $str.="<td style='color: white;background-color: red'>点{$tr[0]},{$tr[1]}</td>";


            }else{
                $str.="<td>{$tr[0]},{$tr[1]}</td>";
            }
        }
        $str.="<tr>";

    };
    $str.="</table>";
    return $str;
}
function getHtml($positions,$lineDot,$shortLine,$n){
    $str="<table border='1'>";

    foreach (array_chunk($positions,$n+1) as $row){
        $str.="<tr>";
        foreach ($row as $tr){
            if(in_array($tr,$lineDot)){
                if(in_array($tr,$shortLine)){
                    $str.="<td style='color: white;background-color: blue'>点{$tr[0]},{$tr[1]}</td>";
                }else{
                    $str.="<td style='color: white;background-color: red'>点{$tr[0]},{$tr[1]}</td>";
                }

            }else{
                $str.="<td>{$tr[0]},{$tr[1]}</td>";
            }
        }
        $str.="<tr>";

    };
    $str.="</table>";
    return $str;
}

function distance($start,$end){
    return abs($end[0]-$start[0])+abs($end[1]-$start[1]);
}

function notPlacedDot($positions,$n)
{
    
    $notPlacedDot=[];
    foreach ($positions as $position){
        $dotWrapper=GetDotWrappers($position);

        foreach ($dotWrapper as $dot){
            if($dot[0]<0||$dot[1]<0||$dot[0]>$n||$dot[1]>$n){
                $notPlacedDot[]=$dot;
            }
        }
    }
    return $notPlacedDot;
}

/**
 * 是否是坏点
 * @param $dotWrapper
 * @param $placedDot
 * @param $notPlacedDot
 * @return bool
 */
function badDot($position,$placedDot,$notPlacedDot,$n){
    
    $dotWrapper=GetDotWrappers($position);
    $i=0;
    foreach ($dotWrapper as $dot){
        if($dot[0]<0||$dot[1]<0||$dot[1]>$n||in_array($dot,$placedDot)||in_array($dot,$notPlacedDot)){
            $i++;
        }
    }
    if($i==4){
        return true;
    }
    return false;

}


function GetDotWrappers($placementEd){
    $top = calculateXY($placementEd[0],$placementEd[1],'top');
    $bottom = calculateXY($placementEd[0],$placementEd[1],'bottom');
    $left = calculateXY($placementEd[0],$placementEd[1],'left');
    $right = calculateXY($placementEd[0],$placementEd[1],'right');
    return [$top,$bottom,$left,$right];
}

function calculateXY($x,$y,$default='top')
{
    switch ($default){
        case 'top':
            $y=$y+1;
            break;
        case 'bottom':
            $y=$y-1;
            break;
        case 'left':
            $x=$x-1;
            break;
        case 'right':
            $x=($x+1);
            break;
        case 'left_top':
            $x=($x-1);
            $y=($y+1);
            break;
        case 'right_top':
            $x=($x+1);
            $y=($y+1);
            break;
        case 'right_bottom':
            $x=($x+1);
            $y=($y-1);
            break;
        case 'left_bottom':
            $x=($x-1);
            $y=($y-1);
            break;
    }

    return [$x,$y];
}

输出:

解迷宫
点0,0点1,0点2,0点3,0点4,05,06,07,0点8,0点9,0点10,0点11,0点12,0点13,0点14,0点15,0点16,0点17,0点18,019,020,0
0,1点1,1点2,1点3,1点4,1点5,16,1点7,1点8,19,110,111,112,113,114,115,1点16,1点17,1点18,1点19,120,1
0,2点1,2点2,2点3,24,2点5,2点6,2点7,28,29,210,211,212,213,214,215,216,2点17,2点18,2点19,220,2
0,31,32,3点3,3点4,3点5,3点6,3点7,38,39,310,311,312,313,314,315,316,3点17,318,319,320,3
0,41,42,4点3,44,4点5,4点6,4点7,48,4点9,4点10,4点11,412,413,414,415,416,4点17,4点18,4点19,4点20,4
0,51,52,5点3,5点4,55,56,5点7,5点8,5点9,510,5点11,5点12,513,514,515,516,517,518,519,520,5
0,61,62,63,6点4,65,66,67,68,69,610,6点11,6点12,613,614,615,616,617,618,619,620,6
0,71,72,73,7点4,75,76,77,78,79,710,7点11,7点12,713,714,715,716,717,718,719,720,7
0,81,82,83,8点4,8点5,8点6,8点7,8点8,8点9,8点10,8点11,8点12,813,814,815,816,817,818,819,820,8
0,91,92,93,94,95,96,97,98,99,910,911,912,913,914,915,916,917,918,919,920,9
0,101,102,103,104,105,106,107,108,109,1010,1011,1012,1013,1014,1015,1016,1017,1018,1019,1020,10
0,111,112,113,114,115,116,117,118,119,1110,1111,1112,1113,1114,1115,1116,1117,1118,1119,1120,11
0,121,122,123,124,125,126,127,128,129,1210,1211,1212,1213,1214,1215,1216,1217,1218,1219,1220,12
0,131,132,133,134,135,136,137,138,139,1310,1311,1312,1313,1314,1315,1316,1317,1318,1319,1320,13
0,141,142,143,144,145,146,147,148,149,1410,1411,1412,1413,1414,1415,1416,1417,1418,1419,1420,14
0,151,152,153,154,155,156,157,158,159,1510,1511,1512,1513,1514,1515,1516,1517,1518,1519,1520,15
0,161,162,163,164,165,166,167,168,169,1610,1611,1612,1613,1614,1615,1616,1617,1618,1619,1620,16
0,171,172,173,174,175,176,177,178,179,1710,1711,1712,1713,1714,1715,1716,1717,1718,1719,1720,17
0,181,182,183,184,185,186,187,188,189,1810,1811,1812,1813,1814,1815,1816,1817,1818,1819,1820,18
0,191,192,193,194,195,196,197,198,199,1910,1911,1912,1913,1914,1915,1916,1917,1918,1919,1920,19
0,201,202,203,204,205,206,207,208,209,2010,2011,2012,2013,2014,2015,2016,2017,2018,2019,2020,20

迷宫路线
点0,0点1,0点2,0点3,0点4,05,06,07,0点8,0点9,0点10,0点11,0点12,0点13,0点14,0点15,0点16,0点17,0点18,019,020,0
0,1点1,1点2,1点3,1点4,1点5,16,1点7,1点8,19,110,111,112,113,114,115,1点16,1点17,1点18,1点19,120,1
0,2点1,2点2,2点3,24,2点5,2点6,2点7,28,29,210,211,212,213,214,215,216,2点17,2点18,2点19,220,2
0,31,32,3点3,3点4,3点5,3点6,3点7,38,39,310,311,312,313,314,315,316,3点17,318,319,320,3
0,41,42,4点3,44,4点5,4点6,4点7,48,4点9,4点10,4点11,412,413,414,415,416,4点17,4点18,4点19,4点20,4
0,51,52,5点3,5点4,55,56,5点7,5点8,5点9,510,5点11,5点12,513,514,515,516,517,518,519,520,5
0,61,62,63,6点4,65,66,67,68,69,610,6点11,6点12,613,614,615,616,617,618,619,620,6
0,71,72,73,7点4,75,76,77,78,79,710,7点11,7点12,713,714,715,716,717,718,719,720,7
0,81,82,83,8点4,8点5,8点6,8点7,8点8,8点9,8点10,8点11,8点12,813,814,815,816,817,818,819,820,8
0,91,92,93,94,95,96,97,98,99,910,911,912,913,914,915,916,917,918,919,920,9
0,101,102,103,104,105,106,107,108,109,1010,1011,1012,1013,1014,1015,1016,1017,1018,1019,1020,10
0,111,112,113,114,115,116,117,118,119,1110,1111,1112,1113,1114,1115,1116,1117,1118,1119,1120,11
0,121,122,123,124,125,126,127,128,129,1210,1211,1212,1213,1214,1215,1216,1217,1218,1219,1220,12
0,131,132,133,134,135,136,137,138,139,1310,1311,1312,1313,1314,1315,1316,1317,1318,1319,1320,13
0,141,142,143,144,145,146,147,148,149,1410,1411,1412,1413,1414,1415,1416,1417,1418,1419,1420,14
0,151,152,153,154,155,156,157,158,159,1510,1511,1512,1513,1514,1515,1516,1517,1518,1519,1520,15
0,161,162,163,164,165,166,167,168,169,1610,1611,1612,1613,1614,1615,1616,1617,1618,1619,1620,16
0,171,172,173,174,175,176,177,178,179,1710,1711,1712,1713,1714,1715,1716,1717,1718,1719,1720,17
0,181,182,183,184,185,186,187,188,189,1810,1811,1812,1813,1814,1815,1816,1817,1818,1819,1820,18
0,191,192,193,194,195,196,197,198,199,1910,1911,1912,1913,1914,1915,1916,1917,1918,1919,1920,19
0,201,202,203,204,205,206,207,208,209,2010,2011,2012,2013,2014,2015,2016,2017,2018,2019,2020,20