Screenshots (v2)

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)

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...

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)

---

É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:

• devkitSMS (SMSlib et PSGlib): https://github.com/sverx/devkitSMS
• png2tile (conversion d'images PNG vers le format SMS): https://github.com/yuv422/png2tile
• DefleMask tracker: https://deflemask.com/
• sdcc (Small Device C Compiler), un compilateur C supportant le Z80: https://deflemask.com/

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.