Home Assistant : le cœur de votre maison connectée

Dans le monde de la domotique, de nombreuses solutions promettent de vous simplifier la vie. Mais peu offrent la puissance, la flexibilité et le respect de la vie privée de Home Assistant. Si vous cherchez à unifier tous vos appareils connectés, à créer des automatisations poussées et à garder le contrôle total sur vos données, alors vous êtes au bon endroit. Découvrons ensemble ce qu’est Home Assistant et comment nos guides peuvent vous aider à vous lancer.

Qu’est-ce que Home Assistant et pourquoi l’adopter ?

Home Assistant est une plateforme domotique open-source et gratuite qui s’installe localement chez vous, par exemple sur un mini-ordinateur comme un Raspberry Pi. [4] Son rôle est de servir de « cerveau » central pour tous vos équipements intelligents (ampoules, prises, thermostats, capteurs, etc.), quelle que soit leur marque. [4, 7]

Les avantages à utiliser Home Assistant sont nombreux et déterminants :

• Confidentialité et contrôle local : Contrairement à de nombreuses solutions cloud, Home Assistant fonctionne chez vous. Vos données ne sont pas envoyées sur des serveurs externes, et votre domotique continue de fonctionner même en cas de coupure Internet. [6]
• Compatibilité universelle : Avec des milliers d’intégrations disponibles, Home Assistant peut communiquer avec une quantité impressionnante d’appareils. [8] Il fait le pont entre des écosystèmes qui, normalement, ne se parlent pas.
• Personnalisation sans limites : De la création de tableaux de bord sur mesure à la mise en place de scénarios complexes basés sur n’importe quel déclencheur, tout est possible. [10]
• Une communauté forte et active : En tant que projet open-source, il bénéficie de la contribution de milliers de passionnés à travers le monde, garantissant des évolutions constantes et une aide précieuse. [5]

Passez à la pratique avec nos guides détaillés

Pour vous aider à exploiter le potentiel de Home Assistant, nous avons préparé des articles qui abordent des problématiques concrètes. Ils sont conçus pour vous faire gagner du temps et vous donner les bonnes pratiques dès le départ.

1. Maîtrisez votre consommation avec une carte de suivi énergétique

L’une des applications les plus utiles de la domotique est le suivi de la consommation électrique. Dans ce guide, nous vous montrons pas à pas comment transformer les données brutes de vos prises connectées en un tableau de bord visuel et interactif. Vous apprendrez à afficher la puissance en temps réel, à estimer les coûts et à identifier les appareils les plus gourmands.

→ Lire l’article : Créer une carte de configuration personnalisée pour les prises de courant

2. Identifiez et listez vos appareils de manière fiable

Pour créer des automatisations, il est crucial de savoir exactement comment s’appellent vos appareils (leur « ID d’entité »). Il peut arriver que les noms techniques diffèrent de ceux que vous avez choisis, créant de la confusion. Cet article vous explique pourquoi ce phénomène se produit et vous montre la méthode la plus simple et la plus sûre pour obtenir la liste correcte et à jour de toutes vos prises, directement depuis l’interface de Home Assistant.

→ Lire l’article : Lister nos prises de courant avec l’API, le guide complet

Quand nous voulons automatiser nos appareils dans Home Assistant, la première étape est souvent d’obtenir une liste fiable de nos entités, comme nos prises connectées (les « switch »). Une méthode qui semble logique serait d’interroger l’API, mais nous avons découvert que cela peut prêter à confusion. Voyons ensemble pourquoi et quelle est la méthode la plus simple et la plus fiable pour y parvenir.

L’explication : pourquoi certains identifiants semblent étranges ?

Nous avons parfois remarqué une différence entre les identifiants de nos prises et ceux listés par certains outils. Cela vient de la manière dont Home Assistant gère les noms et les identifiants (Entity ID) des appareils, surtout après leur première connexion via une intégration comme Zigbee2MQTT.

1. Découverte initiale de l’appareil

Quand nous ajoutons une nouvelle prise, Home Assistant lui crée automatiquement une entité avec un ID par défaut, souvent basé sur son adresse technique (comme l’adresse IEEE Zigbee). C’est pourquoi nous pouvons voir des entrées peu parlantes comme switch.0x70b3d52b601a7af7.

2. Renommage par nos soins

Ensuite, nous allons logiquement dans l’interface de Home Assistant pour trouver ce nouvel appareil et le renommer afin qu’il soit plus facile à identifier. Par exemple :

• Nom convivial : « Cellier Prise Machine Laver »
• ID de l’entité : Nous le changeons pour switch.cellier_prise_machine_laver.

3. Le « fantôme » de l’ancien ID

