Figure 1. Navigation Mesh and Navigation Graph with a path connecting points A and B.

Navigation Mesh

Agents in game can use a navigation mesh to find the path from location A to location B by an algorithm which we outline in very general terms. First, given the initial agent's location A, the algorithm finds what triangle Ta of the mesh contains A and what triangle Tb contains B (the destination). Then, a shortest path across the mesh can be built. This path is a list L of connected triangles from triangle Ta to triangle Tb. Usually this is done using A* (a-star) algorithm (see [Matthews2002] for an excellent introduction into A*).

Since any paths inside navigation triangles are valid, knowing the list L allows us to connect A to B with a piece-wise linear path. Hence, the calculation of L accomplishes our task, at least in its first rough approximation. Usually further manipulations of the path are desirable as this rough path looks too robotic. This issue is quite obvious from the figure above. While improving aesthetics of the path is a fascinating topic, we will not go any deeper on this.

Navigation meshes can often be naturally derived from collision geometry in an automated or completely automatic manner. It can be updated in run time as well, but this may be challenging due to the performance constraints unless we deal with only small portions of the mesh at a time.

Navigation Graph

Navigation graph approaches the problem of building navigation data from a dual perspective. Yet the techniques involved are often similar in many ways to a mesh-based approach.
Namely, the graph is based on nodes, which are not intended to cover all navigable geometry but rather provide useful markers and serve as waypoints. A set of 2D primitives (circles, quads and the like) can be used to represent nodes in a navigation graph. Any path inside a node is considered valid. Also, a path (usually - a straight line) from any point in the environment to any point inside any node is considered to be valid provided it satisfies some additional constraints. The most common constraint is that the path does not intersect collision geometry. Additionally, we may exclude high drops, too steep slopes, water surfaces, etc.

More often than not, checking against collision and other terrain properties along the path could be expensive. Such checks can be replaced by checking against much simpler representations of un-navigable geometry via blocking primitives. The blocking primitives are by far less-detailed and are often limited to boxes (oriented or axis-aligned) and cylinders. This allows for very efficient testing of ray intersection against blocking primitives. Note that the navigation mesh usually doesn’t require addition of blocking primitives as all information about the navigable area is already included in the navigation mesh.

Below, Figure 2 shows an example of blocking primitives which are semi transparent red axis-aligned boxes with white outlines placed along the walls, trash cans and other obstacles. The navigation graph has yellow-green nodes connected with bright yellow edges. The area shown approximately corresponds to the lower left corner of the test environment on Figure 1. (The door is not unlocked yet so there is no connection to the indoors part of the test environment.)

Figure 2 Blocking Primitives and Navigation Graph (Environment model: courtesy of Inna Cherneykina.)

Given a navigation graph and a set of blocking primitives, we can construct a path using the following algorithm: From starting point A we look for the closest navigation node Na such that the line of view from A to Na is not blocked by any primitive. In a similar manner we find node Nb for destination point B. Then using a-star we find a list of nodes connecting Na to Nb. On the figure below the navigation graph from Figure 1 is shown together with blocking primitives (pale pink boxes).

Figure 3 Navigation Graph and Blocking Primitives

Navigation graphs may offer certain advantages over navigation meshes. To start with, the graph can easily incorporate navigation slots of objects placed into the environment. Say, we need an agent to approach a door and orient itself in a certain way to successfully open it. With navigation graphs the slots indicating desired position near the door can become just another node in the graph, likely with some additional attributes (orientation, and may also contain an indication of what type of animation to use for opening the door, etc.)

Second, since the navigation graph is not tied to the level geometry in the same direct way as navigation mesh, it can offer extra flexibility during level design. The nodes are usually represented as objects in the level design tools. As such they can be easier manipulated than triangles in a navigation mesh where designers should care about preserving topological properties of the mesh. By tweaking graph nodes location the designer can introduce certain subtle (and not so subtle) desirable effects influencing pathing in the environment.

Needless to say, manual generation of a navigation graph and its tweaking can be very time consuming. Another downside is that such handcrafted graphs are difficult to update if the geometry changes during the design process and they require extra care in case of run-time modifications in game.

Summarizing, we may conclude that a navigation mesh is more appropriate when navigation data is generated automatically and a navigation graph may be more preferred when level designers’ input is needed or necessary. This leads to the necessity of simplifying creation and maintenance of the navigation graph when it is subject to manual modification.

Manual creation of navigation graph and its validation

There are several technical considerations to take into account while creating a navigation graph.

Optimal density of the graph

On one hand the graph has to be dense enough in the environment to provide navigable nodes accessible from each valid location. On the other hand an excessively-detailed graph is hard to build manually and may lead to longer a-star calculation times. Also it tends to result in a robotic look of agents: they tend to stick to nodes without taking obvious shortcuts.

Surprisingly a sparse graph may also lead to an increase of run-time calculations or even breaking down of the algorithm if it does not take into consideration the following situation – see Figure 4.

Figure 4 Picking nearest node on the other side of the wall

On Figure 4 the agent is placed at location A. When looking for the nearest node it would pick the one highlighted in red. Obviously it is the wrong node to start a path with. Hence a sanity check for intersection of the ray agent-selected node against blocking primitives would be needed to prevent the agent running into the wall on its way to the highlighted node. But then, if the selected node is rejected, we need to find another one which is nearby yet reachable directly. There may be an expensive calculation involved in this additional search, depending on the complexity of the environment.

Hence an off-line procedure validating the navigation graph may also check for such gaps in the graph rather than rely on run-time code to recover from lack of nodes.

Taking into account finite size of the agents

Next, edges of the navigation graph have to be placed in such a way that following along them would keep agents sufficiently far from any collision geometry. Generally, as soon as an agent reaches node N_i on its path, it can immediately turn towards the next node N_i+1, see Figure 5. On this figure collision with geometry outlined by a blocking primitive may occur along the highlighted path from A to B. On the left side of this Figure some paths between N_i and N_i+1 are ok but many are blocked as shown.

Figure 5 Transition between nodes:
(left) the agent may turn at distance R from the node center;
(right) a wider corridor has to be clear of obstacles.

Thus, it's not only the edges of the graph but a wider area between each of the two connected nodes has to be clear of obstacles. This area is a 2D cylinder with the bases at the nodes and sides defined by external mutual tangents. It is not always easy to satisfy this requirement when creating a navigation graph manually.

A useful technique to keep agents from coming too close to the walls is a method based on Minkowski sums and is widely adopted in robotics [deBerg2010]. The main idea behind this approach can be explained in simplified terms as follows: Suppose that an agent has a bounding sphere of radius R, which we will also call the agent’s radius. Apparently we want to keep an agent away from walls at a distance of at least R. Also suppose that originally blocking primitives were created exactly aligned with the collision geometry. If we "inflate" the primitives by adding R on each side along each dimension, and shrink the navigable area correspondingly by the same amount, we may represent the agent as a point. Conveniently this will keep the agent away from the actual collision geometry during navigation. The procedure of inflating blocking primitives and shrinking navigable areas can be done automatically in the development pipeline (preferably) or in run-time. The figure below illustrates this technique. Lighter-color blocking primitives were obtained from original ones using such inflation.

Figure 6 Inflated Blocking Primitives (light red) overlaid with original
primitives (dark red) and navigation graph

To summarize this section, it is better to avoid completely manual creation of navigation graphs as it is an error-prone and time-consuming process. As an alternative we should look for completely automatic techniques or, sometimes, the combination of manual steps with automated procedures. From this perspective it was worth outlining manual steps of navigational graph creation to flesh out the main constraints.

Connecting nodes via triangulation algorithms

Out of all manual steps, placing nodes without actually connecting them by edges is the easier and faster part of the task. Luckily it is possible to automate connecting existing nodes in an environment that already contains blocking primitives. Delaunay triangulation [deBerg2010] provides one of the possible solutions.

Triangulation of a planar set of points connects them by edges in such a way that no edges intersect each other (planarity of connection graph) and no more edges can be added without breaking this condition (maximal property). Delaunay triangulation offers some additional benefits: it maximizes minimal angle of all the triangles in the triangulation. Thus it tends to produce least amount of “thin” triangles. This property by itself may not seem to be very important but it comes from the fact that Delaunay triangulation is a dual object for Voronoi diagram [deBerg2010].

