Maze Solving - Computerphile

Aug 15, 2023

Maze Solving - Computerphile

Putting search algorithms into practice. Dr Mike Pound reveals he likes nothing more in his spare time, than sitting in front of the TV coding.

EXTRA BITS: • EXTRA BITS - Maze Solving Code - Comp…

Mike’s Code: http://bit.ly/MikesMarvellousMazes

http://www.facebook.com/computerphile
https://twitter.com/computer_phile

This video was filmed and edited by Sean Riley.

Computer Science at the University of Nottingham: http://bit.ly/nottscomputer

Computerphile is a sister project to Brady Haran’s Numberphile. More at http://www.bradyharan.com

Content

0 -> try a little bit different today after

2.58 -> we did the video on Dykstra I thought

4.23 -> well you know sometimes I like to go

6.12 -> home and sometimes do a bit of

7.89 -> programming in front of the TV you know

9.51 -> the person I am and one of the cool

12.03 -> things that you about being other

13.019 -> program is if you think all i wonder if

14.91 -> i could write something that would solve

15.96 -> mazes you can immediately go and

17.94 -> actually do that that thing so that's

19.59 -> what we're doing today I've come over a

21.689 -> bit of a part of a small program not

23.369 -> very complicated that fold mazes that

27.48 -> you give it an image for you get amazed

29.64 -> it worked his way through it and then

30.99 -> output say the same picture made from

33.27 -> red line on it is very exciting and but

36.18 -> I've also actually implemented lot of

38.25 -> different search approaches so I didn't

39.51 -> go into depth and breadth first search

40.68 -> and a star and Dykstra

45.56 -> want to see the actual code those things

46.94 -> then we'll make it available so other

48.71 -> people can follow along tweak it maybe

50.78 -> improve on what I've done it comes back

52.76 -> down to date well for the implementation

55.76 -> video doesn't it because there are so

57.83 -> many ways you can program something that

59.69 -> solves an image-based maze and how I've

64.46 -> done it is okay it probably isn't the

66.56 -> optimal I I had in mind i wanted to do

68.78 -> really big mazes in fifteen thousand

70.7 -> pixels by 15,000 pixel maybe bigger

72.98 -> about around now so I can't go any

74.75 -> bigger than that but so i'd love you to

77.93 -> be most semi efficient at the very least

79.94 -> you know not completely impractical and

82.16 -> so I thought to started by coming up

84.26 -> with some rules that my maid have to

87.26 -> follow because yeah okay so I could I

89.45 -> could give it any maze any picture made

91.91 -> a photograph of amazed but then most of

94.07 -> the time i'm going to be doing is now

95.36 -> just trying to turn that into a

96.92 -> structure in memory and that's what a

99.32 -> job right you want to be there I mean

101.119 -> yeah yeah and i'm just doing it in front

102.38 -> of the TV you know I get carried away so

104.18 -> what I said was I have a black and white

107.72 -> pixel image that hopefully doesn't have

111.53 -> jpeg compression on it because activex

113.36 -> everything is a blackboard all the way

114.95 -> around the outside that the wall and

116.66 -> then any black pixels wall anyway pixels

118.97 -> path and their intention to the top and

121.91 -> an expert at the bottom that that was my

123.59 -> boat my rules

124.7 -> I almost the other boot made it don't

126.649 -> follow the rules are going to work in

128.39 -> myself where you can follow me to extend

130.34 -> myself with how they're closed amazed if

132.2 -> you want I've got a very small image

133.819 -> here called tiny dot PNG which you can't

137.84 -> see because windows does not like to

139.76 -> expand these qualifies of images what

142.79 -> you don't do is give it the 50,000

144.62 -> 50,000 image first go because if you

146.51 -> have any kind of problem you've no idea

147.98 -> what we want my baby started a small

149.99 -> image you can actually sort of debug

151.94 -> what's going on in the code you could

153.47 -> say well I was expecting this to happen

155.03 -> and it didn't which means i made a

156.59 -> mistake or something like this to start

158.84 -> with a small cases and then work your

161.18 -> way up to the bigger think hopefully

163.01 -> once you've got to add overbust album

165.56 -> that work for small limited on the mazes

167.66 -> just get a big amazing should figure

170.51 -> cross work first time we should think so

173.959 -> i've taught amazed right that took ages

176.629 -> to draw in video it but

178.55 -> you know just giving all this in a