Voici le point crucial : Home Assistant garde souvent une trace de l’ancien ID (switch.0x70b3d52b601a7af7) mais le désactive. L’entité que nous utilisons au quotidien est bien la nouvelle (switch.cellier_prise_machine_laver). Le problème est que les requêtes brutes sur l’API peuvent lister ces anciens ID « fantômes » qui sont désactivés et cachés dans l’interface, mais toujours présents dans la base de données.

Les entités que nous voyons correctement, comme switch.veranda_prise_armoire ou switch.cuisine_prise_table, sont simplement des appareils pour lesquels nous avons déjà fait ce renommage depuis longtemps.

La Solution : obtenir la liste correcte et active en 30 secondes

La meilleure méthode n’est donc pas de scripter une requête API, mais d’utiliser directement l’interface de Home Assistant. C’est la source de vérité la plus fiable pour connaître l’état actuel de nos entités.

Voici comment nous pouvons obtenir la liste correcte et complète :

1. Allons dans notre interface Home Assistant.
2. Naviguons vers Paramètres > Appareils et services, puis cliquons sur l’onglet Entités.
3. Dans la barre de recherche située en haut de la liste, tapons simplement switch. pour n’afficher que les commutateurs.
4. (Optionnel) Pour être encore plus précis, nous pouvons cliquer sur l’icône de filtre et sélectionner l’intégration qui gère nos prises (par exemple, Zigbee2MQTT, ZHA, Tuya, etc.).

Nous obtiendrons alors la liste exacte de toutes nos entités switch actuellement actives, avec les bons ID que nous avons définis.

C’est la colonne « ID de l’entité » de cette vue filtrée que nous devons utiliser pour toutes nos futures configurations et automatisations.

Cherchons-nous à mieux comprendre et gérer notre consommation électrique ? Grâce à la puissance de Home Assistant et à une carte de configuration personnalisée (config-template-card), il est possible de créer un tableau de bord dynamique et détaillé de nos prises électriques.

Dans cet article, nous allons décortiquer ensemble un exemple de template pour montrer comment nous pouvons regrouper, analyser et afficher les données de nos prises connectées de manière claire et intuitive.

Avant de commencer, assurons-nous d’avoir :

• Home Assistant installé et fonctionnel.
• Des prises connectées (Zigbee, Wi-Fi, etc.) intégrées à Home Assistant et qui remontent la consommation d’énergie (capteurs power et energy).
• La carte config-template-card installée depuis HACS (Home Assistant Community Store).
• Une connaissance de base du langage de templating Jinja2, utilisé par Home Assistant, est un plus !

Comprendre le Template : Notre tableau de bord décortiqué

Avant de nous plonger dans le code, il est essentiel de comprendre comment ce template fonctionne. Il ne s’agit pas d’une simple suite d’instructions, mais d’un petit programme dynamique qui génère une interface riche et interactive. Il utilise le langage de templating Jinja2, intégré à Home Assistant, pour transformer les données brutes de nos capteurs en informations claires et utiles.

Voici une analyse détaillée, section par section, de tout ce que nous pouvons faire et personnaliser.

La Structure de Base : custom:config-template-card

Le cœur de notre installation est cette carte personnalisée. Elle agit comme un « moteur » qui va lire toutes nos entités et régénérer le contenu d’une autre carte (ici, une carte markdown qui interprète du HTML) à chaque changement d’état.

• entities : C’est la liste de surveillance. Nous devons y placer toutes les entités (interrupteurs, capteurs de puissance, etc.) que nous souhaitons utiliser dans notre template. Dès que l’état de l’une d’elles change, toute la carte se met à jour en temps réel.
• card : Définit la carte qui sera affichée. Nous utilisons type: markdown car elle nous offre une liberté totale sur la mise en forme grâce à l’interprétation du HTML.

Section 1 : Définitions & Variables Centrales

Au début du code, nous définissons toutes les variables qui serviront de base à notre tableau de bord. C’est la « centrale de configuration » de notre template.

• {%- set days = ... -%} : Récupère la valeur d’un sélecteur (input_select). Cela nous permet de changer à la volée la période d’analyse de l’historique sans toucher au code.
• {%- set outlets_data = [...] -%} : La variable la plus importante. C’est une liste où l’on associe l’identifiant technique de chaque prise à un nom convivial (ex: 'Salon TV'). Pour ajouter ou modifier une prise, il suffit de le faire dans cette liste !
• {%- set kwh_cost = ... -%} : Ici, nous définissons le coût de notre kilowattheure pour obtenir des estimations financières précises.
• {%- set outlets_total = 12 -%} : Le nombre total de prises listées. Pensez à mettre ce chiffre à jour si vous ajoutez ou supprimez des appareils de la liste outlets_data.
• {%- set unavailable_states = [...] -%} : Une sécurité pour éviter les erreurs de calcul si une prise devient indisponible (unavailable) ou si son état est inconnu (unknown).

Section 2 : Calculs des Totaux

