[09 Sep 2008] How to manage a tree data structure?

[Paolo Canonici]

Note: This is an archived post that was originally sent to the Hollywood mailing list on Tue, 09 Sep 2008 16:04:40 +0200

Hi all,

I regularly read the messages here in the group, but I never wrote because of my poor english. Now I'm having some difficulty so I decided to ask for help here... I'm developing a multiplatform old-style adventure game in Hollywood, wich features a small scripting language too. The scripting is needed to manage the status variables during the game action. Briefly I implemented the lexer and now I'm writing the parser that generates the syntax tree to be able to evaluate the expressions, but I can't figure out how to manage the tree data structure.

My difficulty lies in the way Hollywood manages the function's formal parameters, because I can't pass value by reference in a function call... is correct? Values are always passed by value, so I can't keep the pointer of the last processed node.

I.e. see the following code fragment:

Code: Select all

function    mscInsertSyntaxTreeNode(root, currentNode, lastOperatorNode, newTok)
    local    newSTNode    = mcsCreateSyntaxTreeNode(newTok)
   
    if (getType(root) = #NIL)
        switch(newSTNode.type)
            case #MCSTYPE_OPERATOR:
                return(newSTNode, newSTNode, newSTNode)
            case #MCSTYPE_NUMBER or #MCSTYPE_IDENTIFIER:
                return(newSTNode, nil, newSTNode)
        endswitch
    else
        switch(newSTNode.type)
            case #MCSTYPE_OPERATOR:
                if (getType(lastOperatorNode) = #NIL)
                    lastOperatorNode = mcsInsertSyntaxTreeChildNode(newSTNode, currentNode)
                     ...
                endif
               
            case #MCSTYPE_NUMBER or #MCSTYPE_IDENTIFIER:
                lastOperatorNode = mcsInsertSyntaxTreeChildNode(lastOperatorNode, newSTNode)
                ...
        endswitch
        return(root, lastOperatorNode, newSTNode)
    endif
endfunction

function    mcsParser(tokenStream)
    local    tokCount        = listItems(tokenStream)
    local    root            = nil
    local    currentNode        = nil
    local    lastOperatorNode    = nil
    local    newTok            = nil
   
    for local i = 0 to tokCount - 1
        newTok    = tokenStream[i]
        ; Il nuovo nodo viene inserito nella struttura sintattica corrente
        root, lastOperatorNode, currentNode = mscInsertSyntaxTreeNode(root, currentNode, lastOperatorNode, newTok)
    next
    return(root)
endfunction

In the mcsInsertSyntaxTreeChildNode function call, the lastOperatorNode is disconnected from the root! How do I work around this problem? I need to maintain a sort of reference pointer to the root, the current node and the last operator's node.

Note: I voluntarily set aside the inverse Polish notation to maintain the ease of writing script expressions.

I hope someone can help me and I apologize for my english!

Thanks!

[airsoftsoftwair]

Note: This is an archived post that was originally sent to the Hollywood mailing list on Thu, 11 Sep 2008 23:18:59 +0200

Hmm, correct me if I'm wrong, but wouldn't it be much easier to just use a table to store your data tree? The code you posted looks like if you were trying to port some C code to Hollywood. In C lists are usually organized in the way your code tries to do it, but in Hollywood this can really be done much easier by just using tables. You don't have to allocate anything at all, you can just stuff nodes into the table as you like it...

[Paolo Canonici]

Note: This is an archived post that was originally sent to the Hollywood mailing list on Fri, 12 Sep 2008 13:28:21 +0200

Hi Andreas,

I'm just using nested tables, so that each node is a table that contains data and the list (table) of children.

The idea that it seems C porting code is perhaps due to the fact that I'm not yet very familiar with Hollywood so I tend to use the approach experienced with C and Pascal.

The scripting system will work with brief (short) expressions associated with certain actions of the player, and then I felt that this structure was suitable and convenient because I can easily obtain the result with a recursive function on the tree.

Some examples of use might be as follows:

Code: Select all

locationIsVisible = playerHasObject("map") or playerHasTalkedTo("cartographer")

or:

Code: Select all

playerPoints += 100

In this regard, could be very useful to have an Hollywood function to execute a line of code at run-time... to do something like:

Code: Select all

varName = eval("Pow(2,4)")

or even:

Code: Select all

eval("varName = "..myCustomCode)

I used a similar system for the management of dialogues in a previous adventure game written with Director's Lingo: in a single text file, there was the dialogue and the code to manage the dialogue itself. It was a pretty simple mechanism!

The code (lexer and parser that generate the tree) now works with algebraic expressions, and although it is not yet completed it looks like this (apologise for Italians comments):

Code: Select all

function    mscInsertSyntaxTreeNode(root, currentNode, lastOperatorNode, newTok)
    local    newSTNode    = mcsCreateSyntaxTreeNode(newTok)
   
    if (getType(root) = #NIL)
        switch(newSTNode.type)
            case #MCSTYPE_OPERATOR:
                return(newSTNode, newSTNode, newSTNode)
            case #MCSTYPE_NUMBER:
                return(newSTNode, nil, newSTNode)
            case #MCSTYPE_IDENTIFIER:
                return(newSTNode, nil, newSTNode)
        endswitch
    else
        switch(newSTNode.type)
            case #MCSTYPE_OPERATOR:
                if (getType(lastOperatorNode) = #NIL)
                    ; Se non ci sono precedenti operatori, vuol dire che l'albero è appena iniziato, c'è solo un valore al suo interno
                    lastOperatorNode = mcsInsertSyntaxTreeChildNode(newSTNode, currentNode)
                    root = newSTNode
                else
                    ; Confronto la priorità di questo operatore con lastOperatorNode
                    switch (newSTNode.index)
                        case #MCSOPERATOR_PARENTOPEN:
                            ; Quando incontro una parentesi aperta, questa diviene sempre figlia del precedente operatore (se esiste)
                            mcsInsertSyntaxTreeChildNode(lastOperatorNode, newSTNode)
                            lastOperatorNode = newSTNode
                        case #MCSOPERATOR_PARENTCLOSE:
                            /*
                                Quando incontro una parentesi chiusa, risalgo l'albero fino alla relativa parentesi aperta
                                e la rimpiazzo con quella chiusa
                            */
                            local    tmpNode        = mcsFindSyntaxTreeNodeByOperatorType(currentNode, #MCSOPERATOR_PARENTOPEN)
                            if (MCTableHasElement(tmpNode, "type"))
                                local    tmpFather    = tmpNode.father
                                local    tmpChild    = mcsCutSyntaxTreeChildNode(tmpNode)
                               
                                if (MCTableHasElement(tmpFather, "type"))
                                    mcsCutSyntaxTreeChildNode(tmpFather)
                                    mcsInsertSyntaxTreeChildNode(tmpFather, newSTNode)
                                else
                                    root = newSTNode
                                endif

                                if (MCTableHasElement(tmpChild, "type"))
                                    mcsInsertSyntaxTreeChildNode(newSTNode, tmpChild)
                                endif
                               
                                lastOperatorNode = newSTNode
                            else
                                ;Errore: manca la parentesi aperta!
                                lastOperatorNode = newSTNode
                            endif
                        default:
                            local    prec1    = MCSOperator[lastOperatorNode.index].precedence
                            local    prec2    = MCSOperator[newSTNode.index].precedence
                            if (lastOperatorNode.index = #MCSOPERATOR_PARENTCLOSE)
                                ; Se il precedente operatore è una parentesi chiusa, semplicemente lo rimpiazzo con l'operatore appena trovato
                                lastOperatorNode = mcsReplaceSyntaxTreeNode(lastOperatorNode, newSTNode)
                            elseif (prec1 < prec2)
                                ; lastOperator ha priorità minore di quello corrente
                                local    tmpChild    = mcsCutSyntaxTreeChildNode(lastOperatorNode)
                                mcsInsertSyntaxTreeChildNode(newSTNode, tmpChild)
                                mcsInsertSyntaxTreeChildNode(lastOperatorNode, newSTNode)
                                lastOperatorNode = newSTNode
                            else
                                local    tmpFather    = lastOperatorNode.father
                               
                                lastOperatorNode = mcsInsertSyntaxTreeChildNode(newSTNode, lastOperatorNode)
                                if (MCTableHasElement(tmpFather, "type"))
                                    mcsCutSyntaxTreeChildNode(tmpFather)
                                    mcsInsertSyntaxTreeChildNode(tmpFather, newSTNode)
                                else
                                    root = lastOperatorNode
                                endif
                            endif
                    endswitch
                endif
               
            case #MCSTYPE_NUMBER:
                ; Aggiungo l'elemento come figlio di lastOperatorNode
                lastOperatorNode = mcsInsertSyntaxTreeChildNode(lastOperatorNode, newSTNode)
            case #MCSTYPE_IDENTIFIER:
                ; Aggiungo l'elemento come figlio di lastOperatorNode
                lastOperatorNode = mcsInsertSyntaxTreeChildNode(lastOperatorNode, newSTNode)
        endswitch
        return(root, lastOperatorNode, newSTNode)
    endif
endfunction

function    mcsParser(tokenStream)
    local    tokCount        = listItems(tokenStream)
    local    root            = nil
    local    currentNode        = nil
    local    lastOperatorNode    = nil
    local    newTok            = nil
   
    for local i = 0 to tokCount - 1
        newTok    = tokenStream[i]
        ; Il nuovo nodo viene inserito nella struttura sintattica corrente
        root, lastOperatorNode, currentNode = mscInsertSyntaxTreeNode(root, currentNode, lastOperatorNode, newTok)
       
        mcsCreateBrushSyntaxTree(root)
        mcsSaveBrushSyntaxTree(i)
    next
    return(root)
endfunction

Every suggestion will be welcome, thanks a lot!

I have many topics to be proposed to this discussion group, but for me it is also very difficult to write in English!

[Allanon]

Note: This is an archived post that was originally sent to the Hollywood mailing list on Fri, 12 Sep 2008 19:46:16 -0000

Hello Paolo, don't worry about your english, I'm italian too and my english is pretty weird, so please don't hesitate to write your feelings and ideas ^_^ We need to help each other to maximize our Hollywood experience and to help Andreas to develop and add features to his wonderful creature ^^

Good coding and welcome to this board (as writer too )

Fabio

[airsoftsoftwair]

Note: This is an archived post that was originally sent to the Hollywood mailing list on Fri, 12 Sep 2008 23:17:15 +0200

Hi Andreas, I'm just using nested tables, so that each node is a table that contains data and the list (table) of children. The idea that it seems C porting code is perhaps due to the fact that I'm not yet very familiar with Hollywood so I tend to use the approach experienced with C and Pascal. The scripting system will work with brief (short) expressions associated with certain actions of the player, and then I felt that this structure was suitable and convenient because I can easily obtain the result with a recursive function on the tree.

Some examples of use might be as follows: locationIsVisible = playerHasObject("map") or playerHasTalkedTo("cartographer") or: playerPoints += 100

In this regard, could be very useful to have an Hollywood function to execute a line of code at run-time... to do something like: varName = eval("Pow(2,4)") or even: eval("varName = "..myCustomCode)

If you're only targetting Amiga systems, you could use ARexx as an "Eval" function, i.e.

Code: Select all

; Evaluate expression 5*4+(6-3)*2/4 using ARexx
result = RunRexxScript("var = 5*4+(6-3)*2/4\nReturn var\n", TRUE)

But of course, this would only work on Amiga. Not on Mac/Windows.

The reason why there is no function which would allow you to pass Hollywood code as a string is that this could be used to create a Hollywood full version! For example, imagine there is a function RunHollywoodCode() which could be used like this:

Code: Select all

RunHollywoodCode("NPrint('Hello from run time code!')\nWaitLeftMouse\nEnd")

Then someone could compile the following program and upload it to Aminet:

Code: Select all

f$ = FileRequest("Select Hollywood script to run")
OpenFile(1, f$)
contents$ = ReadString(1, FileLength(1))

Print("Now executing your script...")
RunHollywoodCode(contents$)

Now everybody would be able to run Hollywood scripts without having to buy the full version. That's the problem why I can't implement a function to run Hollywood code Such a function could be used to "crack" Hollywood.

But I see that in your case such a function would be really useful. But I can't think of a way of implementing it without exposing Hollywood to crackers.

Or would it be sufficient for your project if such a function would be limited to parse a single line of code? How extensive is the code you want to execute at run-time? Is it just a single line? Just some evaluation of math expressions? Or what exactly do you want to be able to do at run-time?

By the way, your English is perfectly comprehensible. Your source code is much more cryptical to me

[Paolo Canonici]

Note: This is an archived post that was originally sent to the Hollywood mailing list on Tue, 16 Sep 2008 11:47:12 +0200

Unfortunately the game must run on all these platform: Amiga, Windows and MacOSX so I can't use the RunRexxScript function.

Currently my little scripting system is able to execute a single statement (math or boolean expression) at a time and I have not yet implemented any keyword so the system limits the "programmer" to assign values to variables that he will require.

Of course I will implement the keywords necessary to manage conditional jumps, wich will be useful for the dialogues development. I don't think ti will be necessary to add more elements to the scripting and I'm still thinking if it can be really useful to add the ability to call some internal game function.

Thanks for your attention! Paolo.

[airsoftsoftwair]

Note: This is an archived post that was originally sent to the Hollywood mailing list on Tue, 16 Sep 2008 13:33:18 +0200

Unfortunately the game must run on all these platform: Amiga, Windows and MacOSX so I can't use the RunRexxScript function.

Currently my little scripting system is able to execute a single statement (math or boolean expression) at a time and I have not yet implemented any keyword so the system limits the "programmer" to assign values to variables that he will require. Of course I will implement the keywords necessary to manage conditional jumps, wich will be useful for the dialogues development. I don't think ti will be necessary to add more elements to the scripting and I'm still thinking if it can be really useful to add the ability to call some internal game function.

Ok. I will also try to see if there's a feasible way of allowing internal scripting without exposing Hollywood.

Please don't hesitate to ask if you need some specific function for your game. I'm always willing to support major projects written using Hollywood because big projects like your game or SCUILib by Fabio are always a very helpful to test the strength of Hollywood. So if you're missing a specific function, don't hesitate to ask on this list and I'll see what I can do.

[TheMartian]

Note: This is an archived post that was originally sent to the Hollywood mailing list on Tue, 16 Sep 2008 18:22:41 -0000

Speaking of making 'executable' strings in Hollywood. Wouldn't it be feasible to take advantage of LUAs ability to use any string as indexes in a table?

A simple assignment in a script, as in the string "LET v1 4" (assign 4 to the variable v1) could be implemented like this...

Code: Select all

variables={}
action={}

action[cmd$]=function(varname$,value)
  variables[varname$]=value
EndFunction

Where cmd$ is "LET", varname$ is used as an index in a table for variables and value is... well the value assigned to variable [varname$]

So the function used to interpret the "LET" statement would be:

Code: Select all

action["LET]=function(varname$,value)
  variables[varname$]=value
EndFunction

You would probably also need a table with the names of the variable indexes, so you could search for used variable names (Unless there is a way to find out which strings you have used as indexes for a table by other means.)

Similarly command strings could be constructed like this:

Code: Select all

"GO WEST" //where direction$ = "WEST"//

action["GO"]=function(direction$)
  // some code to handle moving westwards on the map //
EndFunction

If directions$ was a list you could as easily implement a multicommand string like "GO WEST EAST EAST" for three consecutive movements.

Anyway I look forward to see the result of your project.

regards Jesper

[airsoftsoftwair]

Note: This is an archived post that was originally sent to the Hollywood mailing list on Wed, 17 Sep 2008 11:39:35 +0200

Speaking of making 'executable' strings in Hollywood. Wouldn't it be feasible to take advantage of LUAs ability to use any string as indexes in a table?

[...]

Yes, it could certainly be done this way but I think Paolo's main concern was to have expressions handled correctly, e.g. "LET v1 4*5*(v3-v2)*v4+2" or something. It gets more difficult to write a parser for such code that respects operator & parentheses priorities etc.

[TheMartian]

Note: This is an archived post that was originally sent to the Hollywood mailing list on Wed, 17 Sep 2008 20:18:57 -0000

Hmm. Would it not be a help to convert such expressions to reverse polish notation before interpreting them. Then the calculations could be done recursively. I think the example would have to be translated into something like this if I remember my old HP finance calculator programming correctly:

Code: Select all

"4 5 * v3 v2 - * v4 * 2 +"

Getting rid of paranthesis considerations in the parser can only be a good thing. Handling of priorities are implicit in the format of the expression

Of course the translation from 'human' form to a stack-friendly reverse polish notation form should be done by the program...

I am just thinking loud and haven't actually tried it, but it is an idea.

regards Jesper