javascript - 在 Javascript 中存储树数据

Question

我需要存储数据来表示这一点：

水 + 火 = 蒸汽
水 + 土 = 泥
泥 + 火 = 岩石

目标如下：我有可拖动的 HTML div，当<div id="Fire">和<div id="Mud">重叠时，我添加<div id="Rock">到屏幕上。曾经在 iPhone 或 Android 上玩过炼金术吗？同样的东西

现在，我这样做的方式是一个 JS 对象：

var stuff = {
    'Steam' : { needs: [ 'Water', 'Fire'] },
    'Mud'   : { needs: [ 'Water', 'Earth'] },
    'Rock'  : { needs: [ 'Mud',   'Fire'] },
    // etc...
};

每次一个 div 与另一个重叠时，我都会遍历对象键并检查“需要”数组。

我可以处理这种结构，但我想知道我是否可以做得更好？

编辑：我应该补充一点，我还需要存储一些其他的东西，比如简短的描述或图标名称。所以我有Steam: { needs: [ array ], desc: "short desc", icon:"steam.png"},

最后编辑：感谢大家的贡献，我在您的所有评论中发现了非常有价值的意见

Answer 1

如何直接编码具有其他依赖项的元素以及它们产生的内容？

var elements = {
  water: {
    earth: 'mud', //water with earh produces mud
    fire: 'steam'
  },
  fire: {
    water: 'steam',
    mud: 'rock'
  },
  earth: {
    water: 'mud'
  },
  mud: {
    fire: 'rock'
  }
}

因此，当您拥有 #div1 和 #div2 时，您只需执行以下操作：

elements[div1][div2]
elements['fire']['water']
"steam"

并且您获得了生成元素的 id。

Answer 2

每当您创建数据结构时，您需要牢记以下几点：

1. 熵应该很高（即冗余应该更少）。
2. 元素的访问时间应该更短。

我看到树的方式并不是表示您尝试建模的数据的最佳方式。

但是，您在代码中展示的内容很好。创建一个对象，其属性是方程的右侧元素：

var stuff = {
    Steam: ...,
    Mud: ...,
    Rock: ...
};

这允许及时访问元素O(1)。

方程的左侧可以像您所做的那样建模为数组。这就是我会做的。

然而，将它们包装在一个额外的对象中只是额外的冗余，它会增加元素的访问时间。

我会这样建模：

var stuff = {
    Steam: ["Water", "Fire"],
    Mud: ["Water", "Earth"],
    Rock: ["Mud", "Fire"]
};

然后，您可以通过用它们各自的基本“材料”替换数组中所有出现的复合“材料”来规范化您的表格。

编辑：根据您的评论，我建议您使用如下数据结构（您可以并且应该将其存储在.json文件中）：

{
    "Water": {
        "needs": []
    },
    "Fire": {
        "needs": []
    },
    "Earth": {
        "needs": []
    },
    "Steam": {
        "needs": ["Water", "Fire"]
    },
    "Mud": {
        "needs": ["Water", "Earth"]
    },
    "Rock": {
        "needs": ["Water", "Earth", "Fire"]
    }
}

你应该存储基本的东西而不是复合的东西的原因是，同样的东西stuff可能是由一种以上的复合材料组合而成的。以基本形式存储成分是最少冗余的。

Answer 3

我玩过炼金术，我会用指向所需对象的链接替换需求数组。我还创建了一个我认为您在游戏中需要的制作数组。设置此深度链接一次会使后续查找更快。

var stuff = {
  Fire: {
    name: 'Fire', active: true, needs: []
  }
  ,Water: {
    name: 'Water', active: true, needs: []
  }
  ,Earth: {
    name: 'Earth', active: true, needs: []
  }
  ,Steam: {
    name: 'Steam', active: false, needs: ['Water','Fire']
  }
  ,Mud: {
    name: 'Mud', active: false, needs: ['Water','Earth']
  }
  ,Rock: {
    name: 'Rock', active: false ,needs: ['Mud','Fire']
  }
};

for (var name in stuff) {
    // create links for needs and wants
    for (var i=0, n; n = stuff[name].needs[i]; i++) {
        if (stuff[n]) {
            stuff[name].needs[i] = stuff[n];
            if (!stuff[n].makes) stuff[n].makes = [];
            stuff[n].makes.push(stuff[name]);
        }
    }
    (function (o) {
        o.getNeeds = function () {
            var needs = [];
            for (var i=0, n; n = o.needs[i]; i++) {
                needs.push(o.needs[i].name);
            }
            return needs;
        };
        o.getMakes = function () {
            var makes = [];
            if (!o.makes) o.makes = [];
            for (var i=0, n; n = o.makes[i]; i++) {
                makes.push(o.makes[i].name);
            }
            return makes;
        };
        o.dump = function () {
            return o.name + " needs(" + o.getNeeds().join(',') + "), makes(" + o.getMakes().join(',') + ")";
        };
    })(stuff[name]);
}