Avant d’afficher quoi que ce soit, le template effectue une première boucle pour calculer toutes les valeurs globales. Cela évite de répéter les mêmes calculs plusieurs fois.

• {%- set total_power = namespace(sum=0) -%} : Nous utilisons un namespace. C’est une astuce Jinja2 pour créer une variable qui peut être modifiée à l’intérieur d’une boucle. Ici, nous créons des « compteurs » pour la puissance totale, l’énergie totale et le nombre de prises allumées.
• {%- for ... -%} ... {%- endfor -%} : La boucle parcourt chaque prise de notre liste outlets_data et additionne les puissances et énergies pour alimenter nos compteurs.

Section 3 : Tableau détaillé des prises

C’est ici que la magie opère pour afficher la liste de tous nos appareils. Le code génère dynamiquement un tableau HTML pour un affichage propre et aligné.

• <thead> <tr> <th>...</th> </tr> </thead> : Ces balises définissent la section d’en-tête de notre tableau.
• {%- for outlet_info in outlets_data -%} : Une seconde boucle parcourt nos prises, mais cette fois pour générer une ligne de tableau (<tr>) pour chaque appareil.
• Icônes dynamiques :
  • switch_icon : Affiche un point vert 🟢 si la prise est allumée, rouge 🔴 si elle est éteinte, et blanc ⚪ si l’état est inconnu.
  • power_icon : Donne un indice visuel de la consommation : un feu 🔥 pour une forte consommation, un éclair ⚡ pour une consommation modérée, et une ampoule 💡 pour une faible consommation.
• {{ power | round(1) }} : Le filtre round(1) permet d’arrondir les chiffres à une décimale pour un affichage plus lisible.

Section 4 : Tableau de Bord Global & Analyse Financière

Cette section reprend les totaux calculés précédemment pour les afficher dans un tableau de synthèse clair, incluant des conversions et estimations.

• Pourcentages et Conversions : Le code calcule le pourcentage de prises actives et convertit la puissance totale de Watts (W) en kilowatts (kW).
• Estimations de Coût : En utilisant notre variable kwh_cost, le template estime le coût financier basé sur la consommation enregistrée (total_energy) et sur la puissance instantanée (total_power).

Section 5 : Analyse Intelligente de la Consommation

Pour aller plus loin qu’un simple affichage, cette section analyse la consommation en temps réel pour identifier les appareils les plus gourmands.

• Catégorisation : Le code utilise une condition if/elif/else pour classer chaque appareil dans l’une des trois listes : « Gros », « Modérés » ou « Faibles » consommateurs.
• Affichage Conditionnel : La section entière, ainsi que chaque catégorie, ne s’affiche que si elle contient au moins un appareil. Notre tableau de bord reste ainsi propre et ne montre que les informations pertinentes.

Section 6 : Recommandations Dynamiques

La touche finale : un tableau de bord qui nous donne des conseils !

• {%- if total_power.sum > 300 -%} : Cette section n’apparaît que si notre consommation totale dépasse un seuil que nous définissons (ici, 300W).
• Message d’alerte : Si le seuil est dépassé, un message formaté en liste à puces (<ul>) apparaît pour nous alerter et nous donner des pistes d’action. C’est l’exemple parfait d’une interface qui s’adapte au contexte.

Nous avons maintenant toutes les clés pour comprendre, adapter et faire évoluer ce template selon nos besoins !

type: custom:config-template-card
entities:
  - input_select.garden_history_days
  - switch.0x70b3d52b601433db
  - sensor.0x70b3d52b601433db_power
  - sensor.0x70b3d52b601433db_energy
  - sensor.0x70b3d52b601433db_linkquality
  - switch.0x70b3d52b601a7af7
  - sensor.0x70b3d52b601a7af7_power
  - sensor.0x70b3d52b601a7af7_energy
  - sensor.0x70b3d52b601a7af7_linkquality
  - switch.0x70b3d52b6017f0cd
  - sensor.0x70b3d52b6017f0cd_power
  - sensor.0x70b3d52b6017f0cd_energy
  - sensor.0x70b3d52b6017f0cd_linkquality
  - switch.0x70b3d52b601a79fc
  - sensor.0x70b3d52b601a79fc_power
  - sensor.0x70b3d52b601a79fc_energy
  - sensor.0x70b3d52b601a79fc_linkquality
  - switch.0x70b3d52b601a7a26
  - sensor.0x70b3d52b601a7a26_power
  - sensor.0x70b3d52b601a7a26_energy
  - sensor.0x70b3d52b601a7a26_linkquality
  - switch.cuisine_prise_table
  - sensor.cuisine_prise_table_power
  - sensor.cuisine_prise_table_energy
  - sensor.cuisine_prise_table_linkquality
  - switch.cuisine_prise_the
  - sensor.cuisine_prise_the_power
  - sensor.cuisine_prise_the_energy
  - sensor.cuisine_prise_the_linkquality
  - switch.cuisine_prise_cafe
  - sensor.cuisine_prise_cafe_power
  - sensor.cuisine_prise_cafe_energy
  - sensor.cuisine_prise_cafe_linkquality
  - switch.veranda_prise_piscine
  - sensor.veranda_prise_piscine_power
  - sensor.veranda_prise_piscine_energy
  - sensor.veranda_prise_piscine_linkquality
  - switch.veranda_prise_armoire
  - sensor.veranda_prise_armoire_power
  - sensor.veranda_prise_armoire_energy
  - sensor.veranda_prise_armoire_linkquality
  - switch.jardin_prise_ikea
  - sensor.jardin_prise_ikea_power
  - sensor.jardin_prise_ikea_energy
  - sensor.jardin_prise_ikea_linkquality
  - switch.0x70b3d52b601440c9
  - sensor.0x70b3d52b601440c9_power
  - sensor.0x70b3d52b601440c9_energy
