src/craftdef.cpp

   1 /*
   2 Minetest
   3 Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>
   4
   5 This program is free software; you can redistribute it and/or modify
   6 it under the terms of the GNU Lesser General Public License as published by
   7 the Free Software Foundation; either version 2.1 of the License, or
   8 (at your option) any later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU Lesser General Public License for more details.
  14
  15 You should have received a copy of the GNU Lesser General Public License along
  16 with this program; if not, write to the Free Software Foundation, Inc.,
  17 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include "craftdef.h"
  21
  22 #include "irrlichttypes.h"
  23 #include "log.h"
  24 #include <sstream>
  25 #include <set>
  26 #include <algorithm>
  27 #include "gamedef.h"
  28 #include "inventory.h"
  29 #include "util/serialize.h"
  30 #include "util/string.h"
  31 #include "util/numeric.h"
  32 #include "util/strfnd.h"
  33 #include "exceptions.h"
  34
  35 inline bool isGroupRecipeStr(const std::string &rec_name)
  36 {
  37         return str_starts_with(rec_name, std::string("group:"));
  38 }
  39
  40 static bool hasGroupItem(const std::vector<std::string> &recipe)
  41 {
  42         for (const auto &item : recipe) {
  43                 if (isGroupRecipeStr(item))
  44                         return true;
  45         }
  46         return false;
  47 }
  48
  49 inline u64 getHashForString(const std::string &recipe_str)
  50 {
  51         /*errorstream << "Hashing craft string  \"" << recipe_str << '"';*/
  52         return murmur_hash_64_ua(recipe_str.data(), recipe_str.length(), 0xdeadbeef);
  53 }
  54
  55 static u64 getHashForGrid(CraftHashType type, const std::vector<std::string> &grid_names)
  56 {
  57         switch (type) {
  58                 case CRAFT_HASH_TYPE_ITEM_NAMES: {
  59                         std::ostringstream os;
  60                         bool is_first = true;
  61                         for (const std::string &grid_name : grid_names) {
  62                                 if (!grid_name.empty()) {
  63                                         os << (is_first ? "" : "\n") << grid_name;
  64                                         is_first = false;
  65                                 }
  66                         }
  67                         return getHashForString(os.str());
  68                 } case CRAFT_HASH_TYPE_COUNT: {
  69                         u64 cnt = 0;
  70                         for (const std::string &grid_name : grid_names)
  71                                 if (!grid_name.empty())
  72                                         cnt++;
  73                         return cnt;
  74                 } case CRAFT_HASH_TYPE_UNHASHED:
  75                         return 0;
  76         }
  77         // invalid CraftHashType
  78         assert(false);
  79         return 0;
  80 }
  81
  82 // Check if input matches recipe
  83 // Takes recipe groups into account
  84 static bool inputItemMatchesRecipe(const std::string &inp_name,
  85                 const std::string &rec_name, IItemDefManager *idef)
  86 {
  87         // Exact name
  88         if (inp_name == rec_name)
  89                 return true;
  90
  91         // Group
  92         if (isGroupRecipeStr(rec_name) && idef->isKnown(inp_name)) {
  93                 const struct ItemDefinition &def = idef->get(inp_name);
  94                 Strfnd f(rec_name.substr(6));
  95                 bool all_groups_match = true;
  96                 do {
  97                         std::string check_group = f.next(",");
  98                         if (itemgroup_get(def.groups, check_group) == 0) {
  99                                 all_groups_match = false;
 100                                 break;
 101                         }
 102                 } while (!f.at_end());
 103                 if (all_groups_match)
 104                         return true;
 105         }
 106
 107         // Didn't match
 108         return false;
 109 }
 110
 111 // Deserialize an itemstring then return the name of the item
 112 static std::string craftGetItemName(const std::string &itemstring, IGameDef *gamedef)
 113 {
 114         ItemStack item;
 115         item.deSerialize(itemstring, gamedef->idef());
 116         return item.name;
 117 }
 118
 119 // (mapcar craftGetItemName itemstrings)
 120 static std::vector<std::string> craftGetItemNames(
 121                 const std::vector<std::string> &itemstrings, IGameDef *gamedef)
 122 {
 123         std::vector<std::string> result;
 124         result.reserve(itemstrings.size());
 125         for (const auto &itemstring : itemstrings) {
 126                 result.push_back(craftGetItemName(itemstring, gamedef));
 127         }
 128         return result;
 129 }
 130
 131 // Get name of each item, and return them as a new list.
 132 static std::vector<std::string> craftGetItemNames(
 133                 const std::vector<ItemStack> &items, IGameDef *gamedef)
 134 {
 135         std::vector<std::string> result;
 136         result.reserve(items.size());
 137         for (const auto &item : items) {
 138                 result.push_back(item.name);
 139         }
 140         return result;
 141 }
 142
 143 // convert a list of item names, to ItemStacks.
 144 static std::vector<ItemStack> craftGetItems(
 145                 const std::vector<std::string> &items, IGameDef *gamedef)
 146 {
 147         std::vector<ItemStack> result;
 148         result.reserve(items.size());
 149         for (const auto &item : items) {
 150                 result.emplace_back(std::string(item), (u16)1,
 151                         (u16)0, gamedef->getItemDefManager());
 152         }
 153         return result;
 154 }
 155
 156 // Compute bounding rectangle given a matrix of items
 157 // Returns false if every item is ""
 158 static bool craftGetBounds(const std::vector<std::string> &items, unsigned int width,
 159                 unsigned int &min_x, unsigned int &max_x,
 160                 unsigned int &min_y, unsigned int &max_y)
 161 {
 162         bool success = false;
 163         unsigned int x = 0;
 164         unsigned int y = 0;
 165         for (const std::string &item : items) {
 166                 // Is this an actual item?
 167                 if (!item.empty()) {
 168                         if (!success) {
 169                                 // This is the first nonempty item
 170                                 min_x = max_x = x;
 171                                 min_y = max_y = y;
 172                                 success = true;
 173                         } else {
 174                                 if (x < min_x) min_x = x;
 175                                 if (x > max_x) max_x = x;
 176                                 if (y < min_y) min_y = y;
 177                                 if (y > max_y) max_y = y;
 178                         }
 179                 }
 180
 181                 // Step coordinate
 182                 x++;
 183                 if (x == width) {
 184                         x = 0;
 185                         y++;
 186                 }
 187         }
 188         return success;
 189 }
 190
 191 // Removes 1 from each item stack
 192 static void craftDecrementInput(CraftInput &input, IGameDef *gamedef)
 193 {
 194         for (auto &item : input.items) {
 195                 if (item.count != 0)
 196                         item.remove(1);
 197         }
 198 }
 199
 200 // Removes 1 from each item stack with replacement support
 201 // Example: if replacements contains the pair ("bucket:bucket_water", "bucket:bucket_empty"),
 202 //   a water bucket will not be removed but replaced by an empty bucket.
 203 static void craftDecrementOrReplaceInput(CraftInput &input,
 204                 std::vector<ItemStack> &output_replacements,
 205                 const CraftReplacements &replacements,
 206                 IGameDef *gamedef)
 207 {
 208         if (replacements.pairs.empty()) {
 209                 craftDecrementInput(input, gamedef);
 210                 return;
 211         }
 212
 213         // Make a copy of the replacements pair list
 214         std::vector<std::pair<std::string, std::string> > pairs = replacements.pairs;
 215
 216         for (auto &item : input.items) {
 217                 // Find an appropriate replacement
 218                 bool found_replacement = false;
 219                 for (auto j = pairs.begin(); j != pairs.end(); ++j) {
 220                         if (inputItemMatchesRecipe(item.name, j->first, gamedef->idef())) {
 221                                 if (item.count == 1) {
 222                                         item.deSerialize(j->second, gamedef->idef());
 223                                         found_replacement = true;
 224                                         pairs.erase(j);
 225                                         break;
 226                                 }
 227
 228                                 ItemStack rep;
 229                                 rep.deSerialize(j->second, gamedef->idef());
 230                                 item.remove(1);
 231                                 found_replacement = true;
 232                                 output_replacements.push_back(rep);
 233                                 break;
 234
 235                         }
 236                 }
 237                 // No replacement was found, simply decrement count by one
 238                 if (!found_replacement && item.count > 0)
 239                         item.remove(1);
 240         }
 241 }
 242
 243 // Dump an itemstring matrix
 244 static std::string craftDumpMatrix(const std::vector<std::string> &items,
 245                 unsigned int width)
 246 {
 247         std::ostringstream os(std::ios::binary);
 248         os << "{ ";
 249         unsigned int x = 0;
 250         for(std::vector<std::string>::size_type i = 0;
 251                         i < items.size(); i++, x++) {
 252                 if (x == width) {
 253                         os << "; ";
 254                         x = 0;
 255                 } else if (x != 0) {
 256                         os << ",";
 257                 }
 258                 os << '"' << items[i] << '"';
 259         }
 260         os << " }";
 261         return os.str();
 262 }
 263
 264 // Dump an item matrix
 265 std::string craftDumpMatrix(const std::vector<ItemStack> &items,
 266                 unsigned int width)
 267 {
 268         std::ostringstream os(std::ios::binary);
 269         os << "{ ";
 270         unsigned int x = 0;
 271         for (std::vector<ItemStack>::size_type i = 0;
 272                         i < items.size(); i++, x++) {
 273                 if (x == width) {
 274                         os << "; ";
 275                         x = 0;
 276                 } else if (x != 0) {
 277                         os << ",";
 278                 }
 279                 os << '"' << (items[i].getItemString()) << '"';
 280         }
 281         os << " }";
 282         return os.str();
 283 }
 284
 285
 286 /*
 287         CraftInput
 288 */
 289
 290 std::string CraftInput::dump() const
 291 {
 292         std::ostringstream os(std::ios::binary);
 293         os << "(method=" << ((int)method) << ", items="
 294                 << craftDumpMatrix(items, width) << ")";
 295         return os.str();
 296 }
 297
 298 /*
 299         CraftOutput
 300 */
 301
 302 std::string CraftOutput::dump() const
 303 {
 304         std::ostringstream os(std::ios::binary);
 305         os << "(item=\"" << item << "\", time=" << time << ")";
 306         return os.str();
 307 }
 308
 309 /*
 310         CraftReplacements
 311 */
 312
 313 std::string CraftReplacements::dump() const
 314 {
 315         std::ostringstream os(std::ios::binary);
 316         os<<"{";
 317         const char *sep = "";
 318         for (const auto &repl_p : pairs) {
 319                 os << sep
 320                         << '"' << (repl_p.first)
 321                         << "\"=>\"" << (repl_p.second) << '"';
 322                 sep = ",";
 323         }
 324         os << "}";
 325         return os.str();
 326 }
 327
 328 /*
 329         CraftDefinitionShaped
 330 */
 331
 332 CraftDefinitionShaped::CraftDefinitionShaped(
 333                 const std::string &output_,
 334                 unsigned int width_,
 335                 const std::vector<std::string> &recipe_,
 336                 const CraftReplacements &replacements_):
 337         output(output_), width(width_), recipe(recipe_), replacements(replacements_)
 338 {
 339         if (hasGroupItem(recipe))
 340                 priority = SHAPED_AND_GROUPS;
 341         else
 342                 priority = SHAPED;
 343 }
 344
 345 std::string CraftDefinitionShaped::getName() const
 346 {
 347         return "shaped";
 348 }
 349
 350 bool CraftDefinitionShaped::check(const CraftInput &input, IGameDef *gamedef) const
 351 {
 352         if (input.method != CRAFT_METHOD_NORMAL)
 353                 return false;
 354
 355         // Get input item matrix
 356         std::vector<std::string> inp_names = craftGetItemNames(input.items, gamedef);
 357         unsigned int inp_width = input.width;
 358         if (inp_width == 0)
 359                 return false;
 360         while (inp_names.size() % inp_width != 0)
 361                 inp_names.emplace_back("");
 362
 363         // Get input bounds
 364         unsigned int inp_min_x = 0, inp_max_x = 0, inp_min_y = 0, inp_max_y = 0;
 365         if (!craftGetBounds(inp_names, inp_width, inp_min_x, inp_max_x,
 366                         inp_min_y, inp_max_y))
 367                 return false;  // it was empty
 368
 369         std::vector<std::string> rec_names;
 370         if (hash_inited)
 371                 rec_names = recipe_names;
 372         else
 373                 rec_names = craftGetItemNames(recipe, gamedef);
 374
 375         // Get recipe item matrix
 376         unsigned int rec_width = width;
 377         if (rec_width == 0)
 378                 return false;
 379         while (rec_names.size() % rec_width != 0)
 380                 rec_names.emplace_back("");
 381
 382         // Get recipe bounds
 383         unsigned int rec_min_x=0, rec_max_x=0, rec_min_y=0, rec_max_y=0;
 384         if (!craftGetBounds(rec_names, rec_width, rec_min_x, rec_max_x,
 385                         rec_min_y, rec_max_y))
 386                 return false;  // it was empty
 387
 388         // Different sizes?
 389         if (inp_max_x - inp_min_x != rec_max_x - rec_min_x ||
 390                         inp_max_y - inp_min_y != rec_max_y - rec_min_y)
 391                 return false;
 392
 393         // Verify that all item names in the bounding box are equal
 394         unsigned int w = inp_max_x - inp_min_x + 1;
 395         unsigned int h = inp_max_y - inp_min_y + 1;
 396
 397         for (unsigned int y=0; y < h; y++) {
 398                 unsigned int inp_y = (inp_min_y + y) * inp_width;
 399                 unsigned int rec_y = (rec_min_y + y) * rec_width;
 400
 401                 for (unsigned int x=0; x < w; x++) {
 402                         unsigned int inp_x = inp_min_x + x;
 403                         unsigned int rec_x = rec_min_x + x;
 404
 405                         if (!inputItemMatchesRecipe(
 406                                         inp_names[inp_y + inp_x],
 407                                         rec_names[rec_y + rec_x], gamedef->idef())) {
 408                                 return false;
 409                         }
 410                 }
 411         }
 412
 413         return true;
 414 }
 415
 416 CraftOutput CraftDefinitionShaped::getOutput(const CraftInput &input, IGameDef *gamedef) const
 417 {
 418         return CraftOutput(output, 0);
 419 }
 420
 421 CraftInput CraftDefinitionShaped::getInput(const CraftOutput &output, IGameDef *gamedef) const
 422 {
 423         return CraftInput(CRAFT_METHOD_NORMAL,width,craftGetItems(recipe,gamedef));
 424 }
 425
 426 void CraftDefinitionShaped::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 427          IGameDef *gamedef) const
 428 {
 429         craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 430 }
 431
 432 u64 CraftDefinitionShaped::getHash(CraftHashType type) const
 433 {
 434         assert(hash_inited); // Pre-condition
 435         assert((type == CRAFT_HASH_TYPE_ITEM_NAMES)
 436                 || (type == CRAFT_HASH_TYPE_COUNT)); // Pre-condition
 437
 438         std::vector<std::string> rec_names = recipe_names;
 439         std::sort(rec_names.begin(), rec_names.end());
 440         return getHashForGrid(type, rec_names);
 441 }
 442
 443 void CraftDefinitionShaped::initHash(IGameDef *gamedef)
 444 {
 445         if (hash_inited)
 446                 return;
 447         hash_inited = true;
 448         recipe_names = craftGetItemNames(recipe, gamedef);
 449
 450         if (hasGroupItem(recipe_names))
 451                 hash_type = CRAFT_HASH_TYPE_COUNT;
 452         else
 453                 hash_type = CRAFT_HASH_TYPE_ITEM_NAMES;
 454 }
 455
 456 std::string CraftDefinitionShaped::dump() const
 457 {
 458         std::ostringstream os(std::ios::binary);
 459         os << "(shaped, output=\"" << output
 460                 << "\", recipe=" << craftDumpMatrix(recipe, width)
 461                 << ", replacements=" << replacements.dump() << ")";
 462         return os.str();
 463 }
 464
 465 /*
 466         CraftDefinitionShapeless
 467 */
 468
 469 CraftDefinitionShapeless::CraftDefinitionShapeless(
 470                 const std::string &output_,
 471                 const std::vector<std::string> &recipe_,
 472                 const CraftReplacements &replacements_):
 473         output(output_), recipe(recipe_), replacements(replacements_)
 474 {
 475         if (hasGroupItem(recipe))
 476                 priority = SHAPELESS_AND_GROUPS;
 477         else
 478                 priority = SHAPELESS;
 479 }
 480
 481 std::string CraftDefinitionShapeless::getName() const
 482 {
 483         return "shapeless";
 484 }
 485
 486 bool CraftDefinitionShapeless::check(const CraftInput &input, IGameDef *gamedef) const
 487 {
 488         if (input.method != CRAFT_METHOD_NORMAL)
 489                 return false;
 490
 491         // Filter empty items out of input
 492         std::vector<std::string> input_filtered;
 493         for (const auto &item : input.items) {
 494                 if (!item.name.empty())
 495                         input_filtered.push_back(item.name);
 496         }
 497
 498         // If there is a wrong number of items in input, no match
 499         if (input_filtered.size() != recipe.size()) {
 500                 /*dstream<<"Number of input items ("<<input_filtered.size()
 501                                 <<") does not match recipe size ("<<recipe.size()<<") "
 502                                 <<"of recipe with output="<<output<<std::endl;*/
 503                 return false;
 504         }
 505
 506         std::vector<std::string> recipe_copy;
 507         if (hash_inited)
 508                 recipe_copy = recipe_names;
 509         else {
 510                 recipe_copy = craftGetItemNames(recipe, gamedef);
 511                 std::sort(recipe_copy.begin(), recipe_copy.end());
 512         }
 513
 514         // Try with all permutations of the recipe,
 515         // start from the lexicographically first permutation (=sorted),
 516         // recipe_names is pre-sorted
 517         do {
 518                 // If all items match, the recipe matches
 519                 bool all_match = true;
 520                 //dstream<<"Testing recipe (output="<<output<<"):";
 521                 for (size_t i=0; i<recipe.size(); i++) {
 522                         //dstream<<" ("<<input_filtered[i]<<" == "<<recipe_copy[i]<<")";
 523                         if (!inputItemMatchesRecipe(input_filtered[i], recipe_copy[i],
 524                                         gamedef->idef())) {
 525                                 all_match = false;
 526                                 break;
 527                         }
 528                 }
 529                 //dstream<<" -> match="<<all_match<<std::endl;
 530                 if (all_match)
 531                         return true;
 532         } while (std::next_permutation(recipe_copy.begin(), recipe_copy.end()));
 533
 534         return false;
 535 }
 536
 537 CraftOutput CraftDefinitionShapeless::getOutput(const CraftInput &input, IGameDef *gamedef) const
 538 {
 539         return CraftOutput(output, 0);
 540 }
 541
 542 CraftInput CraftDefinitionShapeless::getInput(const CraftOutput &output, IGameDef *gamedef) const
 543 {
 544         return CraftInput(CRAFT_METHOD_NORMAL, 0, craftGetItems(recipe, gamedef));
 545 }
 546
 547 void CraftDefinitionShapeless::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 548         IGameDef *gamedef) const
 549 {
 550         craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 551 }
 552
 553 u64 CraftDefinitionShapeless::getHash(CraftHashType type) const
 554 {
 555         assert(hash_inited); // Pre-condition
 556         assert(type == CRAFT_HASH_TYPE_ITEM_NAMES
 557                 || type == CRAFT_HASH_TYPE_COUNT); // Pre-condition
 558         return getHashForGrid(type, recipe_names);
 559 }
 560
 561 void CraftDefinitionShapeless::initHash(IGameDef *gamedef)
 562 {
 563         if (hash_inited)
 564                 return;
 565         hash_inited = true;
 566         recipe_names = craftGetItemNames(recipe, gamedef);
 567         std::sort(recipe_names.begin(), recipe_names.end());
 568
 569         if (hasGroupItem(recipe_names))
 570                 hash_type = CRAFT_HASH_TYPE_COUNT;
 571         else
 572                 hash_type = CRAFT_HASH_TYPE_ITEM_NAMES;
 573 }
 574
 575 std::string CraftDefinitionShapeless::dump() const
 576 {
 577         std::ostringstream os(std::ios::binary);
 578         os << "(shapeless, output=\"" << output
 579                 << "\", recipe=" << craftDumpMatrix(recipe, recipe.size())
 580                 << ", replacements=" << replacements.dump() << ")";
 581         return os.str();
 582 }
 583
 584 /*
 585         CraftDefinitionToolRepair
 586 */
 587
 588 CraftDefinitionToolRepair::CraftDefinitionToolRepair(float additional_wear_):
 589         additional_wear(additional_wear_)
 590 {
 591         priority = TOOLREPAIR;
 592 }
 593
 594 static ItemStack craftToolRepair(
 595                 const ItemStack &item1,
 596                 const ItemStack &item2,
 597                 float additional_wear,
 598                 IGameDef *gamedef)
 599 {
 600         IItemDefManager *idef = gamedef->idef();
 601         if (item1.count != 1 || item2.count != 1 || item1.name != item2.name
 602                         || idef->get(item1.name).type != ITEM_TOOL
 603                         || itemgroup_get(idef->get(item1.name).groups, "disable_repair") == 1) {
 604                 // Failure
 605                 return ItemStack();
 606         }
 607
 608         s32 item1_uses = 65536 - (u32) item1.wear;
 609         s32 item2_uses = 65536 - (u32) item2.wear;
 610         s32 new_uses = item1_uses + item2_uses;
 611         s32 new_wear = 65536 - new_uses + floor(additional_wear * 65536 + 0.5);
 612         if (new_wear >= 65536)
 613                 return ItemStack();
 614         if (new_wear < 0)
 615                 new_wear = 0;
 616
 617         ItemStack repaired = item1;
 618         repaired.wear = new_wear;
 619         return repaired;
 620 }
 621
 622 std::string CraftDefinitionToolRepair::getName() const
 623 {
 624         return "toolrepair";
 625 }
 626
 627 bool CraftDefinitionToolRepair::check(const CraftInput &input, IGameDef *gamedef) const
 628 {
 629         if (input.method != CRAFT_METHOD_NORMAL)
 630                 return false;
 631
 632         ItemStack item1;
 633         ItemStack item2;
 634         for (const auto &item : input.items) {
 635                 if (!item.empty()) {
 636                         if (item1.empty())
 637                                 item1 = item;
 638                         else if (item2.empty())
 639                                 item2 = item;
 640                         else
 641                                 return false;
 642                 }
 643         }
 644         ItemStack repaired = craftToolRepair(item1, item2, additional_wear, gamedef);
 645         return !repaired.empty();
 646 }
 647
 648 CraftOutput CraftDefinitionToolRepair::getOutput(const CraftInput &input, IGameDef *gamedef) const
 649 {
 650         ItemStack item1;
 651         ItemStack item2;
 652         for (const auto &item : input.items) {
 653                 if (!item.empty()) {
 654                         if (item1.empty())
 655                                 item1 = item;
 656                         else if (item2.empty())
 657                                 item2 = item;
 658                 }
 659         }
 660         ItemStack repaired = craftToolRepair(item1, item2, additional_wear, gamedef);
 661         return CraftOutput(repaired.getItemString(), 0);
 662 }
 663
 664 CraftInput CraftDefinitionToolRepair::getInput(const CraftOutput &output, IGameDef *gamedef) const
 665 {
 666         std::vector<ItemStack> stack;
 667         stack.emplace_back();
 668         return CraftInput(CRAFT_METHOD_COOKING, additional_wear, stack);
 669 }
 670
 671 void CraftDefinitionToolRepair::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 672         IGameDef *gamedef) const
 673 {
 674         craftDecrementInput(input, gamedef);
 675 }
 676
 677 std::string CraftDefinitionToolRepair::dump() const
 678 {
 679         std::ostringstream os(std::ios::binary);
 680         os << "(toolrepair, additional_wear=" << additional_wear << ")";
 681         return os.str();
 682 }
 683
 684 /*
 685         CraftDefinitionCooking
 686 */
 687
 688 CraftDefinitionCooking::CraftDefinitionCooking(
 689                 const std::string &output_,
 690                 const std::string &recipe_,
 691                 float cooktime_,
 692                 const CraftReplacements &replacements_):
 693         output(output_), recipe(recipe_), cooktime(cooktime_), replacements(replacements_)
 694 {
 695         if (isGroupRecipeStr(recipe))
 696                 priority = SHAPELESS_AND_GROUPS;
 697         else
 698                 priority = SHAPELESS;
 699 }
 700
 701 std::string CraftDefinitionCooking::getName() const
 702 {
 703         return "cooking";
 704 }
 705
 706 bool CraftDefinitionCooking::check(const CraftInput &input, IGameDef *gamedef) const
 707 {
 708         if (input.method != CRAFT_METHOD_COOKING)
 709                 return false;
 710
 711         // Filter empty items out of input
 712         std::vector<std::string> input_filtered;
 713         for (const auto &item : input.items) {
 714                 const std::string &name = item.name;
 715                 if (!name.empty())
 716                         input_filtered.push_back(name);
 717         }
 718
 719         // If there is a wrong number of items in input, no match
 720         if (input_filtered.size() != 1) {
 721                 /*dstream<<"Number of input items ("<<input_filtered.size()
 722                                 <<") does not match recipe size (1) "
 723                                 <<"of cooking recipe with output="<<output<<std::endl;*/
 724                 return false;
 725         }
 726
 727         // Check the single input item
 728         return inputItemMatchesRecipe(input_filtered[0], recipe, gamedef->idef());
 729 }
 730
 731 CraftOutput CraftDefinitionCooking::getOutput(const CraftInput &input, IGameDef *gamedef) const
 732 {
 733         return CraftOutput(output, cooktime);
 734 }
 735
 736 CraftInput CraftDefinitionCooking::getInput(const CraftOutput &output, IGameDef *gamedef) const
 737 {
 738         std::vector<std::string> rec;
 739         rec.push_back(recipe);
 740         return CraftInput(CRAFT_METHOD_COOKING,cooktime,craftGetItems(rec,gamedef));
 741 }
 742
 743 void CraftDefinitionCooking::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 744         IGameDef *gamedef) const
 745 {
 746         craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 747 }
 748
 749 u64 CraftDefinitionCooking::getHash(CraftHashType type) const
 750 {
 751         if (type == CRAFT_HASH_TYPE_ITEM_NAMES) {
 752                 return getHashForString(recipe_name);
 753         }
 754
 755         if (type == CRAFT_HASH_TYPE_COUNT) {
 756                 return 1;
 757         }
 758
 759         // illegal hash type for this CraftDefinition (pre-condition)
 760         assert(false);
 761         return 0;
 762 }
 763
 764 void CraftDefinitionCooking::initHash(IGameDef *gamedef)
 765 {
 766         if (hash_inited)
 767                 return;
 768         hash_inited = true;
 769         recipe_name = craftGetItemName(recipe, gamedef);
 770
 771         if (isGroupRecipeStr(recipe_name))
 772                 hash_type = CRAFT_HASH_TYPE_COUNT;
 773         else
 774                 hash_type = CRAFT_HASH_TYPE_ITEM_NAMES;
 775 }
 776
 777 std::string CraftDefinitionCooking::dump() const
 778 {
 779         std::ostringstream os(std::ios::binary);
 780         os << "(cooking, output=\"" << output
 781                 << "\", recipe=\"" << recipe
 782                 << "\", cooktime=" << cooktime << ")"
 783                 << ", replacements=" << replacements.dump() << ")";
 784         return os.str();
 785 }
 786
 787 /*
 788         CraftDefinitionFuel
 789 */
 790
 791 CraftDefinitionFuel::CraftDefinitionFuel(
 792                 const std::string &recipe_,
 793                 float burntime_,
 794                 const CraftReplacements &replacements_):
 795         recipe(recipe_), burntime(burntime_), replacements(replacements_)
 796 {
 797         if (isGroupRecipeStr(recipe_name))
 798                 priority = SHAPELESS_AND_GROUPS;
 799         else
 800                 priority = SHAPELESS;
 801 }
 802
 803 std::string CraftDefinitionFuel::getName() const
 804 {
 805         return "fuel";
 806 }
 807
 808 bool CraftDefinitionFuel::check(const CraftInput &input, IGameDef *gamedef) const
 809 {
 810         if (input.method != CRAFT_METHOD_FUEL)
 811                 return false;
 812
 813         // Filter empty items out of input
 814         std::vector<std::string> input_filtered;
 815         for (const auto &item : input.items) {
 816                 const std::string &name = item.name;
 817                 if (!name.empty())
 818                         input_filtered.push_back(name);
 819         }
 820
 821         // If there is a wrong number of items in input, no match
 822         if (input_filtered.size() != 1) {
 823                 /*dstream<<"Number of input items ("<<input_filtered.size()
 824                                 <<") does not match recipe size (1) "
 825                                 <<"of fuel recipe with burntime="<<burntime<<std::endl;*/
 826                 return false;
 827         }
 828
 829         // Check the single input item
 830         return inputItemMatchesRecipe(input_filtered[0], recipe, gamedef->idef());
 831 }
 832
 833 CraftOutput CraftDefinitionFuel::getOutput(const CraftInput &input, IGameDef *gamedef) const
 834 {
 835         return CraftOutput("", burntime);
 836 }
 837
 838 CraftInput CraftDefinitionFuel::getInput(const CraftOutput &output, IGameDef *gamedef) const
 839 {
 840         std::vector<std::string> rec;
 841         rec.push_back(recipe);
 842         return CraftInput(CRAFT_METHOD_COOKING,(int)burntime,craftGetItems(rec,gamedef));
 843 }
 844
 845 void CraftDefinitionFuel::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 846         IGameDef *gamedef) const
 847 {
 848         craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 849 }
 850
 851 u64 CraftDefinitionFuel::getHash(CraftHashType type) const
 852 {
 853         if (type == CRAFT_HASH_TYPE_ITEM_NAMES) {
 854                 return getHashForString(recipe_name);
 855         }
 856
 857         if (type == CRAFT_HASH_TYPE_COUNT) {
 858                 return 1;
 859         }
 860
 861         // illegal hash type for this CraftDefinition (pre-condition)
 862         assert(false);
 863         return 0;
 864 }
 865
 866 void CraftDefinitionFuel::initHash(IGameDef *gamedef)
 867 {
 868         if (hash_inited)
 869                 return;
 870         hash_inited = true;
 871         recipe_name = craftGetItemName(recipe, gamedef);
 872
 873         if (isGroupRecipeStr(recipe_name))
 874                 hash_type = CRAFT_HASH_TYPE_COUNT;
 875         else
 876                 hash_type = CRAFT_HASH_TYPE_ITEM_NAMES;
 877 }
 878
 879 std::string CraftDefinitionFuel::dump() const
 880 {
 881         std::ostringstream os(std::ios::binary);
 882         os << "(fuel, recipe=\"" << recipe
 883                 << "\", burntime=" << burntime << ")"
 884                 << ", replacements=" << replacements.dump() << ")";
 885         return os.str();
 886 }
 887
 888 /*
 889         Craft definition manager
 890 */
 891
 892 class CCraftDefManager: public IWritableCraftDefManager
 893 {
 894 public:
 895         CCraftDefManager()
 896         {
 897                 m_craft_defs.resize(craft_hash_type_max + 1);
 898         }
 899
 900         virtual ~CCraftDefManager()
 901         {
 902                 clear();
 903         }
 904
 905         virtual bool getCraftResult(CraftInput &input, CraftOutput &output,
 906                         std::vector<ItemStack> &output_replacement, bool decrementInput,
 907                         IGameDef *gamedef) const
 908         {
 909                 output.item = "";
 910                 output.time = 0;
 911
 912                 // If all input items are empty, abort.
 913                 bool all_empty = true;
 914                 for (const auto &item : input.items) {
 915                         if (!item.empty()) {
 916                                 all_empty = false;
 917                                 break;
 918                         }
 919                 }
 920                 if (all_empty)
 921                         return false;
 922
 923                 std::vector<std::string> input_names;
 924                 input_names = craftGetItemNames(input.items, gamedef);
 925                 std::sort(input_names.begin(), input_names.end());
 926
 927                 // Try hash types with increasing collision rate
 928                 // while remembering the latest, highest priority recipe.
 929                 CraftDefinition::RecipePriority priority_best =
 930                         CraftDefinition::NO_RECIPE;
 931                 CraftDefinition *def_best = nullptr;
 932                 for (int type = 0; type <= craft_hash_type_max; type++) {
 933                         u64 hash = getHashForGrid((CraftHashType) type, input_names);
 934
 935                         /*errorstream << "Checking type " << type << " with hash " << hash << std::endl;*/
 936
 937                         // We'd like to do "const [...] hash_collisions = m_craft_defs[type][hash];"
 938                         // but that doesn't compile for some reason. This does.
 939                         auto col_iter = (m_craft_defs[type]).find(hash);
 940
 941                         if (col_iter == (m_craft_defs[type]).end())
 942                                 continue;
 943
 944                         const std::vector<CraftDefinition*> &hash_collisions = col_iter->second;
 945                         // Walk crafting definitions from back to front, so that later
 946                         // definitions can override earlier ones.
 947                         for (std::vector<CraftDefinition*>::size_type
 948                                         i = hash_collisions.size(); i > 0; i--) {
 949                                 CraftDefinition *def = hash_collisions[i - 1];
 950
 951                                 /*errorstream << "Checking " << input.dump() << std::endl
 952                                         << " against " << def->dump() << std::endl;*/
 953
 954                                 CraftDefinition::RecipePriority priority = def->getPriority();
 955                                 if (priority > priority_best
 956                                                 && def->check(input, gamedef)) {
 957                                         // Check if the crafted node/item exists
 958                                         CraftOutput out = def->getOutput(input, gamedef);
 959                                         ItemStack is;
 960                                         is.deSerialize(out.item, gamedef->idef());
 961                                         if (!is.isKnown(gamedef->idef())) {
 962                                                 infostream << "trying to craft non-existent "
 963                                                         << out.item << ", ignoring recipe" << std::endl;
 964                                                 continue;
 965                                         }
 966
 967                                         output = out;
 968                                         priority_best = priority;
 969                                         def_best = def;
 970                                 }
 971                         }
 972                 }
 973                 if (priority_best == CraftDefinition::NO_RECIPE)
 974                         return false;
 975                 if (decrementInput)
 976                         def_best->decrementInput(input, output_replacement, gamedef);
 977                 return true;
 978         }
 979
 980         virtual std::vector<CraftDefinition*> getCraftRecipes(CraftOutput &output,
 981                         IGameDef *gamedef, unsigned limit=0) const
 982         {
 983                 std::vector<CraftDefinition*> recipes;
 984
 985                 auto vec_iter = m_output_craft_definitions.find(output.item);
 986
 987                 if (vec_iter == m_output_craft_definitions.end())
 988                         return recipes;
 989
 990                 const std::vector<CraftDefinition*> &vec = vec_iter->second;
 991
 992                 recipes.reserve(limit ? MYMIN(limit, vec.size()) : vec.size());
 993
 994                 for (std::vector<CraftDefinition*>::size_type i = vec.size();
 995                                 i > 0; i--) {
 996                         CraftDefinition *def = vec[i - 1];
 997                         if (limit && recipes.size() >= limit)
 998                                 break;
 999                         recipes.push_back(def);
1000                 }
1001
1002                 return recipes;
1003         }
1004
1005         virtual bool clearCraftRecipesByOutput(const CraftOutput &output, IGameDef *gamedef)
1006         {
1007                 auto vec_iter = m_output_craft_definitions.find(output.item);
1008
1009                 if (vec_iter == m_output_craft_definitions.end())
1010                         return false;
1011
1012                 std::vector<CraftDefinition*> &vec = vec_iter->second;
1013                 for (auto def : vec) {
1014                         // Recipes are not yet hashed at this point
1015                         std::vector<CraftDefinition*> &unhashed_inputs_vec = m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0];
1016                         std::vector<CraftDefinition*> new_vec_by_input;
1017                         /* We will preallocate necessary memory addresses, so we don't need to reallocate them later.
1018                                 This would save us some performance. */
1019                         new_vec_by_input.reserve(unhashed_inputs_vec.size());
1020                         for (auto &i2 : unhashed_inputs_vec) {
1021                                 if (def != i2) {
1022                                         new_vec_by_input.push_back(i2);
1023                                 }
1024                         }
1025                         m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].swap(new_vec_by_input);
1026                 }
1027                 m_output_craft_definitions.erase(output.item);
1028                 return true;
1029         }
1030
1031         virtual bool clearCraftRecipesByInput(CraftMethod craft_method, unsigned int craft_grid_width,
1032                 const std::vector<std::string> &recipe, IGameDef *gamedef)
1033         {
1034                 bool all_empty = true;
1035                 for (const auto &i : recipe) {
1036                         if (!i.empty()) {
1037                                 all_empty = false;
1038                                 break;
1039                         }
1040                 }
1041                 if (all_empty)
1042                         return false;
1043
1044                 CraftInput input(craft_method, craft_grid_width, craftGetItems(recipe, gamedef));
1045                 // Recipes are not yet hashed at this point
1046                 std::vector<CraftDefinition*> &unhashed_inputs_vec = m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0];
1047                 std::vector<CraftDefinition*> new_vec_by_input;
1048                 bool got_hit = false;
1049                 for (std::vector<CraftDefinition*>::size_type
1050                                 i = unhashed_inputs_vec.size(); i > 0; i--) {
1051                         CraftDefinition *def = unhashed_inputs_vec[i - 1];
1052                         /* If the input doesn't match the recipe definition, this recipe definition later
1053                                 will be added back in source map. */
1054                         if (!def->check(input, gamedef)) {
1055                                 new_vec_by_input.push_back(def);
1056                                 continue;
1057                         }
1058                         CraftOutput output = def->getOutput(input, gamedef);
1059                         got_hit = true;
1060                         auto vec_iter = m_output_craft_definitions.find(output.item);
1061                         if (vec_iter == m_output_craft_definitions.end())
1062                                 continue;
1063                         std::vector<CraftDefinition*> &vec = vec_iter->second;
1064                         std::vector<CraftDefinition*> new_vec_by_output;
1065                         /* We will preallocate necessary memory addresses, so we don't need
1066                                 to reallocate them later. This would save us some performance. */
1067                         new_vec_by_output.reserve(vec.size());
1068                         for (auto &vec_i : vec) {
1069                                 /* If pointers from map by input and output are not same,
1070                                         we will add 'CraftDefinition*' to a new vector. */
1071                                 if (def != vec_i) {
1072                                         /* Adding dereferenced iterator value (which are
1073                                                 'CraftDefinition' reference) to a new vector. */
1074                                         new_vec_by_output.push_back(vec_i);
1075                                 }
1076                         }
1077                         // Swaps assigned to current key value with new vector for output map.
1078                         m_output_craft_definitions[output.item].swap(new_vec_by_output);
1079                 }
1080                 if (got_hit)
1081                         // Swaps value with new vector for input map.
1082                         m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].swap(new_vec_by_input);
1083
1084                 return got_hit;
1085         }
1086
1087         virtual std::string dump() const
1088         {
1089                 std::ostringstream os(std::ios::binary);
1090                 os << "Crafting definitions:\n";
1091                 for (int type = 0; type <= craft_hash_type_max; ++type) {
1092                         for (auto it = m_craft_defs[type].begin();
1093                                         it != m_craft_defs[type].end(); ++it) {
1094                                 for (std::vector<CraftDefinition*>::size_type i = 0;
1095                                                 i < it->second.size(); i++) {
1096                                         os << "type " << type
1097                                                 << " hash " << it->first
1098                                                 << " def " << it->second[i]->dump()
1099                                                 << "\n";
1100                                 }
1101                         }
1102                 }
1103                 return os.str();
1104         }
1105         virtual void registerCraft(CraftDefinition *def, IGameDef *gamedef)
1106         {
1107                 verbosestream << "registerCraft: registering craft definition: "
1108                                 << def->dump() << std::endl;
1109                 m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].push_back(def);
1110
1111                 CraftInput input;
1112                 std::string output_name = craftGetItemName(
1113                                 def->getOutput(input, gamedef).item, gamedef);
1114                 m_output_craft_definitions[output_name].push_back(def);
1115         }
1116         virtual void clear()
1117         {
1118                 for (int type = 0; type <= craft_hash_type_max; ++type) {
1119                         for (auto &it : m_craft_defs[type]) {
1120                                 for (auto &iit : it.second) {
1121                                         delete iit;
1122                                 }
1123                                 it.second.clear();
1124                         }
1125                         m_craft_defs[type].clear();
1126                 }
1127                 m_output_craft_definitions.clear();
1128         }
1129         virtual void initHashes(IGameDef *gamedef)
1130         {
1131                 // Move the CraftDefs from the unhashed layer into layers higher up.
1132                 std::vector<CraftDefinition *> &unhashed =
1133                         m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0];
1134                 for (auto def : unhashed) {
1135                         // Initialize and get the definition's hash
1136                         def->initHash(gamedef);
1137                         CraftHashType type = def->getHashType();
1138                         u64 hash = def->getHash(type);
1139
1140                         // Enter the definition
1141                         m_craft_defs[type][hash].push_back(def);
1142                 }
1143                 unhashed.clear();
1144         }
1145 private:
1146         std::vector<std::unordered_map<u64, std::vector<CraftDefinition*> > >
1147                 m_craft_defs;
1148         std::unordered_map<std::string, std::vector<CraftDefinition*> >
1149                 m_output_craft_definitions;
1150 };
1151
1152 IWritableCraftDefManager* createCraftDefManager()
1153 {
1154         return new CCraftDefManager();
1155 }