6. Collision Checks
Here we want to encompass all possible collisions that can take place between units and nodes. The image below illustrates an example of what conditions we are required to check to ensure that our project works.
Important conditions to implement are unit collision with nodes, units dealing damage, and unit death that are implemented as events 77 to 81.
7. Find Path
The core functions that are used by Player and AI Controls consists of these two functions that are the “Find_Nodes” and “A_Star” functions. The “Find_Nodes” and “A_Star” functions are based off Dijkstra’s and A* algorthims respectively. Events 118 and 119 are crucial to be executed last as to properly trigger the “Find_Nodes” and “A_Star” functions due the structure of conditions of Player and AI Controls.
7.1 Dijkstra's algorithm or Find_Nodes Function
The “Find_Nodes” function is built on principles of Dijkstra's algorithm that is we start off with all nodes unvisited and cost of travel to them infinite. Proceeding further, we select a starting node and set it to be as a visited node with a cost to travel from start to zero, see events 91 to 93.
Next events 94 and 95 are not part of the algorthim but part of the game functionality where we want to know how far to search from the starting node. Followed after event 96 and its nested events are executed returning the result of which nodes a unit can travel to.
Event 104 based on the obtained results from event 96 highlights which nodes that a unit can travel to along with event 105 indicating which nodes have a target that the unit has a reach.
Inside of event 96, we want pick the node that we are visiting and find its adjacent nodes. We do so for all empty nodes every time picking the node with the smallest travel cost f(n) and setting them to already visited nodes so that we do not revisit the same nodes over again.
The genius part takes places at event 99 where all nodes are scaled up in order to detect node collision with itself in the form of a family object. Moving forward to event 100 for node is overlapping itself and is unvisited for each other node compute the cost of travel from node to other node and execute events 101 and 102.
Starting from event 102, our nodes during the first visit are unvisited we compute the cost of travel and set them to as visiting. On the second visit we pick the visiting nodes compare their cost to the new computed cost and see if we can update the shortest path event 101. We only update the cost of travel if the computed new travel cost from one node to the next node is less than already existing cost of the other node.
Later event 103 reverses the operation performed in event 99 that is scales down all the nodes to their original size.
7.2 A* algorthim
This working A* algorthim is all thanks to this example where you can find an example of the A* at work. The implemented “Find_Nodes” is a similar copy of “A_Star” but modified to perform a different operation, which is to find the travel and fire range. “A_Star” on the other hand is mostly used for AI pathfinding from the start to the goal node.
Starting with event 106, we set all nodes as not being in the closed or open list, resetting cost of travel, and memory of what is the next node to travel to. When the “A_Star” is called on we will receive two input arguments a start node IID and end or goal node IID.
Inside the “A_Star” function we intentionally in event 107 set the start_node to be the end node IID and the end_node to the be start node IID. This is done for the purpose of going from the end node to the start node, finding a path from end to start, so that we can tell our computer what is he next node to travel to from where it is currently located at.
Next event 108 we initialize the our start_node (which is the goal we are trying to reach) to be in the open list with a heuristic function h(n) equal to the Euclidean distance from start to end nodes. Cost of the path from start to current node g(n) is zero and the estimated cost f(n) equals to the summation of g(n) and h(n).
The algorithm execution beings to take place in event 109 where the algorithm will continue to run until the goal node is reached for that the a local variable called done is used to disable the while loop once event 111 has been satisfied. Event 111 will disable the algorithm, event 112 will go from start node to end node picking all nodes and adding their UID’s the text object Turn travel_list.
Event 110 will always pick the node with the smallest f(n) value (minimum path of resistance) remove it from the open list and move it to the closed list. Then event 113 will enlarge the node size to enable node overlap with itself.
From even 114 we pick other nodes that are not yet in the closed list and compute their cost. Event 116 will pick nodes that are not in the open list and moves then into the open list along with updating the cost of travel to the other node. Once in the open list, event 115, check if the current travel cost of other node is less than the computed cost if it is remove it from the open list to later be updated by event 116 its values.
In the end event 117 return, all nodes back to their original state.