Le concours du reporter

Circuit de F1
mercredi 15 janvier 2003
par  Gaétan RYCKEBOER, Pascal Brognez
popularité : 1%

Pour les vacances 1995, période propice à la méditation, la réflexion et le jeu, le Reporter lançait un concours de programmation auprÚs de ses lecteurs.

Cette période avait été choisie spécialement en pensant aux étudiants qui auraient ainsi plus de temps à y consacrer qu’en période scolaire (s’ils n’ont pas autre chose a penser bien sur :-).

Aujourd’hui, CLX se propose de faire revivre ce concours sous Linux, en adaptant les rÚgles.

Introduction

L’objet du concours en lui-même est très simple. Il va s’agir de créer un pilote logiciel de formule 1.

Ce concours se veut rester dans l’esprit qui anime le REPORTER depuis sa création, à savoir rester accessible à tous quelque soit son niveau en programmation et être un moyen de partager une passion via le plaisir du "jeu" et non pas pour l’appât du gain.

Ce concours n’est donc pas primé selon le concept traditionnel Faire les choses comme tout le monde n’est pas notre sport favori :-). Ce qui ne veut pas dire que les participants n’y trouveront pas leur bonheur.

Outre le plaisir de participer que procure un jeu collectif, les 50 premiers d’entre-vous qui nous auront fait parvenir le résultat de leurs cogitations avant la clôture du concours recevront tous un cadeau.

Bien entendu cela ne concerne que les 50 premiers qui nous auront envoyé un programme parfaitement opérationnel, c’est-à-dire capable de traiter dans le respect des règles et sans planter au moins 70% des circuits qu’il aura à parcourir. Voilà qui va décevoir les astucieux qui espèraient envoyer un p’tit programme se contentant de s’exécuter rien que pour obtenir un cadeau :-)

Ici seul le mérite compte, il n’est pas nécessaire d’être vainqueur pour avoir droit à son cadeau.

A l’époque, celui-ci se présentait sous la forme d’un abonnement gratuit d’un an (4 numéros) au Reporter.

Les participants auraient reçu donc dans leur boite à lettre dès sa parution et en priorité le REPORTER sur disquette en version Dos et Windows. Et comme il restait de la place sur ces supports, Le reporter n’aurait pas manqué de la combler avec quelques petits bonus.

Aujourd’hui, nous proposons des cadeaux de valeur comparable, c’est à dire un abonnement gratuit à la liste de diffusion du CLX, un accès privilégié au site WEB de CLX ave la possibilité de publier des articles, et peut-être d’autres bonus. Si d’aimables mécènes souhaitent apporter leur contribution à la renaissance de ce concours en faisant bénéficier ces mêmes 50 premiers candidats de petits cadeaux, ils seront les bienvenus.

Nous ne manquerons pas de les signaler sur le site.

Dernière petite chose, tous les mois précédant la clôture du concours, nous ferons paraître les résultats des programmes reçus obtenus sur un circuit de référence (avec le nom de leur auteur bien sûr).

Il est temps maintenant que vous preniez connaissance des règles du jeu, mais n’oubliez pas que si l’important est de participer (Pierre de Coubertin), l’essentiel est de s’amuser (Le Reporter).

- présentation générale du concours
- règles d’évolution de la F1
- règles de description du circuit

en cours de rédaction
- syntaxe des fichiers résultat
- structure du pilote automatique
- création et vérification des circuits
- chronométrage du résultat
- règles de participation
- épreuves de qualification
- résumons par un exemple concret
- Le concours du Reporter : Annexes

Présentation

A la base, il s’agit d’un concours de programmation : chaque participant doit écrire un programme qui permet de piloter au plus vite une formule 1 sur un circuit quelconque dont il ne connait pas a priori le parcours.

Il faut donc écrire un programme de pilote automatique de formule 1.

En fait ce concours s’apparente à celui organisé à sa grande époque, par la revue Micro-Système. Ce concours avait passionné une bonne partie de la France, mais limitait fortement la participation car il fallait réaliser un vrai modèle réduit de voiture.

La différence c’est qu’ici le concours est uniquement logiciel et chacun peut facilement participer : il suffit de posséder un ordinateur compatible PC. Peu de moyens sont donc nécessaires (c’est ouvert à tous ou presque) et seule l’astuce du programmeur lui permettra de faire la différence.

Pour cela, des règles très simples définissent le comportement ’physique’ de la voiture sur la piste. Le programme doit respecter ces règles, tout en suivant le tracé de la piste qui constitue le circuit, et joindre au plus vite la ligne d’arrivée.

L’originalité de ce concours réside dans le fait que même les organisateurs du concours (nous-même) ignorent sur quelles pistes se dérouleront les courses !

En effet chaque participant doit aussi fournir un fichier ’circuit’ contenant une piste dont le tracé est laissé à sa discrétion, (et qui a priori favorisera son propre pilote).

Chacun des participants fera tourner sa voiture sur son propre circuit, mais aussi sur les circuits de ses adversaires.

Bref pour gagner, il faut jouer sur les deux tableaux :

- 1) Développer un pilote logiciel qui puisse tourner vite sur n’importe quel circuit sans en connaitre a priori le parcours.
- 2) Décrire un circuit sélectif, qui tendra à pieger et ralentir au maximum les pilotes adversaires par sa complexité tout en favorisant le sien.

Bien entendu il n’est pas question que vous perdiez du temps à créer un circuit ou un programme de chronométrage.

