1"""# Requirements
   2
   3The HierarchyCraft package is meant to able the conception of arbitrary underlying hierarchial
   4structures in environments.
   5Thus HierarchyCraft allows to manipulate and visualize those underlying hierarchies.
   6
   7## Requirements graph
   8
   9In HierarchyCraft, transformations allow to obtain items, to reach zones or to place items in zones.
  10Thus transformations are the links defining the requirements between items (and zones).
  11
  12A list of transformations can thus be transformed in a graph linking items and zones as illustrated bellow:
  13
  14![Transformation To Requirements](../../docs/images/TransformationToRequirements.png)
  15
  16We can represent all those links in a multi-edged directed graph (or MultiDiGraph), where:
  17
  18- nodes are either an 'item', a 'zone' or an 'item in zone'.
  19(See `hcraft.requirements.RequirementNode`)
  20- edges are indexed per transformation and per available zone
  21and directed from consumed 'item' or 'item in zone' or necessary 'zone'
  22to produced 'item' or 'item in zone' or destination 'zone'.
  23(See `hcraft.requirements.RequirementEdge`)
  24
  25To represent the initial state of the world, we add a special '#Start' node
  26and edges with uniquely indexes from this '#Start' node to the start_zone and
  27to every 'item' in the start_items. Also we add a uniquely indexed edge
  28from every 'zone' to every 'item in zone' in the corresponding zone in start_zones_items.
  29
  30## Requirements levels
  31
  32Hierarchical levels can be computed from a requirements graph.
  33The 'START#' node is at level 0 then accessible nodes from the 'START#' node are level 1,
  34then accessible items from level 1 items are level 2, ... until all nodes have a level.
  35
  36Nodes may be accessible by mutliple options (different transformations),
  37those options are represented by the indexes of edges.
  38To be attributed a level, a node needs at least an index where
  39all the predecessors of this node with this index have a level.
  40Then the node's level=1+min_over_indexes(max(predecessors_levels_by_index)).
  41
  42See `hcraft.requirements.compute_levels` for implementation details.
  43
  44
  45## Collapsed acyclic requirements graph
  46
  47Once the requirements graph nodes have a level, cycles in the graph can be broken
  48by removing edges from higher levels to lower levels.
  49
  50We then obtain the collapsed acyclic requirements graph by removing duplicated edges.
  51This graph can be used to draw a simpler view of the requirements graph.
  52This graph is used to find relevant subtasks for any item or zone,
  53see `hcraft.purpose.RewardShaping.REQUIREMENTS_ACHIVEMENTS`.
  54
  55# Example
  56
  57```python
  58# Obtain the raw Networkx MultiDiGraph
  59graph = env.world.requirements.graph
  60
  61# Plot the collapsed acyclic requirements graph
  62import matplotlib.pyplot as plt
  63_, ax = plt.subplots()
  64env.world.requirements.draw(ax)
  65plt.show()
  66```
  67
  68For a concrete example, here is the underlying hierarchy of the toy environment MinicraftUnlock:
  69<img
  70src="https://raw.githubusercontent.com/IRLL/HierarchyCraft/master/docs/images/requirements_graphs/MiniHCraftUnlock.png"
  71width="90%"/>
  72
  73"""
  74
  75from enum import Enum
  76from pathlib import Path
  77import random
  78from PIL import Image, ImageDraw, ImageFont
  79
  80from typing import TYPE_CHECKING, Any, Dict, List, Optional, Set, Tuple, Union
  81
  82import networkx as nx
  83import numpy as np
  84
  85import seaborn as sns
  86from matplotlib import pyplot as plt
  87import matplotlib.patches as mpatches
  88from matplotlib.axes import Axes
  89from matplotlib.legend_handler import HandlerPatch
  90
  91from hebg.graph import draw_networkx_nodes_images, get_nodes_by_level
  92from hebg.layouts.metabased import leveled_layout_energy
  93import hcraft
  94
  95from hcraft.render.utils import load_or_create_image, obj_image_path
  96from hcraft.transformation import InventoryOperation, InventoryOwner
  97
  98if TYPE_CHECKING:
  99    from hcraft.elements import Item, Stack, Zone
 100    from hcraft.transformation import Transformation
 101    from hcraft.world import World
 102
 103
 104class RequirementNode(Enum):
 105    """Node types in the requirements graph."""
 106
 107    START = "start"
 108    ZONE = "zone"
 109    ITEM = "item"
 110    ZONE_ITEM = "zone_item"
 111
 112
 113class RequirementEdge(Enum):
 114    """Edge types in the requirements graph."""
 115
 116    ZONE_REQUIRED = "zone_required"
 117    ITEM_REQUIRED = "item_required"
 118    ITEM_REQUIRED_IN_ZONE = "item_required_in_zone"
 119    START_ZONE = "start_zone"
 120    START_ITEM = "start_item"
 121    START_ITEM_IN_ZONE = "start_item_in_zone"
 122
 123
 124class RequirementTheme:
 125    """Defines the colors to draw requirements graph nodes and edges"""
 126
 127    DEFAULT_COLORS = {
 128        "item": "red",
 129        "zone": "green",
 130        "zone_item": "blue",
 131        "item_required": "red",
 132        "zone_required": "green",
 133        "item_required_in_zone": "blue",
 134        "start_zone": "black",
 135        "start_item": "black",
 136        "start_item_in_zone": "black",
 137    }
 138    """Default colors"""
 139
 140    def __init__(
 141        self,
 142        default_color: Any = "black",
 143        edge_colors=None,
 144        **kwargs,
 145    ) -> None:
 146        self.colors = self.DEFAULT_COLORS.copy()
 147        self.colors.update(kwargs)
 148        self.default_color = default_color
 149
 150        def rgba_to_hex(r, g, b, a=0.5):
 151            hexes = "%02x%02x%02x%02x" % (
 152                int(r * 255),
 153                int(g * 255),
 154                int(b * 255),
 155                int(a * 255),
 156            )
 157            return f"#{hexes.upper()}"
 158
 159        if edge_colors is None:
 160            edge_colors = sns.color_palette("colorblind")
 161            random.shuffle(edge_colors)
 162        self.edges_colors = [rgba_to_hex(*color) for color in edge_colors]
 163
 164    def color_node(self, node_type: RequirementNode) -> Any:
 165        """Returns the themed color of the given node depending on his type."""
 166        if not node_type:
 167            return self.default_color
 168        return self.colors.get(node_type.value, self.default_color)
 169
 170    def color_edges(self, edge_index: int):
 171        """Returns the themed color of the given edge depending on his type."""
 172        edge_color_index = edge_index % len(self.edges_colors)
 173        edge_color = self.edges_colors[edge_color_index]
 174        return edge_color
 175
 176
 177class DrawEngine(Enum):
 178    PLT = "matplotlib"
 179    PYVIS = "pyvis"
 180
 181
 182class Requirements:
 183    def __init__(self, world: "World"):
 184        self.world = world
 185        self.graph = nx.MultiDiGraph()
 186        self._digraph: nx.DiGraph = None
 187        self._acydigraph: nx.DiGraph = None
 188        self._build()
 189
 190    def draw(
 191        self,
 192        ax: Optional[Axes] = None,
 193        theme: Optional[RequirementTheme] = None,
 194        layout: "RequirementsGraphLayout" = "level",
 195        engine: DrawEngine = DrawEngine.PLT,
 196        save_path: Optional[Path] = None,
 197        **kwargs,
 198    ) -> None:
 199        """Draw the requirements graph on the given Axes.
 200
 201        Args:
 202            ax: Matplotlib Axes to draw on.
 203            layout: Drawing layout. Defaults to "level".
 204        """
 205        if theme is None:
 206            theme = RequirementTheme()
 207
 208        apply_color_theme(self.graph, theme)
 209
 210        pos = compute_layout(self.digraph, layout=layout)
 211
 212        if save_path:
 213            save_path.parent.mkdir(exist_ok=True)
 214
 215        engine = DrawEngine(engine)
 216        if engine is DrawEngine.PLT:
 217            if ax is None:
 218                raise TypeError(f"ax must be given for {engine.value} drawing engine.")
 219            _draw_on_plt_ax(
 220                ax,
 221                self.digraph,
 222                theme,
 223                resources_path=self.world.resources_path,
 224                pos=pos,
 225                level_legend=True,
 226            )
 227
 228            if save_path:
 229                plt.gcf().savefig(
 230                    save_path, dpi=kwargs.get("dpi", 100), transparent=True
 231                )
 232
 233        if engine is DrawEngine.PYVIS:
 234            if save_path is None:
 235                raise TypeError(
 236                    f"save_path must be given for {engine.value} drawing engine."
 237                )
 238            _draw_html(
 239                self.graph,
 240                resources_path=self.world.resources_path,
 241                filepath=save_path,
 242                pos=pos,
 243                depth=self.depth,
 244                width=self.width,
 245                **kwargs,
 246            )
 247
 248    @property
 249    def digraph(self) -> nx.DiGraph:
 250        """Collapsed DiGraph of requirements."""
 251        if self._digraph is not None:
 252            return self._digraph
 253        self._digraph = collapse_as_digraph(self.graph)
 254        return self._digraph
 255
 256    @property
 257    def acydigraph(self) -> nx.DiGraph:
 258        """Collapsed leveled acyclic DiGraph of requirements."""
 259        if self._acydigraph is not None:
 260            return self._acydigraph
 261        self._acydigraph = break_cycles_through_level(self.digraph)
 262        return self._acydigraph
 263
 264    @property
 265    def depth(self) -> int:
 266        """Depth of the requirements graph."""
 267        return self.graph.graph.get("depth")
 268
 269    @property
 270    def width(self) -> int:
 271        """Width of the requirements graph."""
 272        return self.graph.graph.get("width")
 273
 274    def _build(self) -> None:
 275        self._add_requirements_nodes(self.world)
 276        self._add_start_edges(self.world)
 277        for edge_index, transfo in enumerate(self.world.transformations):
 278            self._add_transformation_edges(transfo, edge_index, transfo.zone)
 279        compute_levels(self.graph)
 280
 281    def _add_requirements_nodes(self, world: "World") -> None:
 282        self._add_nodes(world.items, RequirementNode.ITEM)
 283        self._add_nodes(world.zones_items, RequirementNode.ZONE_ITEM)
 284        if len(world.zones) >= 1:
 285            self._add_nodes(world.zones, RequirementNode.ZONE)
 286
 287    def _add_nodes(
 288        self, objs: List[Union["Item", "Zone"]], node_type: RequirementNode
 289    ) -> None:
 290        """Add colored nodes to the graph"""
 291        for obj in objs:
 292            self.graph.add_node(req_node_name(obj, node_type), obj=obj, type=node_type)
 293
 294    def _add_transformation_edges(
 295        self,
 296        transfo: "Transformation",
 297        transfo_index: int,
 298        zone: Optional["Zone"] = None,
 299    ) -> None:
 300        """Add edges induced by a HierarchyCraft recipe."""
 301        zones = set() if zone is None else {zone}
 302
 303        in_items = transfo.min_required("player")
 304        out_items = [
 305            item for item in transfo.production("player") if item not in in_items
 306        ]
 307
 308        in_zone_items = transfo.min_required_zones_items
 309        out_zone_items = [
 310            item for item in transfo.produced_zones_items if item not in in_zone_items
 311        ]
 312
 313        other_zones_items = {}
 314        if transfo.destination is not None:
 315            required_dest_stacks = transfo.get_changes("destination", "min")
 316            other_zones_items[transfo.destination] = required_dest_stacks
 317
 318        required_zones_stacks = transfo.get_changes("zones", "min")
 319        if required_zones_stacks is not None:
 320            for other_zone, consumed_stacks in required_zones_stacks.items():
 321                other_zones_items[other_zone] = consumed_stacks
 322
 323        for other_zone, other_zone_items in other_zones_items.items():
 324            # If we require items in other zone that are not here from the start,
 325            # it means that we have to be able to go there before we can use this transformation
 326            # or that we can add the items in the other zone from elsewhere.
 327            if not _available_in_zones_stacks(
 328                other_zone_items,
 329                other_zone,
 330                self.world.start_zones_items,
 331            ):
 332                alternative_transformations = [
 333                    alt_transfo
 334                    for alt_transfo in self.world.transformations
 335                    if alt_transfo.get_changes("zones", "add") is not None
 336                    and _available_in_zones_stacks(
 337                        other_zone_items,
 338                        other_zone,
 339                        alt_transfo.get_changes("zones", "add"),
 340                    )
 341                ]
 342                if len(alternative_transformations) == 1:
 343                    alt_transfo = alternative_transformations[0]
 344                    if alt_transfo.zone is None or not alt_transfo.zone == other_zone:
 345                        in_items |= alt_transfo.min_required("player")
 346                        in_zone_items |= alt_transfo.min_required_zones_items
 347                    else:
 348                        zones.add(other_zone)
 349                elif not alternative_transformations:
 350                    zones.add(other_zone)
 351                else:
 352                    continue
 353                    raise NotImplementedError("A complex case, raise issue if needed")
 354
 355        transfo_params = {
 356            "in_items": in_items,
 357            "in_zone_items": in_zone_items,
 358            "zones": zones,
 359            "index": transfo_index,
 360            "transfo": transfo,
 361        }
 362
 363        for out_item in out_items:
 364            node_name = req_node_name(out_item, RequirementNode.ITEM)
 365            self._add_crafts(out_node=node_name, **transfo_params)
 366
 367        for out_zone_item in out_zone_items:
 368            node_name = req_node_name(out_zone_item, RequirementNode.ZONE_ITEM)
 369            self._add_crafts(out_node=node_name, **transfo_params)
 370
 371        if transfo.destination is not None:
 372            node_name = req_node_name(transfo.destination, RequirementNode.ZONE)
 373            self._add_crafts(out_node=node_name, **transfo_params)
 374
 375    def _add_crafts(
 376        self,
 377        in_items: Set["Item"],
 378        in_zone_items: Set["Item"],
 379        zones: Set["Zone"],
 380        out_node: str,
 381        index: int,
 382        transfo: "Transformation",
 383    ) -> None:
 384        for zone in zones:
 385            edge_type = RequirementEdge.ZONE_REQUIRED
 386            node_type = RequirementNode.ZONE
 387            self._add_obj_edge(out_node, edge_type, index, zone, node_type, transfo)
 388        for item in in_items:
 389            node_type = RequirementNode.ITEM
 390            edge_type = RequirementEdge.ITEM_REQUIRED
 391            self._add_obj_edge(out_node, edge_type, index, item, node_type, transfo)
 392        for item in in_zone_items:
 393            node_type = RequirementNode.ZONE_ITEM
 394            edge_type = RequirementEdge.ITEM_REQUIRED_IN_ZONE
 395            self._add_obj_edge(out_node, edge_type, index, item, node_type, transfo)
 396
 397    def _add_obj_edge(
 398        self,
 399        end_node: str,
 400        edge_type: RequirementEdge,
 401        index: int,
 402        start_obj: Optional[Union["Zone", "Item"]] = None,
 403        start_type: Optional[RequirementNode] = None,
 404        edge_transformation: Optional["Transformation"] = None,
 405    ):
 406        start_name = req_node_name(start_obj, start_type)
 407        self._add_nodes([start_obj], start_type)
 408        self.graph.add_edge(
 409            start_name, end_node, type=edge_type, key=index, obj=edge_transformation
 410        )
 411
 412    def _add_start_edges(self, world: "World"):
 413        start_index = -1
 414        if world.start_zone is not None:
 415            edge_type = RequirementEdge.START_ZONE
 416            end_node = req_node_name(world.start_zone, RequirementNode.ZONE)
 417            self._add_obj_edge(
 418                end_node, edge_type, start_index, start_type=RequirementNode.START
 419            )
 420            start_index -= 1
 421        for start_stack in world.start_items:
 422            edge_type = RequirementEdge.START_ITEM
 423            end_node = req_node_name(start_stack.item, RequirementNode.ZONE_ITEM)
 424            self._add_obj_edge(
 425                end_node, edge_type, start_index, start_type=RequirementNode.START
 426            )
 427            start_index -= 1
 428        for zone, start_zone_items in world.start_zones_items.items():
 429            edge_type = RequirementEdge.START_ITEM_IN_ZONE
 430            start_type = RequirementNode.ZONE
 431            for start_zone_stack in start_zone_items:
 432                end_node = req_node_name(
 433                    start_zone_stack.item, RequirementNode.ZONE_ITEM
 434                )
 435                self._add_obj_edge(end_node, edge_type, start_index, zone, start_type)
 436                start_index -= 1
 437
 438
 439def req_node_name(obj: Optional[Union["Item", "Zone"]], node_type: RequirementNode):
 440    """Get a unique node name for the requirements graph"""
 441    if node_type == RequirementNode.START:
 442        return "START#"
 443    name = obj.name
 444    if node_type == RequirementNode.ZONE_ITEM:
 445        name = f"{name} in zone"
 446    return node_type.value + "#" + name
 447
 448
 449def compute_levels(graph: Requirements):
 450    """Compute the hierachical levels of a RequirementsGraph.
 451
 452    Adds the attribute 'level' to each node in the given graph.
 453    Adds the attribute 'nodes_by_level' to the given graph.
 454    Adds the attribute 'depth' to the given graph.
 455    Adds the attribute 'width' to the given graph.
 456
 457    Args:
 458        graph: A RequirementsGraph.
 459
 460    Returns:
 461        Dictionary of nodes by level.
 462
 463    """
 464
 465    def _compute_level_dependencies(graph: nx.MultiDiGraph, node):
 466        predecessors = list(graph.predecessors(node))
 467        if len(predecessors) == 0:
 468            graph.nodes[node]["level"] = 0
 469            return True
 470        if "level" in graph.nodes[node]:
 471            return True
 472
 473        pred_level_by_key = {}
 474        for pred, _node, key in graph.in_edges(node, keys=True):
 475            pred_level = graph.nodes[pred].get("level", None)
 476            if key not in pred_level_by_key:
 477                pred_level_by_key[key] = []
 478            pred_level_by_key[key].append(pred_level)
 479
 480        max_level_by_index = []
 481        for key, level_list in pred_level_by_key.items():
 482            if None in level_list:
 483                continue
 484            max_level_by_index.append(max(level_list))
 485        if len(max_level_by_index) == 0:
 486            return False
 487        level = 1 + min(max_level_by_index)
 488        graph.nodes[node]["level"] = level
 489        return True
 490
 491    all_nodes_have_level = True
 492    for _ in range(len(graph.nodes())):
 493        all_nodes_have_level = True
 494        incomplete_nodes = []
 495        for node in graph.nodes():
 496            incomplete = not _compute_level_dependencies(graph, node)
 497            if incomplete:
 498                incomplete_nodes.append(node)
 499                all_nodes_have_level = False
 500        if all_nodes_have_level:
 501            break
 502
 503    if not all_nodes_have_level:
 504        raise ValueError(
 505            "Could not attribute levels to all nodes. "
 506            f"Incomplete nodes: {incomplete_nodes}"
 507        )
 508
 509    nodes_by_level = get_nodes_by_level(graph)
 510    graph.graph["depth"] = max(level for level in nodes_by_level)
 511    graph.graph["width"] = max(len(nodes) for nodes in nodes_by_level.values())
 512    return nodes_by_level
 513
 514
 515def break_cycles_through_level(digraph: nx.DiGraph):
 516    """Break cycles in a leveled multidigraph by cutting edges from high to low levels."""
 517    acygraph = digraph.copy()
 518    nodes_level = acygraph.nodes(data="level", default=0)
 519    for pred, node in digraph.edges():
 520        if nodes_level[pred] >= nodes_level[node]:
 521            acygraph.remove_edge(pred, node)
 522    return acygraph
 523
 524
 525def collapse_as_digraph(multidigraph: nx.MultiDiGraph) -> nx.DiGraph:
 526    """Create a collapsed DiGraph from a MultiDiGraph by removing duplicated edges."""
 527    digraph = nx.DiGraph()
 528    digraph.graph = multidigraph.graph
 529    for node, data in multidigraph.nodes(data=True):
 530        digraph.add_node(node, **data)
 531    for pred, node, key, data in multidigraph.edges(keys=True, data=True):
 532        if not digraph.has_edge(pred, node):
 533            digraph.add_edge(pred, node, keys=[], **data)
 534        digraph.edges[pred, node]["keys"].append(key)
 535    return digraph
 536
 537
 538def _available_in_zones_stacks(
 539    stacks: Optional[List["Stack"]],
 540    zone: "Zone",
 541    zones_stacks: Dict["Zone", List["Stack"]],
 542) -> bool:
 543    """
 544    Args:
 545        stacks: List of stacks that should be available.
 546        zone: Zone where the stacks should be available.
 547        zones_stacks: Stacks present in each zone.
 548
 549    Returns:
 550        True if the given stacks are available from the start. False otherwise.
 551    """
 552    if stacks is None:
 553        return True
 554    is_available: Dict["Stack", bool] = {}
 555    for consumed_stack in stacks:
 556        start_stacks = zones_stacks.get(zone, [])
 557        for start_stack in start_stacks:
 558            if start_stack.item != consumed_stack.item:
 559                continue
 560            if start_stack.quantity >= consumed_stack.quantity:
 561                is_available[consumed_stack] = True
 562        if consumed_stack not in is_available:
 563            is_available[consumed_stack] = False
 564    return all(is_available.values())
 565
 566
 567class RequirementsGraphLayout(Enum):
 568    LEVEL = "level"
 569    """Layout using requirement level and a metaheuristic."""
 570    SPRING = "spring"
 571    """Classic spring layout."""
 572
 573
 574def apply_color_theme(graph: nx.MultiDiGraph, theme: RequirementTheme):
 575    for node, node_type in graph.nodes(data="type"):
 576        graph.nodes[node]["color"] = theme.color_node(node_type)
 577        for pred, _, key in graph.in_edges(node, keys=True):
 578            graph.edges[pred, node, key]["color"] = theme.color_edges(key)
 579
 580
 581def compute_layout(
 582    digraph: nx.DiGraph, layout: Union[str, RequirementsGraphLayout] = "level"
 583):
 584    layout = RequirementsGraphLayout(layout)
 585    if layout == RequirementsGraphLayout.LEVEL:
 586        pos = leveled_layout_energy(digraph)
 587    elif layout == RequirementsGraphLayout.SPRING:
 588        pos = nx.spring_layout(digraph)
 589    return pos
 590
 591
 592def _draw_on_plt_ax(
 593    ax: Axes,
 594    digraph: nx.DiGraph,
 595    theme: RequirementTheme,
 596    resources_path: Path,
 597    pos: dict,
 598    level_legend: bool = False,
 599):
 600    """Draw the requirement graph on a given Axes.
 601
 602    Args:
 603        ax: Axes to draw on.
 604
 605    Return:
 606        The Axes with requirements_graph drawn on it.
 607
 608    """
 609    edges_colors = [
 610        theme.color_edges([et for et in RequirementEdge].index(edge_type))
 611        for _, _, edge_type in digraph.edges(data="type")
 612    ]
 613    edges_alphas = [_compute_edge_alpha(*edge, digraph) for edge in digraph.edges()]
 614    # Plain edges
 615    nx.draw_networkx_edges(
 616        digraph,
 617        pos=pos,
 618        ax=ax,
 619        arrowsize=20,
 620        arrowstyle="->",
 621        edge_color=edges_colors,
 622        alpha=edges_alphas,
 623    )
 624
 625    for node, node_data in digraph.nodes(data=True):
 626        node_obj = node_data.get("obj", None)
 627        if node_obj is not None:
 628            digraph.nodes[node]["color"] = theme.color_node(node_data["type"])
 629            image = load_or_create_image(node_obj, resources_path, bg_color=(0, 0, 0))
 630            digraph.nodes[node]["image"] = np.array(image)
 631    draw_networkx_nodes_images(digraph, pos, ax=ax, img_zoom=0.3)
 632
 633    # Add legend for edges (if any for each type)
 634    legend_arrows = []
 635    for legend_edge_type in RequirementEdge:
 636        has_type = [
 637            RequirementEdge(edge_type) is legend_edge_type
 638            for _, _, edge_type in digraph.edges(data="type")
 639        ]
 640        if any(has_type):
 641            legend_arrows.append(
 642                mpatches.FancyArrow(
 643                    *(0, 0, 1, 0),
 644                    facecolor=theme.color_edges(
 645                        [et for et in RequirementEdge].index(legend_edge_type)
 646                    ),
 647                    edgecolor="none",
 648                    label=str(legend_edge_type.value).capitalize(),
 649                )
 650            )
 651
 652    # Add legend for nodes (if any for each type)
 653    legend_patches = []
 654    for legend_node_type in RequirementNode:
 655        has_type = [
 656            RequirementNode(node_type) is legend_node_type
 657            for _, node_type in digraph.nodes(data="type")
 658        ]
 659        if any(has_type):
 660            legend_patches.append(
 661                mpatches.Patch(
 662                    facecolor="none",
 663                    edgecolor=theme.color_node(legend_node_type),
 664                    label=str(legend_node_type.value).capitalize(),
 665                )
 666            )
 667
 668    # Draw the legend
 669    ax.legend(
 670        handles=legend_patches + legend_arrows,
 671        handler_map={
 672            # Patch arrows with fancy arrows in legend
 673            mpatches.FancyArrow: HandlerPatch(
 674                patch_func=lambda width, height, **kwargs: mpatches.FancyArrow(
 675                    *(0, 0.5 * height, width, 0),
 676                    width=0.2 * height,
 677                    length_includes_head=True,
 678                    head_width=height,
 679                    overhang=0.5,
 680                )
 681            ),
 682        },
 683    )
 684
 685    ax.set_axis_off()
 686    ax.margins(0, 0)
 687
 688    # Add Hierarchies numbers
 689    if level_legend:
 690        nodes_by_level: Dict[int, Any] = digraph.graph["nodes_by_level"]
 691        for level, level_nodes in nodes_by_level.items():
 692            level_poses = np.array([pos[node] for node in level_nodes])
 693            mean_x = np.mean(level_poses[:, 0])
 694            if level == 0:
 695                ax.text(mean_x - 1, -0.07, "Depth", ha="left", va="center")
 696            ax.text(mean_x, -0.07, str(level), ha="center", va="center")
 697    return ax
 698
 699
 700def _draw_html(
 701    graph: Union[nx.DiGraph, nx.MultiDiGraph],
 702    filepath: Path,
 703    resources_path: Path,
 704    pos: Dict[str, Tuple[float, float]],
 705    depth: int,
 706    width: int,
 707    **kwargs,
 708):
 709    from pyvis.network import Network
 710
 711    resolution = [max(96 * width, 600), max(64 * depth, 1000)]
 712    nt = Network(height=f"{resolution[1]}px", directed=True)
 713    serializable_graph = _serialize_pyvis(
 714        graph,
 715        resources_path,
 716        add_edge_numbers=kwargs.get("add_edge_numbers", False),
 717        with_web_uri=kwargs.get("with_web_uri", False),
 718    )
 719
 720    poses = np.array(list(pos.values()))
 721    poses = np.flip(poses, axis=1)
 722    poses_min = np.min(poses, axis=0)
 723    poses_max = np.max(poses, axis=0)
 724    poses_range = poses_max - poses_min
 725    poses_range = np.where(poses_range == 0, 1.0, poses_range)
 726
 727    def scale(val, axis: int):
 728        return (val - poses_min[axis]) / poses_range[axis] * resolution[axis]
 729
 730    for node, (y, x) in pos.items():
 731        serializable_graph.nodes[node]["x"] = scale(x, 0)
 732        serializable_graph.nodes[node]["y"] = scale(y, 1)
 733
 734    nt.from_nx(serializable_graph)
 735    nt.options.interaction.hover = True
 736    nt.toggle_physics(False)
 737    nt.inherit_edge_colors(False)
 738    nt.write_html(str(filepath))
 739
 740
 741def _compute_edge_alpha(pred, _succ, graph: nx.DiGraph):
 742    alphas = [1, 1, 1, 1, 1, 0.5, 0.5, 0.5, 0.2, 0.2, 0.2]
 743    n_successors = len(list(graph.successors(pred)))
 744    alpha = 0.1
 745    if n_successors < len(alphas):
 746        alpha = alphas[n_successors - 1]
 747    return alpha
 748
 749
 750def _serialize_pyvis(
 751    graph: nx.MultiDiGraph,
 752    resources_path: Path,
 753    add_edge_numbers: bool,
 754    with_web_uri: bool,
 755):
 756    """Make a serializable copy of a requirements graph
 757    by converting objects in it to dicts."""
 758    serializable_graph = nx.MultiDiGraph()
 759
 760    for node, node_data in graph.nodes(data=True):
 761        node_type = node_data.get("type")
 762        node_obj: Optional[Union[Item, Zone]] = node_data.get("obj")
 763
 764        flat_node_data = {}
 765
 766        if node_type is RequirementNode.ITEM:
 767            title = f"{node_obj.name.capitalize()}"
 768        elif node_type is RequirementNode.ZONE_ITEM:
 769            title = f"{node_obj.name.capitalize()} in zone"
 770        elif node_type is RequirementNode.ZONE:
 771            title = f"{node_obj.name.capitalize()}"
 772        elif node_type is RequirementNode.START:
 773            title = f"{node_type.value.capitalize()}"
 774
 775        flat_node_data["title"] = title
 776
 777        label = ""
 778        if node_obj is not None:
 779            flat_node_data["name"] = node_obj.name
 780            image_path = obj_image_path(node_obj, resources_path)
 781            if image_path.exists():
 782                flat_node_data["shape"] = "image"
 783                if with_web_uri:
 784                    relative_path = image_path.relative_to(
 785                        Path(hcraft.__file__).parent.parent.parent
 786                    )
 787                    uri = (
 788                        "https://raw.githubusercontent.com/IRLL/HierarchyCraft/master/"
 789                        f"{relative_path.as_posix()}"
 790                    )
 791                else:
 792                    uri = image_path.as_uri()
 793                flat_node_data["image"] = uri
 794            label = title
 795
 796        if not label:
 797            flat_node_data["font"] = {
 798                "color": "transparent",
 799                "strokeColor": "transparent",
 800            }
 801
 802        flat_node_data["label"] = label
 803
 804        flat_node_data.update(node_data)
 805        flat_node_data.pop("obj")
 806        flat_node_data.pop("type")
 807
 808        serializable_graph.add_node(node, **flat_node_data)
 809
 810    done_edges = []
 811    for start, end, key, edge_data in graph.edges(data=True, keys=True):
 812        transfo: "Transformation" = edge_data.get("obj")
 813        edge_type: RequirementEdge = edge_data.get("type")
 814
 815        flat_edge_data = {
 816            "hoverWidth": 0.1,
 817            "selectionWidth": 0.1,
 818            "arrows": {"middle": {"enabled": True}},
 819        }
 820
 821        if transfo is None:
 822            edge_title = edge_type.value.capitalize()
 823        else:
 824            conditions, effects = repr(transfo).split("⟹")
 825            conditions = conditions.strip()
 826            effects = effects.strip()
 827            edge_title = (
 828                f"{edge_type.value} for {transfo.name} (transformation {key}):"
 829                "\n"
 830                "\nConditions:"
 831                f"\n{conditions}"
 832                "\nEffects:"
 833                f"\n{effects}"
 834            )
 835
 836            if add_edge_numbers:
 837                flat_edge_data["arrows"] = {
 838                    "from": _start_number_dict(
 839                        transfo,
 840                        edge_type,
 841                        serializable_graph.nodes[start]["name"],
 842                        resources_path,
 843                    ),
 844                    "to": _end_number_dict(
 845                        transfo,
 846                        graph.nodes[end]["type"],
 847                        serializable_graph.nodes[end]["name"],
 848                        resources_path,
 849                    ),
 850                }
 851        flat_edge_data["title"] = edge_title
 852
 853        edge_color = edge_data.pop("color")
 854        idle_edge_color = edge_color if graph.number_of_edges() < 100 else "#80808026"
 855        flat_edge_data["color"] = {
 856            "color": idle_edge_color,
 857            "highlight": edge_color,
 858            "hover": edge_color,
 859        }
 860
 861        n_edges = graph.number_of_edges(start, end)
 862        if n_edges > 1:
 863            edge_id = done_edges.count((start, end))
 864            flat_edge_data["smooth"] = {
 865                "enabled": True,
 866                "roundness": 0.05 + 0.08 * edge_id,
 867                "type": "curvedCW",
 868            }
 869            done_edges.append((start, end))
 870        elif graph.has_edge(end, start):
 871            flat_edge_data["smooth"] = {
 872                "enabled": True,
 873                "roundness": 0.15,
 874                "type": "curvedCW",
 875            }
 876        else:
 877            flat_edge_data["smooth"] = {"enabled": False}
 878
 879        flat_edge_data.update(edge_data)
 880        flat_edge_data.pop("obj")
 881        flat_edge_data.pop("type")
 882
 883        serializable_graph.add_edge(start, end, **flat_edge_data)
 884
 885    return serializable_graph
 886
 887
 888def _start_number_dict(
 889    transfo: "Transformation",
 890    edge_type: RequirementEdge,
 891    start_name: str,
 892    resources_path: Path,
 893):
 894    if edge_type is RequirementEdge.ITEM_REQUIRED:
 895        min_amount_of_start = [
 896            stack.quantity
 897            for stack in transfo.get_changes(
 898                InventoryOwner.PLAYER, InventoryOperation.MIN
 899            )
 900            if stack.item.name == start_name
 901        ][0]
 902        from_text = f"≥{min_amount_of_start}"
 903    elif edge_type is RequirementEdge.ITEM_REQUIRED_IN_ZONE:
 904        min_amount_of_start = [
 905            stack.quantity
 906            for stack in transfo.get_changes(
 907                InventoryOwner.CURRENT, InventoryOperation.MIN
 908            )
 909            if stack.item.name == start_name
 910        ][0]
 911        from_text = f"≥{min_amount_of_start}"
 912    else:
 913        return None
 914
 915    return _arrows_data_for_image_uri(_get_text_image_uri(from_text, resources_path))
 916
 917
 918def _end_number_dict(
 919    transfo: "Transformation",
 920    end_type: RequirementNode,
 921    end_name: str,
 922    resources_path: Path,
 923) -> Optional[dict]:
 924    if end_type is RequirementNode.ITEM:
 925        amount_of_end = [
 926            stack.quantity
 927            for stack in transfo.get_changes(
 928                InventoryOwner.PLAYER, InventoryOperation.ADD
 929            )
 930            if stack.item.name == end_name
 931        ][0]
 932        to_text = f"+{amount_of_end}"
 933    elif end_type is RequirementNode.ZONE_ITEM:
 934        amount_of_end = [
 935            stack.quantity
 936            for stack in transfo.get_changes(
 937                InventoryOwner.CURRENT, InventoryOperation.ADD
 938            )
 939            if stack.item.name == end_name
 940        ][0]
 941        to_text = f"+{amount_of_end}"
 942    else:
 943        return None
 944
 945    return {
 946        "to": _arrows_data_for_image_uri(
 947            _get_text_image_uri(to_text, resources_path, flipped=True)
 948        )
 949    }
 950
 951
 952def _arrows_data_for_image_uri(number_uri: str):
 953    return {
 954        "enabled": True,
 955        "src": number_uri,
 956        "type": "image",
 957        "imageWidth": 24,
 958        "imageHeight": 12,
 959    }
 960
 961
 962def _get_text_image_uri(
 963    text: str,
 964    resources_path: Path,
 965    flipped: bool = False,
 966):
 967    numbers_dir = Path(resources_path).joinpath("text_images")
 968    numbers_dir.mkdir(exist_ok=True)
 969    image = _create_text_image(text)
 970    filename = text
 971    if flipped:
 972        filename = f"{text}_flipped"
 973        image = image.transpose(Image.ROTATE_180)
 974    number_path = numbers_dir / f"{filename}.png"
 975    image.save(number_path)
 976    return number_path.as_uri()
 977
 978
 979def _create_text_image(
 980    text: str,
 981    fill_color=(130, 130, 130),
 982    font_path: Optional[Path] = "arial.ttf",
 983) -> "Image.Image":
 984    """Create a PIL image for an Item or Zone.
 985
 986    Args:
 987        obj: A HierarchyCraft Item, Zone, Recipe or property.
 988        resources_path: Path to the resources folder.
 989
 990    Returns:
 991        A PIL image corresponding to the given object.
 992
 993    """
 994    image_size = (96, 48)
 995    image = Image.new("RGBA", image_size, (0, 0, 0, 0))
 996    draw = ImageDraw.Draw(image)
 997
 998    center_x, center_y = image_size[0] // 2, image_size[1] // 2
 999
1000    font = ImageFont.truetype(font_path, size=32)
1001    draw.text((center_x, center_y), text, fill=fill_color, font=font, anchor="mm")
1002    return image