A Voronoi diagram of a discrete set of N points (nodes) on a plane can be defined as subdivision of the plane into N regions (aka Dirichlet domains) by finding the nearest node for each point on a plane. If a point is on equal distance d from two or more nodes N_i1,…,N_ik, and no other nodes are closer than d then it belongs to the boundary of the corresponding domains.

Figure 7 Voronoi cells and Delaunay Triangulation (no blocked edges
removed) for the graph nodes

Voronoi diagrams appear naturally in tasks like optimal placement of retail stores in a neighborhood to minimize travel distance to them, or placing re-translators for wireless networks. Pretty much any modern book on computational geometry has at least a chapter or two on both Delaunay triangulation and Voronoi diagrams so we will not spend more time on the definitions or examples.

A Voronoi diagram of the navigation nodes shows which node will be picked for each starting point when searching for the first node on the path hence its obvious importance for building navigation graphs and placing nodes. As a side note, consider Voronoi cells overlaid over blocking primitives in the problematic area from Figure 4

Figure 8 Voronoi cells overlaid over blocking primitives.
Blue shaded cell extends beyond blocking primitive and creates problematic
situation shown on Figure 4.

Such overlay of Voronoi cells over blocking primitives can easily reveal too sparse placement of the nodes with respect to the blocking primitives. A formal requirement for correct placement of nodes with respect to the primitives to ensure that all nearest nodes are immediately reachable is the following: If V is Voronoi cell corresponding to a node N, and Bi are blocking primitives, i=1,..,M, and \ is set-theoretical subtraction then we need a set V’ = V \ (union of all Bi) obtained by subtracting from V all of the blocking primitives to be convex and the node N must belong to it.

There are a number of algorithms for building Delaunay triangulation and corresponding Voronoi subdivisions. For practical purposes we can use available implementations like the one coming with the OpenCV library [Bradski2008], [OCV]. Alternatively we can adopt implementations described in text books like [ORourke2000]. While sub-optimal in terms of complexity, these implementations provide sufficient performance for most practical purposes when the number of nodes is not too high. Using hierarchical graphs when possible will make Delaunay triangulation task tractable even for quite big environments.

After Delaunay triangulation is built, the edges of the graph intersecting blocking primitives are removed. Removal of edges intersecting blocking primitives may uncover nodes placed problematically from the point of view of finding the nearest initial node in the graph. Connection between nodes C and D is conspicuously missing from the graph suggesting that Voronoi cells for these nodes may not have enough coverage to include all points like A on Figure 4. There are few more similarly missing edges of the graph and sure enough all of them indicate problems with nodes layout.

Figure 9 Navigation graphs obtained from Delaunay triangulation by
removing edges blocked by primitives. “Missing” edges on the left (like
between nodes C and D) indicate problematic placement of nodes fixed on
the right version of the graph.

It is worth mentioning that hierarchical approach to graph construction and to the search of the nearest node alleviates the problem of picking the wrong initial node based on proximity alone. We will elaborate on this it in the section on hierarchical navigation graphs.

Sometimes it is necessary to include particular edges into the final triangulation. This variation of the Delaunay triangulation problem is called constrained and is considerably more difficult [Seidel1988]. However, for navigation purposes, we may have enough freedom to just add new edges after the initial navigation graph is built.

Navigable areas from collision geometry

It is useful to extract navigable areas from collision geometry as a polygonal mesh regardless of what is the target representation: navigation graph or navigation mesh. Navigation mesh can be directly created from this data but the navigation graph would require several additional steps that we will discuss later.

To create such polygonal representation we may consider rendering collision geometry into a sufficiently high resolution bitmap. It can be achieved by running rendering in the modeling application used as a level design tool or procedurally, directly from the scene data.

In most of the simpler cases the level geometry can be projected onto a plane without overlaps (e.g. a single floor of a building, or an outdoor terrain without caves or overhangs). The entire horizontal collision geometry can be rendered onto a horizontal plane using orthographic projection in one color (say, blue) and the vertical collision elements (walls and obstacles) can be rasterized as 1-pixel wide lines of different color (say, red), so that we can tell obstacles from navigable parts.

Since there are so many variations on the tools and modeling applications used in game development, we will skip discussion of the rendering step. We will assume that we already have a reasonably detailed map of flat pieces of collision geometry. It is also necessary to obtain a coordinate transformation allowing conversion of pixel coordinates into in-game coordinates (say, (x,y) scene coordinates).

Next after rendering, a flood fill algorithm in 2D raster image can be applied. Different variations of flood fill algorithms may work for this purpose. In OpenCV a result similar to flood fill may be achieved via (adaptive) threshold operation. (Look up cvThershold and cvAdaptiveThreshold: the first one will almost surely cover all your needs). We don’t go into details because of highly diverse source of the bitmaps due to the diversity of modeling tools and methods but the idea behind converting the rendered image into binary image of navigable areas is mostly self-evident and technically not too difficult.

As an aside note, we may use the rendered source image to inflate one-pixel width blocking lines by half width of the max dimension of the agent radius. This can be done using OpenCV dilate operation. On the other hand, we can delay this until later steps when we obtain polygonal representation of the navigable area.

Polygonization of a binary image can be handled via contour detection. Here we outline the algorithm using Python (OpenCV now conveniently ships with pre-built Python binding).

• Create binary image of the navigable area (namely, 8bit single channel black and white image) by rendering environment with appropriate settings. We start below with ready image on Figure 10.
   
  
• Run contours extraction. This requires steps:
  

  image = cv.LoadImage(navigableArea)
  storage = cv.CreateMemStorage(0)
  contours = cv.FindContours(image, storage,
               cv.CV_RETR_CCOMP, cv.CV_CHAIN_APPROX_SIMPLE)
  contours = cv.ApproxPoly(contours, storage, cv.CV_POLY_APPROX_DP, 3, 1)

  
  

Figure 10 Extracting contours from binary image. The contours hierarchy
has single contour on the top level and total depth =1 because of single
inner contour (rotated rectangle).

We have several options on how to proceed next with building polygonal mesh from the contours. Ideally we want to obtain triangular mesh, and this is a well known problem of polygon triangulation [dBerg2010], [Orourke2000]. Our situation is a bit more complex as our polygons may have holes. Also one of our objectives is to have triangulation similar to Delaunay triangulation (no excessively skinny triangles). Yet using constrained Delaunay triangulation may be an algorithmic overkill. Though not optimal in terms of performance (complexity is at least that one of Delaunay triangulation), we may consider the following step:

• Run Delaunay triangulation on the vertices of extracted contours. Tessellate Delaunay mesh using contours to include edges and corresponding triangles from the extracted contours (Figure 11).
  

Figure 11 Delaunay mesh with added contours on the left is not flat: points
A and B mark intersecting edges. Adding vertices at the locations A and B
and repeating triangulation flattens the mesh (right).

Finally, we complete procedure with the step:

• Eliminate edges and faces that are not covering navigable terrain (Figure 11 right). The result is shown on the Figure below.
  

Figure 12 Triangulation of navigable area. This mesh may be optionally
optimized or tessellated further.

Concluding our discussion of extraction of the navigable area as a polygonal mesh, we should mention that OpenCV algorithms work particularly well with computer generated images such as those obtained from level design tools. This makes them a robust element of the game pipeline.

As a side note, to compare this “sterile” setup with real world applications of OpenCV check out an article [Botana2010]. It provides an excellent coverage of contours detection and their handling. It is related to real-world images for augmented reality games. Working with images acquired with a camera is much more challenging.

Automatic placement of nodes for navigable areas

So far we completed triangulation of navigable area. Such triangular mesh can be easily converted into navigation mesh by augmenting it with explicit connectivity information if necessary. We could be done at this point if we decide to go with navigation mesh, but we can also use triangulation for building a navigation graph.

“Art gallery” navigation graph

Given some triangulation of the navigable area we can follow a minimalist approach and use the results of the art gallery theorem [deBerg2010], [ORourke200]. It asks for placing minimal number of guards in a polygonal shaped gallery so that all of the walls are seen by a guard. The additional twist here is that we may have holes in our polygonal representation so generally we are not dealing with simple polygons as in the basic art gallery theorem.

