The Artificial Intelligence Depot has been fortunate enough to catch up with the creator of PathEngine, Thomas Young. He answers Alex Champandard's questions about his background in game AI, the status of development, and his plans for the future.
Alex Champandard: Thomas, could you introduce yourself briefly, and tell us what you do for a living?
Thomas Young: Ok, for a living I guess you can say I'm an AI programmer. That's the job I took when I joined Gremlin Interactive in Sheffield after leaving university to work on computer games. Working on game AI pretty soon got me onto writing pathfinding systems. I found that an understanding of how to move around the environment was central to the behaviours I wanted to code. The problem of capturing this kind of understanding, together with the problem of creating realistic animation, always seemed to me to be two really important problems for game AI, and this has shaped much of my work over the years. I left Gremlin (now Infogrames Sheffield House) in 2000 to work as an independant contractor, and now I've set up a company in France to provide pathfinding systems as middleware license (as well as bespoke systems built with the same code base).
AC: Most of your work within the games industry has been focused on path-finding. All your knowledge and recent efforts are focusing on a new library, PathEngine. How long has it taken to develop so far, and how much time do you devote to this weekly?
TY: I wouldn't say in fact that most of my work has been focused on pathfinding. Certainly for each of the projects I worked on I was the guy responsible for pathfinding. But I've spent a lot of time working on other stuff like AI, animation and collision. Although these other systems are related to pathfinding, it is really more about pathfinding fitting into an overall system as opposed to focusing on pathfinding. But yeah you can say this library is the culmination of knowledge gained over six years or more. The actual code base for PathEngine is built from prototypes and ideas I've been playing around with in the background for a long time but it is only over the last few months that I've had the chance to put these all together. How much time a week? I still spend some time supporting the systems I provided for Outcast 2, but with evenings and weekends taken into account this still leaves a good 40+ hours a week for PathEngine.
AC:With the emergence of complex agents within computer games, some developers and researchers are increasingly finding that the navigation needs to be closely integrated into the agent to provide ideal flexibility and efficiency. How do you justify the need for a standalone path-finding library?
If characters are subject to reasonably complex collision then solving the
problem of moving around arbitrary sets of obstructions also becomes
complex. And it's just not good design to put the responsibility for solving
this kind of problem at the level of specific behaviours. That path very
often leads to
hacks and workarounds in beta to fix problems where specific behaviours fail
to navigate around certain configurations of obstacles. And the problem is
that there's bound to
be another configuration of obstacles waiting to defeat each workaround. For
reliable behaviour you need a generalised solution that works with arbitrary
sets of obstacles.
So I guess I'm saying that some kinds of integration are not a good idea. PathEngine is designed to abstract the geometric aspect of navigation away from the behaviour code. This is done by providing a set of geometric queries about obstructions in an agent's environment and about possibilities for movement around these obstructions.
Above this kind of encapsulation I agree that integration of navigation and behaviour is essential. And in fact the queries provided by PathEngine are designed to enable this by serving as set of building blocks for behaviour. Behaviour code calls these queries as needed to achieve the specific goals of that behaviour. PathEngine provides a system for managing dynamic obstacles with 'collision contexts' and this turns out to be an extremely powerful mechanism for building navigational decision making into the behaviour code.
I think that this kind of approach becomes necessary when characters are subject to reasonably complex collision. By this I really mean anything more complex than tile-based collision. If character movement and collision is all based around a single tile-based representation then you don't need PathEngine.
AC:The success of such a standalone library seems dependant on the simplicity and quality of the interface. How did you go around designing this? How simple would it be to integrate this module into a navigation system, or even better, into a complete agent?
You're absolutely right, the quality of this interface is essential.
The interface for PathEngine is all about exposing the functionality of the
underlying system. Because PathEngine is built around an extremely well defined
collision model this makes the behaviour of the system very well defined and gives
us a very clean interface.
For integration into complete agents I think the main issue is movement under collision. It is usually not too difficult to describe behaviours in terms of the geometric queries that PathEngine provides. The difficult bit is often to ensure that behaviours can actually implement movement along a path given that agent movement is subject to arbitration by the collision system. This is where a well defined collision model for pathfinding comes in very handy.
This collision model gives us two very interesting possibilities.
The first option is really the ideal situation for an AI programmer. This
means that the pathfinder is guaranteed to understand any position that an
agent can get to. It also means an agent is guaranteed to be able to move
along any path returned by the pathfinder.
The downside of this option is that it will most probably mean simplifying
character collision. We can still use a layered collision architecture,
however, to add complex and interesting interactions that are not included
in the pathfinding collision model.
For the second option we can ensure that pathfinding space is a subset of true unobstructed space for the collision model. This means that the agent is guaranteed to be able to move along any path returned by the pathfinder. With this approach it remains possible for the agent to be pushed outside valid space for the pathfinder, but PathEngine provides a 'find closest valid point' query that can be used to resolve this kind of situation.
AC:One of the strong points of the library lies in its ability to interpret arbitrary ground meshes (notably imported from 3DS). Was it difficult to handle such varied layouts? Does the performance of the pre-processing suffer from this flexibility?
Well yes the system handles pretty much arbitrary self overlapping ground
meshes, but these meshes still need to be created to correspond to the level
geometry (which could take the form of completely arbitrary 3d polygonal
data). This ground mesh creation can be done manually by the artists or can
be semi-automated for example by creating modifier stacks of boolean
operations in Max. I will be looking to create tools to better automate the
generation of this mesh in the future. This will probably take the form of CSG
operations to combine a base ground mesh with arbitrary polygonal data. Using a base
ground mesh has some advantages in that it provides a frame of reference as
levels are modified, and in that it gives the developer control over the
resulting collision model for the pathfinder (so it makes it easy to avoid
problems such as characters getting through collision into part of a level
where they should not be).
The core preprocessing operation is to make a minkowski expansion inward from the external edges of the ground mesh. In fact I found that it is surprisingly difficult to perform this operation for the general case of a self overlapping mesh. If you take the same approach as in CSG boolean operations then this will fail in certain situations where the agents shape is big with respect to overlapping features of the geometry. But I am pleased to have found an (I think) elegant solution where the expanded edges are projected through the mesh and at the same time clipped at silhouette corners. Fortunately this method is also pretty efficient so the performance of the preprocessing doesn't suffer.
AC:How well does the algorithm scale up with regards to the size of the levels? Hierarchies seem just as useful in graphics as in AI, does the library support some kind of spatial partitioning?
TY: In previous pathfinding systems I used a number of different partitioning and clusterisation systems, each to implement a different optimisation. This time around the mesh data structure is taking the central role both for localising data lookup for the algorithms used and for optimisations relating to connectivity. There are a number of optimisations specifically targeted at making the algorithm scale well map size. There will be another version of the demo released around the end of March with some benchmark maps included to address these kinds of issues.
AC: Quake3's Area Awareness System (AAS) seems quite similar to your technology, using expanded brushes to determine area connectivity and to find the current location of the bot. How does your system compare? Once computed, can the routing data also be cached to prevent further processing?
Quake3's AAS is an impressive bit of technology. There are some similarities
to PathEngine, but at the core the two systems are very different and are built with very
The Quake3 AAS was built specifically for Quake 3 Arena bot navigation. These bots have got to be able to take full advantage of 3d levels in the same way that human players do. (So they need to be able to jump across gaps, swim underwater and so on.) On the other hand the bots don't need deal with dynamic obstacles in a very sophisticated manner. If one bot is blocked by another (or by the player) there is a single universally applicable (and extremely aggresive) solution.
Both systems are based on making an inward expansion of unobstructed space by the shape of the agent to obtain a pathfinding space. Quake3 AAS does this in 3d to obtain a set of connected spaces. Navigation still takes place essentially on the ground face of those spaces, but the 3d connectivity information is used to compute 'reachabilities' representing the possibility to move between a pair of spaces by jumping or whatever. PathEngine is based on a 3d ground mesh, but the expansion and pathfinding are performed in '2.5d' on the surface of that mesh.
The downside of PathEngine's 2.5d representation is that it does not natively support the same kind of 3D features as the Quake3 AAS. There are some tricks for representing certain kinds of 3d features with PathEngine using the dynamic obstacles mechanism - for example vertical cliffs or crates that can be climbed over - but this doesn't extend to more complex features such as overhanging ledges. Operating in 2.5d enables the PathEngine collision model to be well defined, and makes the dynamic obstacles feature possible.
The quake3 reachabilities are specific to exactly how actions like jumping are actually implemented in the movement and collision code. This makes the navigation system tightly integrated to other systems in the game - if the behaviour of collision or movement code is changed slightly then navigation through reachabilities could be broken. Quake3 AAS doesn't support integrating dynamically placed obstacles into the navigation. This would require performing the 3D CSG operations and then the subsequent reachability generation on the fly.
To summarise, a system like Quake3 AAS provides more 3D features but does not provide dynamic obstacles, and integration with a developers own systems for collision and movement will be more difficult.
Regarding caching routing data, for PathEngine this kind of optimisation is provided in terms of updating a path that has already found with new start and/or end points.
AC: Despite you claiming the demo is not fully optimal, the results are impressive -- barely taking a few milli-seconds for each path computation (if my stopwatch is accurate ;) What aspects of the library will your optimisation work focus on?
That's pretty nifty work with that stopwatch, mate!
But in fact a few milliseconds is really quite a long time for a pathfinding
query, and the environment used for the demo is not very complex.
The demo is not intended to be any kind of indication of performance, but
was released just to provide an example of the collision model implemented
by the pathfinder. As I say, watch out for a version of the demo around the end of March with
better performance and more interesting maps.
Optimisations will really focus on two things - scalability with respect to large maps (as mentioned earlier), and scalability with respect to the number of dynamic obstacles included in a pathfinding query. Of course the raw speed of the system is also important as well as scalability! The system will continue to be optimised as time goes by, with the optimisations guided by a published set of benchmarks.
AC:The range of games that your library is targeting remains quite broad; basically would any environment defined with a polygonal floor mesh seems a reasonable setup? I've also read that this walkable surface can vary and overlap in all dimensions, as long as the agent can move along it freely. Assuming you wanted to handle fully 3D games like Descent, would extending the library be an easy task, and are there any plans to do that?
Yes, I think PathEngine is suitable for any environment where a good percentage of the
environment is static and the agents spend most of their time walking around on the floor of the world.
Although PathEngine doesn't include the same range of 3D reachabilities as a Quake3 AAS, there are
still plenty of possibilities for getting bad guys jumping off ledges and so on.
Navigation for a fully 3d game such as Descent is easier than navigation for games like Quake 3 in one sense. The ships in Descent can move freely through the 3d space so pathfinding queries can again be based around a clear geometric paradigm.
There is a twist for extending points of visibility pathfinding to 3d. The silhouettes of objects become edges as oppoesed to points, so each intermediate step for pathfinding must be represented as a continuous range of potential paths as opposed to a single path. It is an interesting problem, but I don't think there is much of a demand for this. For some reason you don't see many games like Descent. (Although personally I think it was a classic.)
AC:One notable detail on your website is the intention to license the library as middle-ware. Despite everyone claiming that this is the future of game development, I see very little movement towards this. Do you personally believe this too, and are you confident with the prospects of your PathEngine as middle-ware?
TY:Well I know that I have personally worked on a number of games where a
middleware system such as PathEngine should have been used, had it been
available.I have to admit that my early efforts at pathfinding left a lot to be
desired. Pathfinding can seem like a relatively easy task but there are so
many important details. There are a lot of problems can come up in beta if the
whole thing is not thought out very carefully. Also a better pathfinding
system makes it much easier to build interesting and reliable
movement-based AI. The bottom line is that I know a system such as
PathEngine would have saved a lot of time and money for a number of
Perhaps the greatest advantage is for small companies who want to create great games but don't have a lot of money or simply would prefer to stay lean. An interesting possibility is to use pathfinding collision for character movement, and thereby avoid having to develop a collision engine for this task. In this case you can save the money and risk associated with having to develop two major game subsystems.
With larger companies it is all a matter of communication. I know that AI programmers love to write their own pathfinding systems. I need to demonstrate the advantages of a well defined collision model and dynamic obstacles. I think that the possibilities for building more and more sophisticated higher level AI are even more interesting than trying to build something like PathEngine from scratch.
AC:I noticed on your background page that you have a degree in AI from an English university. How useful has that proved itself over the years? With all this commotion about specific Game Programming university courses, which would you favour?
At the time I didn't feel as if I was learning very much, but looking back I
think it was a very useful experience.
I'm glad I chose a degree in AI as it made an interesting slant on the
programming experience I already had.
One important skill that university taught me was how to write essays.
Of course and AI degree gives a very good grounding in AI fundamentals such as A*
which is useful for pathfinding.
I think this turned out to be a big advantage if only because it meant that
I saw the A* algorithm as a starting point rather than an achievement in
I can't comment on game programming university courses as I just don't know enough about them!
AC:You've also been in contact with the industry for an impressive number of years now. From your point of view, how have things changed for AI developers? How do you foresee the future for game AI guru's?
Machines are faster, but I don't think that game AI has changed enough.
Perhaps there are just not enough resources for the average game development
project to do justice to the AI. Middleware is one way that this can change.
I think one way is by formalising an important part of the problem, as in
PathEngine. Another way might be by using engines that integrate collision, animation
and navigation. Then the development team can focus on providing graphical
content, a story, and some specific behaviours.
I think there is a hard target for game AI right now, which is to provide the same kind of movement and behaviour that we see in films, but in an interactive setting. I'd like to hope that this can be achieved in the not too distant future.
AC: Well, many thanks for taking time to answer the questions Thomas! We wish you good luck with PathEngine in the future.
Don't forget to check out the PathEngine website for the latest demo, and much more information about the library, including contact details for those of you that are interested!Footer(); ?>