Share your repls and programming experiences

← Back to all posts
Maze Solving Bot (Dijkstra's Algorithm)
BenjaminGrass (13)

Create by a maze and this bot will find the shortest solution!

https://repl.it/@BenjaminGrass/Maze-Solving-Bot-Dijkstras-Algorithm

Just a few notes:
1. To create the maze enter 1's (the path) and 0's (the walls of the maze).
2. The maze must have a uniform row size.
3. There can only be one start (in the top row) and one finish (in the bottom row).
4. The maze can have any number of rows & columns!
5. The shortest path is represented by 2's after the algorithm has run.
Here's an example maze (albeit a simple one):
010
010
010

Comment any bugs you encounter please!

Commentshotnewtop
AlephZero (260)

Cool! I made a maze generator haha

BenjaminGrass (13)

@alephzero: Yeah I saw, nice job! You think we could integrate the two?

AlephZero (260)

@benjamingrass: Hmm, interesting! I think we probably can, all I nedd is to export the maze to an array of ones and zeroes, which would be easy.
I don't know though, since your program is written in Java and mine is written in Javascript.

BenjaminGrass (13)

@alephzero we could try just adding your JS file to my project (or my java files to yours), although I'm not sure how we could get the two to interact. Can you call a method written in a different language than the file you're calling it in? Because if so I could just use your maze generation (already converted into a 2D array of 1's and 0's) as a parameter for the solving algorithm.

Also, would it be possible for you to read an output of 0's, 1's and 2's and go back into your maze and re-color the shortest solution squares?

AlephZero (260)

@benjamingrass: Intriguing. I don't think I can call a method in a different language. But yeah, I thibk I could read an output. I'll see what I can do :)

abishek12 (0)

Input Row ('done' to finish): 11111111
Input Row ('done' to finish): 00000001
Input Row ('done' to finish): 11111111
Input Row ('done' to finish): 10000000
Input Row ('done' to finish): 11111111
Input Row ('done' to finish): 00000001
Input Row ('done' to finish): 11111111
Input Row ('done' to finish): 10000000
Input Row ('done' to finish): done

11111111
00000001
11111111
10000000
11111111
00000001
11111111
10000000

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at ArrToPoints.convert(ArrToPoints.java:119)
at Main.main(Main.java:87)

BenjaminGrass (13)

@abishek12: There are a couple things that the program needs to run correctly:

  1. The maze must have a uniform row size.

  2. There can only be one start (in the top row) and one finish (in the bottom row).

  3. The path cannot run off the side of the maze

So yours should be:

0100000000

011111110

0000000010

0111111110

0100000000

0111111110

0000000010

0111111110

0100000000

scawsome (0)

For the input
00001000000
01111001110
01001001010
01111011010
00010010110
00111110100
00000001110
01111110010
01001011110
01111000000
00100000000

(The path requires going up, down, left and right, and has a few forks which meet up, with one fork being shorter than the other)

It follows the rules mentioned elsewhere in this page (only 1 start, end, uniform length rows, 0's on either side as retaining walls), so I'm not sure what the issue is.

It errors out with:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
at java.util.ArrayList.rangeCheck(ArrayList.java:657)
at java.util.ArrayList.get(ArrayList.java:433)
at Node.getSmallest(Node.java:49)
at Main.dijkstra(Main.java:130)
at Main.dijkstra(Main.java:159)
at Main.dijkstra(Main.java:159)
at Main.dijkstra(Main.java:159)
at Main.dijkstra(Main.java:159)
at Main.dijkstra(Main.java:159)
at Main.dijkstra(Main.java:159)
at Main.dijkstra(Main.java:159)
at Main.dijkstra(Main.java:159)
at Main.dijkstra(Main.java:159)
at Main.dijkstra(Main.java:159)
at Main.dijkstra(Main.java:159)
at Main.dijkstra(Main.java:159)
at Main.dijkstra(Main.java:159)
at Main.dijkstra(Main.java:159)
at Main.dijkstra(Main.java:159)
at Main.dijkstra(Main.java:159)
at Main.main(Main.java:107)