maze solving by a wavefront

[Brandon Parker]

tsh73, now all you need is the ability to delete a wall after you accidentally place it somewhere...unless I missed something that already exists.


{:0)

Brandon Parker

[plus]

Mar 1, 2022 2:52:42 GMT Brandon Parker said:

tsh73, now all you need is the ability to delete a wall after you accidentally place it somewhere...unless I missed something that already exists.


{:0)

Brandon Parker

Hmm... maybe missed something, or I did. 

My reading of this is that tsh73 is comparing A* method of finding shortest path from start to finish points against what he calls a wavefront method. The wavefront is both simpler and faster than A*. He has provided an great app barrowed from Cassiope34 to allow others to prove it for themselves.

RFO-basic also very interesting news to me!  

[tsh73]

now all you need is the ability to delete a wall after you accidentally place it somewhere

Tick that radio button and try to drag over a wall

[plus]

Oh that's what he was asking about, OK.

[cassiope34]

Feb 28, 2022 19:40:40 GMT tsh73 said:

I just added showing visited cells for wave algorithm
And without obstacles A* surely wins (at least in visited points)


And with some obstacles, that could be circumvented and then continue with line of sight, it still wins


But on your mase which makes path run back and forth - A* covers almost as much points as wave algorithm.

That's exactly what I wanted to ask you tsh73   (and also the possibility of activating the authorized diagonals)

So if I understand correctly: the screenshots on the left are those of A* and those on the right are those of WaveFront!

Overall, if A* tests fewer cells, why is it 7 times slower than WaveFront?

plus : Everyone is welcome on the RFO-Basic forum

I wouldn't want to depopulate this JustBasic forum though

Cheers,
Gilles.

[tsh73]

(and also the possibility of activating the authorized diagonals)

I will try later. It just not there so have to invent something (or adapt from A*)
*DONE*

So if I understand correctly: the screenshots on the left are those of A* and those on the right are those of WaveFront!

Yes

Overall, if A* tests fewer cells, why is it 7 times slower than WaveFront?

One have to look but my guess that using direction may include sorting and it is costly.

[Brandon Parker]

Mar 1, 2022 7:11:07 GMT tsh73 said:

now all you need is the ability to delete a wall after you accidentally place it somewhere

Tick that radio button and try to drag over a wall

Got it...

I did try that, but I only clicked on a "wall" block; I did not move the mouse, so it did not delete the block I clicked on. And, I did not examine the code like I should have either...


{:0)

Brandon Parker

[cassiope34]

Hi,

here is my Android version with an option "Hazard" you use in your first post.

Maze PathFinder.apk (661.37 KB)

NB : You can extract all the files from the APK including the *.bas by simply opening it with a software like 7-zip or Izarc or other zipper / unzipper.

tsh73 : maybe could you add this option "Hazard" in the Just Basic version
In fact, with this option, the Wavefront algorithm is sometimes longer than Astar algorithm and don't give always the shorter path !!


Cheers,
Gilles