La première idée est d’utiliser une grille, où chaque nœud pourrait correspondre par exemple à un pixel du plan. Cette méthode a l’avantage d’être assez précise, mais malheureusement trop gourmande en temps et en mémoire si la zone de travail devient trop grande.
L’utilisation d’une grille étant performant sur des petites zones, il pourrait être intéressante d’essayer de simplifier le graphe, en prenant par exemple un maillage plus grand qu’un simple pixel. Mais une fois encore, un problème se pose, non plus de performance, mais de cohérence dans le chemin. En effet, le chemin va donc passer par les nœuds de la grille, et ne sera donc pas forcement une ligne droite lorsqu’il s’agira de relier deux nœuds, même s’il n’y a pas d’obstacle.

L'utilisation d'une grille provoque un effet d'escalier.

Évidemment, la meilleure solution consisterait à obtenir un graphe collant parfaitement aux obstacles. Le problème restant de trouver comment l’obtenir. En fait, ce n’est pas aussi compliqué que ça peut en avoir l’air, car au final, on a seulement besoin de connaître les sommets des obstacles (à condition que ceux-ci soient des polygones, le cas des figures courbes est plus complexe et je n’en parlerai pas).
Le travail va donc se décomposer en plusieurs étapes:

• Création de la carte des obstacles.
• Création des sommets du graphe.
• Création des arrêtes du graphe.

Création de la carte des obstacles

Il n’y a pas énormément de choses à dire sur cette étape, elle dépend avant tout des besoins du programme. Dans mon exemple, je me contenterais d’utiliser des obstacles rectangulaires car ils sont plus simple à gérer, et que je n’ai pas eu l’occasion de travailler avec d’autre formes. A noter toutefois que rien n’empêche la superposition de plusieurs rectangles.

Les zones d'obstacles

Création des sommets du graphe

Deux sous-étapes sont nécessaires ici, la première consistant à ajouter les futurs nœuds, et la seconde à supprimer ceux qui ne sont pas valides et/ou inutiles.
Dans le cas d’un rectangle, il suffit de prendre les sommets déjà existant. J’ai, dans mon cas, eu besoin d’ajouter une marge autour de mes obstacles, de manière a ce que, lors de l’affichage final, les unités ne se superposent pas aux obstacles.
La marche à suivre est donc simple:

• Ajout des nœuds.

• Détection et suppression des nœuds invalides, c’est à dire qui se retrouvent à l’intérieur d’un rectangle.

Ce qui nous donne:

Les nœuds du graphe

Il y a d’autres tests possibles concernant la validité d’un nœud, comme la non-superposition avec un autre nœud, ainsi que le non-alignement de trois nœuds, cas dans lequel le nœud médian sera sûrement inutile (sauf si un obstacle les sépare).

De plus, une petite note technique, ici j’ai crée les nœuds puis je les ai testé, avant de les supprimer si ils n’étaient pas valides. Il est évident que pour faire les choses correctement, il est plus logique de ne créer le nœud que si la position à laquelle on veut le mettre est une position valide, c’est-à-dire faire le test avant de le créer. Dans le cas où ce n’est pas possible (on ne sait jamais), l’ordre création/test/suppression est une bonne alternative, moins gourmande en mémoire.

Création des arrêtes du graphe

La méthode est exactement la même que pour la création des nœuds, on commence par créer toutes les arrêtes possibles avant de détecter et supprimer celles qui ne sont pas valides:

• Ajout des arrêtes.
• Détection et suppression des arrêtes invalides. Il s’agit des arrêtes qui passent à travers un obstacle, ou qui sont incluses dans une autre arrête (bien que cette possibilité ne puisse arriver si les nœuds inutiles ont été supprimés).

On obtient alors:

Les arrêtes du graphe

Les mêmes remarques que pour la création des nœuds s’appliquent ici, à savoir que créer toutes les arrêtes pourrait être très gourmand en mémoire, surtout si la carte comporte de nombreux obstacles.
Certains auront surement remarqué que, depuis le début, je n’ai pas inclus les points de départ et d’arrivée dans le graphe. Il y a une bonne raison à cela: contrairement aux sommet des rectangles, ces nœuds là ne sont pas fixes, et les arrêtes correspondantes devront être recalculés à chaque déplacement, il est donc possible de pré-calculer les nœuds et arrêtes du graphe, et d’y ajouter à la demande les nœuds de départ et d’arrivée.