Sont donc fournis gratuitement avec ce numéro un programme vous permettant de dessiner graphiquement un circuit conforme ainsi qu’un programme de chronométrage et de validation qui utilise le fichier des déplacements généré par votre pilote logiciel pour évaluer ses performances.

L’éditeur de circuits originel nécessite une carte vga, mais n’est pas indispensable pour créer un circuit. Un simple éditeur de texte suffit comme expliqué plus loin, ce afin de rendre le concours accessible indépendamment du matériel PC utilisé. Par contre, le programme tourne sous DOS.

De même, ce n’est pas parce que l’on parle de ’tourner vite’ ou de ’chronométrage’ qu’il s’agit d’un concours favorisant un langage rapide (ASM par exemple). Comme vous le comprendrez en lisant cet article en détail, les temps en question sont des temps relatifs.

Plus que le langage et sa rapidité, c’est l’astuce du programmeur qui lui permettra de faire la différence. Tout le monde a ses chances dans ce concours, que ce soit un habitué du C ou du basic.

Règles d’évolution de la F1

Les règles qui régissent le déplacement d’une voiture sur la piste d’un circuit quelconque sont assez simples.

Elles sont basées sur un petit jeu qui se pratiquait (et se pratique sûrement encore !) alors que nous usions nos fonds de culottes sur les bancs du lycée...

Imaginez une feuille de papier quadrillée sur laquelle on a délimité une piste à l’aide de deux tracés continus formant un circuit bouclé sur lui-même (vous voyez, ce n’est que du matériel classique pour les cancres du fond de la classe : juste des stylos et du papier !).

Ça se jouait à deux (voire plus), et chacun utilisait un stylo-bille de couleur différente, qui correspondait à la couleur de sa voiture fétiche.

La position de la voiture - qui devait bien sûr toujours rester sur la piste - était indiquée par un petit point, à l’intersection d’une ligne horizontale et d’une ligne verticale du quadrillage de la feuille.

Chacun, à tour de rôle, déplaçait sa voiture, en respectant la règle simple récurrente suivante.

La nouvelle position de la voiture s’obtenait en reportant le déplacement précédent de la voiture, et en choisissant soit le point obtenu, soit l’un de ses 8 voisins immédiats.

GIF - 1.5 ko
Dans l’exemple représenté ci dessus, la voiture, dont le déplacement précédent était de un point vers le haut et de 4 vers la droite, peut maintenant choisir l’un des 9 points indiqué par ’ ?’ comme nouvelle position.

On constate que par ce simple mécanisme, on pouvait accélérer (augmenter le déplacement d’un point), freiner (diminuer d’un point) ou rester à vitesse constante indépendamment dans les deux directions.

On obtenait ainsi un comportement similaire à celui d’une voiture (essayez et vous verrez qu’il ne faut pas prendre des virages tendus à vitesse trop élevée !).

Bien entendu, il fallait aussi s’évertuer à éviter les collisions, soit avec les voitures adverses, soit avec la bord de la piste.

Les différences entre ce jeu scolaire et le concours sont peu nombreuses :

- Pour des raisons de simplification, la position de la voiture est au centre d’un carré (appelons-le "pixel", même si ce n’est pas une dénomination parfaite). Les bords de piste ne sont pas une ligne continue, mais sont aussi définis par des pixels carrés.

Voir ci-dessous un ’zoom’ sur une portion de circuit :

JPEG - 3.8 ko
- Le programme que vous avez à écrire (le pilote logiciel) doit décrire l’évolution d’une seule voiture sur la piste.

En fait, il s’agit plutôt d’essais de qualification que de la course en elle même. Chaque nouveau déplacement de la voiture correspond à un temps factice d’une seconde. La taille d’un
’pixel’ correspond de façon arbitraire à celle d’un carré de 10 mètres par 10 mètres. Ces conventions permettent d’obtenir les vitesses de notre voiture virtuelle, exprimées en km/h, de façon assez réalistes.

Le chronomètrage de votre voiture correspond donc à un chiffre tout à fait identique quelque soit l’ordinateur, car il correspond au nombre de coups nécessaires pour boucler un circuit donné.

Le but, donc, c’est d’écrire un programme qui définit les positions successives de la voiture, en respectant les règles des déplacements, et suivant un tracé donné, afin de boucler un tour en moins de coups que les autres programmes.

Pour ce faire, le circuit est représenté dans un fichier à l’aide de caractères Ascii disposés dans une matrice rectangulaire de 100 lignes par 150 colonnes. Un caractère espace représente la
piste tandis que tout autre représente le décor. Les règles définissant le format de ce fichier sont décrites plus loin.

Le point de départ est fixé (c’est le point de coordonnées x=40 y=4), ainsi que le sens dans lequel il faut faire le tour du circuit (Départ vers la droite, soit un sens qui suit globalement celui des aiguilles d’une montre).

La vitesse au départ est nulle, ce qui signifie que le point d’arrivé du premier déplacement est un des 8 voisins du point de départ (ou plus exactement un des trois placés à sa droite, sinon le départ se ferait en marche arrière :-)

Le but du programme est donc d’écrire un fichier résultat donnant les différentes positions de la voiture calculées pour un circuit donné jusqu’à la ligne d’arrivée (de même coordonnées que le point de départ).

Il est, évidemment, interdit d’entrer en collision avec les bords de la piste, faute de quoi votre formule 1 sera considérée comme détruite et votre tour ne sera pas pris en compte ! (Ce n’est pas très solide ces bolides...)