card:
  type: markdown
  title: 🔌 Prises Électriques
  content: >
    {%- set days = states('input_select.garden_history_days') | int(3) -%}
    {%- set now_time = now() -%}
    {%- set start_date = (now_time - timedelta(days=days)).strftime('%Y-%m-%dT%H:%M:%S.001Z') -%}
    {%- set end_date = (now_time - timedelta(minutes=10)).strftime('%Y-%m-%dT%H:%M:%S.001Z') -%}
    {%- set date_params = '&start_date=' ~ start_date ~ '&end_date=' ~ end_date -%}
    {%- set outlets_data = [
      ['0x70b3d52b601433db', 'Salon TV'],
      ['0x70b3d52b601a7af7', 'M. à laver'],  
      ['0x70b3d52b6017f0cd', 'Grille-Pain'],
      ['0x70b3d52b601a79fc', 'Congélateur'],
      ['0x70b3d52b601a7a26', 'Frigo'],
      ['cuisine_prise_table', 'Cuisine Table'],
      ['cuisine_prise_the', 'Cuisine Thé'],
      ['cuisine_prise_cafe', 'Cuisine Café'],
      ['veranda_prise_piscine', 'Piscine'],
      ['veranda_prise_armoire', 'Veranda bas'],
      ['jardin_prise_ikea', 'Jardin IKEA'],
      ['0x70b3d52b601440c9', 'Prise ?']
    ] -%}
    {%- set kwh_cost = 0.15 -%}
    {%- set outlets_total = 12 -%}
    {%- set unavailable_states = ['unavailable', 'unknown', 'none'] -%}

    <div>
      <div> 📅 <strong>Historique : {{ days }} jour{{ 's' if days > 1 else '' }}</strong> </div>
      <table>
        <thead>
          <tr>
            <th>Prise</th>
            <th>Temps Réel</th>
            <th>Total</th>
            <th>LQI</th>
          </tr>
        </thead>
        <tbody>
          {%- for outlet_info in outlets_data %}
            {%- set outlet_id = outlet_info[0] -%}
            {%- set outlet_name = outlet_info[1] -%}
            {%- set power_state = states('sensor.' ~ outlet_id ~ '_power') -%}
            {%- set energy_state = states('sensor.' ~ outlet_id ~ '_energy') -%}
            {%- set lqi_state = states('sensor.' ~ outlet_id ~ '_linkquality') -%}
            {%- set switch_state = states('switch.' ~ outlet_id) -%}
            {%- set power = power_state | float(0) if power_state not in unavailable_states else 0 -%}
            {%- set energy = energy_state | float(0) if energy_state not in unavailable_states else 0 -%}
            {%- set lqi = lqi_state | int(0) if lqi_state not in unavailable_states else 0 -%}
            {%- set switch_icon = '🟢' if switch_state == 'on' else '🔴' if switch_state == 'off' else '⚪' -%}
            {%- set power_icon = '🔥' if power > 100 else '⚡' if power > 50 else '💡' if power > 0 else '⚪' -%}
            {%- set history_url = '/history?entity_id=sensor.' ~ outlet_id ~ '_power,sensor.' ~ outlet_id ~ '_energy' ~ date_params -%}
            <tr>
              <td>{{ switch_icon }} {{ outlet_name }}</td>
              <td>{{ power_icon }} <a href="{{ history_url }}"> {{ power }}W</a></td>
              <td><a href="{{ history_url }}">{{ energy | round(2) }} kWh</a></td>
              <td>📊 <a href="{{ history_url }}">{{ lqi }}</a></td>
            </tr>
          {%- endfor %}
        </tbody>
      </table>

      {%- set total_power = namespace(sum=0) -%}
      {%- set total_energy = namespace(sum=0) -%}
      {%- set outlets_on = namespace(count=0) -%}
      {%- for outlet_info in outlets_data -%}
        {%- set outlet_id = outlet_info[0] -%}
        {%- set switch_state = states('switch.' ~ outlet_id) -%}
        {%- set power_state = states('sensor.' ~ outlet_id ~ '_power') -%}
        {%- set energy_state = states('sensor.' ~ outlet_id ~ '_energy') -%}
        {%- set is_on = switch_state == 'on' -%}
        {%- set power = power_state | float(0) if power_state not in unavailable_states else 0 -%}
        {%- set energy = energy_state | float(0) if energy_state not in unavailable_states else 0 -%}
        {%- if is_on -%}
          {%- set outlets_on.count = outlets_on.count + 1 -%}
        {%- endif -%}
        {%- set total_power.sum = total_power.sum + power -%}
        {%- set total_energy.sum = total_energy.sum + energy -%}
      {%- endfor %}

      <h3>⚡ Tableau de Bord Électrique</h3>
      <table>
        <thead>
          <tr>
            <th>📊 Métriques</th>
            <th>Valeur</th>
            <th>Détail</th>
          </tr>
        </thead>
        <tbody>
          <tr>
            <td>🔌 Prises Actives</td>
            <td>{{ outlets_on.count }} / {{ outlets_total }}</td>
            <td>{{ ((outlets_on.count / outlets_total) * 100) | round(1) }}%</td>
          </tr>
          <tr>
            <td>⚡ Puissance Totale</td>
            <td>{{ total_power.sum | round(1) }}W</td>
            <td>{{ (total_power.sum / 1000) | round(2) }} kW</td>
          </tr>
          <tr>
            <td>📈 Consommation Totale</td>
            <td>{{ total_energy.sum | round(1) }} kWh</td>
            <td>≈ {{ (total_energy.sum * kwh_cost) | round(2) }}€</td>
          </tr>
          <tr>
            <td>⏱️  Coût Journalier Estimé</td>
            <td>{{ ((total_power.sum * 24 / 1000) * kwh_cost) | round(2) }}€</td>
            <td>{{ (total_power.sum * 24 / 1000) | round(2) }} kWh/j</td>
          </tr>
        </tbody>
      </table>
      {%- set high_consumers = [] -%}
      {%- set medium_consumers = [] -%}
      {%- set low_consumers = [] -%}
      {%- for outlet_info in outlets_data -%}
        {%- set outlet_id = outlet_info[0] -%}
        {%- set outlet_name = outlet_info[1] -%}
        {%- set power = states('sensor.' ~ outlet_id ~ '_power') | float(0) -%}
        {%- if power > 50 -%}
          {%- set high_consumers = high_consumers + [outlet_name ~ ' (' ~ power ~ 'W)'] -%}
        {%- elif power > 5 -%}
          {%- set medium_consumers = medium_consumers + [outlet_name ~ ' (' ~ power ~ 'W)'] -%}
        {%- elif power > 0 -%}
          {%- set low_consumers = low_consumers + [outlet_name ~ ' (' ~ power ~ 'W)'] -%}
        {%- endif -%}
      {%- endfor -%}

      {%- if high_consumers | length > 0 or medium_consumers | length > 0 -%}
        <h3>🔥 Analyse de Consommation</h3>
        {%- if high_consumers | length > 0 -%}
          <div><strong>🔴 Gros Consommateurs (>50W) :</strong><br>
            {%- for consumer in high_consumers %}
              <span>• {{ consumer }}</span>
            {%- endfor %}
          </div>
        {%- endif -%}
        {%- if medium_consumers | length > 0 -%}
          <div><strong>🟡 Consommateurs Modérés (5-50W) :</strong><br>
            {%- for consumer in medium_consumers %}
              <span>• {{ consumer }}</span>
            {%- endfor %}
          </div>
        {%- endif -%}
        {%- if low_consumers | length > 0 -%}
          <div><strong>🟢 Faible Consommation (<5W) :</strong><br>
            {%- for consumer in low_consumers %}
              <span>• {{ consumer }}</span>
            {%- endfor %}
          </div>
        {%- endif -%}
      {%- endif -%}

      {%- if total_power.sum > 300 -%}
        <h3>💡 Recommandations</h3>
        <div>
          <ul>
            <li>⚠️ Consommation élevée détectée ({{ total_power.sum | round(1) }}W)</li>
            <li>🔍 Vérifiez les appareils en veille non nécessaires</li>
            <li>⏰ Programmez les gros consommateurs aux heures creuses</li>
            <li>📊 Surveillez l'évolution sur {{ days }} jours</li>
          </ul>
        </div>
      {%- endif -%}
    </div>

