René's URL Explorer Experiment


Title: Transform the Maze Into a Graph (Video) – Real Python

Open Graph Title: Transform the Maze Into a Graph – Real Python

Description: Transform the Maze into a Graph. To create a graph, you’ll need to provide nodes and edges that connect them. You’ve already established that your maze consists of nodes that represent path intersections, dead ends, and special squares, such as…

Open Graph Description: Transform the Maze into a Graph. To create a graph, you’ll need to provide nodes and edges that connect them. You’ve already established that your maze consists of nodes that represent path intersections, dead ends, and special squares, such as…

Opengraph URL: https://realpython.com/lessons/transform-python-maze-graph/

X: @realpython

direct link

Domain: realpython.com

Hey, it has json ld scripts: 
  {
    "@context": "https://schema.org",
    "@type": "VideoObject",
    "name": "Transform the Maze Into a Graph",
    "description": "Transform the Maze into a Graph. To create a graph, you’ll need to provide nodes and edges that connect them. You’ve already established that your maze consists of nodes that represent path intersections, dead ends, and special squares, such as…",
    "thumbnailUrl": ["https://files.realpython.com/media/Build-a-Pac-Man-Maze-Solver-in-Python_Watermarked.c2e79a85fc99.jpg"],
    "uploadDate": "2023-06-06T14:00:00+00:00",
    "duration": "PT7M6S",
    
    "potentialAction": {
      "@type": "SeekToAction",
      "target": "https://realpython.com/lessons/transform-python-maze-graph/#t={seek_to_second_number}",
      "startOffset-input": "required name=seek_to_second_number"
    }
  }
authorReal Python
theme-color#18354c
color-schemelight dark
twitter:cardsummary_large_image
twitter:imagehttps://files.realpython.com/media/Build-a-Pac-Man-Maze-Solver-in-Python_Watermarked.c2e79a85fc99.jpg
og:imagehttps://files.realpython.com/media/Build-a-Pac-Man-Maze-Solver-in-Python_Watermarked.c2e79a85fc99.jpg
twitter:creator@realpython
og:typevideo.episode
og:site_nameReal Python
apple-mobile-web-app-titleReal Python

Links:

