After learning how to implement A* for path finding, we will now use its power and flexibility to develop some kind of coordinated behavior in order to ambush the player. This algorithm is especially useful when we want a non-expensive solution for the aforementioned problem, and one that is also easy to implement.
This recipe sets the path for every agent to be taken into account when it comes to ambushing a given vertex or point in the graph.
We need a special component for the agents called Lurker
. This class will hold the paths that are to be used later in the navigation process.
The following is the code for Lurker
:
using UnityEngine; using System.Collections; using System.Collections.Generic; public class Lurker : MonoBehaviour { [HideInInspector] public List<int> pathIds; [HideInInspector] public List<GameObject> pathObjs; void Awake() { if (pathIds == null) pathIds = new List<int>(); if (pathObjs == null) pathObjs = new List<GameObject>(); } }
We will create the main function for setting the ambush path for all the agents and then the function for setting each agent's path.
public void SetPathAmbush(GameObject dstObj, List<Lurker> lurkers) { Vertex dst = GetNearestVertex(dstObj.transform.position); foreach (Lurker l in lurkers) { Vertex src = GetNearestVertex(l.transform.position); l.path = AStarMbush(src, dst, l, lurkers); } }
public List<Vertex> AStarMbush( Vertex src, Vertex dst, Lurker agent, List<Lurker> lurkers, Heuristic h = null) { // next steps }
int graphSize = vertices.Count; float[] extra = new float[graphSize]; float[] costs = new float[graphSize]; int i;
for (i = 0; i < graphSize; i++) { extra[i] = 1f; costs[i] = Mathf.Infinity; }
foreach (Lurker l in lurkers) { foreach (Vertex v in l.path) { extra[v.id] += 1f; } }
Edge[] successors; int[] previous = new int[graphSize]; for (i = 0; i < graphSize; i++) previous[i] = -1; previous[src.id] = src.id; float cost = 0; Edge node = new Edge(src, 0); GPWiki.BinaryHeap<Edge> frontier = new GPWiki.BinaryHeap<Edge>();
frontier.Add(node); while (frontier.Count != 0) { if (frontier.Count == 0) return new List<GameObject>(); // next steps } return new List<Vertex>();
node = frontier.Remove(); if (ReferenceEquals(node.vertex, dst)) return BuildPath(src.id, node.vertex.id, ref previous); int nodeId = node.vertex.id; if (node.cost > costs[nodeId]) continue;
successors = GetEdges(node.vertex); foreach (Edge e in successors) { int eId = e.vertex.id; if (previous[eId] != -1) continue; // next step }
cost = e.cost; cost += costs[dst.id]; cost += h(e.vertex, dst); if (cost < costs[e.vertex.id]) { Edge child; child = new Edge(e.vertex, cost); costs[eId] = cost; previous[eId] = nodeId; frontier.Remove(e); frontier.Add(child); }
The A*mbush algorithm analyses the path of every agent and increases the cost of that node. That way, when an agent computes its path using A*, it is better to choose a different route than the one chosen by other agents, thus, creating the perception of an ambush among the target positions.
There is an easy-to-implement improvement over the algorithm, which leads to the P-A*mbush variation. Simply ordering the lurkers' list from the closest to the farthest might provide a better result at almost no extra cost in computation. This is due to the fact that the ordering operation is handled just once, and could be easily implemented via a priority queue, and then retrieves it as a list to the main A*mbush algorithm with no extra changes.