Labyrinthes : différents algorithmes

Tableau comparatif des algorithmes

Traduit en Français par moi-même. Les originaux sont fici.
Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Caractéristiques des algorithmes de création de labyrinthes parfaits

Ce tableau résume les caractéristiques des algorithmes de création de labyrinthes parfaits mentionnés ci-dessus. L’algorithme de labyrinthe unicursal (les labyrinthes unicursaux sont techniquement parfaits) est inclus à titre de comparaison. Voici les descriptions des colonnes :

Impasses : C’est le pourcentage approximatif de cellules qui sont des impasses dans un labyrinthe créé avec cet algorithme, lorsqu’il est appliqué à un labyrinthe orthogonal 2D. Les algorithmes dans le tableau sont triés selon ce critère. Généralement, créer en ajoutant des murs donne le même résultat que creuser des passages, cependant si la différence est significative, le pourcentage d’ajout de murs est indiqué entre parenthèses. La valeur de l’Arbre qui grandit peut en réalité varier de 10% (toujours choisir la cellule la plus récente) à 49% (toujours échanger avec la cellule la plus ancienne). Avec un facteur de course suffisamment élevé, le Retour-récursif peut descendre en dessous de 1%. Le pourcentage maximum possible d’impasses dans un labyrinthe parfait orthogonal 2D est de 66%, ce qui correspondrait à un passage unicursal avec une série d’impasses d’une unité de longueur de chaque côté.