The requirement of visibility posed by the art gallery theorem is exactly the one we want to satisfy for nodes on the first step of path finding (find nearest visible). If the nodes of the graph contain all of the guard locations then we have a graph which allows getting to a node from any navigable location. Note that the guards are not required to see each other so we may need to place additional nodes to complete the graph.

The main step in proving of the art gallery theorem is to triangulate the polygon. Triangulation from inflated blocking primitives was completed in the previous section so we will use it to place the nodes corresponding to the guards. The vertices of the triangulation are valid node positions by construction.

We can choose the first vertex arbitrarily or pick one of the highest order to cover maximum number of triangles. Next node can be placed by finding first triangle that is not entirely visible from any of the existing nodes.

Next we need to check for visibility of nodes from each other and use mesh connectivity to place intermediate nodes to ensure that the graph is correctly connected. Below is an example of such graph.

Figure 13 Graph based on Art Gallery Theorem

Despite being very small and yet valid representation of the navigable area, such a graph is not very useful as is. One of the main reasons is lots of backtracking that will occur during navigation with such graph i.e. agents would be often moving towards a node that is not in the intuitively correct direction of the goal. We discuss this issue in more details in the next section.

Dual graph approach

Dual graph of a triangular mesh [deBerg2010] can be another candidate for the navigation graph. It is built by associating a node with each triangle and then connecting nodes corresponding to the adjacent triangles. Geometrically, the nodes are usually placed at some internal point of the triangle, say, at its center of mass. Obviously, in such dual graph at least one of its nodes is "visible" from any point of the navigable area. However such graph may have problems as shown on the next Figure.

Figure 14 Dual graph of triangulation. Red highlights show possible
intersection of edges with blocking primitives.

The problem we encountered on the Figure above results from possible intersection of the edges of dual graph with blocking primitives. This can be relatively easy to detect and correct by connecting two triangles via an additional one of their common vertices. Also we can use inflated by the agent radius primitives to ensure that the edges of the dual graph are sufficiently far from the collision geometry.

Additionally we can also include vertices and edges of the triangulation into the navigation graph. The result of adding edges connecting dual graph vertices with triangulation vertices and edges of the triangulation is shown below.

Figure 15 Extension of dual graph to corresponding navigation graph.

We can improve two aspects of the graph on Figure 15. Namely, both location and radius of nodes of dual graph can be picked more advantageously. Placing dual graph node at the incenter of the triangle (center of inscribed circle) and setting its radius to the radius of inscribed circle will give a better version of the graph (see Figure 16).

Note that overlapping nodes are not presenting a problem as any path inside a node radius is a valid path. Larger radius of the dual graph nodes would allow the agent to switch to the next node when following a path that includes dual graph node. Presence of the nodes corresponding to the vertices of the triangulated navigable area ensures that there will be no shortcuts across blocked areas due to too large dual nodes.

Figure 16 Placement of dual graph vertices at the incenter of triangle.
Radius of dual nodes set to the radius of the inscribed circle.

The graph shown on the Figure 16 may still present challenges in run-time: consider an agent starting path near the left-most bottom node of the graph and going into any other room. It would find the nearest node (left bottom node) and initially move towards it, and only after reaching it within the radius of the node the agent would turn to follow the path. This will present an obviously undesirable backtracking.

There are few approaches to this problem. One is to remove such redundant nodes (as obviously the graph will serve its purpose without corner nodes). But that will only make the problem slightly less obvious as there will be similar arrangements of nearest node and initial position leading to backtracking.

Another possible solution can be implemented in run time. After the path is calculated, we can check if the agent can start the path from Nth > 1 node by skipping the first few nodes. This will make pathfinding somewhat more expensive as we would need to run ray intersection tests against blocking primitives to ensure that shortcut is acceptable. On the other hand we would still need to do some path “beautification” to make it less robotic so this additional check may be not so expensive in comparison to other calculations we would need to perform.

In concluding this section we can tell that there are more ways to improve the graph on Figure 16, e.g. by reducing number of edges (redundant edges may result in slower run time performance of A*), better placement of nodes, etc. However the graph as we built it will perform reasonably well. Also it could be easily modified by level designers manually, if necessary, to meet their specific needs not covered by automatic graph generation.

Hierarchical graphs

Hierarchical navigation graphs come in handy when dealing with large environments with relatively loosely connected regions. In indoors environment, such connection is usually done via portals. Building "super-graph" with nodes corresponding to regions and edges to portals may greatly reduce load on A* when navigating between distant regions of the environment.

Indeed, first we can identify the super-node corresponding to the region where the agent is located and the super-node for the destination region. An A* run on super graph can return either "no path" if the regions are not connected, or a navigable path in super graph. This path consists of a list of regions the agent needs to visit in order to reach its destination. Navigation within each region is handled by a-star on regular graph.

Such optimization can be extremely helpful in particular in the cases when no path exists. Super-graph is much smaller and the absence of the path, if it happened to be the case, is learned at a much lower cost than exhaustive search on the regular navigation graph. This observation may seem not so important at the first glance but in practice most spikes in the navigation performance are usually coming from A* failing to find the path on a large graph.

Similar optimization is possible when we deal with open terrain and the regions are not so loosely connected. Still super graph would correctly reflect connectivity information on larger scale thus we can avoid expensive searches with negative outcome.

Figure 17 First super-level of navigation graph (left) of the graph on the
right.

Super nodes of the next level of the hierarchy of the navigation graph don’t have to be placed at specific locations. But they are in logical correspondence to the regions they represent. The portal nodes (smaller blue nodes) also have to be in one-to-one correspondence of the portal nodes of the base navigation graph. Note that regions on the right are connected with single edge. This simplifies structure of the super-graph. Super graph still has to provide functionality to estimate distances to allow A* heuristics work efficiently.

Partitioning of the level into regions corresponding to the nodes of super graph has additional benefits. One of them is that we can worry less about situations like on Figure 4 when the nearest node is picked across blocked terrain. If the search for nearest node is limited to the current region then such situations will happen much less often and the search itself will speed up.

Apparently two-level hierarchy can be generalized to more levels but this is rarely justified in practice.

It is possible to come up with an automatic procedure to build a super graph from the original navigation graph but it is also often done manually. Hierarchical graphs are natural notion for graph-based navigation and reuse most of the code of the underlying a-star-based framework. Thus adding and supporting super graph can be quite easy and straightforward while performance advantages can be really dramatic. This may be a strong argument in favor of choosing graph-based approach for many types of environments.

Conclusion

In this article we focused on navigation graphs as a still-frequent solution to represent navigation data for games. The discussion covered several topics related to creation of navigation graphs for game environments based on different representation of navigable geometry in the game. Each stage of navigation graph creation contains a number of problems with deep roots in computational geometry. As we showed, insights from image processing can also benefit navigation graph creation.

While presented material is not sufficient to build a complete system, by far, it exposes some of the interesting aspects of the process and provides pointers to further research to those who are not relying on middle-ware for their routing needs.

Some of the approaches discussed here were applied to one of the projects the author worked in the past. Those approaches proved to be practical enough, not just of academic interest. Also the belief is that there are many more interesting topics in the area of navigation graph generation that can benefit game developers who are adventurous enough to go after custom solutions for their navigation needs.

References

[Botana2010] César Botana “Electric Eye: Pattern Recognition in Augmented Reality”, Game Developer Magazine, December 2010, pp.22-25

[Bradski2008] Garry Bradski, Adrian Kaehler “Learning OpenCV: Computer Vision with the OpenCV library” O’Reilly 2008, 555 pages

[deBerg2010] Mark de Berg et al, Computational Geometry: Algorithms and Applications, 3d edition, Springer, 2010, 386 pages.

[Matthews2002] James Matthews "Basic A* Pathfinding Made Simple" AI Game Programming Wisdom, Charles River Media 2002, pp. 105-103

[Snook2000] Greg Snook “Simplified 3D Movement and Pathfinding Using Navigation Meshes” in Game Programming Gems, Charles River Media, editor Mark DeLoura, 2000, pp. 288-304

