AI Pathfinding Algorithm

[last halo]

from collections import deque
from Algorithms import aStarAlgorithm as astar
import heapq

def isFinished(path, allCoords):
    return set(map(tuple, path)).intersection(set(map(tuple, allCoords))) == set(map(tuple, allCoords))

def getKClosestCoords(curCoord, allCoords, checkedCoords, k):
    closestCoords = []
    curX, curY = curCoord
    uncheckedCoords = {coord for coord in allCoords if coord not in checkedCoords}
    for coord in uncheckedCoords:
        x, y = coord
        distance = (x - curX)**2 + (y - curY)**2
        heapq.heappush(closestCoords, (distance, coord))

    kClosestCoords = [coord for dist, coord in heapq.nsmallest(k, closestCoords)]
    return kClosestCoords

def getClosestFreeCoord(curCoord, allCoords, checkedCoords):
    kClosestCoords = getKClosestCoords(curCoord, allCoords, checkedCoords, k=10)
    closestDistance = float('inf')
    closestCoord = None
    for coord in kClosestCoords:
        if coord in checkedCoords:
            continue
        distance = (coord[0] - curCoord[0])**2 + (coord[1] - curCoord[1])**2
        if distance < closestDistance:
            closestDistance = distance
            closestCoord = coord
    return closestCoord

def etchSketch(allCoords):
    def getPath():
        complete = False
        checkedCoords = set()
        path = deque()
        def check(coord):
            nonlocal complete
            if complete or coord == None:
                return
            checkedCoords.add(coord)
            aroundCoords = [(coord[0]+1, coord[1]), (coord[0]-1, coord[1]), (coord[0], coord[1]+1), (coord[0], coord[1]-1)]
            full = False
            while not full:
                full = True
                for i in range(len(aroundCoords)):
                    if complete or coord == None:
                        return
                    if aroundCoords[i] in allCoords and aroundCoords[i] not in checkedCoords:
                        path.append(coord)
                        check(aroundCoords[i])
                        full = False
                if full:
                    if isFinished(path, allCoords):
                        complete = True
                        return
                    freeCOord = getClosestFreeCoord(coord, allCoords, checkedCoords)
                    if(freeCOord == None):
                        path.append(coord)
                        complete = True
                        return
                    path.extend(astar.astar(coord, freeCOord, allCoords))
                    check(freeCOord)
        check(allCoords[0])
        return path
    return getPath()

white pixels are just painted here in the order of the outputted path from my algorithm. If a pixel is more opaque, it just means the path has back over itself again

I want to preferably get it to have as little backtracks as possible

you can think of it all like one of these games, but there are obstacles and boundaries and it is just one color -

[copper junco]

When you say it back-tracks, are you highlighting only the final route it finds or the full search path? I.e. is the backtracking because it thinks the shortest path is one direction but after a while realises it wasn't and has to backtrack and go the other direction? If you are just highlighting the final route found then look at your heuristic because A* is guaranteed to find the shortest route so it shouldn't backtrack at all. If you are showing the full search progress as it happens then sure, there is always likely to be backtracking unless the route is very simple.

[last halo]

basically, in the priority of right left down up, it starts at the first coord in the allCoords array, and it goes to the next coord, in the priority order, and it will keep going until it reaches a coord where all the surrounding coords have been checked already, so in that case it will find the closest coord that hasn’t been checked and use the a* algorithm to get to there. then it will do the priority move thing until it reaches another dead end

and the resulting path is the entire search path

that’s the best algorithm i have come up with so far, if you have another suggestion on how to make it better feel free to say

[last halo]

is there at least another algorithm that I can use, such as breadth-depth search or MST?

[copper junco]

I was too quick with my reply before, I'm not sure there is a simple solution at all. Your instinct of a genetic algorithm was probably good although even that will take some time to converge I would imagine. The only other thing I can think of is to have it stick to the outside edge (wall-following basically) then as long as the shape is regular in width it should fill in the shape from the outside-in with no overwrites, and if it does overwrite, just a single line to escape a narrow area. That's maybe prioritize left, up, right, down something like that? Then search for the closest open space if none adjacent as you do.