Tuesday, 8 March 2011

Naive Javascript (possibly OO) questions

So I've got a data structure I want to initialize for a game map, for example:

// A grid is a collection of cells. It is initialized to the default contents.
function Grid(rows, cols, default)
this.rows = rows;
this.cols = cols;
this.cells = new Array(cols);
for(x = 0; x < cols; x++)
this.cells[x] = new Array(rows);
for(y = 0; y < rows; y++)
this.cells[x][y] = default;

Now, my question is given I want to have default represent a particular terrain type at a location, plus unit types, plus improvements etc. I can see 2 ways of approaching this:

1. Have multiple grids, each of which points to a different thing e.g. TerrainGrid, UnitGrid etc. where a thing might be an integer value, string, head of a linked list and so on.

2. Have a single grid, MapGrid, which points to a Cell object which contains information about these multiple things.

Now the complication is of course, I want multiple view ports pointing at possibly different lists of grids for e.g. multiple players, isometric views, overhead views, different map projections, so I also need a ViewPort object which contains a list of (possibly non-rectangular) cells. (Technically, a view port should always be a rectangular projection, so maybe call it MapProjection instead).

Now, here's the naive question. How do I ensure that I only have a single instance of each cell in my ViewPorts? My approach would be the view port contains a list of (x,y) coordinates of the cells in the view, but is there any advantage to directly pointing at the Cell objects, assuming I go with a single Cell object in a single Grid as opposed to multiple grids. If I do, how do I ensure that I'm using a reference to a cell (and not a copy) and that if I destroy a ViewPort I don't delete the underlying cells. What about concurrency issues, where I have two players acting on the same underlying cell object through different ViewPorts?

These are terribly naive questions which because of the elegant design of C, never really enter the picture when I'm working on Unangband.

I can see how people get paralyzed trying to develop in so-called higher level languages.


Kris said...

Are the ViewPorts going to store additional data? If not, then anything more than the boundary size may be overkill.

OTOH, linking directly to the cell object takes out a some maths and a few dereferences, which might help in an inner loop. I think you need to try pretty hard to get a copy rather than a reference. Destroying stuff really shouldnt happen- let it go out of scope and the garbage collector will deal with it.

Are we talking javascript in-a-browser, or on some other platform? IIRC in-a-browser is explicitly single-threaded, which makes concurrency problems largely go away.

But I'm not sure how this jibes with multiple players- are we talking some network thing? That would add a whole layer of complexity leaving javascript the least of your concurrency worries...

Note that despite a fair amount of web hackery, I'm not exactly a js guru, so take this with a grain of salt...

Tom said...

As Kris said, unless you try to hard to create a copy, it's a reference.

var o = {}; //o is now a pointer to an object

Iwan said...

Are we talking Node.js here? Anyway...

First of all, do you want your rows/cols/cells values to be public? If no, using "this.x" is the wrong way to go.

I would suggest that you use an array (technically an Object) of properties for each cell.


Then you can go ahead and say

this.cells[x][y].terrain="stone floor";
this.cells[x][y].loot=["large claymore","a small ring"];

This takes advantage of the dynamic nature of Javascript.

You can also go ahead and use

this.cells[x][y] = default;

and pass an object as "default"

default = {"terrain":"stone floor", "monsters":"Goblin"};

Hope that helps

Anonymous said...
This comment has been removed by a blog administrator.
Anonymous said...

Sounds like a good chunk of your concern here is about garbage collection, really. Outside of that, there's not much reason to be worrying about "copies" of things, or "deleting" stuff.

Essentially, you want to treat object references like the pointers you're used to, except that they don't need to be explicitly malloced or freed. Because of that, many things are much easier. But to someone who's used to explicitly managing memory, it can seem a little daunting.

The only danger I see in what you're describing is in the "default" cell. Specifically, if you want to be able to get the cell at a given location, then modify it, you're going to have a potential problem if you grab the "default" cell, modify it, and all of the default cells change at once. Because of that, you'll either want to make all of the cells different cells (initialized from the default), so that when you change their fields you're only changing it at the one location, or you'll need to be careful to check if the cell you want to change is the default one when you go to modify it, and make a new copy at that time.

But this is really the same issue as if you were using C and had a single copy of a cell struct that you used for all of the defaults: if you have an array of pointers to cells, and many of those pointers are to the "default" cell, you'll need to check if you're pointing to the default there, too.

In Javascript in particular, you might do this with an object prototype. Something like:

function cell() {
    return this;
cell.prototype = {
    terrain: "stone floor",
    symbol: "."

In this case, every cell would get these qualities by default when you do "new cell()", but if you write to the cell, its content would change. (And if you wanted, you could modify the default values in the middle of execution by changing cell.prototype.)

Then in your loop, instead of saying this.cells[x][y] = default, say this.cells[x][y] = new cell().

As for your multi-player thoughts... that's not uncomplicated in Javascript, but it's no less complicated in C. You're talking about synchronizing state between clients and servers there, which is a whole different kettle of fish. (Or if you're not, you're talking about synchronizing access via mutexes and such.) Can't really say much about it without more detail.

kikito said...

I'd use one matrix or list of cells, storing one single "class" of cells. This class would hold "location-related" information:

* the kind of terrain (field, mountains, lake)
* the amount of gold
* the height

Each cell would have one (or several) lists of entities.

* There're two orcs on this cell
* There's a city on this cell

Having one "superclass" for all the cells seems the right choice, simply because you will normally want to also include a reference to the cell they are in on the Entities; so you can do things like

if(orc.cell.height > 4) { damage ++; }
if(city.cell.gold > 10) { city.cell.gold --; }

Jonathan Stickles Fox said...

I haven't worked with Javascript, but I believe it works the same way as Actionscript in how it handles object references -- primitives, such as integers, are assigned and passed by value, while objects, including Arrays, are assigned and passed by reference.

Technically, this isn't a double standard. Rather than storing object and array data by value, all object and array variables are actually references. You then pass your reference by value. The "new" keyword in C++ works the same way, returning a pointer rather than an actual object.

One ramification is what J. Prevost says above, which is that you need to be careful with how you assign a default node. If you don't explicitly make a copy when initializing new nodes, you can end up with a large matrix of references to a single node.

Darius Kazemi said...

I second Iwan's comment.

Andrew Doull said...

Iwan: I probably won't make the cells directly public, if only because I want to be able to support game replays and will have to record deltas to the original map as game play progresses.

And limeJS fwiw (Which is built on Closure).

Andrew Doull said...

Thanks everyone for the quick and useful feedback. I should really post programming queries more often, since it seems to bring everyone out of the woodwork :)

x said...

Often, objects on the map use linked lists. But I second the idea about having a "super-class". Having tried both ways, I find it way easier to maintain a single "super-class" than it is to maintain a bunch of smaller classes.

bruce.denby said...

Got it thanks.