Maze solving algorithm

[Boban Vukovic]

Guys,I would like to make an app where little bug should find its way through a maze(labyrinth) !

If someone is interested in helping me,I would like to hear your opinion what would be best(fastest) algorithm for this task.

I have one idea,but really would love to hear some other (maybe faster ) solution.

Thanks in advance!

[Abraham Getzler]

The Lee algorithm is the earliest and easiest ...

In 1961 Lee proposed the algorithm [30, 46] which became one of the most famous, reused and rediscovered algorithms in last century. We start at the destination site. We label neighbours of the site with ‘1’. Then we label their neighbours with ‘2’. Being at the site labelled i we label its non-yet-labelled neighbours with i + 1. Sites occupied by obstacles, or the maze walls, are not labelled. When all accessible sites are labelled the exploration task is completed. To extract the path from any given site of the maze to the destination site we start at the source site. Then we select a neighbour of the source site with lowest value of its label. We add this neighbour to the list. We jump at this neighbour. Then we select its neighbour with lowest value of the label. We add this neighbour to the list. We jump at this neighbour. We continue like that till we get at the destination site. Thus the algorithm computes one-destination-many-sources shortest path. A set of shortest path starting from each site of the maze gives us a spanning tree which nodes are sites of the maze and a root is the site where wave pattern of labelling started to grow.

from https://pdfs.semanticscholar.org/2fc5/c1eb47421bc9beee5f18db0b7adf8e9923f9.pdf

ABG

 

[Boban Vukovic]

Thanks a lot Mr Getzler,I really appreciate your help,but one downside of this algorithm is that bug (program) has to scan entire maze and exit (destination) have to be known in advance.

I was thinking something more like real life,so someone puts you (my little bug) in front of the maze and you dont know anything else.

Anyway I came up with something else:

Bug goes strait in one direction until it bumps the wall.Then it changes direction by +90 deg if possible,or -90 deg if possible,or finally +180 deg and moves further.

if previous field had 3 walls it is dead end,so in present field bug puts a mark in direction opposite of its heading,so it knows it is a dead end.

A bit complicated to explain,but I am posting my aia,and really would like to her your comment.

Didnt bother with resizing maze to fit screen for now,and I adjusted bug size to always be in center of one field

[TimAI2]

Look great Boban!

Noticed the bug misses a turn if it on a "straight"

After I took this screenshot it missed another which

then took it back where it came from, trapped in a loop

Anyway to get the bug to "look ahead" on a "straight" (e.g. top left of maze) in order to

save time having to go to the end.

That said, very clever :) 

[Boban Vukovic]

It was my idea in the first place,if bug can go straight,it dont make turns.

About the"loop",it is not trapped,it  (I guess bug is "it" ,not ""she")  just checks upper left fields,where it never was before.

If you gave it more time,you`d see it finds its way out of the maze

Love the idea to look ahead on straight,though.

[Boban Vukovic]

I need help with something; I downloaded png from here http://www.mazegenerator.net/   

I would like my app to download images on a button click.

I managed so far to click Generate button with some Javascript,but cant download generated image.

Any help would be highly appreciated