안기영 (Ahn, Ki Yung): Party MoveNPC

1 About ¶

PartyMoveNPC is a DSL (domain specific language) prototype, which aims to describe the party movement of NPC (non-player characters) in a game. Each object, an NPC, has its own script describing its state and conditional clauses of movements and state transitions for each state. This script is to be executed every game turn so that each object could decide its movement and state. It is implemented in Haskell using the [http]

Glasgow Haskell Compiler (ghc-5.02.3) with the [http]

Happy Parser Generator (happy-1.13). I suggested this prototype in the Gretech Corporation. The demo program is built using a [http]

FunGEn, a game engine for Haskell, based on [http]

HOpenGL. Functional programming languages, especially pure language like [http]

Haskell is excellent for design and emplimentation of DSL.

[edit]

2 Demo ¶

A party of 4 NPC moves around the map following its leader. You can edit the scripts to modify the behavior of each NPC.

[edit]

2.1 Download ¶

PartyMoveNPC.zip (source and win32 binary)

[edit]

2.2 Snapshots ¶

[edit]

2.3 Developement Plattform ¶

cygwin (cygwin1.dll version 1.3.10) : A UNIX environment, developed by Red Hat, for Windows.
Glasgolow Haskell Compiler 5.02.3 : A robust, fully-featured, optimising interactive and batch compilation system for the Haskell 98 language.
happy-1.13 : The Parser Generator for Haskell
FunGEn-0.1 : A
HOpenGL-1.02 : A Haskell binding for the OpenGL graphics API (GL 1.2.1 / GLU 1.3) and the portable OpenGL utility toolkit GLUT.

[edit]

3 Design Overview ¶

Any game has a basic unit of cycle or turn. In each turn or cycle operation for current game state happens and calculates the next game state. There are several kinds of objects in a game. For example, a pacman, ghosts, dots and walls in a pacman game. A pacman is a player character, ghosts are NPC(non-player character)s and the others are objects which is not a character at all. NPCs are not controlled by the player but their behavior is quite complicated compared to non-character objects. NPC movement needs analysis of current game state and calculations to decide the movement. If NPC movement is hard coded in the program using general purpose language is inefficient development choice since it is hard to modify or expand the strategy of the movement. Therefore, domain specific language called game scripts are used for certain purposes including NPC movement description.

PartyMoveNPC is designed for NPC movement considering party movement. Complicated control structures such as loop are unnecessary since the game cycle itself is already a loop. Looping is also dangerous since infinite loop in the script would block the entire game execution. The aim of this script is to describe analysis of conditions and reaction based on the analysis for each cycle. Therefore, state and clause based simple structure is enough to handle this goal. If complicated functions are needed it should be provided as a primitive function so that the script itself could be kept as simple as possible.

Following example shows usage PartyMoveNPC. Each object has its own state apart form the global game state and movement strategies for each state. Every object should have the initial state called start. attr, state and move are primitive functions; attr sets and gets the attribute, state set the state and move means to move towered the postion.

start
[
    true : attr($pos,0,0), state($right).
]

right
[
    attr($pos,0)<29 : move(29,0).
    true : state($up).
]

up
[
    attr($pos,1)<29 : move(29,29).
    true : state($left).
]

left
[
    attr($pos,0)>0 : move(0,29).
    true : state($down).
]

down
[
    attr($pos,1)>0 : move(0,0).
    true : state($right).
]

[edit]

4 Formal Definition ¶

[edit]

4.1 Syntax ¶

[edit]

4.1.1 Operators ¶

The operaters follow the common notation. Their associativity and precedence is like the following. Operator with least precedence comes first.

'|'                left
'&'                left
'~'                left
'<' '=' '>'        none
'+' '-'            left
'*' '/'            left
'-' (unary)        left

[edit]

4.1.2 BNF ¶

<Script>    ::= <StateAList>

<StateAList>  ::= {- empty -}
                | <StateAList> <StateA>

<StateA>    ::= <var> '[' <ClauseList> ']'

<ClauseList>  ::= {- empty -}
                | <ClauseList> <Clause>

<Clause>    ::= <Exp> ':' <CmdList> '.'

<Exp> ::= true
        | false
        | int
        | '$' var
        | <Exp> '=' <Exp>
        | <Exp> '<' <Exp>
        | <Exp> '>' <Exp>
        | <Exp> '|' <Exp>
        | <Exp> '&' <Exp>
        | '~' <Exp>
        | '(' <Exp> ')'
        | <Exp> '+' <Exp>
        | <Exp> '-' <Exp>
        | <Exp> '*' <Exp>
        | <Exp> '/' <Exp>
        | '-' <Exp>
        | var 
        | var '(' <ExpList> ')'

<CmdList> ::= {- empty -}
            | <Cmd>
            | <CmdList> ',' <Cmd>

<Cmd> ::= var
        | var '(' <ExpList> ')'

<ExpLists> ::= <Exp>
             | <ExpList> ',' <Exp>

[edit]

4.2 Semantics ¶

O : object
E : environment
S : state

[edit]

