views:

73

answers:

6

I'm working on creating a basic RPG game engine prototype using JavaScript and canvas. I'm still working out some design specs on paper, and I've hit a bit of a problem I'm not quite sure how to tackle.

I will have a Character object that will have an array of Attribute objects. Attributes will look something like this:

function(name, value){
    this.name = name;
    this.value = value;
    ...
}

A Character will also have "skills" that are calculated off attributes. A skills value can also be determined by a formula entered by the user. A legit formula would look something like this:

((@attribute1Name + (@attribute2Name / 2) * 5)

where any text following the @ sign represents the name of an attribute belonging to that character. The formula will be entered into a text field as a string.

What I'm having a problem with is understanding the proper way to parse and evaluate this formula. Initially, my plan was to do a simple replace on the attribute names and eval the expression (if invalid, the eval would fail). However, this presents a problem as it would allow for JavaScript injection into the field. I'm assuming I'll need some kind of FSM similar to an infix calculator to solve this, but I'm a little rusty on my computation theory (thanks corporate world!). I'm really not asking for someone to just hand me the code so much as I'd like to get your input on what is the best solution to this problem?

EDIT: Thanks for the responses. Unfortunately life has kept me busy and I haven't tried a solution yet. Will update when I get a result (good or bad).

A: 

I think instead of letting them put the whole formula in, you could have select tags that have operations and values, and let them choose.

ie. a set of tags with attribute-operation-number:

<select>         <select> <input type="text">
@attribute1Name1  +        (check if input is number)
@attribute1Name2  -
@attribute1Name3  *
@attribute1Name4  /

etc.

digitalFresh
Thanks for this idea. It is an option. If I get hung up on creating the free-form formula field this could be a viable alternative until I can get a more robust solution. It's also arguable that this would be easier for users as they wouldn't have to worry about formula syntax as much. I'll have to try both and see what kind of feedback I get. Thanks!
framauro13
Try this for a minute and you'll see that it's way too tedious and slow.
Aaron Digulla
A: 

There is a really simple solution: Just enter a normal JavaScript formula (i.e. as if you were writing a method for your object) and use this to reference the object you're working on.

To change this when evaluating the method use apply() or call() (see this answer).

Aaron Digulla
This was what I planned on doing. Once validated, replace @'s with 'this.' and eval. My biggest concern was the user injecting JavaScript into the field before eval was called. I'll definitely test this out though... as they say, the simplest answer is often the correct one. I wish that always applied to software.
framauro13
If your game engine is to become something like Facebook (where anyone can edit the formulas), any way of editing the formulas is too dangerous because it will upset the balance of the game. So my guess is that you offer this for game designers in which case you can and should trust them.
Aaron Digulla
A: 

I recently wrote a similar application. I probably invested far too much work, but I went the whole 9 yards and wrote both a scanner and a parser.

The scanner converted the text into a series of tokens; tokens are simple objects consisting of token type and value. For the punctuation marks, value = character, for numbers the values would be integers corresponding to the numeric value of the number, and for variables it would be (a reference to) a variable object, where that variable would be sitting in a list of objects having a name. Same variable object = same variable, natch.

The parser was a simple brute force recursive descent parser. Here's the code.

My parser does logic expressions, with AND/OR taking the place of +/-, but I think you can see the idea. There are several levels of expressions, and each tries to assemble as much of itself as it can, and calls to lower levels for parsing nested constructs. When done, my parser has generated a single Node containing a tree structure that represents the expression.

In your program, I guess you could just store that Node, as its structure will essentially represent the formula for its evaluation.

Given all that work, though, I'd understand just how tempting it would be to just cave in and use eval!

Carl Smotricz
An FSM seems to be the "proper" solution, but for what I'm trying to achieve I'm still not sure if it's too much overkill. I was told by a coworker that an FSM would be the "easiest" and "safest" approach. Safest, sure. I'm not entirely convinced it's "easiest" yet. Thanks for the parser code, I'll dig into it more later.
framauro13
I've considered hand-writing an FSM for my task, but when I let Bison go to town it turned out there are 12 or 18 states required for that simple expression! An FSM is fast and relatively simple, but I feel it would s#ck to write one for evaluating expressions. I did use an FSM for my scanner, though, and that was sweetly easy.
Carl Smotricz
+2  A: 

Different idea, hence a separate suggestion:

eval() works fine, and there's no need to re-invent the wheel.

Assuming that there's only a small and fixed number of variables in your formula language, it would be sufficient to scan your way through the expression and verify that everything you encounter is either a parenthesis, an operator or one of your variable names. I don't think there would be any way to assemble those pieces into a piece of code that could have malicious side effects on eval.

So:

  • Scan the expression to verify that it draws from just a very limited vocabulary.
  • Let eval() work it out.

Probably the compromise with the least amount of work and code while bringing risk down to (near?) 0. At worst, a misuser could tack parentheses on a variable name in an attempt to execute the variable.

Carl Smotricz
This was my original thought. Using a regex to limit the input, count the parenthesis, verfiy variable names, then eval. I was told by a coworker that an FSM would be the easiest and safest approach. I agree with "safe", but "easy" is debatable :)
framauro13
A: 

I'm fascinated by the task of getting this done by the simplest means possible.

Here's another approach:

  1. Convert infix to postfix;
  2. use a very simple stack-based calculator to evaluate the resulting expression.

The rationale here being, once you get rid of the complication of "* before +" and parentheses, the remaining calculation is very straightforward.

Carl Smotricz
Instead of adding another answer, I suggest to edit your first one.
Aaron Digulla
I'd considered that, but that's the semantics for changing an answer, not for presenting a completely different one. I will edit out the apology, though; it contributes nothing.
Carl Smotricz
A: 

You could look at running the user-defined code in a sandbox to prevent attacks:
http://stackoverflow.com/questions/195149/is-it-possible-to-sandbox-javascript-running-in-the-browser

Tobias Cohen