180.41 -> little bit wayward here but you know

182.12 -> each of these square in a square and I

184.91 -> had enough nothing like that about it

186.2 -> than that

186.8 -> so my walls are that the outside is

191 -> black

191.69 -> apart from the top has one picture of

193.55 -> light which is the entrance and the

195.11 -> bottom have one picture of which is the

196.67 -> exit those are my rules that have come

197.99 -> up with now I said there are loads of

200.42 -> ways we could solve that maze

201.68 -> programmatically perhaps the first one I

203.99 -> did and it's so in the most obvious one

205.82 -> is just to put it into memory and then

208.1 -> kind of freak pixel look at the

209.9 -> neighbors and see if we can go there and

211.67 -> then move there and if maybe we can go a

213.47 -> bit further and so on so that with my

215.3 -> credit first trial implementation what I

217.91 -> did was like I copied it into memory or

219.62 -> storage array and then I say that's my

221.9 -> start position at not 123 naught but and

225.92 -> I said we'll look where can I go from

227.18 -> free not well well the left pixel to

229.67 -> know is is black the color there and the

232.04 -> next pixel across for North is black

235.91 -> longer there but this one isn't this 31

238.4 -> is white so i'll go there and I'll

240.62 -> continue my search from there and I

242.12 -> think the same for the blue car looked

243.65 -> at look left look like process and every

245.72 -> pixel like this is basically a flat

248.48 -> field but it's nothing smart about this

250.1 -> and it does work in the sense that it

254.87 -> will get into the end is loaded very

256.43 -> quickly you have to have a small but

258.29 -> says which nodes have been visited if

260 -> you otherwise you're just going to go up

261.35 -> and down up and down up and down up and

263.03 -> down it and get yourself into a loop or

265.64 -> here we got an actual loop we want to go

267.74 -> around and mailed if we don't have any

269.33 -> idea about where we've been so i created

271.19 -> another a variety of the exact same size

273.14 -> as this which was a true-or-false of a

276.32 -> foodie the right and just if you've been

278.72 -> visited you get that true and will ever

280.97 -> go back there but because by definition

282.95 -> we don't want to go backwards glue come

285.53 -> from

286.07 -> right but what if you get go to a

288.62 -> dentist partially so the data structure

291.53 -> that i'm using to do this breadth first

292.85 -> search is it's one that keep a bit about

297.56 -> our box to approach in our previous

298.91 -> video keeps retractable windows that

301.01 -> currently under consideration but

302.99 -> haven't been invented yet

304.4 -> so you know if it's been looking down

305.96 -> here have this one and maybe this one

308.09 -> maybe this one and when it gets to the

310.19 -> end here

311.23 -> we'll just go out and work out a little

312.91 -> fall back to this one so it highly

314.95 -> inherently allows itself to backtrack

317.47 -> and if I love doing it as you said that

320.47 -> as you sort of suggested which was I

322.72 -> just kind of followed blindly then i'm

325.39 -> going to be doing a lot of backtracking

326.5 -> now I had actually implemented version

328.45 -> of that was much aware that of life left

332.05 -> turn version as well good luck Hardaway

335.02 -> and implement a few different approaches

336.31 -> the problem with what i did here by

338.59 -> which is why i'm not showing the code of

340.48 -> this particular version is that it's a

342.55 -> beneficent like it's it's not massively

345.61 -> inefficient in memory because the right

346.99 -> don't take up a huge amount we even for

348.85 -> a really big image you know you know we

350.8 -> love these kind of images when we take

352.39 -> high-resolution photographs and things

354.07 -> so it's not inconceivable that you have

357.37 -> that amount of memory the issue more is

360.34 -> that over made of that kind of Sighs the

363.97 -> amount of nose under consideration start

366.19 -> to grow really quite rapidly that put

368.44 -> the memory and computational overhead

369.76 -> that we don't want and also if I'm

372.52 -> walking down this path here let's say

374.83 -> and I'm here like I can't let the right

377.17 -> here called left or right here

378.79 -> I called left to right here and I'm

380.59 -> spending a lot of time going to this one

382.42 -> adding it to the queue to this one and

383.89 -> then and going down here i'm taking one

386.02 -> two three four steps when we really want

388.21 -> that with a surprise now spit at people

390.01 -> interview at some point I'm going to

391.87 -> have to travel down there but I don't

394.12 -> want to store that information in memory

