Javascript Pathfinding, Steering, and AI (March 1, 2009)

Over the past month, I've found some great sources of information on pathfinding, steering, and AI, and how they relate to each other. It's really helped me to conceptualize their interactions, making it easier to come up with a system that works more the way I wanted it to.

For example, the pathfinding code uses a macro-node search algorithm that can be pro grammatically generated from a grid based terrain map. This reduces the number of nodes that need to be evaluated for each path, and should result in a significantly reduced pathfinding cost, especially for long paths. An example of what the macro-node map might look like can be seen in the figure below. Dark rectangles represent non-traversable areas while the light colored rectangles represent the opposite.

In conjunction with the new macro-node pathfinding, simple steering would be used to generate more realistic movement and interactions between objects. Below is a mock-up of a macro-node map with three separate paths superimposed over the top.

The three paths CA, CB, and DC are each drawn in three different colors, representing the three different stages of pathfinding. Yellow for pathfinding between macro-nodes, blue for biased paths, and green for the actual paths followed when steering is factored in. The biased path (blue) is generated by taking the average of the next two points along the path calculated by the pathfinder (yellow). In the case of path CA, you can see how it generates a much more realistic and efficient path

Status

As far as actual progress of the code I'll need to be able to implement this, it breaks down roughly as follows:

Pathfinding: ~60%
Steering: ~5%
AI: ~0%