Donjon Aléatoire

19 October 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 :

##########################################
##########################################
##########################################
##########################################
##########################################
##########################################
##########################################
##########################################
##########################################
##########################################
##########################################
##########################################

Code :: Récursion & Pièces

Mettons en place la base de la récursion et créons les pièces.

Classe :: DungeonGeneratorpublic Dungeon generate(Random seed) {
  // instanciation et initialisation du donjon (vu précédemment)
  generate(dungeon, zone, seed);
  return dungeon;
}

/**
 * Si il est possible de couper la zone en deux, 
 * on le fait sinon on en crée une pièce
 */
private void generate(Dungeon dungeon, Zone zone, Random seed) {
  if (shouldSplit(zone, seed)) {
    if (zone.getWidth() > zone.getHeight()) {
      splitVertical(dungeon, zone, seed);
    } else {
      splitHorizontal(dungeon, zone, seed);
    }
  } else {
    createRoom(dungeon, zone, seed);
  }
}

/**
 * Pour créer une pièce il suffit d'enlever les murs à l’intérieur
 */
private void createRoom(Dungeon dungeon, Zone zone, Random seed) {
  Zone room = zone.reduce(1, 1);
  fill(dungeon, room, DungeonElt.EMPTY);
}

/**
 * Pour découper une zone en deux, on sélectionne une colonne aléatoirement 
 * respectant la possibilité de créer deux pièces. 
 * Avec les deux zones crées on part en récursion.
 */ 
private void splitVertical(Dungeon dungeon, Zone zone, Random seed) {
  int v = nextInt(seed, zone.getStartX() + MIN_ROOM_SIZE + 1, zone.getEndX() - MIN_ROOM_SIZE);
  for (Zone child : zone.splitVertical(v)) {
    generate(dungeon, child, seed);
  }
}

private void splitHorizontal(Dungeon dungeon, Zone zone, Random seed) {
  int h = nextInt(seed, zone.getStartY() + MIN_ROOM_SIZE + 1, zone.getEndY() - MIN_ROOM_SIZE);
  for (Zone child : zone.splitHorizontal(h)) {
     generate(dungeon, child, seed);
  }
}

/**
 * La zone peu être coupé en deux si elle peu contenir deux pièces
 * de taille minimales en vertical ou en horizontal
 */
private boolean shouldSplit(Zone zone, Random seed) {
  return zone.getWidth() > MIN_ROOM_SIZE * 2 + 1 || zone.getHeight() > MIN_ROOM_SIZE * 2 + 1;
}
Classe :: Zone/**
 * Reduit la taille de la zone dans les deux directions
 */
public Zone reduce(int x, int y) {
  return new Zone(sx + x, ex - x, sy + y, ey - y);
}

/**
 * Coupe la zone en deux suivant la ligne h
 */
public Zone[] splitHorizontal(int h) {
  return new Zone[] { new Zone(sx, ex, sy, h), new Zone(sx, ex, h, ey) };
}

/**
 * Coupe la zone en deux suivant la colonne v
 */
public Zone[] splitVertical(int v) {
  return new Zone[] { new Zone(sx, v, sy, ey), new Zone(v, ex, sy, ey) };
}

Et voici le résultat :

##########################################
#    #   #    #    #     #   #      #    #
#    #   #    #    #     #   #      #    #
#    #   #    #    #     #   #      #    #
#    #   #    #    #     #   #      #    #
#    #####    #    #     #   ########    #
######   ######    #     #   #      ######
#    #   #    ################      #    #
#    #   #    #     #    #   #      #    #
#    #   #    #     #    #   #      #    #
#    #   #    #     #    #   #      #    #
##########################################

Code :: Ajout des Portes

Après chaque récursion il faut ajouter une porte pour permettre de passer d'une pièce crée à l'autre, mais bien sur cette porte doit donnée sur des éléments non solide de chaque coté.

Classe :: DungeonGeneratorprivate void splitVertical(Dungeon dungeon, Zone zone, Random seed) {
  int v = nextInt(seed, zone.getStartX() + MIN_ROOM_SIZE + 1, zone.getEndX() - MIN_ROOM_SIZE);
  for (Zone child : zone.splitVertical(v)) {
    generate(dungeon, child, seed);
  }
  addVerticalDoor(dungeon, zone, seed, v);
}

/**
 * Pour ajouter une porte il faut prende aléatoirement une coordonnée 
 * sur le mur jusqu'à en avoir une ne donnant sur aucun mur des deux cotés
 */
private void addVerticalDoor(Dungeon dungeon, Zone zone, Random seed, int v) {
  int y = 0;
  do {
    y = nextInt(seed, zone.getStartY(), zone.getEndY());
  } while (dungeon.get(v + 1, y).isSolid() || dungeon.get(v - 1, y).isSolid());
  dungeon.set(v, y, DungeonElt.DOORV);
}

