Cruise Missile Navigation AI for World in Conflict blog - blahdy

Cruise missiles are essentially unmanned aircraft (just without recycle feature). For accurate portrayal of such weapon for World in Conflict, we need to make sure they use a set of navigation waypoints, flying low (at height of between 25 to 50 ft) and evading radar detection.

We would prefer that the cruise missiles use fly around the edges of the map, preferring to avoid contact with enemy and maintain the element of surprise for as long as possible -- at the expense of missile taking much longer to arrive on its target.

In order to program such artificial intelligence into the system for navigation, we use Shortest Path First implementation utilizing Dijkstra algorithm. Every waypoint known in game map is a "node", and distance to every node is known and calculated, to dynamically calculate a flight plan based on the least amount of total "link cost" across the entire path. Come to think of it, Dijkstra algorithm is also very popular with internet routers for calculating shortest paths on network's Interior Gateway Protocol (IGP) topology.

def Generate_Waypoints( self ):
	global nodes
	
	"""
		RGM-109E Tactical Tomahawk for WiC MW
		En Route Navigation for TERCOM mid-course guidance
		
		Rather than running straight to the target and have everyone
		and their grandmother shoot at the Tomahawk, we'd prefer the
		missile to fly low and sneak around on the sides of the map,
		using a set of waypoints.  It will take longer to get there,
		but it allows the Tomahawk to minimize radar detection and
		maintain the element of surprise.
		
		Calculate the shortest 2D world waypoints (X, Z) for the
		cruise missile to navigate thru to approach the terminal
		acquisition area (kill box).  Upon arrival, missile will
		need to transition from en-route control (mid-course) to
		terminal guidance, pitching up to about 100wm height and then
		diving onto the target.
		
               1500 +------------------+--------------------+
                    | (*7) Delta     (*6)      Charlie (*5) |
                    | 1490,0,10     November    1490,0,1490 |
                    |              1490,0,750               |
                    |     Grid         |           Grid     |
                    |      D           |            C       |
                    |                  |                    |
            X   750 +-(*8) Whiskey-----+----------Echo (*4)-+   
           axis     | 750,0,10         |         750,0,1490 |
                    |                  |                    |   
                    |     Grid         |           Grid     |
                    |      A           |            B       |
                    |               10,0,750                |
                    | 10,0,10        Sierra       10,0,1490 |
                    | (*1) Alpha      (*2)       Bravo (*3) |
                  0 +------------------+--------------------+
                                      750                  1500
                                     Z axis
		
		Navigation nodes
		alpha: 1     sierra: 2     bravo: 3   echo: 4
		charlie: 5   november: 6   delta: 7   whiskey: 8
		
		Implement ECMP routing for salvo fires against target grids
		having equidistant paths? 
	"""
	
	INAV_MAX_COST = 32768
	
	def SPF(graph, start, end, visited=[], distances={}, predecessors={} ):
		# Dijkstra Shortest Path First (SPF) Algorithm
		# Credit to/courtesy of:  http://rebrained.com/?p=392
		
		# First time init
		if not visited: distances[start]=0
		
		# Terminal node: find path to it and return
		if start==end:
			path=[]
			while end != None:
				path.append(end)
				end=predecessors.get(end,None)
				
			return path[::-1]
		
		# Process adj nodes and keep track of predecessors
		for neighbor in graph[start]:
			if neighbor not in visited:
				neighbordist = distances.get(neighbor,INAV_MAX_COST)
				tentativedist = distances[start] + graph[start][neighbor]
				if tentativedist < neighbordist:
					distances[neighbor] = tentativedist
					predecessors[neighbor]=start
		
		# adj nodes processed, mark current node as visited
		visited.append(start)
		
		# Find the closest unvisited node to the start
		unvisiteds = dict((k, distances.get(k,INAV_MAX_COST)) for k in graph if k not in visited)
		
		# Get the minimum key in dict unvisiteds
		# This method requires python 2.5+... WiC cpython uses 2.4:
		#    closestnode = min(unvisiteds, key=unvisiteds.get)
		#
		closestnode = min([ (unvisiteds[x],x) for x in unvisiteds ])[1]
		
		# Now take the closest node and recurse, making it current
		return SPF(graph,closestnode,end,visited,distances,predecessors)
	
	nodes = {
			1: math.Vector3( 15, 0, 15 ),
			2: math.Vector3( 15, 0, 750 ),
			3: math.Vector3( 15, 0, 1485 ),
			4: math.Vector3( 750, 0, 1485 ),
			5: math.Vector3( 1485, 0, 1485 ),
			6: math.Vector3( 1485, 0, 750 ),
			7: math.Vector3( 1485, 0, 15 ),
			8: math.Vector3( 750, 0, 15 )
			}
	
	# Get the nearest ingress &amp; egress enroute waypoints for missile
	# launch location and desired target coordinates (terminal basket).
	start_max_dist = INAV_MAX_COST
	end_max_dist = INAV_MAX_COST
		
	for i in nodes:
		len_to_start = ( math.Vector3( self.current_state ) - nodes[i]).Length2D()
		len_to_end = ( math.Vector3( self.PN_Terminal_Basket ) - nodes[i]).Length2D()
		
		if len_to_start < start_max_dist:
			start_wp = i
			start_max_dist = len_to_start
			
		if len_to_end < end_max_dist:
			end_wp = i
			end_max_dist = len_to_end
		
	# SPF link path costs; IGP adjacencies
	graph = {
		1: { 2:7, 8:7 },
		2: { 1:7, 3:7 },
		3: { 2:7, 4:7 },
		4: { 3:7, 5:7 },
		5: { 4:7, 6:7 },
		6: { 5:7, 7:7 },
		7: { 6:7, 8:7 },
		8: { 7:7, 1:7 }
	}
	
	self.ENR_waypoints = SPF(graph, start_wp, end_wp)
	return True