How to represent entities in a grid

Question

I'm attempting to simulate a bunch of simple entities moving around on a grid.

Individual entities will have specific properties and the grid will be a two dimensional array of square cells that may at any time contain anywhere from zero to multiple entities.

What type of data structures would be appropriate here given that I don't want to over engineer things but at the same time see problems with the obvious simple solutions?

If I have an array of entities where each entity has it's coordinates, then this is fine for populating the grid each step. But this makes it so if I want to know something about a given location, then I have to loop through the entire entity array to see if there's an entity at that location. (or adjacent to it if I needed to know something like that)

And the opposite (having the grid array keeping track of everything) runs into the reverse problem where if I want to know something specific about an entity (like it's name or fitness) I need to search through the whole grid array to find the entity I'm looking for.

And finally there's my third approach which seems over engineered: Have an array of all the entities and the grid array be a bunch of arrays of pointers to whatever entities are in that cell. In this third one I think the cells would need to know which entities were in them and the entities would need to know which cell they were in. And I'm not even sure if I want entities to know their coordinates. It might make more sense for them to only recognize their surroundings and then move, relative to their own location. Also, I'm doing this in javascript, so pointers are probably only logically possible with some hack and I'm trying to not over engineer things.

Answer 1

Are these objects, grid and entity, in a system where they each only have relevance when connected to the other? What I mean is will your entity objects only ever be used in this grid? And will this grid object only ever hold entity objects? If so, then you can link them together not just from the grid's perspective, but also from the entity.

I assume that your grid is made up of a main grid object, which likely consists of a collection of rows, and each row has a collection of cells. Each cell of course being equivalent one [x][y] location in an array. Each of these cells will have a collection of entity objects.

If you create your objects to be "hierarchically referential" it will be easy to move through the list. The grid may have a collection of rows, but each row should have a parent property that references to the grid it's apart of. The rows may have a collection of cells, but each cell should have a parent property that refers to its parent row. And each entity object should have a cell property that refers to the cell of which it is apart.

When you create your move() function for the entities, it will need to 1) remove itself from its current cell entity collection, 2) add itself to the new cell collection, and 3) update the entity.cell property to refer to the new cell.

This is an untested mock-up of the kind of structures I'm talking about:

function grid(height, width) {
    this.rows = [];

    this.cellAt = function(row, cell) {
        return this.rows[row].cells[cell];
    };

    this.entitiesAt = function(row, cell) {
        return this.cellAt(row, cell).entities;
    };

    this.addRow = function() {
        var r = new row(this);
        this.rows.push(r);
        return r;
    };

    //create the grid in the default size.
    if (height != null && width != null) {
        var i, j, r;
        for (i = 0; i <= height; i++) {
            r = this.addRow();
            for (j = 0; j <= width; j++)
                r.addCell();
        }
    }
}

function row(parentGrid) {
    this.grid = parentGrid;
    this.cells = [];

    this.getIndex = function() {
        return this.grid.rows.indexOf(this);
    };

    this.addCell = function() {
        var c = new cell(this);
        this.cells.push(c);
        return c;
    };
}

function cell(parentRow) {
    this.row = parentRow;
    this.entities = [];

    this.getIndex = function() {
        return this.row.cells.indexOf(this);
    };

    this.addEntity = function(entity) {
        this.entities.push(entity);
        entity.cell = this;
    };

    this.removeEntity = function(entity) {
        var i = this.entities.indexOf(entity);
        if (i >= 0) this.entities.splice(i, 1);
        entity.cell = null;
    };

    this.removeEntityAt = function(index) {
        if (this.entities.length < index && index >= 0) {
            e = this.entities[index];
            this.entities.splice(index, 1);
            e.cell = null;
        }   
    };
}

function entity() {
    this.cell = null;

    this.getLocation = function() {
        return {
            "row" : this.cell.row.getIndex(),
            "cell" : this.cell.getIndex()
        };
    };

    this.move = function(row, cell) {
        var g = this.cell.row.grid;
        this.cell.removeEntity(this);
        g.cellAt(row, cell).addEntity(this);
    };
}

Note: Careful with indexOf(). It's helpful, but not fully cross browser.

Actual usage would look something like this.

Create the new grid

var grid1 = new grid(100, 100);

Create a new entity and add it to the grid:

var e = new entity();
grid1.cellAt(12, 23).addEntity(e);

Move an entity:

e.move(53, 23);

There is potentially a lot more here. For instance, if this grid, row, cell, and entity objects are going to represent actual HTML elements, in the creation script you can have it create those HTML elements. For example, you might want to create a div element when a new row and/or cell is created. One way to link the array to the div so that you have a connection between the logical grid and the "physical" element:

<div data-row="12" data-cell="23"><div>

Bottom line is that I think creating these structured and "hierarchically referential" objects will make it easier for you to move around in the gird. Also, it would be super easy to modify this to support multiple grids in one document.