[Stout2000] Bryan Stout “The Basics of A* for Path Planning” in Game Programming Gems, Charles River Media, editor Mark DeLoura, 2000, pp. 254-263

[OCV] OpenCV, an open source computer vision library available from SourceForge http://sourceforge.n...opencv-win/2.2/

[Orourke2000] J. O'Rourke “Computational Geometry in C“ Cambridge University Press; 2000, 390 pages

[Seidel1988] R. Seidel. “Constrained Delaunay Triangulations and Voronoi Diagrams with Obstacles.“ Technical Report 260, Inst. for Information Processing, Graz, Austria, 1988

• Situation Summary — Influence maps do a great job of summarizing all the little details in the world and making them easy to understand at a glance. Who's in control of what area? Where are the borders between the territories? How much enemy presence is there in each area?
  
• Historical Statistics — Beyond just storing information about the current situation, influence maps can also remember what happened for a certain period of time. Was this area being assaulted? How well did my previous attack go?
  
• Future Predictions — An often ignored aspect of influence maps, they can also help predict the future. Using the map of the terrain, you can figure out where an enemy would go and how his influence would extend in the future.
  

• If your graph has varying connectivity, and not just a 2D grid with all its connections traversable.
  
• If your world has interesting features like choke-points, large open areas, large obstacles.
  

• Spatial Partition — A way to easily and efficiently partition space and store information (i.e. influence) for each partition. This allows the influence map to store information about the past, gathering statistics about what happened.
  
• Connectivity (optional) — An indication of connectivity between these spatial partitions in space. The connections allow the influence mapping algorithm to predict how influence could spread through the level, predicting what could happen in the future.
  

• Entities, both friendly and enemy soldiers, semi-permanent turrets, etc.
  
• Events like grenade explosions, bullet fire, taking damage.
  

void InfluenceMap::propagateInfluence()
{
  for (size_t i = 0; i < m_pAreaGraph->getSize(); ++i)
  {
	float maxInf = 0.0f;
	Connections& connections = m_pAreaGraph->getEdgeIndices(i);
	for (Connections::const_iterator it = connections.begin();
		it != connections.end(); ++it)
	{
	  const AreaConnection& c = m_pAreaGraph->getEdge(*it);
	  float inf = m_Influences[c.neighbor] * expf(-c.dist * m_fDecay);
	  maxInf = std::max(inf, maxInf);
	}

	m_Influences[i] = lerp(m_Influences[i], maxInf, m_fMomentum);
  }
}

• You need double buffering if you want your influences to be calculated correctly. You can do that by setting the new influence values in a local store, then copying it back into the m_Influences array. If you do an extra propagation step each frame, then you can avoid the copy (at the cost of some extra processing).
  
• Without double buffering, the influence may propagate differently depending on the order of your graph nodes and how you process them. This makes the influence on a grid look a bit more irregular, but nothing fatal! If you're looking for some extra performance this may help a bit in practice.
  
• Here the code uses exponential decay for the influence, which has some nice properties. However, it's a bit slower than linear decay for instance, which only requires a division and not an exponential function.
  
• The code above only handles positive influences and their propagation. If you need to handle negative influences also, then you could also accumulate the minimum influence and combine them together.
  

• Influence maps are particularly easy to get up-and-running! It's less than a page of code.
  
• You'll most likely end up with a variety of different influence maps to provide better information to your AI.
  
• Pick your map representations wisely, though a 2D grid and your existing area graph are the safest bets.
  
• Expect a lot of iteration along with the AI decision making as you tweak the parameters of your influence map.
  

The C4 game engine has to be one of the best kept secrets in the independent gaming community. It has been in development by the principal developer, Eric Lengyel, for several years. It supports many advanced features such as real-time dynamic shadows for any number of lights, fully calculated specular or micro-facet reflections on any surface, and comes with a robust editor to import and prepare geometry for the game engine. It also implements a robust portal culling system, including support in the tools for building portaled level geometry.

Once you buy the engine for $200, you get not only free updates for the life of the engine, but also the full source code. This is quite comparable to the offering that Garage Games has for the Torque Game Engine, but the comparison stops there. Where Torque needs long lighting compile phases, C4 just runs once you've saved your level. Where Torque code resembles a tentacle monster, with tendrils reaching from all place to any other place, the C4 code is very modular and easy to find your way around. Where Torque exporters for packages such as 3ds Max are notoriously finicky and crashing, C4 uses COLLADA for importing any geometry from anywhere. And where Garage Games never answers questions, Eric provides top-notch service and bug fixing through the C4 forums. Perhaps the only reason Eric can do that is that C4 doesn't have as big a following, so it might be in my best interest to not turn you on to C4 :-)

C4 does miss some things that are available in some other game engines, though. It is currently mostly an indoors engine (with outdoors being next on the road map). The physics is quite basic -- spheres and rays collided against the ground, with simple euler based physics. And, last, there is no real scripting language in C4. There are triggers, and controllers, and a visual macro package that can run in response to triggers, but any "real" coding has to be done in C++.

Another thing missing in C4 (and missing in TGE, too), is support for navigation and path finding for NPCs. I spent the last few evenings trying to work something out, mainly for the challenge, and the chance to experience C4 in a little more depth. This article presents my findings, which includes source code and some advice about how to use it with the C4 engine.

While the source code included doesn't expose any C4 code (doing so would be against the C4 license agreement), but it will use the general framework of C4 in its Locator markers and Controller node attachments. However, you can use these same techniques implemented in this code, in some game of your own, as long as you have the same features available to you: placing markers in the world, finding these markers, and testing whether you can move through the world along a given direction or not.

Requirements

The requirement for this navigation system is to make it possible to plan a path, for a player character or non-player character, from point A to point B within the game world, without too much burden on the CPU at runtime. While there are some systems that can do this entirely automatically, the system I present here is implemented based on hints given by the level artist. This has two benefits: First, it allows the artist to express things he knows about the navigability of a level, that an automatic algorithm might not. Second, it's a lot simpler to implement!

The implementation will construct a graph of "navpoints," where each navpoint is connected to some other navpoints in a directed graph approach. An edge in this graph from navpoint A to navpoint B means, that if an NPC starts at point A, and aims at point B, and walks forward, he will get to point B (unless some other movable obstacle is in the way).

There is an additional gnarl, in that the NPC will not be right on one of these navpoints when it needs navigation services, and the final destination (say, the player, or some in-game goal) may not be right at a navpoint either. Thus, we need to be able to get to the closest navpoint from where we currently are, and we need to be able to get from the endpoint of the navigation path to the destination location.

So, to put it all in one place:

• The artist or level designer places navpoints in the level editor, to indicate generally navigable areas.
• These navpoints are discovered during level loading, and the connectivity between them is automatically calculated.
• Navpoint system provides a function "find the navpoint closest to point P, from which you can actually get to P."
• Navpoint system provides a function "find the navpoint closest to point Q, such that you can get from Q to that navpoint."
• Navpoint system provides a function "find a path along the navpoint mesh that travels from navpoint A to navpoint B."

Finding the Navpoints

In the C4 editor, you can place "Locator" markers. You do this by opening the Marker page, selecting the Locator tool, and clicking in the world editor. Once a Locator is placed, you can move it around with the node movement tool, and you can do Get Info on the marker to set the Locator Type, a four-letter code that is used in the game to understand what kind of marker it is.

In the system I implemented, the artist will place Locator markers and make them of Locator type "navi". The system will then find connections between markers on level load time. The component that does this connection finding is a Controller. Controllers are one of the main ways of getting custom code into the C4 scene graph. Any node can have zero or one controllers assigned to it, and the controller can expose Settings which are edited on the node in the World Editor.

I wanted to be able to create different kinds of nav meshes, say for wheeled vehicles versus kangaroos, so I decided that each NavmeshController instance will only consider "navi" Locators that are direct children of the controllers node. Thus, the artist will place all the locators, select them all, and Group them together. You will then add the "Navmesh" controller to that Group node, and set pathfinding parameters (such as jump height) on that controller.

