Define graph models for game data

[oubiwann]

Part of:

• 68

Tasks:

• [x] Decide about general structure
  • [x] explore queries for users
  • [x] explore queries rooms
  • [x] explore queries for objects
• [x] What to use for IDs
• [x] What additional data to store on "label"
• [x] How to best look up, e.g., name by ID
• [x] How to best look up, e.g., ID by name

[oubiwann]

Data modelling ...

So edges offer some interesting possibilities:

• the obvious one being that they are a natural "storage mechanism" for connecting rooms
  • two-way and one-way paths are supported intrinsically, since the Erlang library is for directed graphs
  • by connecting two rooms with an edge and labelling the edge with something like "transit" you've identified exits
  • subtleties apply here, though:
  • e.g., giving edges multi-dimensional labels like label = '(#(type transit) #(size tiny)) could connect two rooms that only a mouse or an insect (or transmogrified player) could traverse
  • or `label = (#(type transit) #(active "last light of Durin's Day")) for a door that will only open on special occasions
• less obvious storage possibilities:
  • room objects, where the edges to the object nodes could be labelled with "contains" thus allowing one to easily query all the objects in a given room
• using that logic, there's no reason that players, NPCs, monsters, animals, etc., couldn't have their locations updated similarly: a move would entail removing and adding edges from and to these other types of nodes

The efficacy of this needs to be tested: how easy is it to treat digraph data as an in-memory database?

Given that digraph is backed by ETS, I see no problem storing all of a MUD's game data there, as long as it gets backed up to disk regularly.

[oubiwann]

Here are a set of experimental uses that demonstrate the possibility of this approach:

(set g (digraph:new))

(set `#(ok ,rm1) (mudstore:load "rooms" "room1"))
(set `#(ok ,rm2) (mudstore:load "rooms" "room2"))
(set `#(ok ,obj1) (mudstore:load "objects" "sword"))
(set `#(ok ,obj2) (mudstore:load "objects" "painting"))
(set `#(ok ,per1) (mudstore:load "characters" "eve"))

(digraph:add_vertex g 'r1 rm1)
(digraph:add_vertex g 'r2 rm2)
(digraph:add_edge g 'r1 'r2 #m(type transit direction east size normal))
(digraph:add_edge g 'r2 'r1 #m(type transit direction west size normal))

(digraph:add_vertex g 'o1 obj1)
(digraph:add_vertex g 'o2 obj2)
(digraph:add_vertex g 'p1 per1)
(digraph:add_edge g 'o1 'r1 #m(type contains))
(digraph:add_edge g 'o2 'r1 #m(type contains))
(digraph:add_edge g 'p1 'r1 #m(type contains))

(defun in-edges (g v)
  (list-comp
    ((<- e (digraph:in_edges g v)))
    (digraph:edge g e)))

(defun out-edges (g v)
  (list-comp
    ((<- e (digraph:out_edges g v)))
    (digraph:edge g e)))

(defun contents (g v)
  (list-comp
    ((<- `#(,_ ,obj ,_ #m(type contains)) (in-edges g v)))
    (let ((`#(,_ ,data) (digraph:vertex g obj)))
      data)))

(defun entrances (g v)
  (list-comp
    ((<- `#(,_ ,obj ,_ #m(type transit)) (in-edges g v)))
    (let ((`#(,_ ,data) (digraph:vertex g obj)))
      data)))

(defun exits (g v)
  (list-comp
    ((<- `#(,_ ,_ ,obj #m(type transit)) (out-edges g v)))
    (let ((`#(,_ ,data) (digraph:vertex g obj)))
      data)))

Example use:

(list-comp
  ((<- v (contents g 'r1)))
  (proplists:get_value 'desc v))

output:

("It's an old, rusty sword that probably isn't very useful anymore."
 "It depicts a dramatic landscape."
 "eve looks fairly ordinary; maybe they should update their description?")

[oubiwann]

We could also use digraph:in_nighbours to get vertices directly:

(defun in-neighbours (g v)
  (list-comp
    ((<- in (digraph:in_neighbours g v)))
    (let ((`#(,_ ,data) (digraph:vertex g in)))
      data)))

However, we'd need to add object type metadata to object files so we could filter by object type ...

Though there is more work using the edge-based approach, the use of edge directions and labels allows one to define nuanced relationships between vertices.

[oubiwann]

As for IDs, I'm tempted just to use uuids ...

[oubiwann]

Same thing as above, but I added uuids to the save files:

(set g (digraph:new))

(set `#(ok ,rm1) (mudstore:load "rooms" "room1"))
(set `#(ok ,rm2) (mudstore:load "rooms" "room2"))
(set `#(ok ,obj1) (mudstore:load "objects" "sword"))
(set `#(ok ,obj2) (mudstore:load "objects" "painting"))
(set `#(ok ,per1) (mudstore:load "characters" "eve"))

(set rm1-id (proplists:get_value 'id rm1))
(set rm2-id (proplists:get_value 'id rm2))
(set obj1-id (proplists:get_value 'id obj1))
(set obj2-id (proplists:get_value 'id obj2))
(set per1-id (proplists:get_value 'id per1))

(digraph:add_vertex g rm1-id rm1)
(digraph:add_vertex g rm2-id rm2)
(digraph:add_edge g rm1-id rm2-id #m(type transit direction east size normal))
(digraph:add_edge g rm2-id rm1-id #m(type transit direction west size normal))

(digraph:add_vertex g obj1-id obj1)
(digraph:add_vertex g obj2-id obj2)
(digraph:add_vertex g per1-id per1)
(digraph:add_edge g obj1-id rm1-id #m(type contains))
(digraph:add_edge g obj2-id rm1-id #m(type contains))
(digraph:add_edge g per1-id rm1-id #m(type contains))

Some use:

(list-comp
  ((<- v (contents g rm1-id)))
  `#m(id ,(proplists:get_value 'id v)
      desc ,(proplists:get_value 'desc v)))

Output:

(#M(desc
      "It's an old, rusty sword that probably isn't very useful anymore."
    id "fc4ae75a-0efb-11ed-abdd-e7e631866491")
 #M(desc "It depicts a dramatic landscape."
    id "f53ca7d2-0efb-11ed-8fc3-8b038c9bb3bb")
 #M(desc
      "eve looks fairly ordinary; maybe they should update their description?"
    id "e10e0102-0efb-11ed-b73a-d77a60b099a2"))

[oubiwann]

With 100s or 1000s of vertices, the use of string identifiers would save the atom table ...

[oubiwann]

I think this one's pretty much done :-)

[oubiwann]

Oh, we could do something interesting for characters ...

• to easily look up all characters in a given game, have there be a perma-vertex that characters can never leave (an edge is created between this vertex and the character during character creation)
• to easily see all the characters that belong to a given user, have there be a perma-vertex associated with the user (an edge is also created between this vertex and the character during character creation)
• inventory can be a node, too ... with a tuple of #(user-id "inventory") as its id, so it's always easy to look up

[oubiwann]

btw, updating a vertex looks like this:

(set rm2 (proplists:delete 'version rm2))
(set rm2 (lists:append '(#(version 2)) rm2))
(digraph:add_vertex g rm2-id rm2)

[ericmanlol]

i'm still unpacking everything but just wanted to say that this whole approach with graphs is awesome/novel, nice job @oubiwann!

[oubiwann]

@ericmanlol Thanks, man!

(I'm having a blast 😉)