How to solve a maze using shaders - Shadron tutorial

welcome to another shade run tutorial and today we will try something not entirely practical but still quite interesting and fun we will try to solve a maze using shaders and draw the shortest path through keep in mind that this is far from the most efficient way to do this but a very simple one which also provides a very nice visualization our input will be a simple black and white image of a maze with green color marking the starting point and red color marking the target location and this is our desired output to solve the maze we will utilize a feedback buffer which is a shader and object that uses its previous state as a texture input to sample from it is very useful for example for modeling cellular automata or fluid dynamics the feedback buffer like any other image has four channels and we will use each of them separately to represent different kinds of data the Alpha channel will remain constant and will represent the maze boundaries with zero alpha the transparent pixels will be displayed as white the green channel will carry a wave originating from the starting point which will spread through the maze and encode the distance from the origin at each pixel it reaches the red Channel is the same but originating at the endpoint the two waves will start simultaneously and they will meet in the middle of the shortest path at this point the sum of both distances is the length of the path unfortunately we cannot copy the value to a global variable so we will use the blue channel to broadcast this value to the other pixels we can then start building the shortest path from the middle until we reach both ends so let's load the input maize image and construct the initial state of the feedback buffer we will sample the maze at the current coordinate and determine the color components of the buffer the starting point is marked green so we will detect it as a high value in the green Channel and low values in the red and blue channels we set the green component 1 in this case and therefore initiate the green starting point wave detecting the end point is the same using the red channel the boundaries of the maze are black so a low value in all three channels indicates a wall if your input has a different color scheme you can simply customize these conditions now the initial state of the feedback buffer looks like this again the pixels with 0 alpha are displayed white the shader that updates the feedback buffer receives the sampler for its previous state as well as position and time Delta we will first sample the previous pixel at this position updated and then return it to do that we will also look at a number of neighboring values and relate their information to our pixel in particular we are looking for the maximum values in the neighborhood which are closest to the waves origin you can try using different numbers of directions and see what happens so using a four cycle we will shift the position by one pixels length in a circle and sample the buffer since waves cannot propagate through walls we will multiply each neighbor by its alpha making it zero if it lies within the boundary finally we update the maximum which will be done separately for each channel since we want the red and green waves to represent the distance from the origin we need to slightly lower their value at each step I arbitrarily chose this fraction because it looked good we also need to update the blue channel with the best known total distance and since we are using an exponentially decreasing metric for the distances we get the total by multiplying them now we just have to update our local value according to the neighboring Maxima also taking into account boundaries at this position and return it we create the feedback buffer using this shader function as well as the initial state function since we need more precision than the standard eight bits per channel we will add the full range flag and in order to make the process faster we may also set a higher update rate only do this if your GPU can handle it though now we can watch the waves spreading through the maze what's left to do is use the contents of the feedback buffer to draw the actual path we will use a handful of parameters for this so let's sample the input image as background as well as the value in the solution buffer we will mix the bath color into the background using the path opacity we compute if the blue wave has reached this point we can determine the difference between the current length and the true path length it will probably never be exactly zero so any value below some tolerance threshold will be considered on the path and to make its edges smoother we will also use smooth step with another parameter and this is the final visualization to get an image of the result you can press space to pass the animation and then save it normally if you have any questions feel free to ask in the comments I really hope you like this video and if you enjoy using Chadron i'd like to ask you to write a review on Steam and if not please let me know what you don't like about it by the way I have also made significant progress on the Mac OS version and if everything goes well it should be available within the next few weeks see you next time

Channel: Shadron

Views: 18,792

Keywords: Shadron, shader, GLSL, maze, fragment shader, feedback buffer, tutorial

Id: GULy4vtkw6w

Length: 6min 45sec (405 seconds)

Published: Wed Oct 18 2017

Reddit Comments

[u/pdbatwork]

That was pretty cool. I am not much into graphics programming, so I don't know the complexity of what you did. But the video was pretty good. Good animations and descriptions.

[u/a4555in]

(I'm not the guy in the video)

[u/celerym]

This seems like a really cool tool actually, thank you for sharing.

[u/Veedrac]

I actually wanted something similar fairly recently, in the sense that it was a path traversal problem to implement on the GPU, though it was easier to design an efficient algorithm than the video shows. I still haven't implemented my solution because I've been bitter about how none of my favourite approaches work in WebGL, but such is life. I'll get around to it eventually.

The general, albeit simplified, idea starts with a black and white image. These are divided into conceptual lines, all of which are either closed loops or have two ends (which may be the same point). A line ends when it collides with the centre of another line (a) or comes to a stop (b), though it may also simply make a turn (c). If two lines intersect (d), they simply pass through each other.

(a)     ₂   (b)         (c)         (d)   ₂
    ¹ ¹ ½       ¹ ¹ ¹       ¹ ¹ ¹       ¹ ½ ¹
        ₂                       ¹         ₂

Note that every image has exactly one unique decomposition, and two lines never end in the same place.

The question is how to produce a new image where each pixel is replaced with the pairs of indices of the start and end of the line it is on. Resolve ½-pixels and cycles in any manner you wish.

[u/neoform]

What library was used?

[u/[deleted]]

Thanks! Now I can find the easiest rout to any girls heart. - youtube comment. They are hilarious.

[u/Ebullient_Me]

Woaah,dude.Its really magnificent.If you are so keen to learn about GLSL Language why not opt for a mini-project and create a youTube channel for the same.Thanks for sharing such quality stuff.Keep us updated with more and more such things.Way to go a4555in(you totally rock man).