Thus, in the NavmeshController::Preprocess() function, which is called when the level first starts up, the Navmesh finds all its children that are Locators of type "navi," and then proceeds to test connectivity between each pair of markers. To prevent this from taking a very long time (N-squared ray casts), the artist can set a maximum distance (radius plus vertical displacement) in the controller settings, and any pair of locators that are further away than this will not be considered as a connected pair. The connected neighbors for each navpoint are then stored in an array. I chose one global array with a separate index table for cacheability, but I think the code would have been cleaner if I just stored one small array for each navpoint. This connectivity array is not stored in the level file; instead it's calculated each time the level starts up. For my small test levels, that operation is so fast you can't measure it; for a really large level, it might make sense to allow saving the calculated connectivity.

Finding Navigability

In my first implementation, I just cast a ray from point A to point B to see whether there was anything in the way. This was great at making NPCs not walk through walls, but they would gladly throw themselves into a lava canyon that was between two separate ledges, as long as the raycast from a navpoint on ledge A to ledge B was unimpeded.

To improve this behavior, I first added the capability for an artist to mark, for a given navpoint, which other navpoints should NOT be considered reachable, even if the raycast says it is. While this allows problem cases to be manually fixed, it turned out to be a cumbersome process, and because of that, very fragile in the face of change to the level geometry.

To even be able to debug these problems, I added a command to the C4 command console which shows and hides navmeshes in the world. To be able to tell different meshes apart (meshes that come from different NavmeshController instances, and thus different groups of "navi" locators), I added a mesh display color property to the controller. I also added some functions to re-build the navigation mesh at runtime, and to list the general status of the navigation mesh system.

Other problems with the generated mesh included very complex interconnectivity, where a navpoint in the corner of a room might be connected to every other navpoint in that room. While technically correct, this creates meshes that look bad (but might play very well). To work around this issue, I added a feature in the calculation where connectivity between two navpoints will not be considered if other connected navpoints are "closer" and in the "same general direction."

At this point, with enough manual tweaking, and setting the global "radius" and "vertical" values according to the level, something playable could be created.

Refining Navigability

Throwing yourself in a lava moat does not count as "intelligent" behavior for an NPC. While working around it with explicit node pair exclusion might work for a tortured artist, it won't work when trying to solve the problem of moving from a random point P to the closest navmesh point. Thus, a better way of finding navigability over some area of level must be found.

I decided to brute-force it. Once I know that there's not a wall between point A and point B, I walk the extent of the ray and sample the height difference along the path. If there is a drop, it doesn't matter, as it's OK to jump off ledges. As long as the drop is not too steep! I added a parameter to the controller for what's considered too steep. Additionally, if a single step up is too steep, the NPC won't be able to climp or jump up, so I added another parameter to the controller for what's considered too steep. Last, I added a third parameter to determine how far to step in each iteration of finding the height profile. This will let artists make navmesh compilation a little faster on levels that don't have complex ramps, moats or other height complexity, while allowing for a very fine-grained navigability determination on harder levels.

The nice part of it is that this function can be used both when calculating navigability during start-up, and when trying to find the closest navmesh point that you can actually get to.

Using the Code

Just add the NavmeshController.cpp and NavmeshController.h files to your "Game" DLL MSVC project and build (this is typically "Game.dll" or "SimpleChar.dll" or "Skeleton.dll" depending on how you started your game).

In your World subclass Render() function, after calling World::Render(), you migth want to call MaybeRenderNavmeshes(). This will draw the navmeshes in wireframe, if the console command to turn them on has been run. ("navmesh show")

If the level designer has built one or more nav meshes, they will be automatically created when the level is loaded. To actually get ahold of one, by name of the group node containing the controller, call GetNavmeshController("name"). If you pass NULL for name, the first navmesh (in scene graph unpacking order) will be returned; this is mostly useful when you have only one navmesh.

To plan a path from point A to point B, call NavmeshPathCreate(begin, end). This will do initial path planning to get to the navmesh, and will then navigate through the mesh to the desired destination. Each step for your navigating character, you'll want to call Move(pos, &dir), passing in your current position, and getting out a desired direction to move in. Once you're done with the navigation (either at the destination, or choosing a different goal), call Dispose() on the returned NavmeshPath.

The NavmeshControllers will be deleted when the level is unloaded, so you do not need to separately manage their lifetime.

Reading the Code

You can download the code in an archive. Some things about the code might be worth mentioning, though.

First, the specific use of templates is a pattern that I use quite often, but might confuse you if you haven't seen it before. When you create a large number of objects of the same general kind, such as settings controls in a GUI, and also wanting to marshal/demarshal data that those same controls act on (or perhaps saving/loading to file, etc), it's nice if you don't have to update a zillion places each time you add a new member variable. To solve that problem, I use a single visitor function, that visits all the member variables, passing in various information about each member as it's being visited. While the file saving code might not care what the title of the member should be when displayed in a GUI, it also doesn't really hurt. Thus, for each operation on the members, a separate actor is created and passed to the visitor function. Most of those actors can actually be re-used between object implementations, so while it's a lot of code to write a single float to a file, or create a single text edit control, it saves a lot of code in the long run. Given that I added different control parameters while moving along with the implementation, I believe this pattern paid for itself during this development effort alone. Any new controller I write for C4 will be a pure time win -- not to mention the bugs I avoid by doing each thing only in one place!

Next, the implementation uses no private or protected members. This is in general a pretty bad idea, if you want to expose the implementation. However, the navmesh implementation is in a .cpp file, so no client of the navmesh can poke at those non-private members, so in this case, it's actually a benefit. Some of you may know of this as "interface programming." Unfortunately, the rest of C4 does not use interfaces; instead it uses concrete classes with sometimes deep inheritance, and heavy use of private members. The draw-back, as I'm sure you know, is that any change to an implementation detail (such as the type of a member variable) will cause a re-compilation of every client of that class, even if the functional interface to the class has not changed.

The A-star function (called NavmeshController::AStarSearchIntoWalkPath) is all one big function, but I believe it's OK to make it one function, as it keeps all the concepts in one place for this algorithm. I will not explain A-star in depth, as there are many tutorials on that on the web, except to say that this implementation shows A-star on a generalized directed graph, rather than just the boring old square tiles most often illustrated. Read the comments for more information!

Finally, the versioning mechanism used in the file I/O is something you might want to pay attention to. It allows you to add new members to an existing data type, and have them persist in newly saved files, while still correctly opening older file versions. In fact, with only a little bit of code change, you could even support writing older versions of files!

The 'navmesh' console command

In the console, once a navmesh is instantiated, you can use the navmesh command to get some useful feedback about the navmeshes and how they do path finding. Here are some example commands.

Final notes

I release the pathfinding code under the MIT license, which basically means that you're free to use it for any purpose, as long as my copyright is retained, and as long as you indemnify and hold harmless me for any damage resulting out of your such use, because I claim no merchantability or fitness for a particular purpose of the code.

I would like to thank Eric Lengyel for writing the C4 engine. I would like to thank the community at the C4 message boards for feedback on the initial implementation and this article. I would like to apologize to my wife, as I've been all grumpy sitting up until the middle of the night writing this code and article. And don't forget to download the code!

Thanks for reading.

• Begin at the starting point A and add it to an "open list" of squares to be considered. The open list is kind of like a shopping list. Right now there is just one item on the list, but we will have more later. It contains squares that might fall along the path you want to take, but maybe not. Basically, this is a list of squares that need to be checked out.
• Look at all the reachable or walkable squares adjacent to the starting point, ignoring squares with walls, water, or other illegal terrain. Add them to the open list, too. For each of these squares, save point A as its "parent square". This parent square stuff is important when we want to trace our path. It will be explained more later.
• Drop the starting square A from your open list, and add it to a "closed list" of squares that you don't need to look at again for now.

• G = the movement cost to move from the starting point A to a given square on the grid, following the path generated to get there.
• H = the estimated movement cost to move from that given square on the grid to the final destination, point B. This is often referred to as the heuristic, which can be a bit confusing. The reason why it is called that is because it is a guess. We really don't know the actual distance until we find the path, because all sorts of things can be in the way (walls, water, etc.). You are given one way to calculate H in this tutorial, but there are many others that you can find in other articles on the web.

