Bloxorz a-Star Search-CodePudding

I am struggling to implement a-Star algorithm on Bloxorz game. Which the goal is reach the end using 1 x 1 x 2 block. I implement the algorithm but it is inconsistent. Sometimes it doesn't give the shortest solution. For example:

maze = ['00011111110000',
        '00011111110000',
        '11110000011100',
        '11100000001100',
        '11100000001100',
        '1S100111111111',
        '11100111111111',
        '000001E1001111',
        '00000111001111']

for this maze my implementation gives this result:

U,L,U,R,R,U,R,R,R,R,R,R,D,R,D,D,D,L,L,L,D,R,D,L,U,R,U,L,D

which has 29 moves. But there is a shorter solution which has 28 moves:

U,L,U,R,R,U,R,R,R,R,R,R,D,R,D,D,D,D,D,R,U,L,L,L,L,L,L,D

Here is my implementation, full code is here, what could i do for it?

class Node:
    def __init__(self,parent:'Node', node_type:str, x1:int, y1:int, x2:int, y2:int, direction:str=''):
        self.parent = parent
        self.node_type = node_type
        self.g = 0
        self.h = 0
        self.f = 0
        self.x1 = x1
        self.y1 = y1
        self.x2 = x2
        self.y2 = y2
        self.visited = False
        self.direction = direction
    def get_positions(self) -> tuple:
        return (self.x1, self.y1, self.x2, self.y2)
    def __eq__(self, other):
        if type(other) is Node:
            return self.x1 == other.x1 and self.y1 == other.y1 and self.x2 == other.x2 and self.y2 == other.y2
        elif type(other) is tuple:
            return self.x1 == other[0] and self.y1 == other[1] and self.x2 == other[2] and self.y2 == other[3]
        else:
            return False
    def __lt__(self, other:'Node'):
        return self.f < other.f

def aStar(start:Node, end:Node, grid:List[List[str]]) -> List[tuple]:
    open_list = []
    closed_list = []
    heapq.heappush(open_list, start)
    while open_list:
        current:Node = heapq.heappop(open_list)
        if current == end:
            return reconstruct_path(current)
        closed_list.append(current)
        for neighbor in get_neighbors(current, grid):
            if neighbor not in closed_list:
                neighbor.g = current.g   1
                neighbor.h = get_heuristic(neighbor, end)
                neighbor.f = neighbor.g   neighbor.h
                if neighbor not in open_list:
                    heapq.heappush(open_list, neighbor)
    return []

def reconstruct_path(current:Node) -> List[tuple]:
    path = []
    while current.parent is not None:
        path.append(current.direction)
        current = current.parent
    return ''.join(path[::-1])

def get_heuristic(current:Node, end:Node) -> int:
    return max(abs(current.x2 - end.x1), abs(current.y2 - end.y1))

CodePudding user response：

Assuming everything else in your implementation is correct, it's just because your heuristic is not admissible.

Consider the maze:

B 1 1 X

You can reach the goal in 2 moves:

1 B B X : move1
1 1 1 B : move2

But your heuristic suggests that it would take at least 3 moves

max(abs(current.x2 - end.x1), abs(current.y2 - end.y1))
= max(abs(0-3), abs(0-0)) = max(3, 0) = 3

The heuristic function can't over-estimate the number of moves it would take to reach the goal for A* to always give optimal paths, because doing so might leave a potential optimal path un-explored upon reaching the goal (the optimal path may have never been expanded because it's cost was over-estimated by h(n)).

You would want a heuristic which takes into account the fact that a given coordinate can change by up to 2 in any given move (when a block goes from standing to lying or vice versa). For this, you could divide the result of your current heuristic function by 2.

def get_heuristic(current:Node, end:Node) -> int:
    return 1/2 * max(abs(current.x2 - end.x1), abs(current.y2 - end.y1))

This gives the length 28 path ULURRURRRRRRDRDDDDDRULLLLLLD.

CodePudding user response：

As inordirection said the problem is about the heuristic function. inordirection's answer not work directly but gave me some idea and i came up with this that works.

return 1/4 * max(max(abs(current.x1 - end.x1), abs(current.y1 - end.y1)), max(abs(current.x2 - end.x2), abs(current.y2 - end.y2)))

Because there might be two points locating the block i should have choose maximum difference of x1 and x2 from end, and y1 and y2 from end than choose maximum of them and multiply by 1/4 because it's chosen from 4 points.