395.59 -> just seems a bit inefficient

397.66 -> so what i did was i wrote a a one-pass

402.1 -> which means one look over the image out

403.75 -> with them to turn this maze into a graph

407.47 -> like that one too dr. video i have no

409.72 -> idea is the optimal album for this

411.43 -> probably not but it was not going to

413.44 -> work and it extends quite reasonably two

415.9 -> large mazes as well let's have a quick

419.2 -> look at how that works let's go with our

420.79 -> green pen if we do one part of them what

423.76 -> we have to do is make all the decisions

424.78 -> we want to make by just cutting process

427.18 -> throughout medical office was and then

428.95 -> across thrown across the rope and you

430.6 -> could do it column wise but for the sake

432.52 -> of argument I've got that the most

434.26 -> obvious thing is once we get to the

435.79 -> start we can slide that the start and

437.71 -> that's good right so the first low we

439.99 -> simply move along until we get to start

442 -> and we create a node

443.92 -> in that position that my note little

445.93 -> have a little object in memory stored it

448.24 -> and it will store any of these

450.13 -> connections 20 neighbors but it can so

452.2 -> that's RS in the dark shades RS yes but

455.2 -> in in my implementation decision to

457.27 -> somewhere in the array this is an actual

459.16 -> tangible object in memory that has a

461.47 -> north east and west connection that

463.45 -> could have something connected to it in

465.37 -> this case is not gonna have a lot of

466.45 -> connection because you know not going to

468.49 -> go anywhere so for the next row i came

471.46 -> up with a number of rules that depending

474.64 -> on whether you're looking at war on the

476.11 -> flat part you do different things right

478.15 -> so the first one for example is if

480.01 -> you're on a wall

481.03 -> don't do anything but you can't right

483.28 -> now there you can't connect and he knows

484.9 -> to that point it doesn't make any sense

486.37 -> right so if you're on a wall but you do

487.66 -> nothing right and it's reflected in the

489.52 -> code if you're on a path and you were on

492.28 -> a wall that means you want to start

494.02 -> something new so we should create a node

495.82 -> but it start to get a little bit

498.01 -> confusing but I can basically I can't

499.93 -> with different rules so in this one we

502.51 -> talked their dad we can't go up we were

504.49 -> already on the path that we do nothing

505.87 -> this one we've got something about that

508.03 -> we can connect to

509.02 -> so we create a node here and we join

510.88 -> them up and we've just created a note so

513.07 -> we join them up like we know which is

515.05 -> literally created on the left so we're

517.6 -> tracking the ones above the ones to the

519.43 -> left and we're going this way down

521.65 -> always so microsoft way can I take a

523.63 -> break in motion TV and then I come back

525.1 -> the next day and and i'm going to ok so

527.8 -> now but this node this goes into

529.96 -> anything this doesn't do anything

531.13 -> because awful down to glow decision to

533.35 -> be made at this node is no point we make

535.48 -> anything in memory for here here this is

537.88 -> an obvious junction we can go down to

539.38 -> this point so we created those and we

541.78 -> connected back to the one we last saw on

543.34 -> the left and then again we get to this

546.61 -> one we're just in front of a wall at the

548.56 -> end of the corridor that's so exciting

550.15 -> we create a node and rejoined out by

552.97 -> this now there's a few statements

554.89 -> involved in that what you saw in your

557.02 -> line think about the steps you have to

560.05 -> take that each given position and what's

562.75 -> going on at that position doesn't take

564.61 -> very long to come up the steps you know

566.56 -> if there is a war on the left is all the

568.75 -> like is there a passel of those are the

571.24 -> things we basically have to check and

573.52 -> they will involve referencing the image

575.08 -> and saying is it was all that pixel

577.16 -> and the next one below by this one

580.639 -> doesn't left her life so it's a path

583.67 -> going downwards and don't do anything on

585.29 -> this one

585.949 -> alright this one the same this on the

587.779 -> side on the next row this one is a

590.48 -> junction so we created knows we

593 -> connected to the last one is all about

594.439 -> it which I stored in the list

596.48 -> incidentally for those of you following

597.889 -> along with my coach so we get to before

599.509 -> mrs. that this is the end of the

600.649 -> corridor we connect that in here we

602.6 -> start one here because that's the

603.769 -> beginning of a corridor end of the

605.629 -> corridor connect them up this one take

