Projet de roguelike
Posté le 26/11/2017 18:35
J'ai commencé la création d'un roguelike en basic casio.
principe du jeu:
une map composée de plusieurs salles est générée procéduralement.
On doit avancer au travers de ces salles pour trouver la sortie en tuant des ennemis, récoltant des pièces, ouvrant des coffres et achetant des objets aux marchants que l'on pourrait rencontrer.
voici l'état actuel du jeu :
génération des salles avec placement des coffres et de la sortie, elle dure environ 5.5s pour 20 salles mais peut prendre 1min45s pour 100 salles(l'algorithme que j'utilise n'est pas super(voir les détails techniques)).
voici une visualisation de l'ensemble des salles ainsi produites avec l'emplacement du joueur dans la salle avec le point(les ouvertures entre les salles ne sont pas montrées).
et on peut se déplacer, ouvrir les coffres(qui ne contiennent rien pour l'instant), et trouver la sortie.
détails techniques :
les salles sont stockées dans une matrice, et toute l'information d'une salle (portes vers les autres salles, coffres, si la sortie se trouve dans cette salle, et plus dans le futur...) est stockée dans une seule case de la matrice, et ces informations peuvent être modifiées au cour de la partie. La sauvegarde des salles prend donc relativement peu de place.
Quant à l'algorithme de génération des salles, il n'est pas très avancé : on prend la salle du milieu de la matrice, on crée une salle dedans en définissant ses attributs aléatoirement puis on se déplace sur une case adjacente aléatoire et on ouvre une porte entre les 2 salles puis on recommence. on continue jusqu'à ce que le nombre désiré de salles est atteint.
le problème de cet algorithme est qu'il est possible de repasser indéfiniment sur les mêmes salles, ce qui rend la génération lente quand il y a beaucoup de salles à créer.
Je me suis d'ailleurs inspiré de
"Zelda - PC" de Remiweb pour les graphismes : les sprites et les murs font la même taille, d'ailleurs pour les combats, je ferai peut être un système similaire.
voilà, c'est tout pour l'instant, n'hésitez pas à poser des questions, faire des suggestions...
(ps: j'ai un peu abandonné space tourist pour le moment, mais peut être que je le finirai plus tard)
Citer : Posté le 26/11/2017 18:42 | #
Pour éviter de passer plusieurs fois par la même salle, tu peux garder à chaque instant en mémoire une liste des salles candidates sous la forme d'une liste de couples (x, y). Au début ce serait uniquement la salle du centre ; ensuite, à chaque étape, une salle aléatoire est tirée dans la liste, retirée de la liste, et toutes les salles voisines pas encores créées sont ajoutées à la liste. Il n'y a pas besoin de tri.
Citer : Posté le 26/11/2017 18:45 | #
Bonne idée, je vais essayer ça.
Citer : Posté le 26/11/2017 18:49 | #
La plupart du temps, il y aura des salles voisines pas encore créées ; tu peux en profiter pour remplacer les coordonnées de la salle choisie par celles d'une de ses voisines candidates au lieu de la supprimer réellement de la liste, ce qui est (à moins que je n'oublie des fonctions) lent.
Citer : Posté le 26/11/2017 18:56 | #
En effet, si tu veux supprimer une valeur dans la liste il faut décaler toutes les valeurs qui sont après, ce qui pourrait être long (après il faut voir combien de salles tu as à générer).
Sinon tu peux aussi essayer l'algorithme du pot de peinture.
Ecrivez vos programmes basic sur PC avec BIDE
Citer : Posté le 26/11/2017 19:03 | #
L'algorithme du pot de peinture?
peux tu m'expliquer le principe s'il te plait?
Citer : Posté le 26/11/2017 19:06 | #
L'algorithme du pot de peinture est déterministe, il ne va pas sortir de map aléatoire tout seul. Annuler de façon aléatoire la peinture lors d'un appel récursif paraît tentant, mais ça resterait mal équilibré (ie. toutes les configurations ne seraient pas du tout équiprobables parce que la direction prise en premier sera favorisée).
Citer : Posté le 26/11/2017 19:15 | #
Dark Storm l'explique ici : https://www.planet-casio.com/Fr/forums/topic14210-1-La-recursivite-en-Basic-Casio.html
Mais c'est vrai qu'il me paraît moins adapté à la génération de salle.
Pour l'adapter à l'aléatoire, tu peux faire une direction aléatoire, puis enfin mettre la salle de début dans une salle aléatoire pour éviter que la première salle n'ait presque toujours qu'une seule porte (la direction choisie en premier).
Ecrivez vos programmes basic sur PC avec BIDE
Citer : Posté le 26/11/2017 19:48 | #
Ok, merci pour les suggestions.
Ajouté le 29/11/2017 à 18:10 :
@Lephenixnoir, j'ai réussi (non sans difficultés) à implémenter ton algorithme.
Il est effectivement plus rapide quand le nombre de salles est important, et l'agencement des salles entre elles est mieux par rapport à l'ancien algorithme. Voici ce qu'on peut obtenir :
pour 20 salles (~5s)
ou bien
pour 100 salles, ce qui peut prendre de 30s à 1min, cet écart de temps est sûrement dû au fait que des salles de la liste peuvent se retrouver bloquées au milieu d'autres salles, et dans ce cas là, elles "polluent" la liste, puisqu'elles ne peuvent pas engendrer d'autres salles. Le fait qu'une salle soit au bord de la matrice contenant les salles augmente ses chances de devenir "infertile", car un de ses côtés ne donnera pas de salle. Augmenter la taille de la matrice peut donc permettre d'accélérer un peu la génération des salles.(j'utilise ici une matrice de 15*15).
Par contre, mon programme est pas très optimisé, il pèse 1884 octets
Citer : Posté le 29/11/2017 18:22 | #
Bien joué ! Un gain de 30 secondes à 1 minute est clairement intéressant. J'aime bien l'aspect des salles aussi ; je me demandais ce que ça allait donner vu que l'aléatoire est pas très contrôlé, mais c'est satisfaisant.
Je ne suis pas sûr que des salles coincées polluent vraiment. Si tu y réfléchis bien, elles sont tout aussi disponibles que les autres, et une fois qu'elles ont été sélectionnées, la liste qu'elles laissent dernière elle a seulement un élément de moins. Ça ne coupe pas l'algorithme dans son « élan ».
Le seul truc un peu embêtant, c'est qu'il faut retirer un élément pour recomposer la liste, et donc déplacer tous ceux qui étaient après. En théorie c'est assez coûteux, en pratique ça tient en une ligne donc je ne suis même pas sûr que ça vaille le coup d'essayer de le changer (sauf si tu as beaucoup de salles dans ta liste). À mon avis, l'ingénierie nécessaire pour passer à une complexité plus faible coûtera plus cher en temps que ce qu'elle permettra de gagner.
Je ne vois pas d'optimisation ou variation de l'algo qui paraisse intéressante, donc pour faire mieux il faudrait plutôt regarder le code. S'il est lourd, il y a peut-être des choses à gagner. On peut le voir ?
Citer : Posté le 29/11/2017 18:37 | #
Voilà le code
{15, 15 -> Dim Mat R
Fill(1111, Mat R
Int (List Ans[1] / 2) -> List 10[2
Int (List Ans[2] / 2) -> List 10[1
List 10[1] -> A
List 10[2] -> B
0000 -> Mat R[B, A
{A + B -> List 1
1 -> D
While D < C
Dim List 1
If Ans > 1 :Then
RanInt#(1, Ans) -> E
Else
1 -> E
IfEnd
ReP List 1[E] -> A
ImP List 1[E] -> B
If &MOD(;Int (Mat R[B, A] / 10 ^ 0), 10) = 0 :Then
If B < List Ans[1] - 1 And Mat R[B + 1, A] = 1111 And D < C :Then
Do
RanInt#(0, 1) -> F
RanInt#(0, 1) -> G
RanInt#(0, 1) -> H
LpWhile F = 1 And G = 1 And H = 1
0 -> Mat R[B + 1, A
F * 10 ^ 0 + Mat R[B + 1, A] -> Mat R[B + 1, A
G * 10 ^ 2 + Mat R[B + 1, A] -> Mat R[B + 1, A]
H * 10 ^ 3 + Mat R[B + 1, A] -> Mat R[B + 1, A]
A + (B + 1) -> List 1[E
Dim List 1 + 1 -> E
D + 1 -> D
Else
&MOD(;Int (Mat R[B + 1, A] / 10 ^ 1), 10) = 1 Or Mat R[B + 1, A] = 1111 => 10 ^ 0 + Mat R[B, A -> Mat R[B, A
IfEnd
IfEnd
If &MOD(;Int (Mat R[B, A] / 10 ^ 1), 10) = 0 :Then
If B > 2 And Mat R[B - 1, A] = 1111 And D < C :Then
Do
RanInt#(0, 1) -> F
RanInt#(0, 1) -> G
RanInt#(0, 1) -> H
LpWhile F = 1 And G = 1 And H = 1
0 -> Mat R[B - 1, A
F * 10 ^ 1 + Mat R[B - 1, A] -> Mat R[B - 1, A]
G * 10 ^ 2 + Mat R[B - 1, A] -> Mat R[B - 1, A]
H * 10 ^ 3 + Mat R[B - 1, A] -> Mat R[B - 1, A]
A + (B - 1) -> List 1[E
Dim List 1 + 1 -> E
D + 1 -> D
Else
&MOD(;Int (Mat R[B - 1, A] / 10 ^ 0), 10) = 1 Or Mat R[B - 1, A] = 1111 => 10 ^ 1 + Mat R[B, A -> Mat R[B, A
IfEnd
IfEnd
If &MOD(;Int (Mat R[B, A] / 10 ^ 2), 10) = 0 :Then
If A > 2 And Mat R[B, A - 1] = 1111 And D < C :Then
Do
RanInt#(0, 1) -> F
RanInt#(0, 1) -> G
RanInt#(0, 1) -> H
LpWhile F = 1 And G = 1 And H = 1
0 -> Mat R[B, A - 1
F * 10 ^ 0 + Mat R[B, A - 1] -> Mat R[B, A - 1]
G * 10 ^ 2 + Mat R[B, A - 1] -> Mat R[B, A - 1]
H * 10 ^ 1 + Mat R[B, A - 1] -> Mat R[B, A - 1]
(A - 1) + B -> List 1[E
Dim List 1 + 1 -> E
D + 1 -> D
Else
&MOD(;Int (Mat R[B, A - 1] / 10 ^ 3), 10) = 1 Or Mat R[B, A - 1] = 1111 => 10 ^ 2 + Mat R[B, A -> Mat R[B, A
IfEnd
IfEnd
If &MOD(;Int (Mat R[B, A] / 10 ^ 3), 10) = 0 :Then
If A < List Ans[2] - 1 And Mat R[B, A + 1] = 1111 And D < C :Then
Do
RanInt#(0, 1) -> F
RanInt#(0, 1) -> G
RanInt#(0, 1) -> H
LpWhile F = 1 And G = 1 And H = 1
0 -> Mat R[B, A + 1
F * 10 ^ 0 + Mat R[B, A + 1] -> Mat R[B, A + 1]
G * 10 ^ 1 + Mat R[B, A + 1] -> Mat R[B, A + 1]
H * 10 ^ 3 + Mat R[B, A + 1] -> Mat R[B, A + 1]
(A + 1) + B -> List 1[E
D + 1 -> D
Else
&MOD(;Int (Mat R[B, A + 1] / 10 ^ 2), 10) = 1 Or Mat R[B, A + 1] = 1111 => 10 ^ 3 + Mat R[B, A -> Mat R[B, A
IfEnd
IfEnd
Locate 1, 1, D
WhileEnd
For 1 -> E To Dim List 1
ReP List 1[E] -> A
ImP List 1[E] -> B
(Mat R[B - 1, A] = 1111 Or &MOD(;Int (Mat R[B - 1, A] / 10 ^ 0), 10) = 1) And &MOD(;Int (Mat R[B, A] / 10 ^ 1), 10) = 0 => Mat R[B, A] + 10 ^ 1 -> Mat R[B, A
(Mat R[B + 1, A] = 1111 Or &MOD(;Int (Mat R[B + 1, A] / 10 ^ 1), 10) = 1) And &MOD(;Int (Mat R[B, A] / 10 ^ 0), 10) = 0 => Mat R[B, A] + 10 ^ 0 -> Mat R[B, A
(Mat R[B, A - 1] = 1111 Or &MOD(;Int (Mat R[B, A - 1] / 10 ^ 3), 10) = 1) And &MOD(;Int (Mat R[B, A] / 10 ^ 2), 10) = 0 => Mat R[B, A] + 10 ^ 2 -> Mat R[B, A
(Mat R[B, A + 1] = 1111 Or &MOD(;Int (Mat R[B, A + 1] / 10 ^ 2), 10) = 1) And &MOD(;Int (Mat R[B, A] / 10 ^ 3), 10) = 0 => Mat R[B, A] + 10 ^ 3 -> Mat R[B, A
Next