1 Востаннє редагувалося VTrim (16.01.2015 12:37:49)

Тема: Пошук шляху в лабіринті (задача)

Створюємо масив координат 10х10, для цього підійде будь-який багатовимірний масив виду $array[y][x] = status, де status - доступність комірки (якщо 1 - значить існує перешкода і її необхідно обійти, 0 - можна проходити). Необхідно скласти шлях, як дістатися з точки А в точку Б обходячи перешкоди. Точки А і Б задаються довільні: А ($a = array("x" => 2, "y" => 3); ), Б ($b = array("x" => 9, "y" => 1); ). Важливе зауваження, необхідно генерувати поле (10х10 або інше) при першому запуску скрипта, після масив зберігається в БД або в ФАЙЛ для подальшої роботи з ним. Мета - знайти найкоротший шлях. Чи можливо рухатися по діагоналі - за бажанням ..

У кого які ідеї?

2

Re: Пошук шляху в лабіринті (задача)

Задача про лабіринт в інтернеті вже добряче розжована. Розказати один з алгоритмів, чи саменькі погуглите?

3

Re: Пошук шляху в лабіринті (задача)

Я краще промовчу..

Хз,зараз спробую перевести код С++
https://ru.wikipedia.org/wiki/Алгоритм_Ли
на PHP

4

Re: Пошук шляху в лабіринті (задача)

До кінця не розібрався..
Потрібна допомога koala

Не до кінця переведений на PHP

<?php
define('W',12); 
define('H',8);        
define('WALL',-1); 
define('BLANK',-2);       
 
//int px[W * H], py[W * H];  
//int grid[h][W];  
 
//не розібрався з двома рядками,що вище.
//їх потрібно оголошувати і якщо так,то як?
 
function lee($ax, $ay, $bx, $by)
{
  $dx[4] = array(1, 0, -1, 0);   
  $dy[4] = array(0, 1, 0, -1);
 
  $d = 0;
  $grid[$ay][$ax] = 0; 
  do {
    $stop = true;        
    for ( $y = 0; $y < H; ++$y )
      for ( $x = 0; $x < W; ++$x )
        if ( $grid[$y][$x] == $d ) 
        {
          for ( $k = 0; $k < 4; ++$k ) 
            if ( $grid[$y + $dy[$k]][$x + $dx[$k]] == BLANK )
            {
              $stop = false;
              $grid[$y + $dy[$k]][$x + $dx[$k]] = $d + 1;      
            }
        }
    $d++;
  } while ( !$stop && $grid[$by][$bx] == BLANK );
 
  if ($grid[$by][$bx] == BLANK) return false;
 
  $len = $grid[$by][$bx];
  $x = $bx;
  $y = $by;
  $d = $len;
  while ( $d > 0 )
  {
    $px[$d] = $x;
    $py[$d] = $y;        
    $d--;
    for ($k = 0; $k < 4; ++$k)
      if ($grid[$y + $dy[$k]][$x + $dx[$k]] == $d)
      {
        $x = $x + $dx[$k];
        $y = $y + $dy[$k]; 
        break;
      }
  }
  $px[0] = $ax;
  $py[0] = $ay; 
  return true;
}
 
echo lee(3, 6, 3, 0);

5

Re: Пошук шляху в лабіринті (задача)

 if ( $grid[$y + $dy[$k]][$x + $dx[$k]]== BLANK )

вилазить за межі масива (до речі, а де він заданий?)

6

Re: Пошук шляху в лабіринті (задача)

Також не бачу де :D

7 Востаннє редагувалося VTrim (16.01.2015 15:17:43)

Re: Пошук шляху в лабіринті (задача)

Я так розумію проблема в тих двох рядках і є.

//int grid[h][W]; 

це ж він і є.
Але не можу догнати як це записати в PHP.

8

Re: Пошук шляху в лабіринті (задача)

VTrim написав:

Я так розумію проблема в тих двох рядках і є.

//int grid[h][W]; 

це ж він і є.
Але не можу догнати як це записати в PHP.

так це ж просто двомірний масив

9

Re: Пошук шляху в лабіринті (задача)

Допустимо так

$px[W * H] = array();
$py[W * H] = array();  
$grid[h][W] = array(); 

10

Re: Пошук шляху в лабіринті (задача)

FakiNyan написав:
VTrim написав:

Я так розумію проблема в тих двох рядках і є.

//int grid[h][W]; 

це ж він і є.
Але не можу догнати як це записати в PHP.

так це ж просто двомірний масив

Загуглив, в PHP це, виявляється, ще та клоунада.