608.269 -> no action and you get the idea

610.1 -> over time we start to fill in wherever

613.25 -> there's an interesting junction anything

615.05 -> to be done

615.709 -> you see that this and we propagate this

617.329 -> through until eventually we finish off

619.939 -> our graph this unit I will actually

622.009 -> finish it off because i went to all the

623.209 -> trouble of doing out there we are

625.85 -> but now it's my algorithm is correct all

628.43 -> of these notes should exactly reflect

630.98 -> are made and what we've got it

633.019 -> insulated increase memory because these

635.06 -> loads a slightly bigger objects in the

636.889 -> underlying away which is just small

638.629 -> numbers but we have to take many fewer

641.36 -> steps to go across this late you know

643.759 -> the step counts from here to here is one

645.829 -> instead of 3 and so on and depending on

649.279 -> the length of your corridors in your

650.509 -> maze you can imagine that drastically

652.16 -> decrease the number of nodes you have to

653.81 -> be expanding into and so they want to

657.259 -> did was I said well okay so i put this

659.389 -> in the maze class so i go to class and

661.43 -> object in memory that stores this maze

663.199 -> have a start

664.579 -> it happened and then I started writing

666.769 -> other classes that their only task is to

669.29 -> go to later be so i did that first

671.779 -> search which expands all of them one

673.97 -> after another

674.63 -> remember next and the next and the flood

676.61 -> fill that first search with his fans as

678.829 -> far as to count one direction and then

680.48 -> the next election and so on and then

682.67 -> left her lonely which is where you with

684.529 -> her less and you get stopped all the

686.63 -> time and it with her left but it's a

689.99 -> closed famous made solving album because

691.939 -> if you're human and you can't see the

694.25 -> whole maze

695.18 -> it was quite well and then I also

697.819 -> implemented Dykstra in a style as well

700.1 -> so we'll see if it works

701.87 -> so that's one of the command prompt soap

704.449 -> in an ideal world I would have a name of

706.91 -> the file read in from a command line

709.04 -> parameters like I do actually have to do

710.57 -> that apartment was a bit lazy and I

712.61 -> hard-coded it so at the moment it was

715.22 -> tiny dot PNG could have told me to and

717.05 -> that's the only made it done so Python

719.6 -> so dot pie

721.49 -> there we are and so it creates the image

723.14 -> didn't take long with this is not a big

725.18 -> maze in fact it took no second to solve

727.64 -> made it only got 23 knows

729.65 -> let's see if that's true 123456789 10 12

733.94 -> 14 efficient any more than 20 22 23 1

737.81 -> quite pleased actually because I could

738.92 -> have been really embarrassing but it's

740.36 -> that pile of debugging that I was doing

742.04 -> early on and getting funny amount of

743.9 -> nose and you think we're done wrong okay

745.61 -> i must have not connected these popular

747.38 -> something I've got a very technical

748.61 -> question for you what was entirely while

751.25 -> all this was going to wasn't le oh yeah

753.71 -> good point arm something like that to

755.63 -> cultural too hard it's got detailed plot

757.46 -> is difficult for me to also do this

758.96 -> community one thing that one

760.22 -> it took six 10,000 for a second i think

762.38 -> that is some fraction of a second to to

765.56 -> actually find the path explored lighting

767.78 -> know that means it looked at mind

769.61 -> impossible cabin nodes and eventually

771.74 -> found a path that would have length 94

773.78 -> here and if we look at the image which

776.06 -> again it difficult to do on this screen

778.64 -> so using the magic of editing this will

780.62 -> now appear very large and extremely

782.12 -> positive rather than that which has also

785.12 -> been linearly interpolated which is

787.1 -> exactly what I didn't want to happen on

788.42 -> this pc my previous video on linear

790.97 -> interpolation so I thought a pass in

793.04 -> from glutamate which represents the

794.75 -> start to the end

795.74 -> let's see if we can do something a

796.97 -> little bit more challenging like so here

800.54 -> i have a 2000 by 2000 image which when

803.45 -> you load up on my screen looks like a my

805.7 -> patent now i use the program with

807.89 -> Daedalus to generate this and you can

809.27 -> generate very large mazes I'm taking it

811.4 -> in some way on faith that there is a

812.81 -> bachelor star island could you know it

816.02 -> doesn't make a slightly different life

817.43 -> program so i had to go in and start the

819.14 -> end by partnumber why did on this one

