SKBN: Un clone de Sokoban pour la Sega Master System

Présentation

SKBN v2

SKBN v2

raphnet level 90

raphnet level 90


SKBN est un clone de Sokoban pour Sega Master System. La première version est parue en 2021 pour le concours de programmation smspower.org. La version actuelle (version 2) offre quelques nouveautés:
  • Davantage de niveaux! Désormais 1736 en tout!
    Jacques Duthen m'a envoyé des niveaux inédits (Sokogen 990702, 990917 et 991123) et j'ai créé ma propre série de 100 niveaux pour la plupart très faciles (raphnet 100).
  • Nouveaux thèmes
    Un total de 4 thèmes sont disponible (V2, V1, Mac et KSoko) dans le menu options.
    Thème V2

    Thème V2

    Thème V1

    Thème V1

    Thème Mac

    Thème Mac

    Thème KSoko

    Thème KSoko

  • Mode pointeur
    Disponible via le menu options, le mode pointeur (vs. marche) où il suffit de pointer l'endroit où le personnage doit se rendre. Le jeu trouve le chemin le plus rapide automatiquement. Pour pousser une caisse, il suffit de cliquer sur celle-ci lorsque le joueur est à côté.
  • Support du Sports Pad et de la Mega Mouse[1]
    Ces périphériques sont parfait pour contrôler un pointeur, ils sont supportés et détectés automatiquement au démarrage dans le port 1 ou 2.
    Mouse and Sports Pad

    Mouse and Sports Pad


  • Nouvel écran titre
    J'ai refait l'écran titre car je n'aimais pas vraiment l'ancien.
[1] La souris Mega Mouse ne fonctionne que sur les consoles Master System et ne peut pas être utilisée sur les systèmes Mark III.


Screenshots (v2)

Écran titre V2

Écran titre V2

Collections

Collections

Collections

Collections

Prévisualisation

Prévisualisation

Crédits

Crédits

Crédits

Crédits

Thème V2

Thème V2

Thème V2

Thème V2

Thème V2

Thème V2

Thème V2

Thème V2

Thème Mac

Thème Mac

Thème Mac

Thème Mac

Thème KSoko

Thème KSoko



Notes de développement / Historique (v2)

Lorsque je développe un jeu, souvent c'est un petit détail ou défi technique qui me motive. Pour la version 1, mon défi était de supporter des tuiles de différentes tailles malgré que la SMS ne supporte que des tuiles de 8x8. Ceci a rendu le codage des engins d'affichage pour les niveaux en tuiles 4x4 et 12x12 très intéressant.

Pour la version 2, je voulais implémenter un système de recherche du chemin le plus court afin de moderniser un peu les commandes du jeu. De nos jours, dans plusieurs version en ligne ou sur mobile, ce jeu est contrôlé à l'aide d'un pointeur. Il suffit donc de pointer l'endroit où l'on souhaite que le personnage se rende pour qu'il s'y déplace - bien entendu seulement si un chemin existe. Ce système me plaît énormément car cela sauve beaucoup d'opérations et de temps.

Mon défi cette fois était donc d'apprendre comment les algorithmes de recherche de chemin fonctionnent et d'en choisir ou modifier un conformément aux contraintes mémoire de la SMS. Cela s'est avéré plus facile que je ne le pensais. J'ai mis en place quelque-chose qui ressemble à l'exemple "Sample algorithm" de la page Wikipedia sur le Pathfinding.

Pendant la recherche, il faut pouvoir stocker une distance pour chaque emplacement. La SMS n'a que 8ko de mémoire vive, et dans ce projet c'était déjà serré. Mais j'ai réussi à me servir d'espace inutilisé, notamment dans un tableau d'octet de 64 par 48 dans lequel l'état du niveau est stocké. Chaque octet représente s'il s'agit d'un mur, d'un plancher, d'une cible, d'une caisse, d'une caisse sur une cible, ou de l'extérieur. Je ne me servais que de 3 bits, les 5 bits du haut était donc libre, c'est donc à cet endroit que j'enregistre la distance. Pas besoin d'un nouveau tableau!

Les algos de recherche de chemin utilisent souvent une liste des prochains emplacement à examiner, mais je ne savais pas quel était l'espace maximal qu'il faudrait prévoir pour cette liste qui permettrait à l'algorithme de fonctionner pour tous les niveaux, mêmes les plus grands, ni si j'aurais assez de mémoire pour cette liste... J'ai donc trouvé une manière de ne pas avoir de liste, en parcourant l'entièreté du tableau à chaque itération à la recherche des prochains canditats.