4.2.1 Script ¶

    ------------
    E,O |-  => E


    E,O |- Clause => E'        S = state(O)
    ------------------------------------
    E,O |- (S,Clause),StateAList => E'


    E,O |- StateAList => E'        S = state(0)
    ----------------------------------------
    E,O |- (S,ClauseList),StateAList => E'

[edit]

4.2.2 Clause ¶

    E,O |- Exp : true        E,O |- CmdList => E'
    --------------------------------------------
    E,O |- (Exp,CmdList),ClauseList => E'


    E,O |- Exp : v        not (v = true)        E,O |- ClauseList => E'
    ---------------------------------------------------------------
    E,O |- (Exp,CmdList),ClauseList => E'

[edit]

4.2.3 Exp ¶

There are boolean, string, integer values in Exp. Comparison follows the semantics we commonly use except that false is less than true, boolean is always less then integer, and integer is always less than string.

    ----------------
    E,O |- true : true


    ------------------
    E,O |- false : false


    -----------------------
    E,O |- $string : string


    ----------
    E,O |- n : n


    E,O |- Exp1 : v1        E,) |- Exp2 : v2        v1 = v2
    -------------------------------------------------------
    E,O |- Exp1 = Exp2 : true


    E,O |- Exp1 : v1        E,O |- Exp2 : v2        not (v1 = v2)
    -------------------------------------------------------------
    E,O |- Exp1 = Exp2 : false


    E,0 |- Exp1 : v1        E,0 |- Exp2 : v2        v1 < v2
    -------------------------------------------------------
    E,O |- Exp1 < Exp2 : true


    E,0 |- Exp1 : v1        E,O |- Exp2 : v2        not (v1 < v2)
    -------------------------------------------------------------
    E,O |- Exp1 < Exp2 : false


    E,O |- Exp1 : v1        E,O |- Exp2 : v2        v1 > v2
    -------------------------------------------------------
    E,O |- Exp1 > Exp2 : true


    E,O |- Exp1 : v1        E,O |- Exp2 : v2        not (v1 > v2)
    -------------------------------------------------------------
    E,O |- Exp1 < Exp2 : false


    E,O |- Exp : true
    --------------------
    E,O |- ~ Exp : false


    E,O |- Exp : v        not (v = true)
    ----------------------------------
    E,O |- ~ Exp : false


    E,O |- Exp : v        not (v = true)
    ----------------------------------
    E,O |- ~ Exp : false


    E,O |- Exp1 : n1        E |- Exp2 : n2        n = n1+n2
    -----------------------------------------------------
    E,O |- Exp1 + Exp2 : n


    E,O |- Exp1 : v1        not (v1 ∈ N)
    -------------------------------------
    E,O |- Exp1 + Exp2 : false


    E,O |- Exp1 : v2        not (v2 ∈ N)
    -------------------------------------
    E,O |- Exp1 + Exp2 : false


    E,O |- Exp1 : n1        E,O |- Exp2 : n2        n = n1-n2
    ---------------------------------------------------------
    E,O |- Exp1 - Exp2 : n


    E,O |- Exp1 : v1        not (v1 ∈ N)
    -------------------------------------
    E,O |- Exp1 - Exp2 : false


    E,O |- Exp1 : v2        not (v2 ∈ N)
    -------------------------------------
    E,O |- Exp1 - Exp2 : false


    E,O |- Exp1 : n1        E |- Exp2 : n2        n = n1*n2
    -----------------------------------------------------
    E,O |- Exp1 * Exp2 : n


    E,O |- Exp1 : v1        not (v1 ∈ N)
    -------------------------------------
    E,O |- Exp1 * Exp2 : false


    E,O |- Exp1 : v2        not (v2 ∈ N)
    -------------------------------------
    E,O |- Exp1 * Exp2 : false


    E,O |- Exp1 : n1        E,O |- Exp2 : n2        n = n1/n2    not (n2 = 0)
    ------------------------------------------------------------------------
    E,O |- Exp1 / Exp2 : n


    E,O |- Exp2 : 0
    ------------------------
    E,O |- Exp1 / Exp2 : false


    E,O |- Exp1 : v1        not (v1 ∈ N)
    -------------------------------------
    E,O |- Exp1 / Exp2 : false


    E,O |- Exp1 : v2        not (v2 ∈ N)
    -------------------------------------
    E,O |- Exp1 / Exp2 : false


    ----------------
    E,O |- var : var@E,O    user defined interpretation of var on E,O


    E,O |- Exp1 : v1    ...    E |- Expn : vn
    ----------------------------------------------------
    E,O |- var ( Exp1, ... , Expn ) : var(v1,...,vn)@E,O    user defined interpretation of var(v1,...,vn) on E,O

[edit]

4.2.4 Cmd ¶

    --------------------
    E,O |- CmdList => E'    user defined interpretation

Contents

1 About ¶

2 Demo ¶

2.1 Download ¶

2.2 Snapshots ¶

2.3 Developement Plattform ¶

3 Design Overview ¶

4 Formal Definition ¶

4.1 Syntax ¶

4.1.1 Operators ¶

4.1.2 BNF ¶

4.2 Semantics ¶

4.2.1 Script ¶

4.2.2 Clause ¶

4.2.3 Exp ¶

4.2.4 Cmd ¶