Le fichier résultat est ensuite passé en paramètre au programme TESTF1.EXE qui se charge de vérifier que le circuit est bien bouclé, qu’il n’y a pas collisions, que les règles de déplacement sont respectées, et en final d’afficher les temps.

Il convient de préciser en détail la manière dont s’effectue les tests de collisions [1], qui vous empêchent de ’mordre’ sur les bas
cotés pour couper un virage.

La règle est simple : on trace la ligne entre le point de départ et d’arrivée de la voiture, et si l’un des points intermédiaires n’est pas sur la piste, il y a collision !

Mais, me diront à juste titre certains d’entre vous, cette règle apparemment simple peut poser un problème, très connu par ceux qui ont déjà écrit des routines de tracé de lignes...

En effet certains cas particuliers peuvent devenir des cas litigieux, comme illustré par l’exemple suivant :
JPEG - 828 octets
Le déplacement de la voiture est de 5 pixels vers la droite et de 1 pixels vers le haut (joignant les deux points jaunes. Pour les deux premiers et les deux derniers pixels, il n’y a pas de problème : si l’un des points gris n’est pas sur la piste, il y a collision.

Par contre pour un décalage de 5 pixels vers la droite, la voiture passe juste au milieu de deux pixels : ceux représentés en rouge. Il n’a pas de raison de privilégier a priori plus une solution que l’autre ! (alors que les routines de tracé de lignes feront un choix ou l’autre selon la manière dont elles sont programmées)

Nous avons donc décidé d’utiliser une routine de test de collision souple, à savoir de déclarer qu’il n’y a pas collision si l’un OU l’autre des deux pixels reste sur la piste.

Bien entendu si les deux pixels (l’un ET l’autre) sont hors de la piste, il y a collision.

Ainsi, quel que soit la routine de ’tracé’ que vous utiliserez, le déplacement sera conforme, évitant toute ambiguïté.

Pour éviter toute discussion concernant la routine de test de collision un exemple de cet algorithme est donné, en langage Pascal (adaptation facile à tout autre langage).

Pour bien comprendre tout ce mécanisme très simple (bien que difficile à expliquer), vous trouverez ci-après quelques exemples illustrant les principes d’évolution.

Notez qu’il s’agit à chaque fois de portions de circuits.

Dans les exemples présentés, les positions précédentes de la voiture sont représentées en jaune

JPEG - 9.3 ko
Pas de problème pour la voiture, elle contrôle bien sa vitesse, ce qui lui permet d’aborder le virage en toute quiétude...

JPEG - 25.7 ko
Sur cet exemple, la voiture va trop vite.. Bien que restant toujours sur la piste, la trajectoire d’un point à l’autre coupe le bord, amenant la routine de test de collision à constater un accident.

JPEG - 9.2 ko
Sur cet exemple la voiture ne va pas trop vite.. Elle reste
toujours sur la piste, et sur le point litigieux clignotant vert, la routine de test de collision, de par sa souplesse,
accepte la trajectoire, considérant que la voiture est passée
juste à gauche.

JPEG - 27 ko
Dans ce cas, le programme déclarera la position de la voiture comme illicite. En effet, le dernier déplacement était de trois pixels vers la droite et la voiture se ’permet’ brusquement un
déplacement que de un pixel.. La position permise de la voiture est l’un des points voisins du point blanc clignotant, ce qui signifie que le crash est inévitable...
JPEG - 22.7 ko
La voiture va trop vite, mais heureusement une impasse lui permet de décélérer.. Il ne lui reste plus qu’à freiner à fond (jusqu’à un déplacement nul en X) pour reprendre le bon chemin, dans
l’autre sens.

Règles de description du circuit

Le fichier de description du circuit, d’extension CIR par convention, a pour but de délimiter la piste sur laquelle doit évoluer la voiture par rapport au reste du dessin.

Par convention, le circuit est compris dans un rectangle de longueur 150 et de hauteur 100 (limites extérieures).

Le fichier est donc simplement constitué d’un ensemble de 100 lignes de chaînes de caractères ASCII. Chaque chaîne de caractères est constituée de 150 caractères utiles, plus les classiques "carriage return" et "line feed" éventuels qui séparent les lignes.

On pourra donc relire aisément ce fichier et mettre les données dans un tableau de caractères de type (par exemple)

.
     donnee: array[0..149,0..99]
             0   1   2   3       146 147 148 149    
           +--------------     -----------------+  
        0  ¦   ¦   ¦   ¦        ¦   ¦   ¦   ¦   ¦  
           +---+---+---+--     -+---+---+---+---¦  
        1  ¦   ¦   ¦   ¦        ¦   ¦   ¦   ¦   ¦  
                                                   
           +---+---+---+--     -+---+---+---+---¦  
        99 ¦   ¦   ¦   ¦        ¦   ¦   ¦   ¦   ¦  
           +--------------     -----------------+  

La première valeur du tableau, comprise entre 0 et 149, comporte les coordonnées en X (longueur) du dessin, avec la valeur 0 représentée classiquement à gauche sur l’écran.

La deuxième valeur du tableau, comprise entre 0 et 99, comporte les coordonnées en Y (hauteur) du dessin, avec la valeur 0 représentée classiquement en haut sur l’écran et correspondant à la première ligne du fichier CIR.

Pour distinguer la piste du reste du circuit, une convention simple : un point de la piste est indiqué dans le fichier par le caractère ’ ’ (espace, code ASCII 32).

Tout autre caractère ASCII doit être considéré par le programme pilote comme ne faisant pas partie de la piste, donc inaccessible à la voiture (rappel : une voiture hors piste provoque un accident qui l’élimine).

Néanmoins, pour permettre une représentation plus avenante du circuit, j’ai décidé d’utiliser une convention faisant correspondre une couleur à certains caractères ASCII.
Cette convention utilise les couleurs typiques de Windows, plutôt que celles de la carte VGA, pour permettre une conversion facile à partir d’un fichier "BMP" non compressé à 16 couleurs.

Cette convention est la suivante :

caractère couleur
A Noir
B Rouge foncé
C Vert foncé
D Jaune foncé
E Bleu foncé
F Magenta foncé
G Cyan foncé
H Gris clair
J Rouge vif
K Vert vif
L Jaune vif
M Bleu vif
N Magenta vif
O Cyan vif
P Blanc

Il faut noter que la couleur gris foncé est attribuée par convention au caractère espace (la piste) et non pas à la lettre ’I’.

Tous les autres caractères ASCII sont dessinés, dans les outils fournis, avec la couleur ’Vert vif’.

Rappelons cependant que ces codes de couleurs n’existent que pour faire joli, et qu’un circuit peut très bien être défini uniquement à l’aide de ’X’ et ’ ’ via un éditeur de textes !

Mais rassurez-vous, vous pouvez complètement ignorer et oublier ces conventions de couleurs : un programme de dessin, CREECIR, est fourni ! Il est documenté plus loin, et va vous aider à créer votre circuit, ainsi que le colorier à votre (bon) goût.

Pour qu’un circuit soit considéré comme conforme, il faut qu’il vérifie les différentes règles suivantes :

- (1) La surface totale occupée par le circuit (piste et décors) doit être de taille 150*100, à savoir 100 lignes de 150 caractères (rappel)

- (2) La piste ne peut pas affleurer les bords du dessin. Plus précisément, on ne pas mettre de caractère ’ ’ en ligne 0 ou 99, ou en colonne 0 et 149. Le but de cette règle est de délimiter facilement le terrain sans avoir à y rajouter un bord fictif (et ainsi faciliter les tests !).

- (3) Une zone de piste est imposée : c’est le rectangle délimité par les points x=20, y=2 et x=59, y=6. C’est au milieu de cette zone que se situe le point de départ (x=40, y=4).

Après avoir bouclé un tour complet, en partant vers la droite (sens x croissant), la ligne d’arrivée est une ligne verticale, de la largeur de la piste, et située en x=40.

Le but de cette règle est, bien entendu, de fixer précisément les points de départ et la ligne d’arrivée, ainsi qu’une largeur et longueur de piste suffisante pour bien démarrer et passer la la ligne d’arrivée en accélération.

Le sens de rotation est fixé (globalement celui des aiguilles d’une montre), car la voiture doit se déplacer au départ dans le sens des x croissant (droite). Elle coupera la ligne d’arrivée lorsqu’elle aura atteint ou dépassé la coordonnée x=40, en venant bien entendu d’une position x plus faible (pas question de couper la ligne d’arrivée dans le mauvais sens !!!) :

JPEG - 6.2 ko La vitesse de départ est nulle, ce qui signifie, en pratique, que le premier point après la position (40,4) est l’un des voisins du point de départ.

- (4) Un seul chemin doit mener du départ vers l’arrivée. Le circuit doit donc être évidemment bouclé sur lui-même, mais il ne peut pas comporter d’ilôts au milieu de la piste. Par ilôt, j’entend un ou plusieurs caractères au beau milieu de la piste.

Par exemple ce genre de configurationest interdit :

JPEG - 2.4 ko
Attention, ceci ne vous interdit pas certains ’pièges’ amusants dans votre circuit. Par exemple la création d’impasses, ayant pour but de tromper les voitures adverses est permise.

JPEG - 2.2 ko
- (5) La largeur de la piste est au minimum de 2. Le but de ce concours est d’écrire un pilote de Formule 1, et pas d’auto cross ! Cette règle peut s’énoncer plus précisément comme suit :
aucun point de la piste ne peut avoir pour "voisin" (i.e. une des 8 cases qui l’entoure) à la fois un bord de piste intérieur et un bord de piste extérieur. Il faut donc toujours au minimum deux caractères de piste (pixels) pour séparer les deux bords, y compris en diagonale.

Dans tous les cas de figure, si vous avez un doute sur la conformité de votre piste au règlement, le programme CREECIR est là pour vous aider en effectuant toutes les vérifications sur votre fichier CIR, et en indiquant, si nécessaire, pour quelle(s) raison(s) un circuit donné n’est pas conforme.


Notez-bien qu’actuellement CLX n’a pas redéveloppé sous Linux, les outils initiaux, fournis par le Reporter et programmés par Luc RiviÚre. Par contre, si vous avez installé FreeDOS (un DOS sous GPL) sur votre machine ou Dosemu (un émulateur DOS sous linux), vous pourrez les utiliser.

Nous allons réécrire des versions minimales de ces outils sous linux et les mettre sous licence GPL. Nous les publieront ici dans un avenir plus ou moins proche (à moins que vous ne vous sentiez le courage de le faire vous-même et d’en faire profiter la communauté entiÚre, bien sûr).

Notez également que la participation au présent concours implique que votre pilote soit publié sur le site de CLX à l’issue du concours sous la license libre de votre choix.

Vous trouverez tous les numéros du Reporter sur le site de l’un des ancien R.O.R.


[1Ci-joint un exemple en Pascal de l’algorithme de test de collision.

C’est une fonction surPiste, qui retourne vraie (TRUE) si la voiture reste sur la piste et faux (FALSE) lorsqu’il y a une collision dans le déplacement.

On suppose au départ que le joueur a placé son circuit dans un tableau donnee[x,y] et que le test donnee[x,y]=piste consiste à savoir si le point concerné est sur la piste.

Facile à adapter si on utilise une autre structure de données.

function surPiste(x,y,xf,yf:integer):boolean;
 { Teste si une ligne joignant x,y à xf,yf est sur le circuit.
   algorithme de Bresenham légèrement modifié pour les cas litigieux.
   retourne vrai (true) si on reste sur la piste,
   retourne faux (false) si on casse la voiture sur un bord.
   L. Rivière }
 var dx,dy,total,xi,yi:integer; ok:boolean;
 begin
   surPiste:=false;

     { Commençons par éliminer les cas triviaux }
   if donnee[x,y]<>piste then exit;
     { Retourne FAUX si on est pas déjà sur la piste! }
   if (x=xf) and (y=yf) then begin
     { Si on est sur la piste et que l'on bouge pas.. }
     surPiste:=true; exit;
   end;
     { Le cas général.. }
   ok:=true;
     { On commence, comme dans la plupart des algo de tracé, à se
       mettre dans le premier quadrant, pour raisonner avec des
       déplacement relatifs positifs }
     { D'abord en X.. dx toujours positif, xi prend le signe (±1) }
   if (x<xf) then begin
      xi:=1; dx:=xf-x;
   end else begin
      xi:=-1; dx:=x-xf;
   end;
     { Ensuite en Y.. dy toujours positif, yi prend le signe (±1) }
   if (y<yf) then begin
      yi:=1; dy:=yf-y;
   end else begin
      yi:=-1; dy:=y-yf;
   end;
     { on se déplace toujours d'un pixel à la fois selon la direction qui
       nécessite le plus de pixel. C'est pourquoi on fait les tests pour
       savoir quel déplacement est le plus grand.. }
   if (dx>dy) then begin
     { Comme le déplacement en X est plus grand, on va y aller de x à xf
       avec l'incrémentant d'un xi à chaque fois.
       Le reste c'est quasi du Bresenham classique, à savoir
       que l'on incrémente un compteur (ici total) d'une valeur égale
       à deux fois le déplacement y. }
     total:=0;
     repeat
       x:=x+xi;
       total:=total+2*dy;
       if (total=dx) then ok:=(donnee[x,y]=piste) else ok:=false;
         { Le cas litigieux signalé pour le test de collision se repère
           au fait que le compteur tombe pile sur la valeur de dx.
           Dans ce cas on met une valeur booléenne (ok) à jour selon le
           fait que l'on soit sur la piste ou non, ceci avant la modification
           de Y. Si on est pas sur le cas litigieux, on met OK à false
           (comme si on était pas sur la piste), car par la suite on fera un
           OU logique... }
       if (total>=dx) then begin
         y:=y+yi; total:=total-2*dx;
       end;
         { Comme tout Bresenham, lorsque l'on atteint ou dépasse dx, on
           incrémente la valeur d'un cran }
       ok:=(ok or (donnee[x,y]=piste));
         { Toute l'astuce du ok précédent. Si on était dans un cas litigieux
           on fait un 'ou' entre avant et après la décrémentation Y, donc
           on est sur la piste lorsque l'un ou l'autre des pixels l'est..
           Sinon (cas non litigieux) on teste bien le seul pixel concerné
           car on fait un 'ou' avec une valeur initialement false }
     until (x=xf) or not(ok);
       { On arrête quand on est plus sur la piste ou que l'on a atteint
         l'objectif x=xf }
   end else begin
     { Idem mais avec un déplacement de base suivant Y }
     total:=0;
     repeat
       y:=y+yi;
       total:=total+2*dx;
       if (total=dy) then ok:=(donnee[x,y]=piste) else ok:=false;
       if (total>=dy) then begin
         x:=x+xi; total:=total-2*dy;
       end;
       ok:=(ok or (donnee[x,y]=piste));
     until(y=yf) or not(ok);
   end;
   surPiste:=ok;
 end;

Commentaires

Logo de Gaétan RYCKEBOER
mercredi 18 juin 2003 à 18h43 - par  Gaétan RYCKEBOER

On vient de corriger l’article, pour aplier à ces désagréables dysfoncionnements.
Envoyez les contrib à clx-concours@clx.anet.fr

Logo de personne
samedi 14 juin 2003 à 22h12 - par  personne

l’adresse concours@clx.anet.fr n’est toujours pas active !
Comment peut-on faire alors ?

lundi 2 juin 2003 à 19h48 - par  kjus

toujours le meme problÚme :( :
I’m sorry to have to inform you that the message returned
below could not be delivered to one or more destinations.

For further assistance, please send mail to

If you do so, please include this problem report. You can
delete your own text from the message returned below.

The Postfix program

<concours@clx.anet.fr> : host gaia.anet.fr[80.118.2.10] said : 550 5.1.1
<concours@gaia.anet.fr>... User unknown

lundi 2 juin 2003 à 18h56 - par  kjus

ok, j’ai réenvoyé.
Normalement mon pilote doit trouver le parcourt idéal, sauf dans certains cas trÚs particuliers :)

lundi 2 juin 2003 à 10h59

Bien sûr. Nous continuons à entasser les participations, jusqu’à la date de cloture.

Pour ce qui est de l’envoi de ta participation, il faut le faire à concours@clx.anet.fr qui a été cassé pendant un temps, mais qui est maintenant réparée.

D’ailleurs, si des participnts ont tenté d’y envoyer leur pilote sans succÚs, il suffit de le renvoyer maintenant.

samedi 31 mai 2003 à 01h19 - par  kjus

Bon j’ai fini mon algo (en une journée !)
Il trouve en 116 déplacements pour le circuit de Monaco.
Je l’envoie bientot..

Mais au vu de la date des messages, le projet est-il toujours mort ou encore vivant ??

vendredi 30 mai 2003 à 19h13 - par  kjus

(J’ai rien dit, c’est précisé..)

vendredi 30 mai 2003 à 11h38 - par  kjus

Bonjour,
Quelles sont les contraintes de temps et de mémoire pour ce problÚme ?
(C’est surtout les contraintes de mémoire qui m’interessent).

Logo de Gaétan RYCKEBOER
vendredi 28 mars 2003 à 11h11 - par  Gaétan RYCKEBOER

CHRISTEE, les distribueturs de l’excellent T.Shirt "Linux Soft Revolution" offrent un dessin numéroté de B.Bellamy.

Site web : CHRISTEE.COM
Logo de Blimp
mercredi 26 mars 2003 à 10h37 - par  Blimp

Pour l’automatisation, il me semble que le plus simple serait d’utiliser des signaux. Au bout de cinq minutes, si le programme tourne toujours, on envoie un SIGTERM interceptable par le programme qui peut alors afficher ce qu’il a trouvé (s’il a trouvé quelque chose). 30 secondes plus tard, si le programme est encore là, envoi d’un SIGKILL non interceptable.

Mon petit calcul est bien sûr le cas le pire mais même en considérant que les 50 programmes tournent en moyenne en 1 minute, ça nous fait quand même 42 heures à appuyer sur une touche ! Perspective peu enthousiasmante.

Blimp.

mardi 25 mars 2003 à 22h34 - par  personne

J’ai personnelement quelques idées sur l’automatisation de procédure de test,afin de ne pas être présent devant l’ordi !
Malheureusement, je ne parviens pas à adresser de e-mail au principal interressé.
Pour répondre sur les critiques que j’ai pu lire, je tiens à préciser que le délai n’est pas trop long pour ceux qui comme moi ne peuvent pas consacrer plus de deux heures par semaine à ce projet.
Par ailleurs le calcul de temps nécessaire à citer en exemple l’exécution des tests n’atteindrait 208 heures que dans le cas où AUCUN programme ne serait en mesure de résoudre le chemin des circuits proposés, et qu’il s’avÚrerait alors nécessaire de l’arréter.
J’ai modifié le source de l’utilitaire de transformation de fichiers bmp en .cir, afin qu’il puisse lire des fichiers BMP possédant un index ou pas, ainsi que 1, 4 ou 8 bits par pixel.
De plus, il s’adapte automatiquement à la couleur de la piste, d’aprÚs la couleur du point de départ de la course.
Là encore, je souhaiterai l’envoyer, mais mes e-mails me sont retournés !
Voici ce que je récupÚre :
Arrival-Date : Fri, 14 Mar 2003 22:57:34 +0100 (CET)
Final-Recipient : rfc822 ; gaetan@nutella.virtual-net.fr
Action : failed
Status : 5.0.0
Diagnostic-Code : X-Postfix ; host vnet.net2.nerim.net[62.4.19.143] said : 550
5.7.1 <gaetan@vnet.net2.nerim.net>... Relaying denied. Proper
authentication required.

Quelq’un comprend pourquoi ?

Logo de Blimp
dimanche 23 mars 2003 à 17h31 - par  Blimp

Tout à fait d’accord. Au départ j’ai écrit la version "force brute" pour évaluer la qualité de mon pilote initial qui était assez rapide mais ne trouvait pas l’optimum. Je pensais alors qu’une analyse exhaustive du parcours me donnerait l’objectif à atteindre quitte à ce que ça tourne pendant des heures. Mais, surprise il tournait en 4-5 minutes sur mon pentium 300. En améliorant un peu la structure de ce programme je l’ai amené en dessous de la minute. J’ai donc deux pilotes (un rapide et sous-optimal, l’autre lent et optimal). J’avais donc songé à les regrouper en un seul pour toujours avoir une solution à disposition.

J’ai quelques circuits qui font mouliner l’approche force brute au delà du temps imparti. Cette solution ne peut donc pas être utilisée seule.

L’autre problÚme c’est que je ne sais pas à quelle vitesse tourne le 486 66Mhz qui sera utilisé. Comme j’ai un pentium 300MHz, j’ai supposé que celui-ci tournait 5 fois plus vite. Mais ce serait utile d’avoir une idée plus précise des performances de la machine cible (une idée toute bête, générer une image avec POV-Ray et voir le temps mis).

Sinon, ce concours m’aura permis de m’améliorer en C++ alors qu’avant je ne faisais quasiment que du C. Les structures de données de la STL sont quand même bien pratiques.

Logo de pacman
dimanche 23 mars 2003 à 11h14 - par  pacman

Juste pour apporter mes deux centimes au débat : j’ai aussi écrit un pilote et je n’ai toujours pas envoyé ma contribution. Pourquoi ? tout simplement parce que ce pilote ne peut pas gagner dans les conditions actuelles. Sur le circuit de Monaco il lui faut 126 pas pour faire un tour contre 115 pour l’optimum. Par contre il pourrait parfaitement tourner sur un 486, donc effectivement j’attends que les rÚgles soient définies de façon plus précise pour voir ce que je peux faire.

Je pourrais par exemple avoir 2 pilotes dans le même programme, un qui assure (la version actuelle) et un second lancé aprÚs en force brute pour éventuellement, dans le temps imparti, améliorer le premier résultat. Mais pour faire ça il faut que j’aie une définition précise du temps disponible, par exemple 5 minutes sur un PC équipé de tel processeur avec telle capacité de mémoire vive et telle distribution de Linux.

Je pourrais aussi essayer de concevoir un circuit qui plante les programmes en force brute, mais là aussi il me faut des limites précises que je n’ai pas pour l’instant !

De toute façon, ce concours m’a beaucoup amusé (c’est toujours ça de gagné), ça m’a permis de découvrir de trÚs beaux outils (wxWindows, Anjuta, DDD) et de valider ainsi pour mes besoins professionnels le développement Windows/Linux alors que je ne connaissais avant que le développement sous Windows. Car ce pilote (écrit en C++) tourne aussi bien sous Linux/X que sous Windows grace à wxWindows !

Logo de Blimp
dimanche 23 mars 2003 à 08h22 - par  Blimp

En fait le problÚme de ce concours est tout bêtement qu’il a été lancé
alors qu’il n’était pas encore prêt : pas de date de fin, pas de
portage des outils sous unix, pas de réglement. Comme le thÚme est
intéressant, des gens ont commencé à développer des pilotes mais comme
rien ne semblait bouger, l’intérêt s’est émoussé. Il suffit de voir
le forum de Julien Balas : plus aucun message aprÚs la mi-février. Je
peux me tromper, mais je ne pense pas qu’il y ait des milliers de
personnes actuellement en train d’écrire des pilotes.

Le plus simple serait sûrement de mettre les choses au carré : mettre à
disposition un validateur de circuit (testcir), un validateur de
parcours (testf1). Le plus important, le créateur de circuit, est
déjà disponible. Définir des régles du jeu, celles du concours du
Reporter ou d’autres, qui décrivent comment sont notés les pilotes sur
un circuit donné : le temps de calcul fait-il partie de la note ou bien
est-ce que c’est seulement le nombre de pas qui importe ? Comment est
pris en compte le cas où un pilote n’arrive pas à finir le circuit
dans le temps imparti. En un mot comment s’effectue le classement sur
un circuit donné et comment ces différents classements s’ajoutent les
uns aux autres pour créer le classement final.

Une fois ceci fait, relancer le concours avec une date limite pas trop
éloignée : un tel concours s’étalant sur 6 mois c’est trop long, un
mois ou deux me paraissent des durées plus raisonnables qui donnent à
chacun le temps d’écrire son pilote sans pour autant avoir à attendre
des lustres les résultats.

Il y a par ailleurs un point qui me turlupine. Chaque pilote va être
testé sur chaque circuit. En supposant que je me trompe et qu’au
final 50 personnes répondent, cela fait 50*50=2500 tests à effectuer.
A cinq minutes le test, cela fait un total de 208 heures pour tester
tous les pilotes. J’imagine mal que quelqu’un va s’asseoir devant son
PC et appuyer sur une touche toutes les cinq minutes pour passer au
pilote suivant (cela ferait 26 jours de test à raison de 8 heures par
jour !). J’imagine donc que tu as prévu des scripts pour automatiser
tous ce processus de tests. Mais dans ce cas, je ne vois pas comment
tu fais ça. Quelle est la technique utilisée ?

Pour ce qui est des lots, je m’en fous. Bon si t’as quelques millions
d’euros à distribuer ça m’intéresse ! Mais ce n’est qu’une motivation
parmi d’autres, le plaisir de résoudre un problÚme, la compétition en
sont d’autres qui me paraissent bien correspondre au thÚme du
concours.

Enfin pour ce qui est du mérite ou non d’un pilote en force brute, je
dirais que, l’important étant le résultat, peu importe que
l’algorithme employé soit élégant ou non (mais un algorithme peut-il
être élégant s’il est inefficace ?). Il sera découvert, et aprÚs ?
Cela montrera simplement que, pour ce problÚme particulier, une
approche en finesse était bien la meilleure ! :)

Blimp (particuliÚrement prolixe ce matin)

Logo de Gaétan RYCKEBOER
mercredi 19 mars 2003 à 15h02 - par  Gaétan RYCKEBOER

Je te trouve défaitiste, et je trouve ça dommage. Pour le moment, j’ai effectivmeent reçu trois pilotes et circuits. Cela ne veut pas dire
- 1/ que le concours est terminé, pour lequel la date de cloture est fixée ce qui sera le cas en le 31 Août 2002,
- 2/ que seuls 3 personnes travaillent sur le projet actuellement. Tu en est la preuve. Nous n’avons pas reçu ta contribution...

D’autre part, tes remarques sur les modalités d’évolution du concours - notamment sur lerÚglement intérieur - sont jsutes. Deux remarques toutefois :
- CLX est une assoication et ne dispose pas de suffisamment de moyens opur permettre de récompenser les participants. Nous fesons appels à des sponsors qui n’ont pas encore tous répondu.
- Le concours ayant été lancé par le fanzine "le reporter", il nous fallait obtenir l’accord des auteurs originaux avant de publier les pages originales que tu peux lire. Le rÚglement intérieur n’est pas encore publié (et le sera bientÎt) ; l’auteur original (Luc RiviÚre) est disparu prématurément ce qui nous a rendu les choses difficiles.

Pour ton pilote, envoies-le ! Tu as encore 4 mois pour le finaliser, et d’ici là, je ne doute pas que - si c’est ton principal moteur - d’autres sponsors seront venus s’ajouter à la liste.

Enfin, les rÚgles du jeu sont adaptées à tous les publics, débutants ou non en dévelopepemet. C’est pour cela que la grille est si petite. Les 5 minutes fatidiques ne sont certes plus adaptées à la puissance actuelle, mais les tous les pilotes seront publiés sous license libre. Un pilote de calcul en force brute n’aura aucun mérite et sera vite découvert une fios les sources publiées.

Logo de Gaétan RYCKEBOER
mercredi 19 mars 2003 à 14h54 - par  Gaétan RYCKEBOER

La liste des lots aux gagnants s’allonge. IKARIOS qui diffuse par correspondance des Tee-Shirts, distributions pressées et objets divers offrira des objets aux gagnants.

Site web : Le site IKARIOS
Logo de Blimp
mardi 18 mars 2003 à 20h21 - par  Blimp

Trois réponses !! Quel succÚs !

C’est dommage parce que ce concours était une bonne idée. Mais bon, des rÚgles du concours inexistantes (la page n’a jamais été publiée), des programmes ne fonctionnant que sous DOS (mais qui fonctionnent tout de même avec un émulateur), pas de date de remise des réponses, pas d’utilitaires de disponibles et utilisables facilement (FreeDOS c’est un poil pénible à utiliser), pas de récompenses. Tout ça ne motive pas !

Personnellement, j’ai écrit un pilote qui marche plutÎt bien, il ne lui manque que quelques bricoles (test du clavier pour s’arrêter, virer des messages de debug, ...), mais pourquoi me fatiguer ? Je me suis bien amusé à le réaliser, il marche. Voilà.

Une remarque pour finir, la taille du circuit est trop petite, 150x100 pouvait peut-être rendre une recherche en force brute irréalisable en 95, maintenant ce n’est plus le cas. Mon programme fonctionne sur ce principe et tourne en un temps tout à fait raisonnable (en deça des cinq minutes fatidiques d’aprÚs mes estimations). Il aurait fallu définir une taille maximale pour les circuits beaucoup plus grande.

Logo de Gaétan RYCKEBOER
mardi 11 mars 2003 à 10h12 - par  Gaétan RYCKEBOER

J’ai actuellement reçu 3 contributions au concours. N’oubliez-pas d’envoyer un circuit géénré avec votre pilote.

Vous pouvez aller-voir aussi la GUI proposé par nu des participant au concours, qui fonctionne sous linux - elle - opur créer vos circuits.

Allez, en piste !

Logo de Gaétan RYCKEBOER
lundi 17 février 2003 à 11h46 - par  Gaétan RYCKEBOER

g++ 3.0 est accepté.

Logo de Blimp
vendredi 14 février 2003 à 17h51 - par  Blimp

Petite question : quels sont les compilateurs disponible. Mon programme est écrit en C++ mais nécessite g++-3.0 au minimum pour compiler (bug dans 2.95).
Je peux toujours le modifier pour qu’il puisse tourner avec une version plus ancienne mais bon..

Annonces

Annuaire LibreNord

Retrouvez l’annuaire de logiciels libres créé par l’association Club Linux Nord-Pas de Calais sur le site suivant http://www.librenord.org


Sur le Web

21 mai - Décryptualité du 20 mai 2019 - Quand les informaticiens se rebiffent

20 mai - Revue de presse de l'April pour la semaine 20 de l'année 2019

20 mai - Interview de Sébastien Broca - Bonus de Philippe Borrel - Internet ou la révolution du partage

20 mai - Projet de loi école de la confiance : amendement 187 sur la priorité au logiciel libre déclaré irrecevable

20 mai - Projet de loi école de la confiance - Discussion au Sénat sur la priorité aux logiciels libres - 17 mai 2019

20 mai - Libre à vous ! Radio Cause Commune - Transcription de l'émission du 14 mai 2019

20 mai - Volontaires en Service Civique recherchés pour une mission de 9 mois

16 mai - Marche mondiale contre Monsanto et Bayer

16 mai - Émission « Libre à vous ! » sur radio Cause Commune (21 mai 2019) - Modèles d'organisation d'entreprises - Transcriptions - Partager est bon

16 mai - Publication officielle du SILL 2019 (Socle interministériel de logiciels libres)

16 mai - Interview de Lionel Maurel - Bonus de Philippe Borrel - Internet ou la révolution du partage

15 mai - Fontaine, ville « libre » - Bonus de La Bataille du Libre

15 mai - L'April présente à la Fête du Libre le 25 mai 2019 à Ivry-sur-Seine (94)

15 mai - Collectivités, participez à l'édition 2019 du label Territoire Numérique Libre

15 mai - Tonton Alias raconte comment il s'est cogné au mur du content ID de Google - Décryptualité du 13 mai 2019

14 mai - « Libre à vous ! » diffusée mardi 14 mai 2019 sur radio Cause Commune - Développement logiciel libre – Next INpact – Internet ou la révolution du partage

14 mai - Pourquoi les logiciels tombent en panne - Décryptualité du 6 mai 2019

14 mai - Animatrice/animateur nature en CDD (30h) pour 4 mois

14 mai - Décryptualité du 13 mai 2019 - Tonton Alias raconte comment il s'est cogné au mur du content ID de Google

13 mai - Revue de presse de l'April pour la semaine 19 de l'année 2019