private void splitHorizontal(Dungeon dungeon, Zone zone, Random seed) {
  int h = nextInt(seed, zone.getStartY() + MIN_ROOM_SIZE + 1, zone.getEndY() - MIN_ROOM_SIZE);
  for (Zone child : zone.splitHorizontal(h)) {
    generate(dungeon, child, seed);
  }
  addHorizontalDoor(dungeon, zone, seed, h);
}

private void addHorizontalDoor(Dungeon dungeon, Zone zone, Random seed, int h) {
  int x = 0;
  do {
    x = nextInt(seed, zone.getStartX(), zone.getEndX());
  } while (dungeon.get(x, h + 1).isSolid() || dungeon.get(x, h - 1).isSolid());
  dungeon.set(x, h, DungeonElt.DOORH);
}

Et voici le résultat :

##########################################
#    #    #     #    |   |      #    #   #
#    |    #     #    #   #      #    #   #
#    #    #     |    #   #      #    #   #
#    #    #     #    #####-#######-###   #
#    #    ####-#######      #   #    #   #
###-###-###      #   #      #   #    #   #
#    #    |      #   #      #   #    ###-#
#    #    #      #   #      |   |    #   #
#    #    #      |   #      #   #    |   #
#    #    #      #   #      #   #    #   #
##########################################

Code :: Remplir les Pièces

On peu facilement ajouter des coffres, monstres et autres dans les pièces en faisant un peu d'aléatoire.

Classe :: DungeonGeneratorprivate void createRoom(Dungeon dungeon, Zone zone, Random seed) {
  Zone room = zone.reduce(1, 1);
  fill(dungeon, room, DungeonElt.EMPTY);
  if (seed.nextFloat() < .8f) {
    dungeon.set(rndRoomX(room, seed), rndRoomY(room, seed), DungeonElt.MONSTER);
  }
  if (seed.nextFloat() < .1f) {
    dungeon.set(rndRoomX(room, seed), rndRoomY(room, seed), DungeonElt.SAFE);
  }
}

private int rndRoomX(Zone zone, Random seed) {
  return nextInt(seed, zone.getStartX(), zone.getEndX() + 1);
}

private int rndRoomY(Zone zone, Random seed) {
  return nextInt(seed, zone.getStartY(), zone.getEndY() + 1);
}

Et voici le résultat :

##########################################
#    #     #  m#   #      |   m #   |    #
#    #     #   |   #    m #     #   #    #
#   m# m   #   #m  #      #     |   #  m #
#    |     #   #   ####-###     #   #    #
#    #     #   #   #      ##-#### ¤ #    #
###-###-#####-######m     #     #  m#    #
#    #   ¤ #   #   #      #m    ##-#######
#   m#     #   | m #      #     #    #   #
#    #     #  m#   |      #     # m  #   #
#    # m   |   #   #      #     #    |   #
##########################################

Pour aller plus loin :

C'est un premier essai mais je pense qu'il s'agit d'une bonne base. J’espère que ce premier tuto sur de l’algorithmie vous aura plus. On peu bien sur l'améliorer comme créer des portes nécessitant des clefs. Ou aller plus loin dans la création des monstres prévoir des loot etc...

Référence & Ressource :

par Shionn, dernière modification le 20 October 2014 10:42
4 réflexions au sujet de « Donjon Aléatoire »
  • Akio 27 October 2014 19:59

    Tu penses qu'il est possible d'utilisée des fichier tmx pour faire un grand fichier tmx qui place aléatoirmente les different "sous fichier" tmx ?

    Pour comprendre l'idée Rogue Like : comme rogue legacy ou binding of isaac

  • Shionn 28 October 2014 16:19

    Navré je ne vois pas ou tu en venir, Tu voudrait faire que les multiples donjon généré ai une cohérence entre eux ?

  • Akio 28 October 2014 22:27

    En gros préparé des bout de carte sur des .tmx et les assembler ensemble de façon aléatoire mais coherente (dans le sens ou une porte menera forcement vers une salle par exemple). Est-ce que c'est possible du coup de generer un grand tmx avec d'autre tmx ? Ou alors je place des trigger à chaque porte qui dit si tu passe cette porte tu charge tel ou tel tmx

  • Shionn 28 October 2014 22:39

    Si ta question est de savoir si slick ou si le format tmx support ce genre de chose. Non.

    En revanche algorithmiquement c'est tout a fait abordable.

Laissez un commentaire

Vous pouvez utilisez du markdown pour la mise en forme

Votre adresse de messagerie ne sera pas publiée.

Temporairement, pour lutter contre les bots, il n'est pas permis de mettre http:// dans le commentaire.