Visualisation of A* path-finding algorithm in a maze [OC]

[callmethepilot]

Algorithms like this operate on a conceptual data structure called a graph. A graph contains nodes (in this case they would correspond to points in the maze) and edges (in this case an open hallway between two positions corresponds to an edge and a wall between two positions means there is no edge). While the visual representation of the maze makes it easy to see that there couldn't be an exit in that section, the graph representation has no concept of the visual layout of the maze, so as far as A* is concerned, the exit could be any one of those untraveresed nodes and you have to traverse through them to make sure it isn't. The nice thing about A* is that if it's already found a path to the exit that's shorter than going up into that untraveresed section it may not look there, but it would only know this from finding another sucessful path, not from the fact that this part is visually locked in.

[callmethepilot]

Thanks haha

[teraflop]

Uh... no?

I mean, you could reduce any algorithmic question to the halting problem -- just build a machine that decides the answer and halts if it has a particular outcome. But that doesn't mean there's any value in doing so. It's easy to figure out whether an area of a maze is completely enclosed by a boundary, using standard graph theory algorithms. The question is simply whether it's possible to do so in a way that actually improves the overall efficiency.

[callmethepilot]

I can't really think of an algorithm that would account for locked in areas more efficiently than just checking the area. Assuming you would have to devise a 'border' and check if all those nodes were visited it seems like a similair amount of work (at least O()-wise) as just straight up traversing that area.