{ "cells": [ { "cell_type": "markdown", "id": "36cee816", "metadata": {}, "source": [ "# Řešení 3. série" ] }, { "cell_type": "code", "execution_count": null, "id": "efe16561", "metadata": {}, "outputs": [], "source": [ "from manim import *" ] }, { "cell_type": "markdown", "id": "36ec08cc", "metadata": {}, "source": [ "## Grafový algoritmus" ] }, { "cell_type": "code", "execution_count": null, "id": "e7a3da39", "metadata": {}, "outputs": [], "source": [ "%%manim -v WARNING -qh GraphAlgorithm\n", "\n", "from random import *\n", "import networkx as nx\n", "\n", "\n", "class GraphAlgorithm(Scene):\n", " def construct(self):\n", " seed(0xDEADBEEF)\n", "\n", " n = 14\n", " p = 3 / n\n", "\n", " # generujeme, dokud nemáme spojitý graf\n", " graph = None\n", " while graph is None or not nx.is_connected(graph):\n", " graph = nx.generators.random_graphs.gnp_random_graph(n, p)\n", "\n", " g = (\n", " Graph(graph.nodes, graph.edges, layout_config={\"seed\": 0})\n", " .scale(2.7)\n", " .rotate(PI / 12)\n", " )\n", "\n", " explored = set()\n", "\n", " def dfs(v, position_object):\n", " \"\"\"Rekurzivní DFS, které posouvá position_object.\"\"\"\n", " neighbours = list(graph.neighbors(v))\n", "\n", " for w in neighbours:\n", " if w in explored:\n", " continue\n", "\n", " # Manim bohužel neorientovaný graf bere jako orientovaný\n", " edge = (v, w) if (v, w) in g.edges else (w, v)\n", "\n", " unexplored_neighbours = [w for w in neighbours if w not in explored]\n", " unexplored_neighbour_edges = [\n", " (a, b)\n", " for a, b in g.edges\n", " if (a == v and b in unexplored_neighbours)\n", " or (b == v and a in unexplored_neighbours)\n", " ]\n", "\n", " # pokud existují neprozkoumaní sousedé, obarveme je\n", " if len(unexplored_neighbours) != 0:\n", " self.play(\n", " *[\n", " g.vertices[q].animate.set_color(ORANGE)\n", " for q in unexplored_neighbours\n", " ],\n", " *[\n", " g.edges[e].animate.set_color(ORANGE)\n", " for e in unexplored_neighbour_edges\n", " ],\n", " )\n", "\n", " explored.add(w)\n", "\n", " # animace přesunu do sousedního vrcholu\n", " # má dvě části - nejprve začneme posun a poté změníme barvy (a flashneme)\n", " \n", " # používáme tu drobný hack - změna barvy posune hrany dopředu, což vypadá špatně\n", " # proto na modrou obarvíme i vrchol v, což jej vyzvedne před ně\n", " # elegantnější řešení je použít z_index, který si objasníme v příštím díle seriálu\n", " self.play(\n", " AnimationGroup(\n", " position_object.animate.move_to(g.vertices[w]),\n", " AnimationGroup(\n", " Flash(g.vertices[w], color=BLUE, flash_radius=0.3),\n", " g.edges[edge].animate.set_color(BLUE),\n", " g.vertices[v].animate.set_color(BLUE),\n", " g.vertices[w].animate.set_color(BLUE),\n", " *[\n", " g.vertices[q].animate.set_color(WHITE)\n", " for q in unexplored_neighbours\n", " if q != w\n", " ],\n", " *[\n", " g.edges[(a, b)].animate.set_color(WHITE)\n", " for (a, b) in unexplored_neighbour_edges\n", " if (a, b) != edge\n", " ],\n", " ),\n", " lag_ratio=0.45,\n", " )\n", " )\n", "\n", " dfs(w, position_object)\n", " self.play(position_object.animate.move_to(g.vertices[v]))\n", "\n", " self.play(Write(g))\n", "\n", " # vyznačení startovního vrcholu\n", " start_vertex = 0\n", "\n", " # objekt, který se posouvá podle toho, na jakém vrcholu jsme\n", " position_object = (\n", " Circle(fill_color=BLUE, fill_opacity=1, stroke_color=BLUE)\n", " .move_to(g.vertices[start_vertex])\n", " .scale(0.15)\n", " )\n", "\n", " self.play(\n", " Flash(g.vertices[start_vertex], color=BLUE, flash_radius=0.3),\n", " g.vertices[start_vertex].animate.set_color(BLUE),\n", " )\n", "\n", " self.add(position_object)\n", "\n", " # spuštění DFS\n", " explored.add(start_vertex)\n", " dfs(start_vertex, position_object)\n", "\n", " self.remove(position_object)\n", " self.play(Unwrite(g))" ] }, { "cell_type": "markdown", "id": "e6f13b54", "metadata": {}, "source": [ "## Fibonacciho posloupnost" ] }, { "cell_type": "code", "execution_count": null, "id": "fc2941bf", "metadata": {}, "outputs": [], "source": [ "%%manim -v WARNING -qh --disable_caching FibonacciSequence\n", "\n", "from random import *\n", "\n", "\n", "class FibonacciSequence(MovingCameraScene):\n", " def create_square(self, size):\n", " \"\"\"Vytvoření čtverce dané velikosti.\"\"\"\n", " return VGroup(Square(side_length=size), Tex(f\"${size}^2$\").scale(size))\n", "\n", " def get_camera_centering_animation(self, squares):\n", " \"\"\"Animace k vycentrování kamery na čtverce.\"\"\"\n", " h = squares.height * 1.5\n", " return self.camera.frame.animate.set_height(h).move_to(squares)\n", "\n", " def construct(self):\n", " squares = VGroup(self.create_square(1))\n", "\n", " self.camera.frame.move_to(squares).set_height(squares.height * 1.5)\n", " self.camera.frame.save_state()\n", "\n", " self.play(Write(squares[0]))\n", "\n", " n = 7\n", "\n", " # vytvoření čtverců a jejich animování\n", " a = 1\n", " b = 1\n", " directions = [RIGHT, UP, LEFT, DOWN]\n", " for i in range(n):\n", " b = b + a\n", " a = b - a\n", "\n", " direction = directions[i % 4]\n", "\n", " new_square = self.create_square(a).next_to(squares, direction, buff=0)\n", " squares.add(new_square)\n", "\n", " self.play(\n", " FadeIn(new_square, shift=direction * a / 3),\n", " self.get_camera_centering_animation(squares),\n", " )\n", "\n", " dot = Dot().move_to(squares[0].get_corner(LEFT + UP)).scale(0.5)\n", "\n", " path = TracedPath(dot.get_center)\n", "\n", " def update_camera_position(camera):\n", " \"\"\"Updater k pozicování kamery nad tečkou.\"\"\"\n", " camera.move_to(dot.get_center())\n", "\n", " self.wait(1)\n", "\n", " # začátek spirály\n", " self.play(\n", " squares.animate.set_color(DARK_GRAY),\n", " AnimationGroup(\n", " self.camera.frame.animate.restore().move_to(dot),\n", " Write(dot),\n", " lag_ratio=0.5,\n", " ),\n", " )\n", "\n", " # nesmíme zapomenout TracedPath přidat do scény, aby byla vykreslována\n", " self.add(path)\n", " \n", " self.camera.frame.add_updater(update_camera_position)\n", "\n", " center_dot = dot.copy()\n", " self.add(center_dot)\n", "\n", " a = 0\n", " b = 1\n", " for i in range(n + 1):\n", " # pole directions je definováno proti směru hodinových ručiček, proto\n", " # sousední dvojice odpovídají bodům ve čtvercích, okolo kterých chceme otáčet\n", " direction = directions[i % 4] + directions[(i + 1) % 4]\n", " b = b + a\n", " a = b - a\n", "\n", " # při každém čtvrtotočení zoomujeme zhruba o poměr sousedních fibonacciho\n", " # čísel, což je phi (zlatý řez); číslo zmenšujeme, aby animace vypadala lépe\n", " phi = (1 + 5 ** (1 / 2)) / 2\n", " zoom_coefficient = phi * 0.9\n", " \n", " self.play(\n", " Rotate(\n", " dot,\n", " about_point=squares[i].get_corner(direction),\n", " angle=PI / 2,\n", " ),\n", " self.camera.frame.animate.scale(zoom_coefficient),\n", " rate_func=linear,\n", " )\n", "\n", " # po dotočení již nechceme držet kameru nad bodem, ani dále tracovat cestu\n", " self.camera.frame.clear_updaters()\n", " path.clear_updaters()\n", "\n", " self.play(self.get_camera_centering_animation(squares))\n", " \n", " self.wait(1)\n", "\n", " # fadeouty + hezké odspirálení\n", " self.play(\n", " FadeOut(squares),\n", " FadeOut(dot),\n", " AnimationGroup(\n", " Unwrite(path, run_time=2),\n", " AnimationGroup(Flash(center_dot, color=WHITE), FadeOut(center_dot)),\n", " lag_ratio=0.9,\n", " ),\n", " )" ] }, { "cell_type": "markdown", "id": "8188912d", "metadata": {}, "source": [ "## Langtonův mravenec" ] }, { "cell_type": "code", "execution_count": null, "id": "cad4e39c", "metadata": {}, "outputs": [], "source": [ "%%manim -v WARNING -qh LangtonAnt\n", "\n", "from random import *\n", "\n", "\n", "class Ant:\n", " \"\"\"Třída mravence (pro čistší kód).\"\"\"\n", "\n", " deltas = [(-1, 0), (0, -1), (1, 0), (0, 1)]\n", "\n", " def __init__(self, position):\n", " self.position = position\n", " self.orientation = 0\n", "\n", " def __get_orientation_delta(self):\n", " \"\"\"O kolik má mravenec posunout.\"\"\"\n", " return self.deltas[self.orientation]\n", "\n", " def __rotate_by_delta(self, delta):\n", " \"\"\"Otočení mravence do libovolného směru o násobek 90 stupňů.\"\"\"\n", " self.orientation = (self.orientation + delta) % len(self.deltas)\n", "\n", " def rotate_left(self):\n", " \"\"\"Otočení mravence doleva.\"\"\"\n", " self.__rotate_by_delta(-1)\n", "\n", " def rotate_right(self):\n", " \"\"\"Otočení mravence doprava.\"\"\"\n", " self.__rotate_by_delta(1)\n", "\n", " def move_forward(self):\n", " \"\"\"Posunutí mravence dopředu.\"\"\"\n", " dx, dy = self.__get_orientation_delta()\n", " self.position[0] += dx\n", " self.position[1] += dy\n", "\n", " def update(self, states):\n", " \"\"\"Posunutí a otočení mravence a upravení stavu.\"\"\"\n", " x, y = self.position\n", "\n", " # znegování pole, na kterém mravenec stojí\n", " states[y][x] = not states[y][x]\n", "\n", " # otočení\n", " if states[y][x]:\n", " self.rotate_right()\n", " else:\n", " self.rotate_left()\n", "\n", " # posunutí\n", " self.move_forward()\n", "\n", "\n", "class LangtonAnt(MovingCameraScene):\n", " def construct(self):\n", " n = 15\n", " state = [[False for _ in range(n)] for _ in range(n)]\n", " squares = [[Square() for _ in range(n)] for _ in range(n)]\n", " squares_vgroup = VGroup(*[*sum(squares, [])]).arrange_in_grid(columns=n, buff=0)\n", "\n", " ant = Ant([n // 2, n // 2])\n", " ant_object = (\n", " SVGMobject(\"ant.svg\")\n", " .set_height(squares_vgroup[0].height * 0.7)\n", " .rotate(PI / 2)\n", " )\n", "\n", " self.play(FadeIn(squares_vgroup), Write(ant_object))\n", "\n", " self.wait(1)\n", "\n", " step_count = 100\n", "\n", " # kolik iterací na začátku a na konci je pomalých\n", " slow_start_iterations = 5\n", " slow_end_iterations = 3\n", "\n", " # jak rychlé jsou animace\n", " slow_run_time = 1\n", " fast_run_time = 0.07\n", "\n", " for i in range(step_count):\n", " x, y = ant.position\n", "\n", " new_color = state[y][x]\n", " rect = squares[y][x]\n", "\n", " running_time = (\n", " fast_run_time\n", " if slow_start_iterations < i < step_count - slow_end_iterations\n", " else slow_run_time\n", " )\n", "\n", " # otáčení mravence\n", " self.play(\n", " Rotate(ant_object, PI / 2 * (1 if new_color else -1)),\n", " run_time=running_time,\n", " )\n", "\n", " # posunutí mravence\n", " ant.update(state)\n", " nx, ny = ant.position\n", "\n", " self.play(\n", " rect.animate.set_fill(BLACK if new_color else WHITE, 1),\n", " ant_object.animate.move_to(squares[ny][nx]),\n", " self.camera.frame.animate.move_to(squares[ny][nx]),\n", " run_time=running_time,\n", " )\n", "\n", " self.wait(1)\n", "\n", " # zjistíme, které čtverce jsou aktuálně bílé\n", " white_squares = VGroup()\n", "\n", " for i in range(n):\n", " for j in range(n):\n", " if state[i][j]:\n", " white_squares.add(squares[i][j])\n", "\n", " # oddálíme a vycentrujeme na tyto čtverce\n", " self.play(\n", " self.camera.frame.animate.move_to(white_squares).set_height(\n", " white_squares.height * 1.2\n", " )\n", " )\n", "\n", " self.play(FadeOut(squares_vgroup), FadeOut(ant_object))" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.10.2" } }, "nbformat": 4, "nbformat_minor": 5 }