please see attached
Question 1: Consider the map below, showing bounding polygons around obstacles. Yellow circles represent the points on the bounding polygons. The agent can navigate in the white spaces. The agent understands that it can move to any point in the space that it can cast a ray that doesn’t intersect with any bounding polygon (or the edge of the map). A path network would help the agent navigate to points in the map for which it cannot cast a ray without intersecting an obstacle. The agent can navigate to the nearest waypoint that it has a clear path to and then navigate between waypoints until it gets close to its desired destination. However, for whatever reason, this map does not have a path network, nor any waypoints. Describe a process whereby an algorithm can automatically identify where to place waypoints. No matter where the agent is in the white space, there should always be at least one waypoint for which the agent can cast a ray without intersecting an obstacle. The algorithm should produce a reasonably small number of way points. The minimum for the example map appears to be 13—the algorithm you describe doesn’t have to produce the absolute minimum number of waypoints, but it should produce less than 30. Part 1. Write your algorithm in pseudocode, explicitly laying out loops and if/else/then conditional statement. Your pseudocode does not need to compile or run, but should provide enough detail for a grader to work through an example map and lay down waypoints. Your pseudocode can assume you are given a list of obstacles, a list of obstacle corners (including map corners), and a list of obstacles edges. You may ignore agent width. You can assume any helper functions in the homework game engine code are available. You can also assume any helper functions exist such as find_nearest_corner(some_point) that would be straightforward to implement. Your algorithm description should not take more than 1/2 page. Part 2. Demonstrate on the example map above by drawing in where your algorithm would put waypoints. Hints: A convex polygon has a useful feature in that one can cast a ray from any point along any edge to any other point along any other edge without leaving the interior of the convex polygon. Convex polygons include squares, rectangles, triangles, though shapes with greater than four edges can also exist and can be irregularly shaped. Any convex polygon with more than three edges can be broken into triangles (also convex polygons). One way to solve the problem is to think about how to break the navigable space into convex polygons and then using these convex polygons to guide the placement of waypoints. You may want to draw any polygons on the map for part 2 to help graders understand your algorithm. How to write good pseudocode: Good pseudocode emphasizes readability over technical accuracy, and should be given in enough detail to work a problem by hand or for someone to have a good idea about how to write actual code. Pseudocode can use English descriptions when necessary or be more like Python. Keep mathematical and code syntax notation to a minimum for readability. For example, the pseudocode for homework 1—creating a path network from a given set waypoints—would look like this: points = a set of given waypoints obstacles = a set of obstacles edges = empty list For all pairs p1 and p2 in points do: If raycast(p1, p2) doesn’t intersect any obstacles AND p1 does not equal p2 then: Create an edge from p1 to p2 and add it to edges return edges In the example I simplified the raycast call and made iterating through obstacles implicit to make the procedure more readable. You can also use implicit iterations—the “For all” line would normally be two nested loops, and the if statement also loops through all obstacles. I also didn’t specify exactly how to construct an “edge” so as to avoid getting into details of how lists and tuples are represented in code. For readability, try to avoid excessive use of code syntax and variables. Your “compiler” is the grader’s human brain, so you can assume some commonsense understanding of your code. I encourage having someone else read your pseudocode and see if they can “execute” it. Your answer here: Given: list of obstacles, list of corner points (including map corners), list of obstacle edges Return: a list of waypoints that are (x, y) coordinates. Question 2: We have discussed in class that behavior trees cannot do anything that cannot be done with finite state machines. Demonstrate it by drawing a finite state machine that is equivalent to the behavior tree below In the behavior tree, actions are green and internal control nodes are blue. Assume all actions take more than one tick to succeed. For example, the “kill” action shoots at the player as long as the player is alive and succeeds once the player is dead. Every tick of the game engine, the tree is traversed and actions either return “fail”, “succeed”, or “in progress”. To create your finite state machine, you will have a “start” state, which is given. You may need to invent new input vocabulary terms such as health_low, player_visible, in_turret, at_base, player_in_range, etc. Indicate any actions performed inside the state by writing the name of the action inside. There should only be one or zero actions inside each state. As with homework 2, the agent keeps track of the current state so it can be checked every tick. Hint: Think about what happens when the daemons in the behavior tree terminate a branch of the tree (e.g., health drops below 25% while patrolling) and how that might be handled in a finite state machine. Don’t forget to consider transitions that need to be in the finite state machine when leaf actions in the behavior tree terminate successfully or unsuccessfully. selector Daemon: if health > 25% then fail sequence Move to base Heal sequence Daemon: if player not visible or health < 25%="" then="" fail="" selector="" daemon:="" if="" turret=""> 50 feet then fail Patrol Move to turret Mount turret Kill sequence Move to player Kill Daemon: if player visible or health <25 % then fail your finite state machine diagram here: the start state is provided. start %="" then="" fail="" your="" finite="" state="" machine="" diagram="" here:="" the="" start="" state="" is="" provided.="">