Feuilles de root

Logiciels libres, programmation et économie

Accueil » Programmation » Programmation Free Pascal » La liste d'action : une implémentation en Free Pascal

La liste d'action : une implémentation en Free Pascal

The action list data structure : a Free Pascal implementation

Cet article est basé sur The Action List Data Structure: Good for UI, AI, Animations, and More.

Présentation rapide

Dans cette article, Randy Gaul propose une structure données très pratique, appelée liste d'actions, utilisable pour l'IHM, l'IA ou les animations.

La liste d'actions (action list) est une structure de données simple utile pour beaucoup de tâches diverses dans un moteur de jeu. Elle remplace avantageusement une machine à états.

Un comportement est souvent géré par une machine à états finis. Habituellement implémentées avec des instructions conditionnelles ou le patron de conception Etat, les machines à états sont rigides et inflexibles. La liste d'action est un schéma d'organisation plus robuste dans le sens où elle modélise d'une manière claire la façon dont les choses se produisent dans la réalité. Pour cette raison la liste d'action est plus intuitive et flexible que l'automate à états.

La liste d'action est simplement un schéma d'organisation pour le concept d'action planifiée. Les actions sont stockées dans une file d'attente. A chaque exécution de la boucle de jeu, la liste est exécutée et toutes les actions de la liste sont exécutées dans l'ordre. Lorsqu'une action est terminée, elle est retirée de la liste.

Voici quelques types de domaine/fonction et les actions qui peuvent être réalisées :

En revanche la liste d'action n'est pas efficace pour gérer des fonctions de bas niveau comme la recherche de chemin ou le flocage. On ne devrait pas non plus implémenter le combat et d'autres domaines du système de jeu hautement spécialisés avec des listes d'actions.

La classe TActionList

L'interface de la classe TActionList est la suivante :

{ TActionList }

    TActionList = class
    private
        FDuration : Single;
        FTimeElapsed : Single;
        FPercentDone : Single;
        FBlocking : Boolean;
        FActions : TList;
    public
        procedure Update(const ADeltaTime : Single);
        procedure PushFront(AAction : TAction);
        procedure PushBack(AAction : TAction);
        procedure InsertBefore(const APosition : Integer; AAction : TAction);
        procedure InsertAfter(const APosition : Integer; AAction : TAction);
        function Remove(AAction : TAction) : TAction;
        function IsEmpty : Boolean;
        function TimeLeft : Double;
        function IsBlocking : Boolean;
        function First : TAction;
        constructor Create;
        destructor Destroy; override;
    end;

Pour stocker les actions, Randy Gaul suggère l'utilisation d'une liste chaînée ou bien le std::vector de C++. L'équivalent en Free Pascal est la Tlist. Comme amélioration, on peut utiliser la liste générique TFPGList de l'unité fgl.

Chaque action devrait être entièrement indépendante de telle manière que la liste d'actions ignore tout du fonctionnement interne de l'action. Cela fait de la liste d'actions un outil extrêmement flexible.

Les classes représentant les actions étendent une classe abstraite TAction.

{ TAction }

    TAction = class
    protected
        FOwnerList : TActionList;
    public
        FIsFinished : Boolean;
        FIsBlocking : Boolean;
        FElapsed : Single;
        FDuration : Single;
        procedure Update(const ADeltaTime : Single); virtual; abstract;
        { Executed whenever an action is inserted into a list }
        procedure OnStart; virtual; abstract;
        { Executed when the action finishes }
        procedure OnStop; virtual; abstract;
    end;

Les méthodes OnStart et OnStop sont exécutées respectivement lorsqu'une action est insérée dans la liste et lorsque l'action se termine. Ces fonctions permettent à l'action d'être entièrement indépendante.

Actions bloquantes ou non bloquantes

Une fonctionnalité importante est la capacité à définir une action comme bloquante ou non bloquante. La distinction est simple : une action bloquante termine la routine d'exécution de la liste d'action et les actions suivantes de la liste ne sont pas exécutées ; une action non bloquante permet l’exécution des actions suivantes.