Stage 1: Préparation
  1. Initialiser la distance de tous les emplacements du niveau comme étant 0
  2. Mettre à 1 la distance des cellules en haut/bas/gauche/droite du joueur, seulement si elles sont "marchables" (marchable = placher ou cible)
  3. Assigner une valeur de 1 à la variable cur_distance (distance courante)

Stage 2: Recherche jusqu'à la destination
Pour chaque emplacement dans la grille du tableau où la distance = cur_distance, faire ceci:
(S'il n'y aucun voisin donc la distance = cur_distance, il n'y a pas de chemin. Abandonner.)
  1. Assigner une distance de cur_distance+1 à tous les voisins marchables dont la distance est actuellement 0.
  2. Si un des voisins est la destination, arrêter ici et passer au stage 3.
  3. Augmenter cur_distance de 1. Si cur_distance dépasse 30, (le maximum -1 pouvant tenir dans 5 bits) assigner 1. (pas 0)
  4. Répéter.

Stage 3: Retracer et marquer le chemin
À ce stage, la destination a été atteinte. Il est temps de marquer le chemin que le joueur devra suivre. La valeur de distance 31 est réservée pour cela. Assigner à la variable cur_distance la distance enregistrée à la cible, puis mettre la distance de la cible à 31 (marqueur de chemin). Ensuite, en commençant avec destination comme emplacement courant:
  1. Inspecter les voisins et en choisir un dont la distance = cur_distance - 1 (ou 30, si cur_distance est 1). S'il y a plusieurs canditats, n'importe lequel fonctionnera. Mettre la distance du voisin choisi à 31 (marqueur de chemin)
  2. Le voisin sélectionné devient l'emplacement courant
  3. Décrémenter cur_distance. Si la valeur tombe à 0, la mettre à 30.
  4. Répéter à partir de l'étape 1 jusqu'à ce que le point de départ soit atteint.

Stage 4: Déplacer le joueur le long du chemin marqué
À ce stage, le joueur n'a qu'à suivre les marqueurs de chemin. Donc en commençant à l'endroit ou le joueur est placé:
  1. Regarder les voisins et trouver celui avec le marqueur de chemin (31).
  2. Déplacer le joueur à cet endroit.
  3. Effacer le marqueur de chemin.
  4. Répéter jusqu'à ce qu'il n'y ait plus de voisins avec un marqueur. Le joueur sera sur la cible.

L'algo décrit ci-dessus fonctionnait bien, mais il était un peu trop lent en raison de l'opération de balayage du tableau de jeu complet à chaque itération du stage 2. J'ai donc créé une petite liste permettant de mémoriser les prochains emplacement à examiner. La liste est très courte (pour ne pas occuper trop de mémoire), alors si elle déborde, la stratégie initiale de balayer le tableau au complet est employée.

Une fois cela en place, il me restait à ajouter le support pour des périphériques de pointages, tels que le Sports Pad et la Mega Mouse. J'ai été agréablement surpris par le Sports Pad. Mon expérience avec le jeu "Sports Pad Soccer" avait fait mauvaise impression... mais utilisé comme un trackball pour déplacer un pointeur, le Sports Pad est en fait très bien!

Voici un vidéo où l'algorithme de recherche est mis à l'épreuve. Marcher autour des murs avec l'ancienne méthode serait un peu déplaisante n'est-ce pas?


Notes de développement / Historique (v1)

écran titre, version 1.4
Et oui, un clone de plus du jeu Sokoban... mais celui-ci a perdu ses voyelles ;-)

SKBN est un clone de sokoban nommé SKBN qui tourne sur la Sega Master System. Le ROM de 128ko contient entre autre les 1043 niveaux des collections Microban et Sasquatch par David W. Skinner.

Un de mes buts dans ce projet était de faire en sorte que la totalité de ces niveaux soient jouables, mêmes ceux de large taille.

