Best way to search through a big plain object

[Daniel Friis Lindegaard]

Hi,

I'm developing a multiplayer game using Socket.io.

Because the amount of players and other game objects can potentially be a lot, I want to be able to select the game objects from an area (x and y coordinate) of the game.

A simplified version of how the gameObjects are stored inside node.js is below:

var gameObjects = {

"0": {x: 0, y: 32, name: "lol"},

"1": {x: 0, y: 32, name: "lol2"},

"11": {x: 0, y: 32, name: "lol3"}

}

There can be thousands of game objects at the same time..

Should I create a multidimensional array (x and y) to hold references to the game objects? Should I just filter the gameObjects or??

What would you think as the best practice?

[Aria Stewart]

You’re looking at an indexing problem. This one’s tricky, and depends greatly on how dense your data is.

If the x and y are mostly empty space, then you’ll want something like an adjacency list — what nodes are near other nodes (or certain grid points)

If they’re dense, you’ll probably want to use two-dimensional arrays.

How often do these searches occur? How much do things get updated?

That’ll play in as well.

Sorry there’s no easy answers, but ‘it depends’.

Aria

[Sofiane Akermoun]

Hello,

Reading your mail remind me a game dev design named quadtree to subdivise the screen or map and permit you to search inside smaller part instead of searching all the map for game object.

It is widely used for collision detection when we have to know where are all objects and check if each objects enter in contact with each others.
There is a lot of way to perform quadtree subdivision and it is huge source of discussion on game development.

May be it could help.

regards,

Sofiane Akermoun

ake...@gmail.com

--
Job board: http://jobs.nodejs.org/
New group rules: https://gist.github.com/othiym23/9886289#file-moderation-policy-md
Old group rules: https://github.com/joyent/node/wiki/Mailing-List-Posting-Guidelines
---
You received this message because you are subscribed to the Google Groups "nodejs" group.
To unsubscribe from this group and stop receiving emails from it, send an email to nodejs+un...@googlegroups.com.
To post to this group, send email to nod...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/nodejs/97c67f0f-8f46-4a85-a29b-c22f46fa4649%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
Sofiane AKERMOUN
ake...@gmail.com

[Joshua Lunsford]

I would recommend a quadtree as well. We have used them in Node.js for a few years. We've had them handle near a million objects with very little tweaking. The quadtree we made was a event based, so each users query of the quad tree had a bounding box centered on the user, and if anything ended up being inserted or removed from the quadtree in that bounding box the users event would fire and inform them. Use the node event loop to your advantage, verse making a CPU intensive blocking quadtree.

To view this discussion on the web visit https://groups.google.com/d/msgid/nodejs/CAN0_x-JqByZzQw93iQqGhcLv-HnrQQRE8NKdveVMfX9%3Dr%2BW1Tg%40mail.gmail.com.

For more options, visit https://groups.google.com/d/optout.

--

Thanks, 

Joshua Taylor Lunsford

[Aria Stewart]

On May 17, 2014, at 12:33 PM, Joshua Lunsford <joshua.tayl...@gmail.com> wrote:

> I would recommend a quadtree as well. We have used them in Node.js for a few years. We've had them handle near a million objects with very little tweaking. The quadtree we made was a event based, so each users query of the quad tree had a bounding box centered on the user, and if anything ended up being inserted or removed from the quadtree in that bounding box the users event would fire and inform them. Use the node event loop to your advantage, verse making a CPU intensive blocking quadtree.

Absolutely the right data structure for a lot of “within this box” or “near this object” type queries!

[Paul Vencill]

I've never done game dev, but I'm curious if there's anything to be gained by offloading this kind of query to the database? Most dbs now (including mongodb) have pretty robust index and search capabilities specifically built for bounding box and shape style queries.

[Aria Stewart]

On May 18, 2014, at 6:02 AM, Paul Vencill <paul.v...@gmail.com> wrote:

> I've never done game dev, but I'm curious if there's anything to be gained by offloading this kind of query to the database? Most dbs now (including mongodb) have pretty robust index and search capabilities specifically built for bounding box and shape style queries.

I’d imagine that for a couple thousand nodes, doing it in-core would be a lot lower latency. BEyond that, worth considering.

[Joshua Lunsford]

Just remember that you have 16.66ms to do any calculations to produce a fluid 60 frames per second. If part of the illusion of creating a seamless game world that is querying the positions of objects, then transferring them to a client, you have make that query as quick as possible to keep that illusion going. We have experimented keeping game objects in redis and updating N number of server processes with pubsub... we could get 1-5ms response time all on the same box. Still good for gaming at that point, so db work isnt off of the plate

[Angel Java Lopez]

I don't have all your context, but:

If the main case is "give me the objects at x,y" (and not the objects NEAR x, y), you can easily implement a two dimensional array

var objects = [];

function putObject(x, y, obj) {

    if (objects[x] == null)

        objects[x] = [];

    if (objects[x][y] == null)

        objects[x][y] = [];

    objects[x][y].push(obj);

}

function getObjects(x, y) {

    if (objects[x] == null)

        return [];

    if (objects[x][y] == null)

        return [];

    return objects[x][y];

}

I would write this using TDD, and then explore different implementations, measuring time.

Make it work, make it right, make it fast (attributed to Kent Beck)

Angel "Java" Lopez

@ajlopez

--

Job board: http://jobs.nodejs.org/
New group rules: https://gist.github.com/othiym23/9886289#file-moderation-policy-md
Old group rules: https://github.com/joyent/node/wiki/Mailing-List-Posting-Guidelines
---
You received this message because you are subscribed to the Google Groups "nodejs" group.
To unsubscribe from this group and stop receiving emails from it, send an email to nodejs+un...@googlegroups.com.
To post to this group, send email to nod...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/nodejs/CABPQR%3DF1HAePkTH-L09tQiQcv67WL2OuRQSpqFKJ__7DtUi8dQ%40mail.gmail.com.

[Peter Rust]

On the in-core vs DB front, NeDB (https://github.com/louischatriot/nedb) might be worth considering -- it's a DB that runs in-core (implemented in JS) -- embedded/in-memory.

To avoid having thousands/millions of objects in JS (which can kill performance due to garbage collection / tracking), the data is stored in a buffer.

-- peter

[Stefano Baghino]

I don't know about quadtrees but you should check out R-Trees. It's a data structure used in geographical information systems to index coordinates and efficiently perform spatial queries on them. I know there's at least one JS implementation in NPM that you could use in a Web app with Browserify. They're perfs are crazy, in a GIS I'm building I could query hundreds of thousands of objects in a matter of 10 ms (in-memory) . If you need more performance you could try to get a C implementation and compile it to ASM.js.

[Stefano Baghino]

*their, sry

[George Stagas]

2014-05-19 5:25 GMT+03:00 Joshua Lunsford <joshua.tayl...@gmail.com>:

Just remember that you have 16.66ms to do any calculations to produce a fluid 60 frames per second.

Not true. If you separate rendering from value updates, you can get away with 10 updates/sec or even less for certain objects. You don't really need 60 updates/sec at the physics/motion level, you need them at the rendering level. You can update much less and use interpolation to still be fluid at 60 fps.

 

--

Job board: http://jobs.nodejs.org/
New group rules: https://gist.github.com/othiym23/9886289#file-moderation-policy-md
Old group rules: https://github.com/joyent/node/wiki/Mailing-List-Posting-Guidelines
---
You received this message because you are subscribed to the Google Groups "nodejs" group.
To unsubscribe from this group and stop receiving emails from it, send an email to nodejs+un...@googlegroups.com.
To post to this group, send email to nod...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/nodejs/CABPQR%3DF1HAePkTH-L09tQiQcv67WL2OuRQSpqFKJ__7DtUi8dQ%40mail.gmail.com.