Une simple valeur booléenne peut être utilisée pour marquer une action comme bloquante.

Une bon exemple d'utilisation d'une action non bloquante est le cas où plusieurs comportements en même temps.

Le concept d'action bloquante ou non bloquante permet de simuler la plupart des comportements requis dans un jeu vidéo.

Voici une implémentation de la méthode Update de TActionList :

procedure TActionList.Update(const ADeltaTime : Single);
var
    i : Integer = 0;
    LActions : TList;
    LAction : TAction;
begin
    LActions := TList.Create;
    LActions.AddList(FActions);

    while i <> LActions.Count do begin
        LAction := TAction(LActions.Items[i]);
        LAction.Update(ADeltaTime);
        if LAction.FIsBlocking then
            Break;
        Inc(i);
    end;

    //delayed destruction
    for i := FActions.Count - 1 downto 0 do
    begin
        LAction := TAction(FActions.Items[i]);
        if LAction.FIsFinished then
        begin
            LAction.OnStop;
            LAction := Remove(LAction);
            FreeAndNil(LAction);
        end;
    end;
end;

Exemple

Détaillons à présent un exemple d'utilisation d'une liste d'actions dans un jeu. Cela permettra d'en démontrer l'utilité et d'en montrer l'utilisation.

Dans un jeu 2D simple, une unité ennemie doit patrouiller, effectuant des aller-retours. Lorsque le joueur s'approche, elle doit lancer une bombe vers lui et effectue une pause. Si le joueur est toujours visible, il doit à nouveau lancer une bombe, sinon, il continue de patrouiller.

Il est possible d'utiliser une machine à états pour modéliser ce comportement. Les transitions entre chaque état doivent être codées manuellement et il faut conserver les états précédents pour continuer plus tard, ce qui s'avère assez pénible. Ce problème est particulièrement bien traité avec une liste d'actions.

Supposons que l'unité ennemie doive patrouiller de gauche à droite.

Voici ce quoi l'action PatrolLeft peut ressembler :

{ TPatrolLeft }

    TPatrolLeft = class(TAction)
    public
        procedure Update(const ADeltaTime : Single); override;
        procedure OnStart; override;
        procedure OnStop; override;
        constructor Create;
        destructor Destroy; override;
    end;

{ TPatrolLeft }

procedure TPatrolLeft.Update(const ADeltaTime : Single);
begin
    // Move the enemy left
    WriteLn('Move the enemy left');

    // Timer until action completion
    FElapsed := FElapsed + ADeltaTime;
    if FElapsed >= FDuration then
        FIsFinished := True;
end;

procedure TPatrolLeft.OnStart;
begin
    // do nothing
end;

procedure TPatrolLeft.OnStop;
begin
    // Insert a new action into the list
    FOwnerList.InsertAfter(1, TPatrolRight.Create);
end;

constructor TPatrolLeft.Create;
begin
    FIsFinished := False;
    FIsBlocking := True;
    FElapsed := 0;
    FDuration := 10;
end;

destructor TPatrolLeft.Destroy;
begin
    WriteLn('TPatrolLeft.Destroy');
    inherited Destroy;
end;

PatrolRight sera quasiment identique mais les directions sont inversées.

Ensuite, on ajoute une action de détection de la présence joueur à proximité. C'est une action non bloquante qui ne se termine jamais. Cette action vérifie si le joueur est présent à proximité de l'unité et si c'est le cas, elle va insérer une nouvelle action ThrowBomb juste avant elle dans la liste d'actions. Elle va également insérer une action Delay après l'action ThrowBomb.

L'action ThrowBomb est une action bloquante qui lance une bombe en direction du joueur. Elle pourrait être suivie par une action ThrowBombAnimation qui joue une animation mais pour simplifier on la remplacera ici par une Pause.

Il s'avère très utile de disposer d'une action qui ne fait rien mais diffère l'exécution de toutes les actions pendant un certain temps.