Type : Il existe deux types d’algorithmes de création de labyrinthes parfaits : Un algorithme basé sur les arbres fait croître le labyrinthe comme un arbre, ajoutant toujours à ce qui est déjà présent, ayant un labyrinthe parfait valide à chaque étape. Un algorithme basé sur les ensembles construit où il le souhaite, gardant la trace des parties du labyrinthe qui sont connectées entre elles, pour s’assurer qu’il peut tout relier pour former un labyrinthe valide une fois terminé. Certains algorithmes comme la Forêt qui grandit font les deux en même temps.

Focus : La plupart des algorithmes peuvent être implémentés soit en creusant des passages, soit en ajoutant des murs. Quelques-uns ne peuvent être réalisés que d’une seule manière. Les labyrinthes unicursaux sont toujours créés par ajout de murs puisqu’ils impliquent de bissecter des passages avec des murs, bien que le labyrinthe de base puisse être créé des deux façons. Le Retour-récursif ne peut pas être fait en ajoutant des murs car cela tend à donner un chemin solution qui suit le bord extérieur, où l’intérieur entier du labyrinthe est attaché à la bordure par une seule tige. De même, la Division récursive ne peut être faite qu’en ajoutant des murs en raison de son comportement de bissection. Chasse et tue est techniquement uniquement réalisé par creusement de passages pour une raison similaire, bien qu’il puisse être fait par ajout de murs si un effort particulier est fait pour croître vers l’intérieur depuis tous les murs frontières de manière égale.

Sans biais : Ceci indique si l’algorithme traite toutes les directions et tous les côtés du labyrinthe de manière égale, où l’analyse du labyrinthe après coup ne peut révéler aucun biais de passage. L’Arbre binaire est extrêmement biaisé, où il est facile de voyager vers un coin et difficile vers son opposé. Le Sidewinder est également biaisé, où il est facile de voyager vers un bord et difficile vers son opposé. L’algorithme d’Eller tend à avoir un passage à peu près parallèle aux bords de début ou de fin. Chasse et tue est sans biais, tant que la chasse est faite colonne par colonne ainsi que ligne par ligne pour éviter un léger biais le long d’un axe.

Uniforme : Ceci indique si l’algorithme génère tous les labyrinthes possibles avec une probabilité égale. « Oui » signifie que l’algorithme est complètement uniforme. « Non » signifie que l’algorithme peut potentiellement générer tous les labyrinthes possibles dans un espace donné, mais pas avec une probabilité égale. « Jamais » signifie qu’il existe des labyrinthes possibles que l’algorithme ne peut jamais générer. Notez que seuls les algorithmes sans biais peuvent être complètement uniformes.

Mémoire : C’est la quantité de mémoire supplémentaire ou de pile nécessaire pour implémenter l’algorithme. Les algorithmes efficaces ne requièrent et ne regardent que la bitmap du labyrinthe elle-même, tandis que d’autres nécessitent un stockage proportionnel à une seule ligne (N), ou proportionnel au nombre de cellules (N^2). Certains algorithmes n’ont même pas besoin d’avoir le labyrinthe entier en mémoire et peuvent être étendus indéfiniment (ceux-ci sont marqués d’un astérisque). L’algorithme d’Eller nécessite le stockage d’une ligne, mais compense largement cela puisqu’il n’a besoin de stocker que la ligne courante du labyrinthe en mémoire. Sidewinder n’a également besoin de stocker qu’une ligne du labyrinthe, tandis que l’Arbre binaire n’a besoin que de garder trace de la cellule courante. La Division récursive nécessite une pile jusqu’à la taille d’une ligne, mais à part cela n’a pas besoin de regarder la bitmap du labyrinthe.

