Coding Challenge 162: Self-Avoiding Walk

The Coding Train

It’s finally time to attempt a Self-Avoiding Walk! In this video, I quickly visualize a simple JavaScript p5.js implementation of a self-avoiding walk. I then tackle the more complex problem of backtracking to find a solution to a space-filling self-avoiding walk.

p5.js Web Editor Sketches:
🕹️ Basic Self Avoiding Walk:
🕹️ Self Avoiding Walk with Backtracking:
🕹️ Self Avoiding Walk 3D:
🕹️ Self Avoiding Walk with Bezier:
🕹️ Self Avoiding Walk with Recursion:
🕹️ Random Walk with Alpha:

🎥 Previous video:
🎥 All videos:

Links discussed in this video:
🔗 Self Avoiding Walk (Wikipedia):
🔗 The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes:
🔗 The pivot algorithm: A highly efficient Monte Carlo method for the self-avoiding walk (sci-hub):

Other videos mentioned in this video:
🎥 Random Walker – Coding Challenge 52:
🎥 Minesweeper – Coding Challenge 71:
🎥 filter() – Array Functions:
🎥 Maze Generator – Coding Challenge 10:
🎥 Recursion – Coding Train 77:
🎥 A* Pathfinding Algorithm – Coding Challenge 51:
🎥 3D Self Avoiding Walk – Coding Train Live (May 27, 2021):

Timestamps:
0:00 Choo choo! Welcome!
1:05 Explain! How can we go about this?
2:29 Code! Let’s add a visited grid.
6:25 Code! What are the options for movement now?
10:34 Code! Let’s check the edges.
12:34 I could stop here but wait.
13:30 Explain! How can we think about backtracking?
15:15 Code! Let’s make a spot class and a path variable.
24:23 Code! Now backtracking!
29:38 Whoops! Copying allOptions was a mistake.
31:19 Code! Maybe we need an end condition.
32:09 Yay! It worked.
32:22 This could take awhile. Could it be improved?

🚂 Website:
👾 Share Your Creation!
🚩 Suggest Topics:
💡 GitHub:
💬 Discord:
💖 Membership:
🛒 Store:
📚 Books:
🖋️ Twitter:
📸 Instagram:

🎥 Coding Challenges:
🎥 Intro to Programming:

🔗 p5.js:
🔗 p5.js Web Editor:
🔗 Processing:

📄 Code of Conduct:

This description was auto-generated. If you see a problem, please open an issue:

(Visited 1 times, 1 visits today)

Leave a Reply