所以,我正在创建一个迷你策略游戏,偶然发现了一个我无法真正解决的问题。
我认为这很容易,但似乎我错了,或者解决方案就在我的鼻子下,但是我正在寻找有关我的问题的另一种观点。
我有一个数据库,上面有一个地图上记录的领土列表。这些领土中的每一个都有相邻领土的清单。
ID | name | adjacent | faction 1 | Name1 | 2;7;10;24 | 5 2 | Name2 | 1;3;7;8 | 4 3 | Name3 | 2;4;5;8 | 8
相邻的ID列表,由半柱分隔
我的目标是找到从某个派系持有的所有领土的最短途径。距离是根据到达该地区所需的步骤数量计算的。
这样,我可以快速获得距离并在这方面应用修饰符。
例如,在上面的数据段中:
-
领土1距离为2,因为它们相邻。
-
领土1距3距离1,因为3相邻2(和2相邻(。
-
领土1距4个距离,因为4相邻3,毗邻2。
目前,我的代码看起来像
function getProximity($connexion, $faction, $terrain)
{
$query = "SELECT id, adjacent FROM worldmap WHERE faction = ".$faction;
$result = mysqli_query($connexion, $query);
$proximity = 10;
while ($row = mysqli_fetch_row($result))
{
$adjacent = explode(";", $row[1]);
if (in_array($terrain, $adjacent))
{
//territory is adjacent, stop looking
return 0;
}
else
{
//if not directly adjacent, seek through the list
foreach($adjacent as $adj)
{
$prox = getSubProximity($connexion, array($row[0]), $adj, $terrain, 1);
if ($prox < $proximity)
{
$proximity = $prox;
}
}
}
}
return $proximity;
}
function getSubProximity($connexion, $from, $terrain, $terrain2, $proximity)
{
//Attempt to break weird loops... not succesful...
if ($proximity > 10)
{
return $proximity;
}
$query = "SELECT id, adjacent FROM worldmap WHERE id = ".$terrain;
$result = mysqli_query($connexion, $query);
while ($row = mysqli_fetch_row($result))
{
$adjacent = explode(";", $row[1]);
if (in_array($terrain2, $adjacent))
{
//territory is adjacent, stop looping
return $proximity;
}
else
{
foreach($adjacent as $adj)
{
//check if we've been through there
if (!in_array($adj, $from))
{
array_push($from, $terrain);
$prox = getSubProximity($connexion, $from, $adj, $terrain2, $proximity+1);
if ($prox < $proximity)
{
$proximity = $prox;
}
}
}
}
}
}
感谢您的帮助,如果您还有其他方法可以获得相同的结果,请随时;数据库结构不是静态的,并且完全由我控制。
我会建议一些事情:
-
mySQL在使用自我引用/分层数据方面并不那么强,因此反对通常的答案("在SQL中进行"(,在PHP中执行逻辑。
-
由于总数据集相对较小,请在一个查询中读取所有区域的数据,然后将数据库排除在外。
-
执行非恢复的广度首次搜索。这样,您只需要一次访问任何世界领土。
-
保留您已经访问过的领土列表,以避免无休止地循环循环,并为此使用关联数组,以便您获得快速键查找(而不是效率低下的
in_array
(。仅保留$from
领域还不够。
这是此类代码的概述:
// This function returns the whole data set in a nice data structure
function getProximityData($connexion) {
$query = "SELECT id, adjacent, faction FROM worldmap";
$result = mysqli_query($connexion, $query);
while ($row = mysqli_fetch_row($result)) {
$territories[$row[0]] = [
"adjacent" => explode(";", $row[1]),
"faction" => $row[2]
];
}
return $territories;
}
function getProximity($territories, $faction, $terrain) {
// mark this terrain as visited
$visited[$terrain] = 1;
// Create queue for breadth first search
$queue = [$terrain];
$steps = 0;
while (count($queue)) {
$next = [];
foreach($queue as $terrain) {
if ($territories[$terrain]["faction"] === $faction) {
// Territory belongs to the faction, stop looking
return $steps;
}
// collect list of unvisited neighbours of this terrain
foreach($territories[$terrain]["adjacent"] as $adj) {
if (!isset($visited[$adj])) { // not yet visited
$next[] = $adj;
$visited[$adj] = 1;
}
}
}
$queue = $next;
$steps++;
}
// Should never get here: it would mean territories are disconnected
}
// Load the world map:
$territories = getProximityData($connexion);
// Example use:
$steps = getProximity($territories, 5, 4); // distance of faction 5 to territory 4.
请注意,将返回给定派系(第二个参数(拥有的领土(最后一个参数(。对于与派系相邻的领土,您将获得1,等等。