• Drop it from the open list and add it to the closed list.
• Check all of the adjacent squares. Ignoring those that are on the closed list or unwalkable (terrain with walls, water, or other illegal terrain), add squares to the open list if they are not on the open list already. Make the selected square the "parent" of the new squares.
• If an adjacent square is already on the open list, check to see if this path to that square is a better one. In other words, check to see if the G score for that square is lower if we use the current square to get there. If not, don't do anything.
  On the other hand, if the G cost of the new path is lower, change the parent of the adjacent square to the selected square (in the diagram above, change the direction of the pointer to point at the selected square). Finally, recalculate both the F and G scores of that square. If this seems confusing, you will see it illustrated below.

• Add the starting square (or node) to the open list.
• Repeat the following:
  a) Look for the lowest F cost square on the open list. We refer to this as the current square.
  b) Switch it to the closed list.
  c) For each of the 8 squares adjacent to this current square …
  • If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.
  • If it isn't on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.
  • If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.
  
  d) Stop when you:
  • Add the target square to the closed list, in which case the path has been found (see note below), or
  • Fail to find the target square, and the open list is empty. In this case, there is no path.
• Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.

• Steering Behavior for Autonomous Characters: Craig Reynold's work on steering is a bit different from pathfinding, but it can be integrated with pathfinding to make a more complete movement and collision avoidance system.
• The Long and Short of Steering in Computer Games: An interesting survey of the literature on steering and pathfinding. This is a pdf file.
• Coordinated Unit Movement: First in a two-part series of articles on formation and group-based movement by Age of Empires designer Dave Pottinger.
• Implementing Coordinated Movement: Second in Dave Pottinger's two-part series.

• Consider a smaller map or fewer units.
• Never do path finding for more than a few units at a time. Instead put them in a queue and spread them out over several game cycles. If your game is running at, say, 40 cycles per second, no one will ever notice. But they will notice if the game seems to slow down every once in a while when a bunch of units are all calculating paths at the same time.
• Consider using larger squares (or whatever shape you are using) for your map. This reduces the total number of nodes searched to find the path. If you are ambitious, you can devise two or more pathfinding systems that are used in different situations, depending upon the length of the path. This is what the professionals do, using large areas for long paths, and then switching to finer searches using smaller squares/areas when you get close to the target. If you are interested in this concept, check out my article Two-Tiered A* Pathfinding.
• For longer paths, consider devising precalculated paths that are hardwired into the game.
• Consider pre-processing your map to figure out what areas are inaccessible from the rest of the map. I call these areas "islands." In reality, they can be islands or any other area that is otherwise walled off and inaccessible. One of the downsides of A* is that if you tell it to look for paths to such areas, it will search the whole map, stopping only when every accessible square/node has been processed through the open and closed lists. That can waste a lot of CPU time. It can be prevented by predetermining which areas are inaccessible (via a flood-fill or similar routine), recording that information in an array of some kind, and then checking it before beginning a path search.
• In a crowded, maze-like environment, consider tagging nodes that don't lead anywhere as dead ends. Such areas can be manually pre-designated in your map editor or, if you are ambitious, you could develop an algorithm to identify such areas automatically. Any collection of nodes in a given dead end area could be given a unique identifying number. Then you could safely ignore all dead ends when pathfinding, pausing only to consider nodes in a dead end area if the starting location or destination happen to be in the particular dead end area in question.

• Sample Code: A* Pathfinder (2D) Version 1.9

• Amit's A* Pages: This is a very widely referenced page by Amit Patel, but it can be a bit confusing if you haven't read this article first. Well worth checking out. See especially Amit's own thoughts on the topic.
• Smart Moves: Intelligent Path Finding: This article by Bryan Stout at Gamasutra.com requires registration to read. The registration is free and well worth it just to reach this article, much less the other resources that are available there. The program written in Delphi by Bryan helped me learn A*, and it is the inspiration behind my A* program. It also describes some alternatives to A*.
• Terrain Analysis: This is an advanced, but interesting, article by Dave Pottinger, a professional at Ensemble Studios. This guy coordinated the development of Age of Empires and Age of Kings. Don't expect to understand everything here, but it is an interesting article that might give you some ideas of your own. It includes some discussion of mip-mapping, influence mapping, and some other advanced AI/pathfinding concepts.

• aiGuru: Pathfinding
• Game AI Resource: Pathfinding
• GameDev.net: Pathfinding

• Minimise memory usage, mainly through minimising duplication of information.
• Process nodes 'on-demand,' rather than forcing the whole network to be processed frequently.
• Keep good connectivity in your game worlds to make the networks efficient.
• Don't be afraid to use the network for more than just pathfinding.

MB = Sum( Np * Vp )

• Doubled or tripled pawns. Two or more pawns of the same color on the same file are usually bad, because they hinder each others movement.
• Pawn rams. Two opposing pawns "butting heads" and blocking each others forward movement constitute an annoying obstacle.
• Passed pawns. Pawns which have advanced so far that they can no longer be attacked or rammed by enemy pawns are very strong, because they threaten to reach the back rank and achieve promotion.
• Isolated pawns. A pawn which has no friendly pawns on either side is vulnerable to attack and should seek protection.
• Eight pawns. Having too many pawns on the board restricts mobility; opening at least one file for rook movement is a good idea.

• It is very difficult to refine an evaluation function enough to gain as much performance as you would from an extra ply of search. When in doubt, keep the evaluator simple and leave as much processing power as possible to alphabeta.
• Unless you are after the World Championship, your evaluator does not need to be all-powerful!
• If your game plays really fast, you may want to try evolving an appropriate evaluator using a genetic algorithm. For chess, though, this would likely require thousands of years!

• Along a certain line of play, you discover a position where one of the players is checkmated or stalemated at depth 3. Obviously, you don't want to keep searching, because the final state of the game has been resolved. Not only would searching to depth 5 be a colossal waste of effort, it may also allow the machine to finagle its way into an illegal solution!
• Now, suppose that, at depth 5, you capture a pawn. The program would be likely to score this position in a favorable light, and your program might decide that the continuation leading to it is a useful one. However, if you had looked one ply further, you might have discovered that capturing the pawn left your queen undefended. Oops.
• Finally, suppose that your queen is trapped. No matter what you do, she will be captured by the opponent at ply 4, except for one specific case where her death will happen at ply 6. If you search to depth 5, the continuations where the queen is captured at ply 4 will be examined accurately, and scored as likely disasters. However, the unique line of play where the queen is only captured at ply 6 (outside of the search tree) doesn't reveal the capture to the machine, which thinks that the queen is safe and gives it a much better score! Now, if all you have to do to push the queen capture outside of the search tree is delay the opponent with a diversion, doing so may be worth the risk: although it could damage your position, it might also cause the opponent to make a mistake and allow the queen to escape. But what if you can only delay the queen capture by sacrificing a rook? To the machine, losing a rook at ply 4 is less damaging than losing a queen, so it will merrily throw its good piece away and "hide" the too-horrible-to-mention queen capture beyond its search horizon. (During its next turn, of course, the machine will discover that the queen must now be captured at ply 4 in all cases, and that it has wasted a rook for no gain.) Hans Berliner described this "horizon effect" a long time ago, and it is the most effective justification for the "quiescence search" described in the next section.

• Suppose that a position is so overwhelmingly in your favor that, even if you skipped your turn, the opponent couldn't respond with anything that would help. (In program terms, you would get a beta cutoff even without making a move.) Suppose further that this position is scheduled to be searched to depth N. The null move, in effect, takes out an entire ply of the search tree (you are searching only the null move instead of all your legal ones) and if your branching factor is B, searching the null move is equivalent to looking at a single depth N-1 subtree instead of B of them. With B=35 as in the typical chess middlegame, null-move search may only consume 3% of the resources required by a full depth-N examination. If the null move search reveals that you are still too strong even without playing (i.e., it creates a cutoff), you have saved 97% of your effort; if not, you must examine your own legal moves as usual, and have only wasted an extra 3%. On average, the gain is enormous.
• Now, suppose that, during quiescence search, you reach a position where your only legal capture is rook-takes-pawn, which is immediately followed by the opponent's knight-takes-rook. You'd be a lot better off not making the capture, and playing any other non-capture move, right? You can simulate this situation by inserting the null move into the quiescence search: if, in a given position during quiescence search, it is revealed that the null move is better than any capture, you can assume that continuing with captures from this position is a bad idea, and that since the best move is a quiet one, this is a position where the evaluation function itself should be applied!

