Algorithme

Donjon Aléatoire

19 octobre 2014 09:12 root Algorithme, Java, Jeux

Cela fait un moment que je cherche à implémenter mon propre algorithme de création de donjon pour faire un jeux type PMT (Porte Monstre Trésors). J'ai fais beaucoup d'essai et de recherche, j'ai trouvé plein d’algorithme, je m'en suis inspiré pour faire mon générateur. Que je vous propose aujourd'hui.

Code :: Structure

Je commence par définir la structure. Donc une carte de donjon est un simplement un tableau à deux dimension composé d'élément (un mur, du sol, ou encore une porte, un escalier, un coffre...) Pour l'instant je me limite uniquement à la structure même du donjon, pas de monstre ni de trésor ou autre joyeuseté. Je peu donc créer la structure du donjon.

Classe :: DungeonEltpublic enum DungeonElt {
  WALL('#', true),
  EMPTY(' ', false),
  DOORV('|', true),
  DOORH('-', true);

  private char graphic;
  private boolean solid;

  private DungeonElt(char graphic, boolean solid) {
    this.graphic = graphic;
    this.solid = solid;
  }

  public char getGraphic() { return graphic; }
  public boolean isSolid() { return solid; }
}
Classe :: Dungeonpublic class Dungeon {
  private DungeonElt[][] maps;

  public Dungeon(int w, int h) {
    maps = new DungeonElt[w][h];
  }

  public int getHeight() { return maps[0].length; }
  public int getWidth() { return maps.length; }
  public void set(int x, int y, DungeonElt elt) { maps[x][y] = elt; }
  public DungeonElt get(int x, int y) { return maps[x][y]; }

  public void print() {
    for (int y = 0; y < getHeight(); y++) {
      for (int x = 0; x < getWidth(); x++) {
        System.out.print(maps[x][y].getGraphic());
      }
      System.out.println();
    }
  }
}

Algorithme :: Principe

Le principe de cet algorithme récursif est de couper la carte en deux récursivement de manière horizontal ou vertical jusqu'à avoir de petite pièces. Puis lors du dépile-ment des récursions nous ajoutons les portes à chaque précédente découpe. C'est un algorithme ressemblant à la construction d'un arbre binaire.

Code :: Base du Générateur

Je vais essayer de décrire cette algorithme étape par étape et en affichant le résultat. Dans cet algorithme, on traite le donjon par partie en le découpant comme je l'ai dis précédemment. Par praticité il est utile de définir une classe Zone pour faciliter ces découpes.

Classe :: DungeonGeneratorpublic class Zone {
  private int sx, ex, sy, ey;

  public Zone(int startx, int endx, int starty, int endy) {
    this.sx = startx; this.ex = endx;
    this.sy = starty; this.ey = endy;
  }

  public int getHeight() { return ey-sy; }
  public int getWidth()  { return ex-sx; }
  public int getStartX() { return sx; }
  public int getEndX()   { return ex; }
  public int getStartY() { return sy; }
  public int getEndY()   { return ey; }
}

Première étapes, générons un donjon de taille aléatoire, qui n'est qu'un block de mur :

Classe :: DungeonGeneratorpublic class DungeonGenerator {
  private static final int MIN_ROOM_SIZE = 3;
  private static final int MIN = 12;
  private static final int MAX = 64;

  public static void main(String[] args) {
    Dungeon dungeon = new DungeonGenerator().generate(new Random(1958));
    dungeon.print();
  }
  public Dungeon generate(Random seed) {
    Dungeon dungeon = new Dungeon(nextInt(seed, MIN, MAX), nextInt(seed, MIN, MAX));
    Zone zone = new Zone(0, dungeon.getWidth() - 1, 0, dungeon.getHeight() - 1);
    fill(dungeon, zone, DungeonElt.WALL);
    return dungeon;
  }

  private void fill(Dungeon dungeon, Zone zone, DungeonElt elt) {
    for (int y = zone.getStartY(); y <= zone.getEndY(); y++) {
      for (int x = zone.getStartX(); x <= zone.getEndX(); x++) {
        dungeon.set(x, y, elt);
      }
    }
  }

  /**
   * Renvoie une valeur aléatoire entre min et max
   */
  private int nextInt(Random seed, int min, int max) {
    return seed.nextInt(max - min) + min;
  }
}

Et voici le résultat, je me suis arranger pour prendre une graine donnant une taille de 12x42 pour l'afficher :