【PHP算法】PHP经典游戏算法之蚂蚁爬杆

在之前的笔记中波波把经常遇到的排序算法用PHP总结了一下，今天开始波波陆续分享一些PHP经典的游戏算法供大家参考学习。

PHP经典游戏算法之蚂蚁爬杆：

有一根27厘米的细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。木杆很细，同一时间只能通过一只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，不会后退。当任意两只蚂蚁碰头时，两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。求所有蚂蚁都离开木杆的最小时间和最大时间。

PHP经典游戏算法之蚂蚁爬杆

PHP版算法源码：

  1. class AntsClimb
  2. {
  3.     /**
  4.      * @var array 蚂蚁位置集合
  5.      */
  6.     protected $position;
  7.     /**
  8.      * AntsClimb constructor.
  9.      *
  10.      * @param array $position
  11.      */
  12.     public function __construct(array $position)
  13.     {
  14.         $this->position = $position;
  15.     }
  16.     /**
  17.      * run
  18.      *
  19.      * @return void
  20.      */
  21.     public function run()
  22.     {
  23.         $pathCalculate = $this->path($this->position);
  24.         echo '<pre>计算-';
  25.         print_r($pathCalculate);
  26.         echo '排序-';
  27.         asort($pathCalculate);
  28.         print_r($pathCalculate);
  29.     }
  30.     /**
  31.      * add2
  32.      *
  33.      * @param $directionArr
  34.      * @param $count
  35.      * @param $i
  36.      * @return mixed
  37.      */
  38.     protected function add2($directionArr, $count, $i)
  39.     {
  40.         if (0 > $i) {
  41.             return $directionArr;
  42.         }
  43.         if (0 === $directionArr[$i]) {
  44.             $directionArr[$i] = 1;
  45.             return $directionArr;
  46.         }
  47.         $directionArr[$i] = 0;
  48.         return $this->add2($directionArr, $count, $i - 1);
  49.     }
  50.     /**
  51.      * path
  52.      *
  53.      * @param $positionArr
  54.      * @return array
  55.      */
  56.     protected function path($positionArr)
  57.     {
  58.         // 生成测试路径
  59.         $pathCalculate = array ();
  60.         $count         = count($positionArr);
  61.         $directionArr  = array_fill(0, $count, 0);
  62.         // 朝向
  63.         $end = str_repeat('1', $count);
  64.         while (true) {
  65.             $path                         = implode('', $directionArr);
  66.             $total                        = $this->calculate($positionArr, $directionArr);
  67.             $pathCalculate['路径:' . $path] = $total;
  68.             if ($end == $path) { // 遍历完成
  69.                 break;
  70.             }
  71.             $directionArr = $this->add2($directionArr, $count, $count - 1);
  72.         }
  73.         return $pathCalculate;
  74.     }
  75.     /**
  76.      * calculate
  77.      *
  78.      * @param $positionArr
  79.      * @param $directionArr
  80.      * @return int
  81.      */
  82.     protected function calculate($positionArr, $directionArr)
  83.     {
  84.         $total = 0;
  85.         // 总用时
  86.         $length = 27;
  87.         // 木杆长度
  88.         while ($positionArr) {
  89.             $total++; // 步增耗时
  90.             $nextArr = array (); // 下一步位置
  91.             foreach ($positionArr as $key => $value) {
  92.                 if (0 == $directionArr[$key]) {
  93.                     $next = $value - 1; // 向0方向走一步
  94.                 } else {
  95.                     $next = $value + 1; // 向1方向走一步
  96.                 }
  97.                 if (0 == $next) { // 在0方向走出
  98.                     continue;
  99.                 }
  100.                 if ($length == $next) { // 在1方向走出
  101.                     continue;
  102.                 }
  103.                 $nextArr[$key] = $next;
  104.             }
  105.             $positionArr = $nextArr;// 将$positionArr置为临时被查找数组
  106.             foreach ($nextArr as $key => $value) {
  107.                 $findArr = array_keys($positionArr, $value);
  108.                 if (count($findArr) < 2) {
  109.                     // 没有重合的位置
  110.                     continue;
  111.                 }
  112.                 foreach ($findArr as $findIndex) {
  113.                     $directionArr[$findIndex] = $directionArr[$findIndex] ? 0 : 1;
  114.                     // 反向处理
  115.                     unset($positionArr[$findIndex]);
  116.                     // 防止重复查找计算
  117.                 }
  118.             }
  119.             $positionArr = $nextArr;
  120.             // 将$positionArr置为下一步结果数组
  121.         }
  122.         return $total;
  123.     }
  124. }

更多PHP经典游戏算法请收藏菠菜园，后续为大家陆续更新哈。

你想把广告放到这里吗？

发表评论

您必须 登录 才能发表留言！