MazeProblems in this scenario will be constructed from a list of strings a $2$D maze of characters indicating the contents of each cell in the for $($row$\_$num,

maze.

In particular, the following table describes what constitutes a valid $()/()$ properly formatted maze in this modified version of our Pathfinder:

Each MazeState $()/()$ location will include exactly $1$ of the above categories, meaning that the initial state cannot also be a target cannot also be on

a mud tile, etc. and mazes provided as input will be validly formatted so you need not check for validity.

i In addition to the standard movement choices of $["$U$","$D$","$L$","$R$"]$ to navigate to each Target, your agent will have the special action $"$S$"$

to shoot, which has the following effects:

All targets that are in the player's line$-$of$-$sight in each of the four cardinal directions North, South, East, and West are destroyed, regardless of

how far away they are how do you shoot in all $4$ directions at once? Practice..

The catch: walls $"$X$"$ will block your shots, BUT your shots will penetrate targets, hitting any targets that may be behind another in the same

direction.

Shooting has a cost of $2,$ and your agent will remain in$-$place in the maze while shooting.

Important Notes:

In any maze for which there a solution, the agent MUST shoot ALL Targets.

If there are solutions, your procedure should return any one of the cost solutions, and can shoot targets in order

to solve it$.$

If a maze has solution, your procedure should be able to handle this and return None.

CODE TO EDIT:

$\text{'}\text{'}\text{'}$

CMSI $2130-$ Homework $1$

Author:

Modify only this file as part of your submission, as it will contain all of the logic

necessary for implementing the A$*$ pathfinder that solves the target practice problem.

$\text{'}\text{'}\text{'}$

import queue

from maze$\_($p$)$roblem import MazeProblem

from dataclasses import $*$

from typing import $*$

import heapq

from maze$\_($p$)$roblem import MazeProblem

from dataclasses import dataclass

from typing import Optional, List, Tuple, Dict

from typing import List, Tuple

@dataclass

class SearchTreeNode:

player$\_($l$)$oc: Tuple$[$int$,$ int$]$

action: str

parent: Optional$["$SearchTreeNode$"]$

# TODO: Add any other attributes and method overrides as necessary!

cost: int $=0$

def $\_(())\_($s$)$tr$\_(\_())($self$)->$ str:

return f$"$@: $\{$self$.$player$\_($l$)$oc$\},$ cost: $\{$self$.$cost$\}"$

def heuristic$($current: Tuple$[$int$,$ int$],$ goal: Tuple$[$int$,$ int$])->$ int:

return abs$($current$[0]-$ goal$[0])+$ abs$($current$[1]-$ goal$[1])$

def pathfind$($problem: "MazeProblem"$)->$ Optional$[$list$[$str$]]$:

$"""$

The main workhorse method of the package that performs A$*$ graph search to find the optimal

sequence of actions that takes the agent from its initial state and shoots all targets in

the given MazeProblem's maze, or determines that the problem is unsolvable.

Parameters:

problem $($MazeProblem$)$:

The MazeProblem object constructed on the maze that is to be solved or determined

unsolvable by this method.

Returns:

Optional$[$list$[$str$]]$:

A solution to the problem: a sequence of actions leading from the

initial state to the goal $($a maze with all targets destroyed$).$ If no such solution is

possible, returns None.

$"""$

# TODO: Implement A$*$ Graph Search for the Pathfinding Biathlon!

return None

This is my old code that uses breadth$-$first tree search!

Modify only this file as part of your submission, as it will contain all of the logic

necessary for implementing the breadth$-$first tree search that solves the basic maz

pathfinding problem.

$\text{'}\text{'}\text{'}$

from queue import Queue

from maze$\_($p$)$roblem import $*$

from dataclasses import $*$

@dataclass

class SearchTreeNode:

$"""$

SearchTreeNodes contain the following attributes to be used in generation of

the Search tree:

Attributes:

player$\_($l$)$oc $($tuple$[$int$,$ int$])$:

The player's location in this node.

action $($str$)$:

The action taken to reach this node from its parent $($or empty if the root$).$

parent $($Optional$[$SearchTreeNode$])$:

The parent node from which this node was generated $($or None if the root$).$

$"""$

player$\_($l$)$oc: tuple$[$int$,$ int$]$

action: str

parent: Optional$["$SearchTreeNode$"]$

def $\_(())\_($s$)$tr$\_(\_())($self$)->$ str:

return $"$@: $"+$ str$($self$.$player$\_($l$)$oc$)$

frontier: Queue $=$ Queue$($maxsize$=0)$ # initialize queue

initial$\_$state $=$ SearchTreeNode$($problem$.$get$\_$initial$\_$loc$(),"",$ None$)$ # intialize the init state

frontier.put$($initial$\_$state$)$# put init state into queue$/$frontier

while not frontier.empty$()$:

current$\_$node $=$ frontier.get$()$

children $=$ problem.get$\_$transitions$($current$\_$node.player$\_$loc$)$ #get dictionary of all possible moves$/$states

for transition in children:

child $=$ SearchTreeNode$($children$[$transition$],$ transition, current$\_$node$)$ #create child node for possible moves and pass parent

if child.player$\_$loc $==$ problem.get$\_$goal$\_$