821.12 -> and so on so let's see if it work

823.55 -> so this is called 2000rpm gee that's a

826.37 -> hard-coded change right on that and it

828.74 -> will take a little bit longer to

830 -> creative ways maybe

836.64 -> get coffee there we go light so it took

841.17 -> a second to create the maid and it had

843.12 -> 760,000 node now when you consider that

846.09 -> amazing with two thousand pixels by 2000

848.46 -> pixels which is four million pixels and

851.91 -> let's say half of them white on average

853.65 -> then you would expect about 2,000 loads

855.75 -> if you were doing it the bad way

857.91 -> how about I try to save some money this

859.71 -> way it's essentially what i'm doing it

861.21 -> and then the actual the actual worm was

863.73 -> it that further breadth-first search

864.9 -> everyone i was breadth-first apparently

867.18 -> punch my code it takes 15 seconds not no

870.18 -> longer to get through that made and

871.86 -> again using wizardry I will resume in on

874.11 -> this and you can see it has found a path

876.06 -> through so it looks like a general

877.74 -> arcing path but if we zoom in you can

879.42 -> see it's actually finding its way from

880.77 -> quite complicated maze the last in class

883.11 -> is that the two major i just put in

885.03 -> that's open perfect mazes that means

887.4 -> there's only one possible solution

889.08 -> everything else is by definition a dead

890.79 -> end now somebody's are like that like if

893.76 -> you were to think of the Manhattan

894.6 -> Bridge systems amazed then in some ways

899.04 -> there's a lot of different parties could

900 -> take and really what you want to do is

901.26 -> find the shortest one tomato got here

903.12 -> has multiple solutions to it and so for

906.66 -> example if I want a depth-first search

908.1 -> on it it will be going down the first

910.32 -> part fine as far as possible and it may

912.57 -> well not take the shortest path because

914.64 -> it would just go down as part of our two

917.43 -> cans and that part might lead to the

918.66 -> exit it just might be very long so if i

921 -> change my algorithm to this image and

923.16 -> then get first right and we run it

926.25 -> okay he didn't take long 6300 knows a

930.54 -> hundredth of a second to actually

931.95 -> calculate it but it found all kinds of

934.41 -> super group through my mace and so calm

936.45 -> down here and then up here again and

938.52 -> back down here now the chances i

940.35 -> probably just jumped across here or

941.91 -> something silly

942.78 -> it just didn't occur to in some sense

944.31 -> because it was falling apart was on I

945.93 -> mean they're searching better associated

947.43 -> is two different problems like depending

949.5 -> on the northern knows you want to expand

951.03 -> but in this case suboptimal it would be

953.25 -> the site is not not the optimal

955.11 -> algorithm to use so I've also

957.15 -> implemented better search and a star and

959.19 -> Isis dices shortest path and so on if I

962.67 -> turn turn it into Dykstra has a bit of

964.83 -> overhead because you've got to set up

966.39 -> your quality q which i'm using Fibonacci

968.4 -> heat

969.15 -> do that because if not he also in the

971.85 -> code that reprogram yourself so if we

973.89 -> run this so the path length that debt

975.93 -> first found with a fountain world and

977.91 -> the parkland dr establish will be the

979.59 -> shortest path is 897 long they've been

982.89 -> taking a bit longer to do it just could

984.6 -> have many overhead mostly there we go

986.49 -> about the actual shortest path through

988.5 -> that maze which is significantly better

990.03 -> than the last one

991.68 -> yeah get download the code have a play

993.27 -> around see if you couldn't work out what

995.1 -> I've done and what I shouldn't have done

996.45 -> that maybe you can fix it and then come

999 -> up with a live album if you want to try

1000.5 -> to work your way through to make and

1002.18 -> depend on how much rather you have you

1003.47 -> can see what kind of that size have made

1005.21 -> it will handle and we look forward to

1007.01 -> seeing some more pictures

1008.48 -> yes but partner isn't as fast as doing

1014.15 -> this in depth they see something like

1015.74 -> that but it's not too bad and absolute

1019.1 -> speed is not important for this because

1020.6 -> i was just looking for fun and deceive

1022.4 -> see you know with work right so you know

1027.77 -> if you want to be implemented in a park

1030.44 -> language is not the point arithmetic and

1032 -> so on been you know go for it but

Source: https://www.youtube.com/watch?v=rop0W4QDOUI