Résultat

Une fois le départ et l’arrivée inclus dans le graphe, il suffit d’appliquer n’importe quel algorithme de recherche de chemin pour obtenir le résultat recherché:

Résultat final

Pour les curieux, toutes les images, sauf la première et la dernière, ont été générée via un script php, disponible ici.
Ce script ne permet que de générer le graphe, et n’implémente pas la recherche de chemin.
Ayant codé ce script rapidement pour tester cette méthode, et n’ayant pas prévu à l’origine de le distribuer, la syntaxe est un peu brouillon et peu, voire pas du tout, commentée. Toutefois, son utilisation est suffisamment simple pour s’y retrouver.

Passons maintenant à la partie importante, le jeu.
Plusra est à l’origine un jeu PC développé par Gil Bear, dans le cadre d’un concours de programmation organisé par SmokingWOLF. Cette version, reprenant une très grande partie des ressources, ainsi que le concept, est donc évidemment distribué avec l’accord du créateur original.
Le principe du jeu est simple, il faut déplacer des blocs de différentes couleurs afin de les faire fusionner et d’obtenir des blocs de la valeur demandée. Il y a, bien évidemment, d’autres règles :

• Une barre de vie, qui, lorsqu’elle arrive à 0, implique une fin de partie.
• De nouveaux blocs qui viennent s’ajouter régulièrement à la surface de jeu. Lorsque l’écran est rempli, la vie diminue rapidement et peut mener à un Game Over assez vite.
• Tout bloc d’une valeur supérieure à 10, qui ne soit pas la celle demandée, sera détruit, et autant de points de vie seront retirés.
• Et quelques autres que je vous laisse découvrir.

Il existe quelque différence entre la version PC et la version PSP, tel que le scoring légèrement modifié, un système de niveaux, la possibilité d’enregistrer les noms dans le tableau de highscores, mais dans l’ensemble, le jeu est le même. Les parties sont également sensiblement plus courtes sur PSP.

Concernant les contrôles de jeu, deux touches seulement sont utilisées, en plus des flèches directionnelles :

• Rond, qui sert, maintenu, à déplacer les blocs à l’aide des flèches.
• Carré, qui permet de faire venir plus rapidement des nouveaux blocs dans la zone de jeu. Attention, ce n’est pas gratuit, en cas d’abus, le Game Over risque d’arriver plus tôt que prévu.

Pour récupérer le jeu, c’est par ici : PlusraPSP (miroir).
Et pour patienter pendant le téléchargement, une petite vidéo de présentation :

Mise à jour du 4 novembre 2009:

• Correction d’un bug au lors du chargement des images.
• Suppression de la possibilité de mettre le jeu en pause, qui rend le jeu beaucoup trop facile, et qui n’était pas censé exister dans la version finale…

Mise à jour du 29 novembre 2009:

• Les images et sons sont maintenant contenu dans une seule archive, ce qui limite le nombre de fichiers à transférer.
• Les Bgm peuvent être supprimées sans que cela n’empêche le jeu de fonctionner (permet de gagner environ 12Mo, le jeu ne fait alors plus qu’environ 40Ko ).
• Ajout d’un écran de chargement.
• Correction d’un bug d’affichage lors de l’ajout d’un nouveau record.

Remilia Scarlet par usotukiya (嘘つき屋)

Bon, j’avais prévu d’écrire un bon gros pavé, histoire de bien commencer, mais je pense qu’en fait je vais me contenter d’une petite présentation simple et rapide.

L’idée de base était d’avoir un endroit pour parler des choses que j’aime, ce qui se résume plus ou moins à deux domaines, la programmation, et le japon, principalement les jeux amateurs et l’animation.
Au final, ça donne des petits utilitaires pour doujingame, bien souvent des extracteurs de ressources, certains sont déjà disponibles sur  la page Tools, d’autres devraient suivre plus tard. En plus de ces petits scripts, il y aura des projets un peu plus conséquents, tel que par exemple des adaptations de doujingame pour PSP, voire des créations originales si je trouve une bonne idée.
Concernant les portages de jeux existants vers la PSP, le premier projet est actuellement en phase finale de test, que les amateurs de jeux de réflexion se préparent, la release devrait arriver avant la fin de la semaine.

Et voilà, je pense que ça devrait aller, maintenant, retour au boulot, les releases vont pas se faire toutes seules.