• An additional function would be required, as there would need to be one for all cardinal directions in order to account for all possible surrounding dangers. An added downfall of this complexity is that one of the "ifDanger*" functions will be virtually meaningless depending on the direction of snake’s travel, since the snake’s neck segment adjacent to the snake’s head is always an adjacent danger, although not one of any consequence to the snake, since it is unable to move back on itself.
• Anytime an "ifDanger*" function was used, it would need the aid of a helper function, such as the new "ifMoving*" functions in order to make intelligent moves based on an assessment of the danger.

• The snake runs into a section of the game board occupied by a wall
• The snake runs into a section of the game board occupied by a segment of the snake’s body
• The number of moves made by the snake exceeds a set limit. This limit was set to 300, slightly larger than the size of the game board. This will prevent a snake from wandering aimlessly around a small portion of the board.

• While moving upward, if there is not danger two ahead, move forward twice.
• Once there is danger two ahead, turn right; snake now moving right one row from the top of the board.
• Turn right again, to begin heading downward.
• Continue moving downward until there is danger directly ahead.
• Once there is danger ahead, turn left; snake now moving right at the bottom of the board.
• Turn left again and return to step one until there is danger to the right of the snake.
• Danger right indicated the final right-hand column, so the snake now moves up until danger is one ahead.
• Once there is danger ahead, turn left to follow the top row of the board (4,7) while moving left; repeat this same step to move down the left-hand side of the board, and when the bottom of the board is reached, return to step 5.

• Assume that there is a way to evaluate a board position so that we know whether Player 1 (whom we will call Max) is going to win, whether his opponent (Min) will, or whether the position will lead to a draw. This evaluation takes the form of a number: a positive number indicates that Max is leading, a negative number, that Min is ahead, and a zero, that nobody has acquired an advantage.
• Max's job is to make moves which will increase the board's evaluation (i.e., he will try to maximize the evaluation).
• Min's job is to make moves which decrease the board's evaluation (i.e., he will try to minimize it).
• Assume that both players play flawlessly, i.e., that they never make any mistakes and always make the moves that improve their respective positions the most.

• The number of possible moves by each player, called the branching factor and noted B.
• The depth of the look-ahead, noted d, and usually described as "N-ply", where N is an integer number and "ply" means one move by one player. For example, the mini-game described above is searched to a depth of 2-ply, one move per player.

• Apply the evaluation function to the positions resulting from the moves, and sort them. Intuitively, this makes sense, and the better the evaluation function, the more effective this method should be. Unfortunately, it doesn't work well at all for chess, because as we will see next month, many positions just can't be evaluated accurately!
• Try to find a move which results in a position already stored in the transposition table; if its value is good enough to cause a cutoff, no search effort needs to be expended.
• Try certain types of moves first. For example, having your queen captured is rarely a smart idea, so checking for captures first may reveal "bonehead" moves rapidly.
• Extend this idea to any move which has recently caused a cutoff at the same level in the search tree. This "killer heuristic" is based on the fact that many moves are inconsequential: if your queen is en prise, it doesn't matter whether you advance your pawn at H2 by one or two squares; the opponent will still take the queen. Therefore, if the move "bishop takes queen" has caused a cutoff during the examination of move H2-H3, it might also cause one during the examination of H2-H4, and should be tried first.
• Extend the killer heuristic into a history table. If, during the course of the game's recent development, moving a piece from G2 to E4 has proven effective, then it is likely that doing so now would still be useful (even if the old piece was a bishop and has been replaced by a queen), because conditions elsewhere on the board probably haven't changed that much. The history heuristic is laughably simple to implement, needing only a pair of 64x64 arrays of integer counters, and yields very interesting results.

• Selective generation: Examine the board, come up with a small number of "likely" moves and discard everything else.
• Incremental generation: Generate a few moves, hoping that one will prove so good or so bad that search along the current line of play can be terminated before generating the others.
• Complete generation: Generate all moves, hoping that the transposition table (discussed in Part II) will contain relevant information on one of them and that there will be no need to search anything at all.

• Look at all possible moves, and all the possible moves resulting from each, recursively.
• Only examine the "best" moves, as determined from a detailed analysis of a position, and then only the "best" replies to each, recursively.

• Finding all of the legal moves available in a position.
• Ordering them in some way, hopefully speeding up search by picking an advantageous order.
• Searching them all one at a time, until all moves have been examined or a cutoff occurs.

• Search does not require much memory. Programs of the 1970's had to make do with small transposition tables and could ill afford pre-processed move generation data structures, limiting the usefulness of the complete generation scheme described above.
• Move generation is more complicated in chess than in most other games, with castling, en passant pawn captures, and different rules for each piece type to contend with.
• Very often, a refutation (i.e., a move that will cause a cutoff) is a capture. For example, if Player A leaves a queen "en prise", the opponent will quickly grab it and wreck A's game. Since there are usually few possible captures in a position, and since generating captures separately is relatively easy, computing captures is often enough to trigger a cutoff at little expense.
• Captures are usually one of the few (if not the only) type of move examined during quiescence search (which will be discussed in a later article), so generating them separately is doubly useful.

• CHESS 4.5 maintains two sets of 64 bitboards, with one bitboard per square on the board. One contains the squares attacked by the piece, if any, located on that square; the other is the transpose, containing all squares occupied by pieces attacking that square. Therefore, if the program is looking for moves that would capture Black's queen, it looks for its position in the basic bitboard database, uses these new data structures to identify the pieces which attack the queen's position, and only generates moves for these pieces.
• Maintaining these "attack bitboards" after each move requires some rather involved technical wizardry, but a tool called a rotated bitboard can accelerate the work significantly. The best discussion of rotated bitboards I have seen was written by James F. Swafford, and can be found on the web at http://sr5.xoom.com/...prg/rotated.htm

• I intend to use the program as a basis for several other games, most of which have no direct counterparts to chess captures.
• I have plenty of memory to play with.
• The code required to implement this technique is simpler to write and to understand; you will thank me when you see it.
• There are several freeware programs that implement piece-meal move generation; the curious reader should look at Crafty, for example, as well as James Swafford's Galahad.

• The original SARGON extended the 64-byte array by surrounding it with two layers of "bogus squares" containing sentinel values marking the squares as illegal. This trick accelerated move generation: for example, a bishop would generate moves by sliding one square at a time until it reached an illegal square, then stop. No need for complicated a priori computations to make sure that a move would not take a piece out of the memory area associated with the board. The second layer of fake squares is required by knight moves: for example, a knight on a corner square might try to jump out of bounds by two columns, so a single protection layer would be no protection at all!
• MYCHESS reversed the process and represented the board in only 32 bytes, each of which was associated with a single piece (i.e., the white king, the black King's Knight's pawn, etc.) and contained the number of the square where that piece was located, or a sentinel value if the piece had been captured. This technique had a serious drawback: it was impossible to promote a pawn to a piece which had not already been captured. Later versions of the program fixed this problem.

• Find the queen's position, which requires a linear search of the array and may take 64 load-test cycles.
• Examine the squares to which it is able to move, in all eight directions, until you either find the king or run out of possible moves.

• Load the "white queen position" bitboard.
• Use it to index the database of bitboards representing squares attacked by queens.
• Logical-AND that bitboard with the one for "black king position".

• Speed. In situations where there are lots of possible transpositions (i.e., in the endgame, when there are few pieces on the board), the table quickly fills up with useful results and 90% or more of all positions generated will be found in it.
• Free depth. Suppose you need to search a given position to a certain depth; say, four-ply (i.e., two moves for each player) ahead. If the transposition table already contains a six-ply result for this position, not only do you avoid the search, but you get more accurate results than you would have if you had been forced to do the work!
• Versatility. Every chess program has an "opening book" of some sort, i.e., a list of well-known positions and best moves selected from the chess literature and fed to the program to prevent it from making a fool out of itself (and its programmer) at the very beginning of the game. Since the opening book's modus operandi is identical to the transposition table (i.e., look up the position, and spit out the results if there are any), why not initialize the table with the opening book's content at the beginning of the game? This way, if the flow of the game ever leaves the opening book and later translates back into a position that was in it, there is a chance that the transposition table will still contain the appropriate information and be able to use it.

