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.
- Define the main function for the ambush:
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); } } - Declare the function for finding each path:
public List<Vertex> AStarMbush( Vertex src, Vertex dst, Lurker agent, List<Lurker> lurkers, Heuristic h = null) { // next steps } - Declare the necessary members for handling the extra cost of computations:
int graphSize = vertices.Count; float[] extra = new float[graphSize]; float[] costs = new float[graphSize]; int i;
- Initialize the regular cost and the extra cost variables:
for (i = 0; i < graphSize; i++) { extra[i] = 1f; costs[i] = Mathf.Infinity; } - Add extra cost to each vertex that is contained in another agent's path:
foreach (Lurker l in lurkers) { foreach (Vertex v in l.path) { extra[v.id] += 1f; } } - Declare and initialize the variables for computing A*:
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>(); - Start implementing the A* main loop:
frontier.Add(node); while (frontier.Count != 0) { if (frontier.Count == 0) return new List<GameObject>(); // next steps } return new List<Vertex>(); - Validate that the goal has already been reached; otherwise it's not worth computing the costs, and it would be better to continue with the usual A* algorithm:
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; - Traverse the neighbors and check whether they have been visited:
successors = GetEdges(node.vertex); foreach (Edge e in successors) { int eId = e.vertex.id; if (previous[eId] != -1) continue; // next step } - If they haven't been visited, add them to the frontier:
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.