Pour y arriver, l'engin supporte différentes tailles de tuiles: 24x24, 16x16, 12x12, 8x8 et 4x4. (à noter que la SMS ne supporte que des tuiles 8x8). L'engin pour les tuiles 12x12 a été un gros défi, puisque les deux grilles (tuiles 8x8 natives vs. tuiles 12x12 virtuelles) ne correspondent et cela créé de jolies complications (tuiles séparés verticalement ou horizontalement, ou tuiles séparés en quatre... les tuiles requises sont générées au vol lors de l'affichage et du jeu!

L'engin 4x4 est surtout utile pour l'aperçu de certains niveaux dans les menus, et aussi pour quelques niveaux très grands.. Ces derniers ne sont probablement jouables qu'avec un émulateur ou via un écran branché en RGB.

Le menu en-jeu offre la possibilité d'annuler le dernier mouvement ou la dernière poussée. L'historique peut contenir un maximum de 1000 événements.

Naturellement, résoudre 1000 niveaux en une session est impensable (probablement) alors le progrès est enregistré en mémoire de sauvegarde, ou directement dans la flash, si programmé sur une cartouche compatible, comme celles que j'ai conçues...
J'ai réalisé ce jeu pour la compétition de programmation pour Sega Master System organisée par smspower.org. Voici le topic pour ce jeu.


Screenshots (v1)



Téléchargement

Version 2.0
14 septembre 2022 (Mercredi)
Après environ un an d'efforts à temps partiel, la version 2 est enfin prête!
  • Ajout de 100 niveaux raphnet (la plupart très faciles)
  • Ajout de niveaux inédits par Jacques Duthen: Sokogen-990702, Sokogen-990917, et Sokogen-991123
  • Nouvel écran titre
  • Nouveaux écrans Options et Crédits
  • Ajout de thèmes : Nouveau (V2), Mac et Ksoko. L'ancien thème (V1) est également disponible.
  • Changement des boutons en jeu: Le bouton 1 ouvre le menu, le bouton 2 annule le dernier déplacement de caisse.
  • Ajout d'un mode pointeur (avec recherche de chemin)
  • Support du Sports Pad et de la Mega Mouse
  • Ajout de musique en arrière plan (peu être déactivée dans les options)
Fichier(s):
skbn-v2.zip (186.7 KB)
Afficher les versions précédentes
Version 1.4
21 mai 2021 (Vendredi)
Corrige l'orthographe de 'Dimitri & Yorick'
Fichier(s):
skbn-v1.4.zip (125.2 KB)
Version 1.3
31 mars 2021 (Mercredi)
  • Add a 'Well Done' message when solving a level
  • Fix a bug where the player could move in diagonal, and undoing the last move would then remove a wall block and add a new box to the level!
  • Move the Level number in the status bar one column to the right to avoid displaying text in the first column.
  • Small tweaks to the tile screen (sharper box corner, black countour)
Fichier(s):
skbn-v1.3.zip (125.2 KB)
Version 1.2
30 mars 2021 (Mardi)
  • Added a 24x24 tiles mode.
  • Boxes now move smoothly, in-sync with the player when pushed. (instead of teleporting).
  • Reworked the player artwork and other small cosmetic details.
  • Correct a bug which caused unsolved levels to show as solved in the menu when scrolling.
  • Display 'player on target' correctly during previews.
Fichier(s):
skbn-v1.2.zip (121.4 KB)
Version 1.1
29 mars 2021 (Lundi)
  • Add a short 'end level' jingle.
  • Add 'Dimitri & Yorick' and 'Sokogen-990602' level sets by Jacques Duthen (Easy levels)
  • Fixed the 'parallax' effect at the end of a level (was not well controlled and jittery on real hardware).
  • Correct initial player position (was not centered until first movement)
  • Fine tune player sprite position in 12x12 tiles levels (was a bit too low)
  • Remove the debug info (number in upper right corner) in 12x12 tile display mode
Fichier(s):
skbn-v1.1.zip (115.2 KB)
Version 1.0
27 mars 2021 (Samedi)
Première version pour la compétition 2021 de smspower.org
Fichier(s):
skbn_release_smscomp2021.zip (112.8 KB)



Également disponible depuis la page du jeu sur smspower.org:
https://www.smspower.org/Homebrew/SKBN-SMS

ainsi que sur itch.io:
https://raphnet.itch.io/skbn


Édition physique

Ce jeu est également disponible en format cartouche depuis mon magasin en ligne! https://www.raphnet-tech.com/products/skbn_sms/index_fr.php



Remerciements

La réalisation de ce jeu a été grandement facilitée par l'existence de plusieurs outils:

Un gros merci aux auteurs de ces outils!


Bien entendu, ce jeu ne serait rien sans son contenu, les niveaux! J'ai utilisé des niveaux qu'il est possible de redistribuer librement, à condition de créditer les auteurs.

  • Merci à David W. Skinner pour les niveaux Microban et Sasquatch.
  • Merci à Jaques Duthen pour les niveaux Dimitri & Yorick, Sokogen 990602, Sokogen-990702, Sokogen-990917, et Sokogen-991123.