stuff.testCombine = function (itemArray) {
    // itemArray is an unordered array of "stuff" names to test, eg ['Water','Fire']
    // if the elements in itemArray match an makes list for an item, this function returns that item.
    // if no combine was found, this function returns false
    if (!itemArray || !itemArray[0] || !stuff[itemArray[0]]) return false;

    // itemArray[0] is the guinea pig item, we see what it can make, and then see what the ingredient lists are and compare them to itemArray
    possible = stuff[itemArray[0]].makes;
    itemArray = itemArray.sort();

    for (var i=0, p; p = possible[i]; i++) {
        var n = p.getNeeds().sort();

        var matched = false;
        // check if n and itemArray are identical
        if (n.length && n.length == itemArray.length) {
          var j = 0;
          for (j=0; j < n.length && n[j] == itemArray[j]; j++);
          if (j == n.length) matched = true;
        }

        if (matched) return p;
    }
    return false;
}

// shows properties of Steam
alert(stuff.Steam.dump());
// shows properties of Water
alert(stuff.Water.dump());

alert("Water can be used to make :\n" + [stuff.Water.makes[0].dump(), stuff.Water.makes[1].dump()].join("\n"));

// stuff.Steam.needs[0] is Water, .makes[1] is Mud, .makes[0] is Rock
alert(stuff.Steam.needs[0].makes[1].makes[0].name);

// test if 'Water', 'Earth' makes something:
var m = stuff.testCombine(['Water','Earth']);
if (!m) { 
    alert('Did not Combine'); 
} else {
    alert('Combined to make ' + m.dump());
}

Answer 4

如果您不介意包含另一个外部库并且熟悉 LINQ，则可以使用linq.js。

var stuff = {
  'Steam' : { needs: ['Water', 'Fire'] },
  'Mud'   : { needs: ['Water', 'Earth'] },
  'Rock'  : { needs: ['Mud',   'Fire'] }
    // etc...
};

function Alchemy(stuff) {
  var recipes = 
    Enumerable.From(stuff).ToLookup(
      "$.Value.needs",
      "$.Key", 
      "Enumerable.From($).OrderBy().ToString('+')"
    );

  this.attempt = function(elem1, elem2) {
    return recipes.Get([elem1, elem2]).ToString();
  };
};

var alchemy = new Alchemy(stuff);
console.log(alchemy.attempt('Fire', 'Mud'));   // "Rock"
console.log(alchemy.attempt('Fire', 'Earth')); // ""
console.log(alchemy.attempt('Fire', 'Water')); // "Steam"

笔记

• Enumerable.From(stuff)将您的stuff对象拆分为其Key和Value部分。
  例如，将Key引用"Rock"和。Value{ needs: ['Mud', 'Fire'] }
• ToLookup()从中创建一个查找字典。它需要3个参数：
  1. 要查找的内容（在本例中为 中的元素"$.Value.needs"）
  2. 如果找到匹配项返回什么（在这种情况下，结果元素的名称，即Key）
  3. 创建字典键的转换函数（在这种情况下，成分数组被转换为排序字符串：['Mud', Fire']成为"Fire+Mud"）。
• 该Get()函数使用相同的转换函数为其参数找到匹配项。

请注意，字符串参数 like"$.Value.needs"是
function ($) { return $.Value.needs; }.

linq.js 还提供了更多有用的功能，可以将复杂的任务转换为单行。

---

编辑：从查找中返回所有附加信息很简单：

function Alchemy(stuff) {
  var recipes = 
    Enumerable.From(stuff).ToLookup(
      "$.Value.needs",
      null, // return the object unchanged 
      "Enumerable.From($).OrderBy().ToString('+')"
    );

  this.attempt = function(elem1, elem2) {
    return recipes.Get([elem1, elem2]).FirstOrDefault();
  };
};

console.log(alchemy.attempt('Fire', 'Mud')); 
/* result
{
  Key: "Rock",
  Value: {
    needs: ["Mud", "Fire"],
    whatever: "else you had defined in {stuff}"
  }
}
*/

Lookup 对象的目的是提高速度。您还可以每次遍历整个对象图：

function alchemy(elem1, elem2) {
  return 
    Enumerable
    .From(stuff)
    .Where(function ($) {
      var recipe = Enumerable.From($.Value.needs);
      return recipe.Intersect([elem1, elem2]).Count() == 2;
    })
    .Select("{element: $.Key, properties: $.Value}")
    .FirstOrDefault();
);

console.log(alchemy('Fire', 'Water'));
// {element: "Steam", properties: {needs: ["Water", "Fire"]}}

请注意，这.Select()是可选的。您可以删除它，在这种情况下，结果将与前面的示例相同。