https://realpython.com/
Start Herehttps://realpython.com/start-here/
Learn Python https://realpython.com/lessons/transform-python-maze-graph/
Your Learning Plan →Your personalized Python learning planhttps://realpython.com/account/learning-plan/
Python Tutorials →In-depth articles and video courseshttps://realpython.com/search?kind=article&kind=course&order=newest&_from=nav_library
Learning Paths →Guided study plans for accelerated learninghttps://realpython.com/learning-paths/
Quizzes & Exercises →Check your learning progresshttps://realpython.com/search?kind=exercise&kind=quiz&_from=nav_library
Browse Topics →Focus on a specific area or skill levelhttps://realpython.com/tutorials/all/
Reference →Concise definitions for common Python termshttps://realpython.com/ref/
Mentor AI →NewYour personal Python mentorhttps://realpython.com/mentor/
Office Hours →Live Q&A calls with Python expertshttps://realpython.com/office-hours/
Community Chat →Learn with other Pythonistashttps://realpython.com/community/
Live Courses →Live, instructor-led Python courseshttps://realpython.com/live/
Books →Round out your knowledge and learn offlinehttps://realpython.com/products/books/
Podcast →Hear what’s new in the world of Pythonhttps://realpython.com/podcasts/rpp/
Unlock All Content and Become a Python Expert →Get unlimited access to all Real Python has to offerhttps://realpython.com/account/join/?from=navbar_learn
Unlock All Content →Become a Python Experthttps://realpython.com/account/join/?from=navbar_learn
More https://realpython.com/lessons/transform-python-maze-graph/
Learner Storieshttps://realpython.com/learner-stories/
Python Newsletterhttps://realpython.com/newsletter/
Python Job Boardhttps://www.pythonjobshq.com
Meet the Teamhttps://realpython.com/team/
Become a Contributorhttps://realpython.com/jobs/
Searchhttps://realpython.com/search
https://realpython.com/search
Joinhttps://realpython.com/account/join/
Sign‑Inhttps://realpython.com/account/login/?intent=navbar&next=%2Flessons%2Ftransform-python-maze-graph%2F
Unlock This Lessonhttps://realpython.com/account/join/?utm_source=rp_lesson&utm_content=python-maze-solver
Unlock This Lessonhttps://realpython.com/account/join/?utm_source=rp_lesson&utm_content=python-maze-solver
https://realpython.com/courses/python-maze-solver/#team
Mazes in Python: Build, Visualize, Store, and Solvehttps://realpython.com/courses/python-maze-solver/
Darren Joneshttps://realpython.com/courses/python-maze-solver/#team
Recommended Tutorialhttps://realpython.com/python-maze-solver/
Course Slides (.pdf)https://realpython.com/courses/python-maze-solver/downloads/mazes-in-python-slides/
Sample Code (.zip)https://realpython.com/courses/python-maze-solver/downloads/mazes-in-python-code/
Ask a Questionhttps://realpython.com/lessons/transform-python-maze-graph/#discussion
https://realpython.com/feedback/survey/course/python-maze-solver/liked/?from=lesson-title
https://realpython.com/feedback/survey/course/python-maze-solver/disliked/?from=lesson-title
Contentshttps://realpython.com/lessons/transform-python-maze-graph/#description
Transcripthttps://realpython.com/lessons/transform-python-maze-graph/#transcript
Discussionhttps://realpython.com/lessons/transform-python-maze-graph/#discussion
00:01https://realpython.com/lessons/transform-python-maze-graph/#t=1.02
Transform the Maze into a Graph.https://realpython.com/lessons/transform-python-maze-graph/#t=1.02
To create a graph,https://realpython.com/lessons/transform-python-maze-graph/#t=3.438
you’ll need to provide nodes and edges that connect them.https://realpython.com/lessons/transform-python-maze-graph/#t=4.97
You’ve already established that your maze consists of nodes that represent pathhttps://realpython.com/lessons/transform-python-maze-graph/#t=8.59
intersections, dead ends, and special squares, such as enemies or the entrance.https://realpython.com/lessons/transform-python-maze-graph/#t=12.41
00:17https://realpython.com/lessons/transform-python-maze-graph/#t=17.3
However, if you connect them directly without taking the corners into account,https://realpython.com/lessons/transform-python-maze-graph/#t=17.3
then you won’t be able to follow the maze’s horizontal and vertical pathways.https://realpython.com/lessons/transform-python-maze-graph/#t=21.9
00:26https://realpython.com/lessons/transform-python-maze-graph/#t=26.54
The image on the left depicts six color-coded nodes,https://realpython.com/lessons/transform-python-maze-graph/#t=26.54
including two intersections in blue, two dead ends in red,https://realpython.com/lessons/transform-python-maze-graph/#t=29.28
as well as the entrance and the exit in green.https://realpython.com/lessons/transform-python-maze-graph/#t=33.54
00:37https://realpython.com/lessons/transform-python-maze-graph/#t=37.34
The image on the right is almost the same, but it adds four corners in yellow,https://realpython.com/lessons/transform-python-maze-graph/#t=37.34
which allow you to preserve the maze’s layout.https://realpython.com/lessons/transform-python-maze-graph/#t=41.25
Your Border model can already identify a .corner, an .intersection,https://realpython.com/lessons/transform-python-maze-graph/#t=47.01
and a .dead_end,https://realpython.com/lessons/transform-python-maze-graph/#t=51.04
while the Role model will tell you whether the associated square has somehttps://realpython.com/lessons/transform-python-maze-graph/#t=52.31
special function in the maze.https://realpython.com/lessons/transform-python-maze-graph/#t=55.66
00:59https://realpython.com/lessons/transform-python-maze-graph/#t=59.66
You can treat the square as a synonym for a graph node because NetworkX letshttps://realpython.com/lessons/transform-python-maze-graph/#t=59.66
you use any object as a node, as long as it’s hashable.https://realpython.com/lessons/transform-python-maze-graph/#t=64.08
The Square class is hashable out of the box because it was implemented as anhttps://realpython.com/lessons/transform-python-maze-graph/#t=67.99
immutable, frozen data class.https://realpython.com/lessons/transform-python-maze-graph/#t=71.93
01:14https://realpython.com/lessons/transform-python-maze-graph/#t=74.271
To use consistent terminology,https://realpython.com/lessons/transform-python-maze-graph/#t=74.271
you’ll define a type alias for the Square class so that you can refer to it as ahttps://realpython.com/lessons/transform-python-maze-graph/#t=76.87
Node in your code.https://realpython.com/lessons/transform-python-maze-graph/#t=81.29
01:23https://realpython.com/lessons/transform-python-maze-graph/#t=83.984
Once you’ve done this,https://realpython.com/lessons/transform-python-maze-graph/#t=83.984
you’ll model the edge as a pair of two nodes,https://realpython.com/lessons/transform-python-maze-graph/#t=86.06
which you can implement as a named tuple.https://realpython.com/lessons/transform-python-maze-graph/#t=88.2
01:48https://realpython.com/lessons/transform-python-maze-graph/#t=108.98
It’s possible to represent edges of directed graphs with this class becausehttps://realpython.com/lessons/transform-python-maze-graph/#t=108.98
it’s an ordered pair.https://realpython.com/lessons/transform-python-maze-graph/#t=112.87
But for now,https://realpython.com/lessons/transform-python-maze-graph/#t=114.253
you’ll only consider undirected graphs with two-way connections between theirhttps://realpython.com/lessons/transform-python-maze-graph/#t=115.07
nodes.https://realpython.com/lessons/transform-python-maze-graph/#t=119.27
02:03https://realpython.com/lessons/transform-python-maze-graph/#t=123.97
Now that you have a representation for nodes and edges,https://realpython.com/lessons/transform-python-maze-graph/#t=123.97
you can start transforming your maze into a graph by first getting a collectionhttps://realpython.com/lessons/transform-python-maze-graph/#t=126.93
of nodes from it.https://realpython.com/lessons/transform-python-maze-graph/#t=130.67
02:11https://realpython.com/lessons/transform-python-maze-graph/#t=131.76
The simple way would be to turn all squares into nodes.https://realpython.com/lessons/transform-python-maze-graph/#t=131.76
However, capturing only intersections,https://realpython.com/lessons/transform-python-maze-graph/#t=135.58
corners, and dead ends as nodes can lead to a more efficient and accuratehttps://realpython.com/lessons/transform-python-maze-graph/#t=137.98
solution for solving mazes.https://realpython.com/lessons/transform-python-maze-graph/#t=142.19
02:24https://realpython.com/lessons/transform-python-maze-graph/#t=144.33
You can identify these nodes by checking the role and border pattern of eachhttps://realpython.com/lessons/transform-python-maze-graph/#t=144.33
square in the maze.https://realpython.com/lessons/transform-python-maze-graph/#t=148.19
Ifhttps://realpython.com/lessons/transform-python-maze-graph/#t=149.616
02:59https://realpython.com/lessons/transform-python-maze-graph/#t=179.89
a square is marked as either a wall or exterior,https://realpython.com/lessons/transform-python-maze-graph/#t=179.89
then it’s definitely not part of the graph,https://realpython.com/lessons/transform-python-maze-graph/#t=182.54
so you skip it with a continue statement.https://realpython.com/lessons/transform-python-maze-graph/#t=184.85
Otherwise,https://realpython.com/lessons/transform-python-maze-graph/#t=188.15
if the square has some special role other than None,https://realpython.com/lessons/transform-python-maze-graph/#t=188.91
then you record it as a graph node.https://realpython.com/lessons/transform-python-maze-graph/#t=191.56
03:18https://realpython.com/lessons/transform-python-maze-graph/#t=198.53
Finally, regardless of the square’s role, you take note of intersections,https://realpython.com/lessons/transform-python-maze-graph/#t=198.53
dead ends, and corners.https://realpython.com/lessons/transform-python-maze-graph/#t=202.81
03:34https://realpython.com/lessons/transform-python-maze-graph/#t=214.36
Thanks to using a Python set,https://realpython.com/lessons/transform-python-maze-graph/#t=214.36
you don’t have to worry about adding the same square more than once when,https://realpython.com/lessons/transform-python-maze-graph/#t=216.16
for example, a reward happens to be placed at an intersection.https://realpython.com/lessons/transform-python-maze-graph/#t=219.48
03:43https://realpython.com/lessons/transform-python-maze-graph/#t=223.52
That’s because sets filter out duplicates.https://realpython.com/lessons/transform-python-maze-graph/#t=223.52
Next,https://realpython.com/lessons/transform-python-maze-graph/#t=227.855
you’ll need to connect your nodes with edges.https://realpython.com/lessons/transform-python-maze-graph/#t=228.48
To do that,https://realpython.com/lessons/transform-python-maze-graph/#t=231.256
you’ll take advantage of the fact that the maze is a rectangular grid.https://realpython.com/lessons/transform-python-maze-graph/#t=232.2
03:56https://realpython.com/lessons/transform-python-maze-graph/#t=236.65
That means you can loop through the nodes you just identified,https://realpython.com/lessons/transform-python-maze-graph/#t=236.65
checking to the right and down for any adjacent nodes in the maze and stoppinghttps://realpython.com/lessons/transform-python-maze-graph/#t=240.14
once you reach a wall.https://realpython.com/lessons/transform-python-maze-graph/#t=243.89
04:07https://realpython.com/lessons/transform-python-maze-graph/#t=247.67
You look for the immediate neighbors of each node supplied to the function.https://realpython.com/lessons/transform-python-maze-graph/#t=247.67
In this case, you will move east and south in the maze,https://realpython.com/lessons/transform-python-maze-graph/#t=251.51
but you could just as well follow the opposite directions,https://realpython.com/lessons/transform-python-maze-graph/#t=254.83
remembering to change the loop indexing and wall detection accordingly.https://realpython.com/lessons/transform-python-maze-graph/#t=257.77
04:53https://realpython.com/lessons/transform-python-maze-graph/#t=293.83
First, you check to the east.https://realpython.com/lessons/transform-python-maze-graph/#t=293.83
You use the bitwise AND operator (&) to check if a border around the current squarehttps://realpython.com/lessons/transform-python-maze-graph/#t=298.34
has a right side, indicating a wall that terminates the search in that direction.https://realpython.com/lessons/transform-python-maze-graph/#t=302.32
05:07https://realpython.com/lessons/transform-python-maze-graph/#t=307.58
If it does, then you break out of the loop.https://realpython.com/lessons/transform-python-maze-graph/#t=307.58
On the other hand,https://realpython.com/lessons/transform-python-maze-graph/#t=310.779
if you find a square located in the same row as your source node is also presenthttps://realpython.com/lessons/transform-python-maze-graph/#t=312.46
in the set of nodes, and there’s no wall between them,https://realpython.com/lessons/transform-python-maze-graph/#t=316.82
then you create an Edge instance.https://realpython.com/lessons/transform-python-maze-graph/#t=319.39
05:21https://realpython.com/lessons/transform-python-maze-graph/#t=321.537
Youhttps://realpython.com/lessons/transform-python-maze-graph/#t=321.537
05:29https://realpython.com/lessons/transform-python-maze-graph/#t=329.36
then perform a similar check, but looking south,https://realpython.com/lessons/transform-python-maze-graph/#t=329.36
checking for bottom walls and checking for nodes in the same column,https://realpython.com/lessons/transform-python-maze-graph/#t=332.48
adding an edge as before.https://realpython.com/lessons/transform-python-maze-graph/#t=335.86
06:08https://realpython.com/lessons/transform-python-maze-graph/#t=368.27
Knowing the edges is sufficient to define a new NetworkX graph object.https://realpython.com/lessons/transform-python-maze-graph/#t=368.27
06:31https://realpython.com/lessons/transform-python-maze-graph/#t=391.66
The initializer method of nx.Graph can optionally take various graph data types,https://realpython.com/lessons/transform-python-maze-graph/#t=391.66
including a collection of edges.https://realpython.com/lessons/transform-python-maze-graph/#t=396.59
Normally,https://realpython.com/lessons/transform-python-maze-graph/#t=399.092
you should create an instance of nx.MultiGraph to account for parallel edgeshttps://realpython.com/lessons/transform-python-maze-graph/#t=399.91
that might appear in one of your mazes.https://realpython.com/lessons/transform-python-maze-graph/#t=404.01
06:46https://realpython.com/lessons/transform-python-maze-graph/#t=406.565
However,https://realpython.com/lessons/transform-python-maze-graph/#t=406.565
the extra corners that you added before make each parallel connection unique,https://realpython.com/lessons/transform-python-maze-graph/#t=407.44
so there’s no need to use a multigraph in this case.https://realpython.com/lessons/transform-python-maze-graph/#t=411.36
In the next section,https://realpython.com/lessons/transform-python-maze-graph/#t=418.65
you’ll use NetworkX to find the shortest path from the entrance to the exit ofhttps://realpython.com/lessons/transform-python-maze-graph/#t=419.77
the maze.https://realpython.com/lessons/transform-python-maze-graph/#t=424.03
Become a Memberhttps://realpython.com/account/join/
https://realpython.com/lessons/solve-python-maze-graph-based/
Overviewhttps://realpython.com/courses/python-maze-solver/
https://realpython.com/lessons/python-maze-shortest-path/
Mazes in Python: Build and Visualize 02:47 https://realpython.com/videos/python-maze-solver-part-1-overview/
Check Out What You'll Make 02:39 https://realpython.com/videos/python-maze-solver-project/
Lay the Groundwork 04:02 https://realpython.com/videos/python-maze-solver-groundwork/
Scaffold the Project Structure 04:50 https://realpython.com/lessons/python-maze-solver-structure/
Represent the Maze With Objects 06:37 https://realpython.com/lessons/represent-maze-with-objects/
Create Border Patterns 06:32 https://realpython.com/lessons/python-maze-border-patterns/
Model the Square 02:25 https://realpython.com/lessons/model-python-maze-square/
Build the Maze 09:07 https://realpython.com/lessons/build-python-maze/
Visualize the Maze With SVG 04:45 https://realpython.com/lessons/python-maze-svg/
Implement Geometric Primitives 04:48 https://realpython.com/lessons/python-maze-geometric-primitives/
Add More Primitives 03:47 https://realpython.com/lessons/python-maze-more-primitives/
Decompose the Border Into Primitives 04:41 https://realpython.com/lessons/decompose-python-maze-border/
Add More Border Patterns 03:58 https://realpython.com/lessons/python-maze-more-border-patterns/
Build the SVG Renderer 03:49 https://realpython.com/lessons/python-maze-svg-renderer/
Add Features to the Renderer 06:50 https://realpython.com/lessons/python-maze-renderer-features/
Draw the Solution 03:13 https://realpython.com/lessons/draw-python-maze-solution/
Preview the Rendered Maze and Its Solution 04:56 https://realpython.com/lessons/preview-python-maze/
Mazes in Python: Build and Visualize (Recap) 01:14 https://realpython.com/lessons/python-maze-solver-part-1-summary/
Mazes in Python: Store and Solve 01:48 https://realpython.com/videos/python-maze-solver-part-2-overview/
Load the Maze From a Binary File 04:55 https://realpython.com/videos/python-maze-binary-file/
Choose Your Data Alignment 05:09 https://realpython.com/videos/python-maze-data-alignment/
Define the File Header and Body 08:12 https://realpython.com/lessons/python-maze-file-header-and-body/
Serialize the Maze 05:22 https://realpython.com/lessons/serialize-python-maze/
Deserialize the Maze 04:32 https://realpython.com/lessons/deserialize-python-maze/
Make the Maze Self-Contained 04:30 https://realpython.com/lessons/python-self-contained-maze/
Update the Maze Class 03:16 https://realpython.com/lessons/python-maze-class/
Solve the Maze Using a Graph-Based Approach 03:01 https://realpython.com/lessons/solve-python-maze-graph-based/
Transform the Maze Into a Graph 07:06 https://realpython.com/lessons/transform-python-maze-graph/
Find the Shortest Path 05:23 https://realpython.com/lessons/python-maze-shortest-path/
Add Weights to Graph Edges 02:36 https://realpython.com/lessons/python-map-weights-graph-edges/
Introduce Enemies and Rewards 06:04 https://realpython.com/lessons/python-maze-enemies-rewards/
Make a Runnable Script 03:59 https://realpython.com/lessons/python-maze-runnable-script/
Mazes in Python: Store and Solve (Recap) 01:23 https://realpython.com/lessons/python-maze-solver-part-2-summary/
Privacy Policyhttps://realpython.com/privacy-policy/

Viewport: width=device-width, initial-scale=1, shrink-to-fit=no, viewport-fit=cover

Robots: max-image-preview:large

URLs of crawlers that visited me.