Comment définir un compteur d'étapes récursif en utilisant les données MySQL en PHP

Question

Je suis donc en train de créer un mini jeu de stratégie pour le plaisir, et je suis tombé sur un problème que je n'arrive pas à résoudre.

Je pensais que ce serait facile, mais il semble que j'avais tort, ou peut-être que la solution est juste sous mon nez, mais je cherche un autre point de vue sur mon problème.

J'ai une base de données avec une liste de territoires enregistrés sur une carte. Chacun de ces territoires contient une liste de territoires adjacents.

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

adjacent étant une liste d'ID séparés par des points-virgules

Mon objectif est de trouver le chemin le plus court vers un territoire à partir de tous les territoires détenus par une certaine faction. La distance est calculée en fonction du nombre d'étapes nécessaires pour atteindre le territoire.

De cette façon, je peux rapidement obtenir la distance et appliquer des modificateurs à cet égard.

Par exemple, dans l'extrait de données ci-dessus :

• Le territoire 1 est à distance 0 du 2, puisqu'ils sont adjacents.

• Le territoire 1 est à 1 distance de 3, puisque 3 est adjacent à 2 (et 2 est adjacent à 1).

• Le territoire 1 est à une distance de 2 de 4, puisque 4 est adjacent à 3, qui est adjacent à 2.

Actuellement, mon code ressemble à ceci ;

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;
                    }
                }
            }
        }
    }
}

Merci pour votre aide, et n'hésitez pas si vous avez d'autres moyens d'obtenir le même résultat ; la structure de la base de données n'est pas statique et entièrement sous mon contrôle.

Answer 1

Certaines choses que je suggérerais :

• MySql n'est pas très fort pour travailler avec des données autoréférentielles/hiérarchiques, donc contre la réponse habituelle ("faites-le en SQL"), exécutez la logique en PHP.

• Puisque l'ensemble des données est relativement petit, lisez toutes les données des territoires en mémoire avec une seule requête, puis laissez la base de données en dehors.

• Effectuer une recherche non récursive, en premier lieu sur l'étendue du champ. De cette façon, vous n'avez besoin de visiter chaque territoire mondial qu'une seule fois au maximum.

• Gardez une liste des territoires que vous avez déjà visités, pour éviter de tourner en rond sans fin, et utilisez un tableau associatif pour cela afin d'obtenir une recherche rapide des clés (au lieu de l'inefficace in_array ). Il ne suffit pas de prendre note d'une $from territoire.

Voici le schéma d'un tel code :

// 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.

Notez que 0 sera retourné pour un territoire (dernier argument) qui est possédé par la faction donnée (deuxième argument). Pour un territoire qui est adjacent à la faction, vous obtiendrez 1, ...etc.