PHP 像素图组效率

Question

我目前有一张 1600 x 1600 的地图存储在 MySQL 中（2,560,000 条记录）。我正在向用户渲染一个简单的 25x25 地图以供交互。用户可以在此地图上 "claim" 个图块。我希望能够计算给定用户拥有的图块的开放面数。我可以将其除以拥有的总图块以确定任意效率等级。

所有地图坐标都简单地存储为 X/Y 值。

我正在寻找可以潜在地处理所述 X/Y 值数组并确定每个拥有的组可以访问多少张开放面孔的东西。例如...

0 = player
x x x x x
x x 0 x x
x x x x x
4 open faces

x x x x x 
x x 0 x x 
x x 0 x x 
x x x x x 
6 open faces

x x x x x 
x x x 0 x
x x 0 x x
x x x x x 
8 open faces

现在我正在做一些低效的数组循环来计算这个。我有一个简单的计数器，然后循环遍历所有值的数组，并在 X 和 Y 的每个方向上寻找值 +-1 以减少计数。每个循环根据发现的数量将 0-4 添加到总计数器。这种方法固有的问题是，随着群体的壮大，计算出来的时间会越来越长。因为一个团可能要消耗20000点以上，所以还是挺有负担的。

非常感谢任何帮助。

Answer 1

一种方法涉及创建 Point class。例如：

class Point {
    public $x;
    public $y;

    public function __construct($x, $y){
        $this->x = $x;
        $this->y = $y;
    }

    public function getNeighbors(){
        // TODO: What if we are at the edge of the board?

        return array(
            new Point($x+1, $y+1),
            new Point($x+1, $y-1),
            new Point($x-1, $y+1),
            new Point($x-1, $y-1),
        );
    }
}

为用户占用的每个点从 class 创建实例：

// Generate array of Points from database
$user_points = array(new Point(134, 245), new Point(146, 456));

迭代生成所有邻居：

// Get a flat array of neighbor Points
$neighbors = array_merge(array_map(function($point){
    return $point->getNeighbors();
}, $user_points));

// TOOD: Remove Points that are equal to values in $user_points

然后，最后，提交COUNT查询"neighbor"点，以确定有多少被其他用户占用并从总数中删除。

（注意：我在需要完成更多工作的地方添加了 TODO。）

The inherent problem with this method is that as a group grows, it will take longer and longer to calculate out.

您应该考虑使用内存中的键值存储，例如 Redis。但是，是的，在时间复杂度方面，查找时间（对于已占用的块）似乎与条目数呈线性关系。

Answer 2

这是我想出的用于确定地理效率的最后一段简单代码。某些事物的名称已更改。 :P

我运行注意到了，一切都是 ajax，所以我决定在多维而不是其他方面进行单一 isset 检查。

$sql = 'SELECT map_x, map_y FROM Map WHERE person_id = :person_id';
$query = $DB->prepare($sql);
$query->execute(array(':nation_id' => $this->person_id));
$counter = 0;
$coords = array();
while($row = $query->fetch())
{
    ++$counter;
    $coords[$row['map_x']][$row['map_y']] = 1;
}
$faces = 0;
foreach($coords as $x => $batch)
{
    foreach($batch as $y => $junk)
    {
        $hits = 4;
        if(isset($coords[$x + 1][$y]))
        {
            --$hits;
        }
        if(isset($coords[$x - 1][$y]))
        {
            --$hits;
        }
        if(isset($coords[$x][$y - 1]))
        {
            --$hits;
        }
        if(isset($coords[$x][$y + 1]))
        {
            --$hits;
        }
        $faces += $hits;
    }
}

PHP 像素图组效率

PHP Pixel Map Group Efficiency

php

mysql

arrays

coordinates