Temps : Ceci donne une idée du temps nécessaire pour créer un labyrinthe avec cet algorithme, les nombres plus bas étant plus rapides. Les nombres sont seulement relatifs les uns aux autres (l’algorithme le plus rapide étant assigné à la vitesse 10) plutôt qu’en unités spécifiques, car le temps dépend de la taille du labyrinthe et de la vitesse de l’ordinateur. Ces nombres proviennent de la création de labyrinthes de passages 100×100 dans la dernière version de Daedalus. Généralement, créer en ajoutant des murs prend le même temps que creuser des passages, cependant si la différence est significative, le temps d’ajout de murs est indiqué entre parenthèses.

Solution : C’est le pourcentage de cellules du labyrinthe que le chemin solution traverse, pour un labyrinthe typique créé par l’algorithme. Cela suppose que le labyrinthe fait 100×100 passages avec le début et la fin dans des coins opposés. C’est une mesure de la « sinuosité » du chemin solution. Les labyrinthes unicursaux ont une sinuosité maximale, puisque la solution traverse l’ensemble du labyrinthe. L’Arbre binaire a la sinuosité minimale possible, où le chemin solution traverse simplement le labyrinthe et ne dévie jamais ou ne cesse jamais de progresser vers la fin. Généralement, créer en ajoutant des murs a les mêmes propriétés que creuser des passages, cependant si la différence est significative, le pourcentage d’ajout de murs est indiqué entre parenthèses.

Source : C’est la source de l’algorithme, ce qui signifie par qui il est nommé, ou qui l’a inventé ou popularisé. Certains sont listés comme « génériques », ce qui signifie qu’ils sont si évidents qu’ils ont été imaginés ou implémentés par de nombreuses personnes indépendamment. Walter Pullen a nommé « Chasse et tue », mais n’a pas inventé la technique, dont on peut trouver des implémentations datant de nombreuses années.

Labyrinthes : différents algorithmes

Labyrinthe Sidewinder

Traduit en Français par moi-même. Les originaux sont ici.
Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Labyrinthe Sidewinder

Cet algorithme simple est très similaire à l’algorithme de l’arbre binaire, et seulement légèrement plus compliqué. Le labyrinthe est généré ligne par ligne : Pour chaque cellule, décidez au hasard de creuser un passage vers la droite. Si un passage n’est pas creusé, alors considérez le passage horizontal qui vient d’être complété, formé par la cellule actuelle et toutes les cellules à gauche qui ont creusé des passages menant jusqu’à elle. Choisissez au hasard une cellule le long de ce passage, et creusez un passage vers le haut à partir de celle-ci (qui doit être la cellule actuelle si la cellule adjacente n’a pas creusé). Alors qu’un labyrinthe en arbre binaire monte toujours depuis la cellule la plus à gauche d’un passage horizontal, un labyrinthe Sidewinder monte depuis une cellule aléatoire. Alors qu’un arbre binaire a les bords supérieur et gauche du labyrinthe formant un long passage, un labyrinthe Sidewinder n’a que le bord supérieur formant un long passage. Comme l’arbre binaire, un labyrinthe Sidewinder peut être résolu de manière déterministe sans erreur de bas en haut, car à chaque ligne, il y aura toujours exactement un passage menant vers le haut. Une solution à un labyrinthe Sidewinder ne reviendra jamais sur elle-même ou ne visitera jamais une ligne plus d’une fois, bien qu’elle « serpente de côté en côté ». Le seul type de cellule qui ne peut pas exister dans un labyrinthe Sidewinder est une impasse avec le passage orienté vers le bas, car cela contredirait le fait que chaque passage montant mène au début. Un labyrinthe Sidewinder a tendance à avoir une solution élitiste, où le bon chemin est très direct, mais il y a beaucoup de longs faux chemins descendant du haut à côté de lui.

Labyrinthes : différents algorithmes

Labyrinthes en arbre binaire

Traduit en Français par moi-même. Les originaux sont ici.
Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Labyrinthes en arbre binaire

