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 bool CraftInput::empty() const
 291 {
 292         for (const auto &item : items) {
 293                 if (!item.empty())
 294                         return false;
 295         }
 296         return true;
 297 }
 298
 299 std::string CraftInput::dump() const
 300 {
 301         std::ostringstream os(std::ios::binary);
 302         os << "(method=" << ((int)method) << ", items="
 303                 << craftDumpMatrix(items, width) << ")";
 304         return os.str();
 305 }
 306
 307 /*
 308         CraftOutput
 309 */
 310
 311 std::string CraftOutput::dump() const
 312 {
 313         std::ostringstream os(std::ios::binary);
 314         os << "(item=\"" << item << "\", time=" << time << ")";
 315         return os.str();
 316 }
 317
 318 /*
 319         CraftReplacements
 320 */
 321
 322 std::string CraftReplacements::dump() const
 323 {
 324         std::ostringstream os(std::ios::binary);
 325         os<<"{";
 326         const char *sep = "";
 327         for (const auto &repl_p : pairs) {
 328                 os << sep
 329                         << '"' << (repl_p.first)
 330                         << "\"=>\"" << (repl_p.second) << '"';
 331                 sep = ",";
 332         }
 333         os << "}";
 334         return os.str();
 335 }
 336
 337 /*
 338         CraftDefinitionShaped
 339 */
 340
 341 CraftDefinitionShaped::CraftDefinitionShaped(
 342                 const std::string &output_,
 343                 unsigned int width_,
 344                 const std::vector<std::string> &recipe_,
 345                 const CraftReplacements &replacements_):
 346         output(output_), width(width_), recipe(recipe_), replacements(replacements_)
 347 {
 348         if (hasGroupItem(recipe))
 349                 priority = PRIORITY_SHAPED_AND_GROUPS;
 350         else
 351                 priority = PRIORITY_SHAPED;
 352 }
 353
 354 std::string CraftDefinitionShaped::getName() const
 355 {
 356         return "shaped";
 357 }
 358
 359 bool CraftDefinitionShaped::check(const CraftInput &input, IGameDef *gamedef) const
 360 {
 361         if (input.method != CRAFT_METHOD_NORMAL)
 362                 return false;
 363
 364         // Get input item matrix
 365         std::vector<std::string> inp_names = craftGetItemNames(input.items, gamedef);
 366         unsigned int inp_width = input.width;
 367         if (inp_width == 0)
 368                 return false;
 369         while (inp_names.size() % inp_width != 0)
 370                 inp_names.emplace_back("");
 371
 372         // Get input bounds
 373         unsigned int inp_min_x = 0, inp_max_x = 0, inp_min_y = 0, inp_max_y = 0;
 374         if (!craftGetBounds(inp_names, inp_width, inp_min_x, inp_max_x,
 375                         inp_min_y, inp_max_y))
 376                 return false;  // it was empty
 377
 378         std::vector<std::string> rec_names;
 379         if (hash_inited)
 380                 rec_names = recipe_names;
 381         else
 382                 rec_names = craftGetItemNames(recipe, gamedef);
 383
 384         // Get recipe item matrix
 385         unsigned int rec_width = width;
 386         if (rec_width == 0)
 387                 return false;
 388         while (rec_names.size() % rec_width != 0)
 389                 rec_names.emplace_back("");
 390
 391         // Get recipe bounds
 392         unsigned int rec_min_x=0, rec_max_x=0, rec_min_y=0, rec_max_y=0;
 393         if (!craftGetBounds(rec_names, rec_width, rec_min_x, rec_max_x,
 394                         rec_min_y, rec_max_y))
 395                 return false;  // it was empty
 396
 397         // Different sizes?
 398         if (inp_max_x - inp_min_x != rec_max_x - rec_min_x ||
 399                         inp_max_y - inp_min_y != rec_max_y - rec_min_y)
 400                 return false;
 401
 402         // Verify that all item names in the bounding box are equal
 403         unsigned int w = inp_max_x - inp_min_x + 1;
 404         unsigned int h = inp_max_y - inp_min_y + 1;
 405
 406         for (unsigned int y=0; y < h; y++) {
 407                 unsigned int inp_y = (inp_min_y + y) * inp_width;
 408                 unsigned int rec_y = (rec_min_y + y) * rec_width;
 409
 410                 for (unsigned int x=0; x < w; x++) {
 411                         unsigned int inp_x = inp_min_x + x;
 412                         unsigned int rec_x = rec_min_x + x;
 413
 414                         if (!inputItemMatchesRecipe(
 415                                         inp_names[inp_y + inp_x],
 416                                         rec_names[rec_y + rec_x], gamedef->idef())) {
 417                                 return false;
 418                         }
 419                 }
 420         }
 421
 422         return true;
 423 }
 424
 425 CraftOutput CraftDefinitionShaped::getOutput(const CraftInput &input, IGameDef *gamedef) const
 426 {
 427         return CraftOutput(output, 0);
 428 }
 429
 430 CraftInput CraftDefinitionShaped::getInput(const CraftOutput &output, IGameDef *gamedef) const
 431 {
 432         return CraftInput(CRAFT_METHOD_NORMAL,width,craftGetItems(recipe,gamedef));
 433 }
 434
 435 void CraftDefinitionShaped::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 436          IGameDef *gamedef) const
 437 {
 438         craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 439 }
 440
 441 u64 CraftDefinitionShaped::getHash(CraftHashType type) const
 442 {
 443         assert(hash_inited); // Pre-condition
 444         assert((type == CRAFT_HASH_TYPE_ITEM_NAMES)
 445                 || (type == CRAFT_HASH_TYPE_COUNT)); // Pre-condition
 446
 447         std::vector<std::string> rec_names = recipe_names;
 448         std::sort(rec_names.begin(), rec_names.end());
 449         return getHashForGrid(type, rec_names);
 450 }
 451
 452 void CraftDefinitionShaped::initHash(IGameDef *gamedef)
 453 {
 454         if (hash_inited)
 455                 return;
 456         hash_inited = true;
 457         recipe_names = craftGetItemNames(recipe, gamedef);
 458
 459         if (hasGroupItem(recipe_names))
 460                 hash_type = CRAFT_HASH_TYPE_COUNT;
 461         else
 462                 hash_type = CRAFT_HASH_TYPE_ITEM_NAMES;
 463 }
 464
 465 std::string CraftDefinitionShaped::dump() const
 466 {
 467         std::ostringstream os(std::ios::binary);
 468         os << "(shaped, output=\"" << output
 469                 << "\", recipe=" << craftDumpMatrix(recipe, width)
 470                 << ", replacements=" << replacements.dump() << ")";
 471         return os.str();
 472 }
 473
 474 /*
 475         CraftDefinitionShapeless
 476 */
 477
 478 CraftDefinitionShapeless::CraftDefinitionShapeless(
 479                 const std::string &output_,
 480                 const std::vector<std::string> &recipe_,
 481                 const CraftReplacements &replacements_):
 482         output(output_), recipe(recipe_), replacements(replacements_)
 483 {
 484         if (hasGroupItem(recipe))
 485                 priority = PRIORITY_SHAPELESS_AND_GROUPS;
 486         else
 487                 priority = PRIORITY_SHAPELESS;
 488 }
 489
 490 std::string CraftDefinitionShapeless::getName() const
 491 {
 492         return "shapeless";
 493 }
 494
 495 bool CraftDefinitionShapeless::check(const CraftInput &input, IGameDef *gamedef) const
 496 {
 497         if (input.method != CRAFT_METHOD_NORMAL)
 498                 return false;
 499
 500         // Filter empty items out of input
 501         std::vector<std::string> input_filtered;
 502         for (const auto &item : input.items) {
 503                 if (!item.name.empty())
 504                         input_filtered.push_back(item.name);
 505         }
 506
 507         // If there is a wrong number of items in input, no match
 508         if (input_filtered.size() != recipe.size()) {
 509                 /*dstream<<"Number of input items ("<<input_filtered.size()
 510                                 <<") does not match recipe size ("<<recipe.size()<<") "
 511                                 <<"of recipe with output="<<output<<std::endl;*/
 512                 return false;
 513         }
 514
 515         std::vector<std::string> recipe_copy;
 516         if (hash_inited)
 517                 recipe_copy = recipe_names;
 518         else {
 519                 recipe_copy = craftGetItemNames(recipe, gamedef);
 520                 std::sort(recipe_copy.begin(), recipe_copy.end());
 521         }
 522
 523         // Try with all permutations of the recipe,
 524         // start from the lexicographically first permutation (=sorted),
 525         // recipe_names is pre-sorted
 526         do {
 527                 // If all items match, the recipe matches
 528                 bool all_match = true;
 529                 //dstream<<"Testing recipe (output="<<output<<"):";
 530                 for (size_t i=0; i<recipe.size(); i++) {
 531                         //dstream<<" ("<<input_filtered[i]<<" == "<<recipe_copy[i]<<")";
 532                         if (!inputItemMatchesRecipe(input_filtered[i], recipe_copy[i],
 533                                         gamedef->idef())) {
 534                                 all_match = false;
 535                                 break;
 536                         }
 537                 }
 538                 //dstream<<" -> match="<<all_match<<std::endl;
 539                 if (all_match)
 540                         return true;
 541         } while (std::next_permutation(recipe_copy.begin(), recipe_copy.end()));
 542
 543         return false;
 544 }
 545
 546 CraftOutput CraftDefinitionShapeless::getOutput(const CraftInput &input, IGameDef *gamedef) const
 547 {
 548         return CraftOutput(output, 0);
 549 }
 550
 551 CraftInput CraftDefinitionShapeless::getInput(const CraftOutput &output, IGameDef *gamedef) const
 552 {
 553         return CraftInput(CRAFT_METHOD_NORMAL, 0, craftGetItems(recipe, gamedef));
 554 }
 555
 556 void CraftDefinitionShapeless::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 557         IGameDef *gamedef) const
 558 {
 559         craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 560 }
 561
 562 u64 CraftDefinitionShapeless::getHash(CraftHashType type) const
 563 {
 564         assert(hash_inited); // Pre-condition
 565         assert(type == CRAFT_HASH_TYPE_ITEM_NAMES
 566                 || type == CRAFT_HASH_TYPE_COUNT); // Pre-condition
 567         return getHashForGrid(type, recipe_names);
 568 }
 569
 570 void CraftDefinitionShapeless::initHash(IGameDef *gamedef)
 571 {
 572         if (hash_inited)
 573                 return;
 574         hash_inited = true;
 575         recipe_names = craftGetItemNames(recipe, gamedef);
 576         std::sort(recipe_names.begin(), recipe_names.end());
 577
 578         if (hasGroupItem(recipe_names))
 579                 hash_type = CRAFT_HASH_TYPE_COUNT;
 580         else
 581                 hash_type = CRAFT_HASH_TYPE_ITEM_NAMES;
 582 }
 583
 584 std::string CraftDefinitionShapeless::dump() const
 585 {
 586         std::ostringstream os(std::ios::binary);
 587         os << "(shapeless, output=\"" << output
 588                 << "\", recipe=" << craftDumpMatrix(recipe, recipe.size())
 589                 << ", replacements=" << replacements.dump() << ")";
 590         return os.str();
 591 }
 592
 593 /*
 594         CraftDefinitionToolRepair
 595 */
 596
 597 CraftDefinitionToolRepair::CraftDefinitionToolRepair(float additional_wear_):
 598         additional_wear(additional_wear_)
 599 {
 600         priority = PRIORITY_TOOLREPAIR;
 601 }
 602
 603 static ItemStack craftToolRepair(
 604                 const ItemStack &item1,
 605                 const ItemStack &item2,
 606                 float additional_wear,
 607                 IGameDef *gamedef)
 608 {
 609         IItemDefManager *idef = gamedef->idef();
 610         if (item1.count != 1 || item2.count != 1 || item1.name != item2.name
 611                         || idef->get(item1.name).type != ITEM_TOOL
 612                         || itemgroup_get(idef->get(item1.name).groups, "disable_repair") == 1) {
 613                 // Failure
 614                 return ItemStack();
 615         }
 616
 617         s32 item1_uses = 65536 - (u32) item1.wear;
 618         s32 item2_uses = 65536 - (u32) item2.wear;
 619         s32 new_uses = item1_uses + item2_uses;
 620         s32 new_wear = 65536 - new_uses + floor(additional_wear * 65536 + 0.5);
 621         if (new_wear >= 65536)
 622                 return ItemStack();
 623         if (new_wear < 0)
 624                 new_wear = 0;
 625
 626         ItemStack repaired = item1;
 627         repaired.wear = new_wear;
 628         return repaired;
 629 }
 630
 631 std::string CraftDefinitionToolRepair::getName() const
 632 {
 633         return "toolrepair";
 634 }
 635
 636 bool CraftDefinitionToolRepair::check(const CraftInput &input, IGameDef *gamedef) const
 637 {
 638         if (input.method != CRAFT_METHOD_NORMAL)
 639                 return false;
 640
 641         ItemStack item1;
 642         ItemStack item2;
 643         for (const auto &item : input.items) {
 644                 if (!item.empty()) {
 645                         if (item1.empty())
 646                                 item1 = item;
 647                         else if (item2.empty())
 648                                 item2 = item;
 649                         else
 650                                 return false;
 651                 }
 652         }
 653         ItemStack repaired = craftToolRepair(item1, item2, additional_wear, gamedef);
 654         return !repaired.empty();
 655 }
 656
 657 CraftOutput CraftDefinitionToolRepair::getOutput(const CraftInput &input, IGameDef *gamedef) const
 658 {
 659         ItemStack item1;
 660         ItemStack item2;
 661         for (const auto &item : input.items) {
 662                 if (!item.empty()) {
 663                         if (item1.empty())
 664                                 item1 = item;
 665                         else if (item2.empty())
 666                                 item2 = item;
 667                 }
 668         }
 669         ItemStack repaired = craftToolRepair(item1, item2, additional_wear, gamedef);
 670         return CraftOutput(repaired.getItemString(), 0);
 671 }
 672
 673 CraftInput CraftDefinitionToolRepair::getInput(const CraftOutput &output, IGameDef *gamedef) const
 674 {
 675         std::vector<ItemStack> stack;
 676         stack.emplace_back();
 677         return CraftInput(CRAFT_METHOD_COOKING, additional_wear, stack);
 678 }
 679
 680 void CraftDefinitionToolRepair::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 681         IGameDef *gamedef) const
 682 {
 683         craftDecrementInput(input, gamedef);
 684 }
 685
 686 std::string CraftDefinitionToolRepair::dump() const
 687 {
 688         std::ostringstream os(std::ios::binary);
 689         os << "(toolrepair, additional_wear=" << additional_wear << ")";
 690         return os.str();
 691 }
 692
 693 /*
 694         CraftDefinitionCooking
 695 */
 696
 697 CraftDefinitionCooking::CraftDefinitionCooking(
 698                 const std::string &output_,
 699                 const std::string &recipe_,
 700                 float cooktime_,
 701                 const CraftReplacements &replacements_):
 702         output(output_), recipe(recipe_), cooktime(cooktime_), replacements(replacements_)
 703 {
 704         if (isGroupRecipeStr(recipe))
 705                 priority = PRIORITY_SHAPELESS_AND_GROUPS;
 706         else
 707                 priority = PRIORITY_SHAPELESS;
 708 }
 709
 710 std::string CraftDefinitionCooking::getName() const
 711 {
 712         return "cooking";
 713 }
 714
 715 bool CraftDefinitionCooking::check(const CraftInput &input, IGameDef *gamedef) const
 716 {
 717         if (input.method != CRAFT_METHOD_COOKING)
 718                 return false;
 719
 720         // Filter empty items out of input
 721         std::vector<std::string> input_filtered;
 722         for (const auto &item : input.items) {
 723                 const std::string &name = item.name;
 724                 if (!name.empty())
 725                         input_filtered.push_back(name);
 726         }
 727
 728         // If there is a wrong number of items in input, no match
 729         if (input_filtered.size() != 1) {
 730                 /*dstream<<"Number of input items ("<<input_filtered.size()
 731                                 <<") does not match recipe size (1) "
 732                                 <<"of cooking recipe with output="<<output<<std::endl;*/
 733                 return false;
 734         }
 735
 736         // Check the single input item
 737         std::string rec_name = craftGetItemName(recipe, gamedef);
 738         return inputItemMatchesRecipe(input_filtered[0], rec_name, gamedef->idef());
 739 }
 740
 741 CraftOutput CraftDefinitionCooking::getOutput(const CraftInput &input, IGameDef *gamedef) const
 742 {
 743         return CraftOutput(output, cooktime);
 744 }
 745
 746 CraftInput CraftDefinitionCooking::getInput(const CraftOutput &output, IGameDef *gamedef) const
 747 {
 748         std::vector<std::string> rec;
 749         rec.push_back(recipe);
 750         return CraftInput(CRAFT_METHOD_COOKING,cooktime,craftGetItems(rec,gamedef));
 751 }
 752
 753 void CraftDefinitionCooking::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 754         IGameDef *gamedef) const
 755 {
 756         craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 757 }
 758
 759 u64 CraftDefinitionCooking::getHash(CraftHashType type) const
 760 {
 761         if (type == CRAFT_HASH_TYPE_ITEM_NAMES) {
 762                 return getHashForString(recipe_name);
 763         }
 764
 765         if (type == CRAFT_HASH_TYPE_COUNT) {
 766                 return 1;
 767         }
 768
 769         // illegal hash type for this CraftDefinition (pre-condition)
 770         assert(false);
 771         return 0;
 772 }
 773
 774 void CraftDefinitionCooking::initHash(IGameDef *gamedef)
 775 {
 776         if (hash_inited)
 777                 return;
 778         hash_inited = true;
 779         recipe_name = craftGetItemName(recipe, gamedef);
 780
 781         if (isGroupRecipeStr(recipe_name))
 782                 hash_type = CRAFT_HASH_TYPE_COUNT;
 783         else
 784                 hash_type = CRAFT_HASH_TYPE_ITEM_NAMES;
 785 }
 786
 787 std::string CraftDefinitionCooking::dump() const
 788 {
 789         std::ostringstream os(std::ios::binary);
 790         os << "(cooking, output=\"" << output
 791                 << "\", recipe=\"" << recipe
 792                 << "\", cooktime=" << cooktime << ")"
 793                 << ", replacements=" << replacements.dump() << ")";
 794         return os.str();
 795 }
 796
 797 /*
 798         CraftDefinitionFuel
 799 */
 800
 801 CraftDefinitionFuel::CraftDefinitionFuel(
 802                 const std::string &recipe_,
 803                 float burntime_,
 804                 const CraftReplacements &replacements_):
 805         recipe(recipe_), burntime(burntime_), replacements(replacements_)
 806 {
 807         if (isGroupRecipeStr(recipe_name))
 808                 priority = PRIORITY_SHAPELESS_AND_GROUPS;
 809         else
 810                 priority = PRIORITY_SHAPELESS;
 811 }
 812
 813 std::string CraftDefinitionFuel::getName() const
 814 {
 815         return "fuel";
 816 }
 817
 818 bool CraftDefinitionFuel::check(const CraftInput &input, IGameDef *gamedef) const
 819 {
 820         if (input.method != CRAFT_METHOD_FUEL)
 821                 return false;
 822
 823         // Filter empty items out of input
 824         std::vector<std::string> input_filtered;
 825         for (const auto &item : input.items) {
 826                 const std::string &name = item.name;
 827                 if (!name.empty())
 828                         input_filtered.push_back(name);
 829         }
 830
 831         // If there is a wrong number of items in input, no match
 832         if (input_filtered.size() != 1) {
 833                 /*dstream<<"Number of input items ("<<input_filtered.size()
 834                                 <<") does not match recipe size (1) "
 835                                 <<"of fuel recipe with burntime="<<burntime<<std::endl;*/
 836                 return false;
 837         }
 838
 839         // Check the single input item
 840         std::string rec_name = craftGetItemName(recipe, gamedef);
 841         return inputItemMatchesRecipe(input_filtered[0], rec_name, gamedef->idef());
 842 }
 843
 844 CraftOutput CraftDefinitionFuel::getOutput(const CraftInput &input, IGameDef *gamedef) const
 845 {
 846         return CraftOutput("", burntime);
 847 }
 848
 849 CraftInput CraftDefinitionFuel::getInput(const CraftOutput &output, IGameDef *gamedef) const
 850 {
 851         std::vector<std::string> rec;
 852         rec.push_back(recipe);
 853         return CraftInput(CRAFT_METHOD_COOKING,(int)burntime,craftGetItems(rec,gamedef));
 854 }
 855
 856 void CraftDefinitionFuel::decrementInput(CraftInput &input, std::vector<ItemStack> &output_replacements,
 857         IGameDef *gamedef) const
 858 {
 859         craftDecrementOrReplaceInput(input, output_replacements, replacements, gamedef);
 860 }
 861
 862 u64 CraftDefinitionFuel::getHash(CraftHashType type) const
 863 {
 864         if (type == CRAFT_HASH_TYPE_ITEM_NAMES) {
 865                 return getHashForString(recipe_name);
 866         }
 867
 868         if (type == CRAFT_HASH_TYPE_COUNT) {
 869                 return 1;
 870         }
 871
 872         // illegal hash type for this CraftDefinition (pre-condition)
 873         assert(false);
 874         return 0;
 875 }
 876
 877 void CraftDefinitionFuel::initHash(IGameDef *gamedef)
 878 {
 879         if (hash_inited)
 880                 return;
 881         hash_inited = true;
 882         recipe_name = craftGetItemName(recipe, gamedef);
 883
 884         if (isGroupRecipeStr(recipe_name))
 885                 hash_type = CRAFT_HASH_TYPE_COUNT;
 886         else
 887                 hash_type = CRAFT_HASH_TYPE_ITEM_NAMES;
 888 }
 889
 890 std::string CraftDefinitionFuel::dump() const
 891 {
 892         std::ostringstream os(std::ios::binary);
 893         os << "(fuel, recipe=\"" << recipe
 894                 << "\", burntime=" << burntime << ")"
 895                 << ", replacements=" << replacements.dump() << ")";
 896         return os.str();
 897 }
 898
 899 /*
 900         Craft definition manager
 901 */
 902
 903 class CCraftDefManager: public IWritableCraftDefManager
 904 {
 905 public:
 906         CCraftDefManager()
 907         {
 908                 m_craft_defs.resize(craft_hash_type_max + 1);
 909         }
 910
 911         virtual ~CCraftDefManager()
 912         {
 913                 clear();
 914         }
 915
 916         virtual bool getCraftResult(CraftInput &input, CraftOutput &output,
 917                         std::vector<ItemStack> &output_replacement, bool decrementInput,
 918                         IGameDef *gamedef) const
 919         {
 920                 if (input.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::PRIORITY_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::PRIORITY_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 clearCraftsByOutput(const CraftOutput &output, IGameDef *gamedef)
1006         {
1007                 auto to_clear = m_output_craft_definitions.find(output.item);
1008
1009                 if (to_clear == m_output_craft_definitions.end())
1010                         return false;
1011
1012                 for (auto def : to_clear->second) {
1013                         // Recipes are not yet hashed at this point
1014                         std::vector<CraftDefinition *> &defs = m_craft_defs[(int)CRAFT_HASH_TYPE_UNHASHED][0];
1015                         defs.erase(std::remove(defs.begin(), defs.end(), def), defs.end());
1016                         delete def;
1017                 }
1018                 m_output_craft_definitions.erase(to_clear);
1019                 return true;
1020         }
1021
1022         virtual bool clearCraftsByInput(const CraftInput &input, IGameDef *gamedef)
1023         {
1024                 if (input.empty())
1025                         return false;
1026
1027                 // Recipes are not yet hashed at this point
1028                 std::vector<CraftDefinition *> &defs = m_craft_defs[(int)CRAFT_HASH_TYPE_UNHASHED][0];
1029                 std::vector<CraftDefinition *> new_defs;
1030                 bool got_hit = false;
1031                 for (auto def : defs) {
1032                         if (!def->check(input, gamedef)) {
1033                                 new_defs.push_back(def);
1034                                 continue;
1035                         }
1036                         got_hit = true;
1037                         std::string output = def->getOutput(input, gamedef).item;
1038                         delete def;
1039                         auto it = m_output_craft_definitions.find(craftGetItemName(output, gamedef));
1040                         if (it == m_output_craft_definitions.end())
1041                                 continue;
1042                         std::vector<CraftDefinition *> &outdefs = it->second;
1043                         outdefs.erase(std::remove(outdefs.begin(), outdefs.end(), def), outdefs.end());
1044                 }
1045                 if (got_hit)
1046                         defs.swap(new_defs);
1047
1048                 return got_hit;
1049         }
1050
1051         virtual std::string dump() const
1052         {
1053                 std::ostringstream os(std::ios::binary);
1054                 os << "Crafting definitions:\n";
1055                 for (int type = 0; type <= craft_hash_type_max; ++type) {
1056                         for (auto it = m_craft_defs[type].begin();
1057                                         it != m_craft_defs[type].end(); ++it) {
1058                                 for (std::vector<CraftDefinition*>::size_type i = 0;
1059                                                 i < it->second.size(); i++) {
1060                                         os << "type " << type
1061                                                 << " hash " << it->first
1062                                                 << " def " << it->second[i]->dump()
1063                                                 << "\n";
1064                                 }
1065                         }
1066                 }
1067                 return os.str();
1068         }
1069         virtual void registerCraft(CraftDefinition *def, IGameDef *gamedef)
1070         {
1071                 TRACESTREAM(<< "registerCraft: registering craft definition: "
1072                                 << def->dump() << std::endl);
1073                 m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0].push_back(def);
1074
1075                 CraftInput input;
1076                 std::string output_name = craftGetItemName(
1077                                 def->getOutput(input, gamedef).item, gamedef);
1078                 m_output_craft_definitions[output_name].push_back(def);
1079         }
1080         virtual void clear()
1081         {
1082                 for (int type = 0; type <= craft_hash_type_max; ++type) {
1083                         for (auto &it : m_craft_defs[type]) {
1084                                 for (auto &iit : it.second) {
1085                                         delete iit;
1086                                 }
1087                                 it.second.clear();
1088                         }
1089                         m_craft_defs[type].clear();
1090                 }
1091                 m_output_craft_definitions.clear();
1092         }
1093         virtual void initHashes(IGameDef *gamedef)
1094         {
1095                 // Move the CraftDefs from the unhashed layer into layers higher up.
1096                 std::vector<CraftDefinition *> &unhashed =
1097                         m_craft_defs[(int) CRAFT_HASH_TYPE_UNHASHED][0];
1098                 for (auto def : unhashed) {
1099                         // Initialize and get the definition's hash
1100                         def->initHash(gamedef);
1101                         CraftHashType type = def->getHashType();
1102                         u64 hash = def->getHash(type);
1103
1104                         // Enter the definition
1105                         m_craft_defs[type][hash].push_back(def);
1106                 }
1107                 unhashed.clear();
1108         }
1109 private:
1110         std::vector<std::unordered_map<u64, std::vector<CraftDefinition*> > >
1111                 m_craft_defs;
1112         std::unordered_map<std::string, std::vector<CraftDefinition*> >
1113                 m_output_craft_definitions;
1114 };
1115
1116 IWritableCraftDefManager* createCraftDefManager()
1117 {
1118         return new CCraftDefManager();
1119 }