[Tremaux] Does not backtrack correctly in simple open world

[rgoupil]

This concern Tremaux's algorithm.

In a very simple open world, the backtracking does not occur correctly. When the entity move straight to a know path, it keep going forward instead of backtracking. Actually it never start backtracking until it reach a dead-end. This lead to erroneous paths.

You can reproduce the issue on your maze solver in JS: Maze: {"start": {"x": 0, "y": 1}, "end": {"x": 11, "y": 9}, "width": 20, "height": 10, "map": "

---

...................* .................. .................. .................. .................. .................. .................. .................. **.*******"}

Direct URL: http://www.primaryobjects.com/maze/?maze={%22start%22:%20{%22x%22:%200,%20%22y%22:%201},%22end%22:%20{%22x%22:%2011,%20%22y%22:%209},%22width%22:%2020,%22height%22:%2010,%22map%22:%20%22********************...................**..................**..................**..................**..................**..................**..................**..................************.********%22}

[primaryobjects]

Cool, thanks for this great example!

A* handles this map very well. But, you're right about Tremaux, it does not solve it efficiently, although it does seem to solve it eventually. I think you're right that it should turn around after it fills the board red, but I think this anomaly is because the map is not a perfect maze, but rather an open area, which the Tremaux algorithm is not effective at solving. See here.

When the algorithm hits a dead-end, it tries to find the next available direction to move, where there is no wall and that the algorithm has only visited once. Since all directions have no wall and only 1 visit, it chooses the first direction it finds - which is straight ahead.

I'm not sure if it should turn around and "backtrack" if there are no well-defined walls anyway. Technically, it is backtracking, it's just doing so by going straight ahead over its previously visited path.

Feel free to play with the code and see if you can find a "fix" if one is needed. I think it is somewhere here or here, but I'm not sure if Tremaux works well anyway with an open area world.

Thanks again for this example.

[rgoupil]

Thank you for your quick answer.

Your point about Tremaux's performance in an open area is right, but quoted straight from the SO answer you linked:

If you're walking down a new passage and encounter a junction you have visited before, treat it like a dead end and go back the way you came so that you won't go around in circles or missing passages.

I am not sure how this rule has been implemented in the walker, but I believe that the way it is described should handle the issue pointed by my example. When hitting the inner end of the spiral, the walker would backtrack out of it until finally getting to the junction to the exit missed earlier and reach it. I need to implement Tremaux as a candidate solution in one of my project and will make sure to try this special case. If I happen to find a way to solve this issue, I'll come back here to play with the code for sure :)

Have a good day and thanks for your article about A* and Tremaux, it is a great source of information to compare both algorithms.

[rgoupil]

Just a quick update. I wrote a basic implementation in C++ and making sure that a path already known is treated as a wall solve the issue of this ticket without harming the performance or the original behaviour of the walker. I will have a look at the javascript in the next days to see if I can find a way to make it work if you don't mind.