C’est fondamentalement l’algorithme le plus simple et le plus rapide possible, cependant les labyrinthes qu’il produit ont une texture très biaisée. Pour chaque cellule, creusez un passage soit vers le haut, soit vers la gauche, mais pas les deux. Dans la version avec ajout de murs, pour chaque sommet ajoutez un segment de mur menant vers le bas ou vers la droite, mais pas les deux. Chaque cellule est indépendante de toutes les autres cellules, où vous n’avez pas besoin de vous référer à l’état des autres cellules lors de sa création. Par conséquent, c’est un véritable algorithme de génération de labyrinthe sans mémoire, sans limite de taille du labyrinthe que vous pouvez créer.
C’est fondamentalement un arbre binaire au sens informatique, si vous considérez le coin supérieur gauche comme la racine, où chaque nœud ou cellule a un parent unique qui est la cellule au-dessus ou à gauche de celle-ci. Les labyrinthes en arbre binaire sont différents des labyrinthes parfaits standards, puisqu’environ la moitié des types de cellules ne peuvent jamais exister en eux. Par exemple, il n’y aura jamais de carrefour, et toutes les impasses ont des passages pointant vers le haut ou vers la gauche, et jamais vers le bas ou vers la droite.
Le labyrinthe a tendance à avoir des passages menant en diagonale du coin supérieur gauche au coin inférieur droit, ce qui rend le labyrinthe beaucoup plus facile à naviguer du coin inférieur droit vers le coin supérieur gauche. Vous pourrez toujours voyager vers le haut ou vers la gauche, mais jamais les deux, donc vous pouvez toujours voyager de manière déterministe en diagonale vers le haut et vers la gauche sans rencontrer d’obstacles. C’est en voyageant vers le bas et vers la droite que vous rencontrerez des choix et des impasses. Notez que si vous retournez un labyrinthe en arbre binaire à l’envers et traitez les passages comme des murs et vice versa, le résultat est fondamentalement un autre arbre binaire.

Labyrinthes : différents algorithmes

Algorithme de la Division récursive

Traduit en Français par moi-même. Les originaux sont ici.
Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Algorithme de la Division récursive

Cet algorithme est un peu similaire au retour-récursif, puisqu’ils sont tous deux basés sur une pile, sauf que celui-ci se concentre sur les murs plutôt que sur les passages. Commencez par créer un mur horizontal ou vertical aléatoire traversant la zone disponible dans une rangée ou une colonne aléatoire, avec une ouverture placée au hasard le long de celui-ci. Ensuite, répétez le processus de manière récursive sur les deux sous-zones générées par le mur de division. Pour de meilleurs résultats, privilégiez le choix horizontal ou vertical en fonction des proportions de la zone, par exemple une zone deux fois plus large que haute devrait être divisée plus souvent par un mur vertical. C’est l’algorithme le plus rapide sans biais directionnel, et peut même rivaliser avec les labyrinthes en arbre binaire car il peut terminer plusieurs cellules à la fois, bien qu’il ait le défaut évident de longs murs traversant l’intérieur. Cet algorithme est une forme de labyrinthes fractals imbriqués, sauf qu’au lieu de toujours créer des labyrinthes de taille de cellule fixe avec des labyrinthes de même taille dans chaque cellule, il divise la zone donnée de manière aléatoire en un labyrinthe de taille aléatoire 1×2 ou 2×1. La division récursive ne fonctionne pas comme un creuseur de passages, car cela aboutirait à un chemin de solution évident qui suit soit le bord extérieur, soit traverse directement l’intérieur.

Labyrinthes : différents algorithmes

Algorithme de Prim (modifié)

Traduit en Français par moi-même. Les originaux sont ici.
Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Algorithme de Prim (modifié)

C’est l’algorithme de Prim pour produire un arbre couvrant minimal, modifié de sorte que tous les poids des arêtes soient les mêmes, mais également implémenté en regardant les cellules plutôt que les arêtes. Il nécessite un espace de stockage proportionnel à la taille du labyrinthe. Pendant la création, chaque cellule est d’un des trois types : (1) « Dedans » : La cellule fait partie du labyrinthe et a déjà été creusée, (2) « Frontière » : La cellule ne fait pas partie du labyrinthe et n’a pas encore été creusée, mais est à côté d’une cellule qui est déjà « dedans », et (3) « Dehors » : La cellule ne fait pas encore partie du labyrinthe, et aucun de ses voisins n’est « dedans » non plus.

Commencez par choisir une cellule, la mettre « dedans », et définir tous ses voisins comme « frontière ». Continuez en choisissant une cellule « frontière » au hasard, et en creusant vers elle à partir d’une de ses cellules voisines qui sont « dedans ». Changez cette cellule « frontière » en « dedans », et mettez à jour tous ses voisins qui sont « dehors » en « frontière ». Le labyrinthe est terminé quand il n’y a plus de cellules « frontière » (ce qui signifie qu’il n’y a plus de cellules « dehors » non plus, donc elles sont toutes « dedans »).

Cet algorithme donne des labyrinthes avec un facteur « rivière » très bas avec beaucoup d’impasses courtes, et une solution plutôt directe. Le labyrinthe résultant est très similaire à l’algorithme de Prim simplifié, avec seulement la subtile distinction que les indentations dans l’arbre en expansion ne sont remplies que si cette cellule frontière est sélectionnée au hasard, contrairement au fait d’avoir trois fois plus de chances de remplir cette cellule via une des arêtes frontières menant à elle. Il s’exécute également très rapidement, plus rapidement que l’algorithme de Prim simplifié car il n’a pas besoin de composer et de maintenir une liste d’arêtes.