PART ONE - TUTORIAL SECTION
Question 1:
a) F=20, G=4, H=16
b) F=20, G=14, H=6
Question 2:
a) The open list contains nodes that are neighbours of processed nodes, but which have not been processed yet. if a node is on the open list, it is still to be processed. When processed, a node’s neighbours are then placed on the open list so that they can also be processed later. This continues until the goal node is found and has been fully processed, or until the open list is empty.
b) The next node to be processed is taken from he open list. This node should have the smallest total cost, and so the open list must be sorted by total cost. The smallest cost node will then be at the front of the open list. A priority queue enables a list to be sorted according to a programmer defined property, in this case by total cost.
c) Each node on the open list is a potential route for A* to take. But A* needs to know how to get from the current node to the neighbour node - so the current node is set as the neighbour node’s parent. Each node has a parent node, and that parent node has a parent node, and so on, leading all the way back to the start node. These parent child relationships are how A* keeps track of the path from the start to a particular node.
d) When deciding which path to take, A* must know the cost of getting from the start node to a particular node. This is the path cost G, so this cost must be stored in every node so that it can be used in the cost calculation.
Question 3:
a)What is the role of A* in this game, and what relationships are there between A* and the game world?
First, when player clicks on a spot, the heuristics are calculated
between the character and the destination. Then when the player moves,
the g value is calculated between the original spot of the character and
the current updated spot of the character. The heuristic cost and g
value is constantly added to become the f value, and if the later f
value is more than the previous f value, the previous f value is taken
as the final f value, as well as its g and h values.
b)What causes A* to execute in this game, i.e. what must happen before the A* algorithm is applied each time? Does this have any implications for the physical design of the game world?
The obstacle nodes must be considered. Yes. If the design is good then the A* will have less problems.
c)A more tricky question. In this game, A* searches through a set of states that represent positions in the game world. How might these states, and transitions between states (steps from one position to another), be modeled?
Question 4:
a) A state description is required to be estimated as there are private methods that cannot be accessed by the agent.
Search nodes help the agent determine the state of the world with extra information state description does not give.