• Pawn structure. Indexed only on the positions of pawns, this table requires little storage, and since there are comparatively few possible pawn moves, it changes so rarely that 99% of positions result in hash table hits.
• Material balance, i.e., the relative strength of the forces on the board, which only changes after a capture or a pawn promotion.

• Generate 12x64 N-bit random numbers (where the transposition table has 2^N entries) and store them in a table. Each random number is associated with a given piece on a given square (i.e., black rook on H4, etc.) An empty square is represented by a null word.
• Start with a null hash key.
• Scan the board; when you encounter a piece, XOR its random number to the current hash key. Repeat until the entire board has been examined.

• For move generation purposes, piece color is irrelevant except for pawns which move in opposite directions.
• There are 64 x 5 = 320 combinations of major piece and square from which to move, 48 squares on which a black pawn can be located (they can never retreat to the back rank, and they get promoted as soon as they reach the eight rank), and 48 where a white pawn can be located.
• Let us define a "ray" of moves as a sequence of moves by a piece, from a certain square, in the same direction. For example, all queen moves towards the "north" of the board from square H3 make up a ray.
• For each piece on each square, there are a certain number of rays along which movement might be possible. For example, a king in the middle of the board may be able to move in 8 different directions, while a bishop trapped in a corner only has one ray of escape possible.
• Prior to the game, compute a database of all rays for all pieces on all squares, assuming an empty board (i.e., movement is limited only by the edges and not by other pieces).
• When you generate moves for a piece on a square, scan each of its rays until you either reach the end of the ray or hit a piece. If it is an enemy piece, this last move is a capture. If it is a friendly piece, this last move is impossible.

• Some way to represent a chess board in memory, so that it knows what the state of the game is.
• Rules to determine how to generate legal moves, so that it can play without cheating (and verify that its human opponent is not trying to pull a fast one on it!)
• A technique to choose the move to make amongst all legal possibilities, so that it can choose a move instead of being forced to pick one at random.
• A way to compare moves and positions, so that it makes intelligent choices.
• Some sort of user interface.

struct GameLevelState {
  int alert;        	// Alert status of enemies //
  struct Positionshot;  // Position of last shot fired //
  int shotTime;     	// Game cycle last shot was fired //
  int hostage;      	// Hostage rescued //
  int explosives;   	// Explosives set or not //
  int tank;         	// Tank destroyed //
  int dialogue;     	// Dialogue variable //
  int complete;     	// Mission completed //
 };

struct Character {
  struct Positionpos;           	// Map position //
  int screenX, screenY;         	// Screen position //
  int animDir, animAction, animNum; // Animation information, action and animation frame number //
  int rank;                     	// Rank //
  int health;                   	// Health //
  int num;                      	// Number of unit //
  int group;                    	// Group number //
  int style;                    	// Style of unit (elf, human) //
  struct AnimationObject animObj;   // Animation object for complex animations //
};

• Units can move in a formation only accessing one master list of movement information. The advantage here is that you do not have to propagate information to every unit in the group when a destination or target changes as they all get their movement information off of the group source.
• Multi-unit coordinated actions, such as surrounding a building, can be controlled at a central location instead of each unit trying to work out where it is in relation to other units and bumping back and forth until they are in the correct position.
• Groups can maintain their structure so that issuing new orders only takes the same amount of time and data as issuing an order to a single unit. Most important you will create something that can be easily understood and read. Changing around 25 units or so and having them try to pass information to each other can be quite a chore if they don’t have any common ground.
• Depending on the formation of the group, obstacle avoidance and detection can be simplified and time to find paths can be reduced, which can be a serious concern when dealing with a large amount of units.

struct GroupUnit {
  int unitNum;              	// Character Number //
  struct Unit *unit;        	// Unit character data //
  struct Positionwaypoint[50];  // Path in waypoints for units //
  int action[50];           	// Actions by waypoints //
  int stepX, stepY;         	// Step for individual units, when in cover mode // 
  int run, walk, sneak, fire, hurt, sprint, crawl;      	// Actions //
  int target;               	// Targets for units //
  struct Position targetPos;	// Target Position //
};

struct Group {
  int numUnits;          	// Units in group //
  struct GroupUnit unit[4];  // Unit info //
  int formation;         	// Formation information for units and group //
  struct Position destPos;   // Destination (for dest. circle) //
  int destPX, destPY;    	// Destination Screen Coords //
  struct Position wayX[50];  // Path in waypoints for group //
  float formStepX, formStepY;  // Formation step values for group movements //
  int formed;            	// If true, then find cover and act as individuals, otherwise move in formation //
  int action, plan;      	// Group action and plans //
  int run, walk, sneak, sprint, crawl, sniper;   // Actions //
  struct Position spotPos;   // Sniper Coords //
  int strategyMode;      	// Group strategy mode //
  int orders[5];         	// Orders for group //
  int goals[5];          	// Goals for group //
  int leader;            	// Leader of the group //
  struct SentryInfo sentry;  // Sentry List //
  struct AIStateaiState; 	// AI State //
};

Figure 1.0 - A Basic Biological Neuron.

• Dendrite(s)........................Responsible for collecting incoming signals.
• Soma................................Responsible for the main processing and summation of signals.
• Axon.................................Responsible for transmitting signals to other dendrites.

Figure 2.0 - A Single Neurode with n Inputs.

Step	Linear	Exponential
Fs(x) =1, if x³q	Fl(x) = x,for all x	Fe(x) =1/(1+e-s x)

Figure 3.0 - A 4 Input, 3 Neurode, SingleLayer Neural Net.


Figure 4.0 - A 2 Layer Neural Network.

Figure 5.0 - The McCulloch-Pitts Neurode.

Figure 6.0 - Basic Logic Functions Implemented with McCulloch-Pitts Nets.

Figure 7.0 - Using the XOR Function to Illustrate Linear Separability.

// MCULLOCCH PITTS SIMULATOR
/////////////////////////////////////////////////////

// INCLUDES
/////////////////////////////////////////////////////

#include <conio.h>
#include <stdlib.h>
#include <malloc.h>
#include <memory.h>
#include <string.h>
#include <stdarg.h>
#include <stdio.h>
#include <math.h>
#include <io.h>
#include <fcntl.h>

// MAIN
/////////////////////////////////////////////////////

void main(void)
{
   float threshold, // this is the theta term used to threshold the summation 
   w1,w2, // these hold the weights
   x1,x2, // inputs to the neurode 
   y_in, // summed input activation
   y_out; // final output of neurode

   printf("\nMcCulloch-Pitts Single Neurode Simulator.\n");
   printf("\nPlease Enter Threshold?");
   scanf("%f",&threshold);

   printf("\nEnter value for weight w1?");
   scanf("%f",&w1);

   printf("\nEnter value for weight w2?");
   scanf("%f",&w2);

   printf("\n\nBegining Simulation:");

   // enter main event loop

   while(1)
   {
  	printf("\n\nSimulation Parms: threshold=%f, W=(%f,%f)\n",threshold,w1,w2);

  	// request inputs from user
  	printf("\nEnter input for X1?");
  	scanf("%f",&x1);

  	printf("\nEnter input for X2?");
  	scanf("%f",&x2);

  	// compute activation
  	y_in = x1*w1 + x2*w2;

  	// input result to activation function (simple binary step)
  	if(y_in >= threshold)
 		y_out = (float)1.0;
  	else
 		y_out = (float)0.0;

  	// print out result
  	printf("\nNeurode Output is %f\n",y_out);

  	// try again
  	printf("\nDo you wish to continue Y or N?");
  	char ans[8];
  	scanf("%s",ans);

  	if(toupper(ans[0])!='Y')
 		break;
   } // end while

   printf("\n\nSimulation Complete.\n");
} // end main

Figure 8.0 - The Basic Neural Net Model Used for Discussion.

Figure 9.0 - Mathematical Decision Boundaries Generated by Weights, Bias, and q

Figure 10.0 - A 4 Node Hopfield Autoassociative Neural Net.