Introduction

La programmation dynamique peut être utilisée pour implémenter des IA de jeu optimales, notamment pour déterminer les chemins les plus courts dans un labyrinthe. Nous allons créer un exemple en JavaScript avec une interface qui permet de visualiser le processus de recherche du chemin le plus court dans un labyrinthe.

Description du Problème

Le problème consiste à trouver le chemin le plus court de l'entrée du labyrinthe à la sortie en utilisant la programmation dynamique. Nous utiliserons l'algorithme de Dijkstra, qui est une approche classique pour ce type de problème.

Implémentation en JavaScript

HTML pour l'Interface de Test

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Labyrinthe - Chemin le Plus Court</title>
    <style>
        body {
            font-family: Arial, sans-serif;
            margin: 20px;
        }
        .grid {
            display: grid;
            grid-template-columns: repeat(10, 30px);
            grid-gap: 2px;
        }
        .cell {
            width: 30px;
            height: 30px;
            display: flex;
            align-items: center;
            justify-content: center;
            border: 1px solid #000;
        }
        .wall {
            background-color: #000;
        }
        .start {
            background-color: #0f0;
        }
        .end {
            background-color: #f00;
        }
        .path {
            background-color: #00f;
        }
    </style>
</head>
<body>
    <h1>Labyrinthe - Chemin le Plus Court</h1>
    <div class="grid" id="maze"></div>
    <button onclick="findShortestPath()">Trouver le Chemin le Plus Court</button>
    <script src="maze.js"></script>
</body>
</html>

JavaScript pour le Labyrinthe et la Recherche de Chemin (maze.js)

// Labyrinthe représenté sous forme de grille 2D
const maze = [
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 0, 1, 1, 1, 1, 1, 0],
    [0, 1, 0, 0, 1, 0, 0, 0, 1, 0],
    [0, 1, 0, 1, 1, 0, 1, 0, 1, 0],
    [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
    [0, 1, 1, 1, 1, 1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 1, 1, 1, 1, 1, 0],
];

// Coordonnées de départ et de fin
const start = [0, 0];
const end = [9, 9];

// Création de la grille HTML
const gridElement = document.getElementById('maze');
function createGrid() {
    gridElement.innerHTML = '';
    for (let i = 0; i < maze.length; i++) {
        for (let j = 0; j < maze[i].length; j++) {
            const cell = document.createElement('div');
            cell.className = 'cell';
            if (maze[i][j] === 1) cell.classList.add('wall');
            if (i === start[0] && j === start[1]) cell.classList.add('start');
            if (i === end[0] && j === end[1]) cell.classList.add('end');
            cell.id = `cell-${i}-${j}`;
            gridElement.appendChild(cell);
        }
    }
}

// Fonction pour trouver le chemin le plus court en utilisant l'algorithme de Dijkstra
function findShortestPath() {
    const rows = maze.length;
    const cols = maze[0].length;
    const distances = Array(rows).fill().map(() => Array(cols).fill(Infinity));
    const visited = Array(rows).fill().map(() => Array(cols).fill(false));
    const previous = Array(rows).fill().map(() => Array(cols).fill(null));

    const queue = [[...start, 0]]; // [row, col, distance]
    distances[start[0]][start[1]] = 0;

    while (queue.length > 0) {
        queue.sort((a, b) => a[2] - b[2]);
        const [row, col, dist] = queue.shift();

        if (visited[row][col]) continue;
        visited[row][col] = true;

        const directions = [
            [0, 1], [1, 0], [0, -1], [-1, 0],
        ];

        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && maze[newRow][newCol] !== 1) {
                const newDist = dist + 1;
                if (newDist < distances[newRow][newCol]) {
                    distances[newRow][newCol] = newDist;
                    previous[newRow][newCol] = [row, col];
                    queue.push([newRow, newCol, newDist]);
                }
            }
        }
    }

    // Reconstruction du chemin le plus court
    let path = [];
    let current = end;
    while (current) {
        path.push(current);
        current = previous[current[0]][current[1]];
    }
    path = path.reverse();

    // Affichage du chemin sur la grille
    for (const [row, col] of path) {
        const cell = document.getElementById(`cell-${row}-${col}`);
        if (!cell.classList.contains('start') && !cell.classList.contains('end')) {
            cell.classList.add('path');
        }
    }
}

// Initialisation de la grille
createGrid();

Explication du Code

  1. Création de la Grille HTML :

    • La grille est générée dynamiquement en fonction du tableau maze.
    • Les murs, le point de départ et le point d'arrivée sont représentés par des classes CSS spécifiques.

  2. Algorithme de Dijkstra :

    • Une matrice distances est utilisée pour mémoriser la distance minimale depuis le point de départ.
    • Une matrice visited garde la trace des cellules déjà visitées.
    • Une matrice previous permet de reconstruire le chemin le plus court.
    • Une file de priorité (queue) est utilisée pour traiter les cellules par ordre de distance croissante.

  3. Recherche et Reconstruction du Chemin :

    • L'algorithme explore les cellules adjacentes pour trouver le chemin le plus court.
    • Une fois le chemin trouvé, il est reconstruit en suivant les cellules précédentes mémorisées.
    • Le chemin est affiché en colorant les cellules correspondantes.

Conclusion

Ce programme utilise la programmation dynamique pour implémenter une IA de jeu capable de trouver le chemin le plus court dans un labyrinthe. L'interface permet de visualiser le labyrinthe et le chemin trouvé, offrant une compréhension claire du fonctionnement de l'algorithme de Dijkstra. Ce type de solution est applicable à de nombreux problèmes de cheminement et d'optimisation dans le domaine des jeux vidéo et au-delà.

Modifié le: lundi 3 juin 2024, 08:28