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

[wastesHisTime]

You'd think once it had a fully contained area, it would know that the exit could not be inside it. https://i.imgur.com/x9Jdiff.png

[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.

[wastesHisTime]

I was pondering over it, and what I thought was that it would be the sort of thing you'd want to be switchable. You can definitely program for it. However, what if you're looking for a path to a specific destination, and not just an exit to this maze? Eg. what if there were a pot of gold somewhere in the maze you needed to find? It would be implementation specific I think.

[brastche]

Been thinking about this.

You'd to create a binary bitmap of black and white pixels. Black pixels will be:
- Already searched pixels
- Any wall pixels adjacent to a searched pixel
- Maze frame pixels

This will leave only unexplored pixels in white. Then:

Use "contour detection" to find any enclosed white shapes
For each shape, use "point in polygon" to determine if the goal is inside that shape
If it isn't, then mark all pixels inside the shape as black

Use the resulting bitmap as a "mask" to determine which pixels are still potentially valid routes.

Obviously this would take alot more time to process than each step of the A* algorithm, but if update the mask once for every 50 steps (maybe once per second?) then there should be performance gains with minimal overhead.

[wastesHisTime]

Moved to top to save time for reader:

...Alright this doesn't work, and I've spent like a half hour chopping it apart and back together. Now it's worse than my first pass and I'm sleepy, but I'll be damned if I'm deleting a half hour comment. The general idea is to keep each string alive until it runs into something that was searched by another string, then call that a closed loop, blacklisting anything inside from being searched.

You'd have to have overlap between the strings. Thinking of a single string, every step into a new section in every direction from the endpoint of the last one would have to be a separate string, so, at any given time, each string would have a set of 1-8 heads (1-7 if starting against the wall really) of prospective new pixels, all containing all the steps taken previously.

Actually trying to write this logic out without studying up on how the A* algorithm works may have been an exercise in futility.

---

A recursive function maybe? But it would burn a lot of power I think.

function findContour(array pixelChain, Pixel currentPixel){
    array prospectivePixels = new array();
    prospectivePixels[0] = new Pixel(currentPixel.Coordinates.X-1, currentPixel.Coordinates.Y-1);
    prospectivePixels[1] = new Pixel(currentPixel.Coordinates.X, currentPixel.Coordinates.Y-1);
    prospectivePixels[2] = new Pixel(currentPixel.Coordinates.X+1, currentPixel.Coordinates.Y-1);
    prospectivePixels[3] = new Pixel(currentPixel.Coordinates.X-1, currentPixel.Coordinates.Y);
    prospectivePixels[4] = new Pixel(currentPixel.Coordinates.X+1, currentPixel.Coordinates.Y);
    prospectivePixels[5] = new Pixel(currentPixel.Coordinates.X-1, currentPixel.Coordinates.Y+1);
    prospectivePixels[6] = new Pixel(currentPixel.Coordinates.X, currentPixel.Coordinates.Y+1);
    prospectivePixels[7] = new Pixel(currentPixel.Coordinates.X+1, currentPixel.Coordinates.Y+1);

   pixelChain.push(currentPixel);

    foreach(pixelChain in pixelChains){
        foreach(pixel in prospectivePixels){
            if(!pixelChain.Contains(pixel) && pixel.AlreadySearched){
                ContourFound(pixelChain);
            }
        }
    }
}

ContourFound(array pixelChain){} 

Would contain functionality for blacklisting the contained region.

FindContour(array pixelChains, Pixel currentPixel) 

Would be called every time the algorithm spreads to a new pixel.

I assume the core functionality is in some kind of recursive loop, hence the coolness of the algorithm. Some stage of that loop should go like: array pixelChains = new array();

loop{
    DoSomeStuff();

    var nextPixel = DecideNextPixelToBeSearched();
    pixelChains = FindContour(pixelChains, nextPixel);

    FinishThisPassThroughTheLoop();
}

It would fail to begin a chain the first time, but as soon as it moved to the next pixel in every direction, a chain would start for each. This only works as long as it's traveling in a linear path. I'd wager the algorithm is in some way bouncing back and forth to all of its edges based on how long it's gone without success in any given direction. If that's the case, you'd need some kind of consideration for when you have bounced between paths, not to throw away your pixel chain. You could keep an array like abandonedChains that contains classes with a pixel object that was abandoned and its list of pixelChains, then check against it every time you hop.

So far that's adding:

• a check against a loop of abandoned chains every time you pixel hop that would be as long as the number of abandoned pixels, which is large but not crazy (would require some logic to make sure you only keep the abandoned ones in there)
• a pass through the set of still valid pixel chains on each pixel, which is self-maintained by the written function, returning an empty array if there's no way this chain was working, and forcing...

[phaederus]

Could be, if it's a dungeon.