1

I'm making an MMO which will have a 2d world. (This is a learning project so don't try to talk me out of it :) I'd like to experiment with a new data store for it, and I've read good things about redis. I've been through the tutorials, and I think I'm beginning to understand redis' strength, but it's not clear how I might model such a world.

Here are some design requirements

  1. I need to be able to send down the current position of elements in the world. It would be acceptable to divide these into geographic "rooms" for performance.
  2. I need to be able to "move" an object in the world, changing its position
  3. I need to get information about an object: what's its name, type, attributes, etc.
  4. I need to be able to calculate basic collisions (obj a wants to move right, is there a rock there?)

How would you model this in redis? Is redis an inappropriate choice?

Sean Clark Hess
  • 15,859
  • 12
  • 52
  • 100
  • We need more information. Among the questions that spring to mind: Does the world have a rectangular (cartesian) grid shape or some other shape? Are its boundaries fixed or can it expand, and in what way? How do you define position, region, place, room, point, etc.? Will there be a hierarchy, e.g. world > region > point? It's probably best to decide what data structures are the best fit and then choosing a data store based on that. Similar question w/ useful answer: http://stackoverflow.com/questions/4551575/data-structure-to-represent-a-maze – Jordan Running Jan 15 '12 at 23:10
  • Let's assume it is an infinite plane. Objects can only be on integer coordinates, and the world will start at 0,0 and go negative and positive. There doesn't HAVE to be a concept of rooms, I think of that as an optimization. Let's say the rooms are simply every 100x100 square of the world. The game's UI wouldn't show the rooms at all. – Sean Clark Hess Jan 15 '12 at 23:28

2 Answers2

2

Assuming the 2D world is split into squares of known coordinates, you would probably do best in redis to produce keys based on the coordinates which return Sets of ID's of objects (or exits/paths, or terrain, etc.)

e.g. a very simple illustration

obj:1:name = Rock
obj:1:passable = false
obj:2:name = Skeleton
obj:2:passable = true
loc:0:0:objs = {1,2} // loc:0:0 contains obj:1 and obj:2
loc:0:0:paths = {0:1, 1:0, 1:1} // three legal paths, to loc:0:1, loc:1:0, loc:1:1

I'm not enough of a redis expert to know if this domain is going to cause you problems in redis, so take my advice with a grain of salt.

jkraybill
  • 3,339
  • 27
  • 32
  • That would make it easy to know if moving to a given loc is valid, but would it be possible to ask redis: "Which locations near x,y (or in room x) are occupied?" (And give back the ids of the objects) – Sean Clark Hess Jan 15 '12 at 23:32
  • Sure, you would query loc:0:0:paths, and then query loc:0:1:objs, loc:1:0:objs, etc, to see the occupation. If you wanted to make it less intensive to do that read, you could also keep an index of loc:0:0:openpaths or something similar which is updated with the occupied status of legal pathed locations. – jkraybill Jan 16 '12 at 01:30
  • Is that not a big deal in redis? Querying a bunch of times? When using mongodb we would use ranges and in queries to avoid that whenever possible. – Sean Clark Hess Jan 16 '12 at 02:07
  • Depends on your architecture, of course -- Redis can easily handle 50k-100k requests per second per machine on commodity hardware. The hash structure can also minimize the number of gets you need to make. Contemplate sharding early on in your design for maximum scalability. – jkraybill Jan 16 '12 at 04:25
1

Redis is a key-value store, and is likely not very well suited to this task out of the box, but if I were gonna take a stab at this, I would probably read up on R-trees (or another spatially oriented data structure) and then map such a data structure onto the key-value store pattern. For instance, you could set your MMO world as an R-tree in Redis, by making each node in the tree correspond to a particular key in Redis, which then would contain the bounding rect (and/or other leaf data) and a list of keys pointing to each of the child nodes.

This will at least allow you to keep your value sizes constrained (a property not necessarily shared by a flat, uniform grid representation), and keep the number of Redis lookups required for any given operation on the order of log(n).

Have fun! Sounds like a fun way to learn.

ipmcc
  • 29,581
  • 5
  • 84
  • 147