Случайный путь между двумя координатами (x, y)

Question

Я работаю над игрой, и мне нужен алгоритм.

У меня есть карта сетки, каждая ячейка имеет 2 координаты: X и Y.

Итак, для начала я иметь начальную ячейку (например, Х = 8: Y = 10), и конец ячейки (Х = 18 Y = 15).

Мне нужен алгоритм, который может найти мне координаты (X: Y) для каждой ячейки между этими двумя точками, но со случайным путем, а не по прямой. Если возможно, максимальное количество ячеек между этими координатами.

Есть ли у вас идеи?

Edit: Вы можете проверить http://alex.moutonking.com/wordpress/?p=44, это мой алгоритм для прямой линии между двумя координатами, мне нужно добавить случайный эффект ..

Answer 1

Вы можете получить все точки, то возвращать случайные значения с точки

$pt1 = array(
     8, 
     10 
); 
$pt2 = array(
     18, 
     15 
); 

$sl = new StraightLine($pt1, $pt2); 
echo $sl->rand(true); // return random points 

Выходные

{ 
    "x": 16, 
    "y": 14 
} 

Чтобы получить все точки

echo $sl; 

Выход

[ 
    { 
     "x": 8, 
     "y": 10 
    }, 
    { 
     "x": 9, 
     "y": 10.5 
    }, 
    { 
     "x": 10, 
     "y": 11 
    }, 
    { 
     "x": 11, 
     "y": 11.5 
    }, 
    { 
     "x": 12, 
     "y": 12 
    }, 
    { 
     "x": 13, 
     "y": 12.5 
    }, 
    { 
     "x": 14, 
     "y": 13 
    }, 
    { 
     "x": 15, 
     "y": 13.5 
    }, 
    { 
     "x": 16, 
     "y": 14 
    }, 
    { 
     "x": 17, 
     "y": 14.5 
    }, 
    { 
     "x": 18, 
     "y": 15 
    } 
] 

Класс Б

class StraightLine implements IteratorAggregate, JsonSerializable { 
    private $pt1 = 0, $pt2 = 0; 
    private $points = array(); 

    function __construct($pt1, $pt2) { 
     if (count($pt1) !== 2 || count($pt2) !== 2) 
      throw new InvalidArgumentException("Expexting only 2 values each"); 

     $this->pt1 = array_values($pt1); 
     $this->pt2 = array_values($pt2); 

     $this->parse(); 
    } 

    public function getIterator() { 
     return new ArrayIterator($this->points); 
    } 

    public function jsonSerialize() { 
     return json_encode($this->points, 128); 
    } 

    public function __toString() { 
     return $this->jsonSerialize(); 
    } 

    public function rand($encode = false) { 
     $k = array_rand($this->points); 
     return $encode ? json_encode($this->points[$k], 128) : $this->points[$k]; 
    } 

    private function parse() { 
     $m = ($this->pt1[1] - $this->pt2[1])/($this->pt1[0] - $this->pt2[0]); 
     $b = $this->pt1[1] - $m * $this->pt1[0]; 
     for($i = $this->pt1[0]; $i <= $this->pt2[0]; $i ++) 
      $this->points[] = array(
        "x" => $i, 
        "y" => $m * $i + $b 
      ); 
    } 
}