我正在为一款游戏工作,我需要一个算法。
我有一个网格地图,每个单元格有两个坐标:X和y
那么,对于开始,我有一个开始单元格(例如X=8:Y=10)和一个结束单元格(X=18:Y=15)。
我需要一个算法,可以找到我的坐标(X:Y)的每个细胞之间的这两个点,但有一个随机路径,而不是一条直线。如果可能的话,在这些坐标之间使用最大数量的单元格。
你有什么想法吗?
编辑:你可以检查http://alex.moutonking.com/wordpress/?p=44,这是我的算法在两个坐标之间的直线,我需要添加一个随机效应..
你可以得到所有的点,然后从点返回一个随机值
$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
);
}
}