For the next part in Gamasutra’s ‘Tooling Around’ feature, which profiles and interviews middleware and tools developers about their products, today’s interview is with Thomas Young, founder of PathEngine, and the creator of the PathEngine SDK. The SDK is an advanced agent movement modeling toolkit which allows users to easily integrate pathfinding and collision, though Young is quick to note that it is “more than just a pathfinding system”. PathEngine also allows its features to be “effectively separated off together into a separate software module”, and boasts a focus on ease of use and minimal support issues. ”We definitely don't aim to provide a generic solution to the overall problem of higher level game AI,” explains Young. “In my experience, higher level AI code tends to need a much closer level of integration with other parts of the game - such as animation, control mechanisms, and so on - may differ greatly with the exact requirements of each game, and is much harder to specify cleanly and treat in a modular fashion.” “It's actually quite hard to pigeon-hole,” he adds with a laugh, “so we tend to just call it an 'agent movement SDK', and leave it at that.” Gamasutra spoke to Young recently and asked about his history in the games industry, the PathEngine SDK, and its uses both now and in the future. When and why was PathEngine formed, and what were the aims and goals of the company at this time? PathEngine was officially formed after I left Infogrames Sheffield - formerly Gremlin Interactive - in 2000, moved to France, and set up independently. To start with this was really just about my services as a contract programmer, with a transition to a 'real' middleware company coming later on. My motivations at that point were a desire to move abroad and see different things, to have more control over my working environment, and so on and so forth. I had already been in charge of pathfinding and AI for a number of titles and had quite a lot of experience with a technique we now call 'points of visibility pathfinding', although in a relatively basic form. My first contract was to provide the pathfinding for Outcast 2, for Appeal, in Belgium. While I loved the original Outcast, the AI was often let down quite badly by problems with the underlying pathfinding, and the guys at Appeal knew that this was a key issue for the sequel. So I significantly reworked the points of visibility techniques I had used previously, adding some key improvements such as support for multiple connected ground layers and more advanced dynamic obstacle functionality. Unfortunately although we were able to achieve some great things for Outcast 2, very sadly this game was not to be. Appeal ran out of funds, failed to secure further investment, and the game was canceled. At this point I was starting to get fairly specialized in points of visibility pathfinding, but I knew this could be taken further. So I decided to switch business models. With another fundamental rework of the basic technique - based on lessons learned with Outcast 2, and notably removing some big constraints on ground mesh input - the PathEngine middleware SDK was born and first offered as a commercial product in early 2002. How did you realize the need for a product like the PathEngine SDK? The need for a rigorous and robust approach to low level agent movement management is something that I experienced directly as part of my own work at Gremlin as an AI programmer. When I started out it was fairly common for AI to be treated as a kind of plug-in to an existing game application, with independent, often arbitrarily chosen data structures for things like path planning, but with agent movement nevertheless then subject to exactly the same game collision systems as player movement. That was how I found myself working initially, but after far too much time working around problems that arise from this kind of approach, having projects in hand, a bit more experience and input into the overall game design, and by leveraging the points of visibility technique, I was able to switch to an alternative architecture. The trick was the use of the same world representation for both initial generation of agent paths and also actual negotiation of agent movement along those paths. Points of visibility pathfinding was absolutely key to making this switch, particularly for the kind of games I was working on at the time, with a camera quite close-in to pathfinding agents and a requirement for a 'cinematic' look and feel. This is because points of visibility pathfinding can support quite a sophisticated movement model, with polygonal boundaries that take agent size into account and a continuous treatment of movement through unobstructed space. But, points of visibility is more complicated than many other approaches to pathfinding, and I could see this complexity increasing, both with the addition of important features and also with the need for additional machinery to make it all fast and robust. On the technical side, I knew that the technique could benefit significantly from a lot more development and the middleware business model was something that made this possible. On the business side I had seen essentially the same basic pathfinding technique applied successfully across a wide variety of different games - with the same common geometric paradigm at the pathfinding level but with the code for behaviors built on top of that varying enormously with the exact requirements of each title. I had also seen how effectively this kind of pathfinding can be organized into an independent module and had seen the benefits of this kind of modularity, even when applied in-house with the rest of the team in the same room as the guy who wrote the pathfinding). What was the development time on the product, and what challenges did you run into in preparing the product for industry use? We can count about six months of product development before the first license sale - in 2002 - but this is not really a very meaningful figure since the SDK has been in continuous development ever since. The API has remained pretty much constant over this time, with very few interface breaking changes, but this is misleading, with some fairly significant changes to what actually goes on under the hood. Some challenges in providing a middleware product successfully (above and beyond the kind of technical challenges I had already encountered previously) include the need for good quality documentation - I guess this is fairly obvious, but was something that took us a while to get right - the need for a generally much higher quality bar, and the importance of effective instrumentation, error checking, and so on. Why has simplicity been such a priority for you in the development of the SDK? Well I think that the search for simplicity is really key to software development in general. As the complexity of the problems and systems we work with increases there's a kind of exponential increase in the amount of work that has to be done. And, unfortunately, as we increase team sizes we see the opposite effect, often with significant reductions in productivity as team size increases. But we're seeing a constant drive for improvements from the consumer, for better games, more interesting and believable behaviors, more content, essentially a drive towards more and more complexity in the corresponding game systems. So it's not usually possible for us to simplify the overall systems a and instead we have to look at reorganizing and moving complexity around - identifying patterns, removing repetition, breaking things into smaller components, and so on. One of the most important ways of reorganizing systems, I believe, is to modularize, and this is essentially what we do very effectively with PathEngine. On your website it notes that the SDK "is designed from the ground up to solve problems that all-too-often only become clear late in the development process". What are these problems, and why you have designed the SDK around fixing them? One of the classic problems is the old 'NPC getting stuck against obstacles' bug. Other variations on this class of problems including pathfinding agents failing to find paths, or moving to places they shouldn't get to. It's actually really, really hard to completely eliminate this class of problems for all the possible situations, environments and configurations of obstacles that can potentially arise. But the trickiest issues tend to be associated with fairly rare situations. So what tends to happen is that everything appears to be working fine until later on in the project. And then perhaps content creators start to get more creative with obstacle placement, or perhaps rendering performance has improved and more detail obstacles can now be placed, or the game goes into beta and finally starts to get some real testing. Unfortunately, although the symptoms can be hard to reproduce, in many cases these kinds of bugs are very often due to really fundamental issues in the way the pathfinding and agent movement is set up, and the kind of code changes required to fix the issues properly are just not possible, or certainly very inadvisable, at that stage of development. I've been in this situation on a number of occasions and the options are then fairly limited. Sometimes it's possible to make hacky workarounds that resolve the problem, but this can then cause bugs in other situations. A second option is to task content creators with working around the issue, but this is obviously less than ideal, and if it occurs more than a couple of times, the effect on content creation can be quite significant, with productivity, creativity and flexibility with respect to requests all effected. A third option is to dumb down the game interactions concerned to work around the problem. Whichever approach is taken, the final total costs of these kinds of issues, in terms of things like reduced productivity, delays to market, and reduced product quality can be potentially very large, and it's really worth taking a bit of time up front to get things right. How has the product developed over the time you've been producing it and how have you acted on feedback to improve the product? I like to think of our approach to product support as combining elements of traditional middleware support models with possibilities for more 'contractor-like' direct support, to really address the requirements of individual licensed titles as effectively as possible. Over the years this approach has had quite a marked effect on the development and evolution of the product. The early development of the product saw some significant improvements to the SDK in collaboration with a company called Mutable Realms, for an MMORPG which had some very demanding pathfinding requirements, at a time when MMOs just didn't do pathfinding - I guess because of the various technical issues involved. Our 2D content processing and mesh federation functionality are two concrete features coming out of this, with the SDK now being used by some very big name MMO clients and applied for pathfinding over some extremely large worlds. Similarly, the requirements and feedback of clients in other game genres have also lead to big improvements in other areas, with the requirements for FPS and strategy games in particular leading to big changes in the way in which we manage dynamic obstacles. Why have you released over 50 iterations of the SDK? I think it's absolutely essential for us to be able to provide our clients with a rapid turn-around for important bug fixes, and the mechanisms that enable us to do this also enable us to make these frequent public releases of the SDK. I'm personally a big fan of agile development processes where this is applicable and I think that, as long as interface breaking changes are kept to bare minimum and effective QA processes are applied, frequent incremental releases are a very good thing. How does the product work on a technical level? The key issue is the world representation and movement model at the core of the SDK. It's just not possible to efficiently search through all the possibilities for movement in a full 3D physics model - we need to simplify the set of movement possibilities considerably in order to make this possible. The movement model chosen for PathEngine is quite a big simplification of full 3D physics - although more sophisticated than the model implied by most other pathfinders in use - but I think it's a very well chosen model which tends to fit very well with the kind of agent movement that we find in the majority of game situations and environments; specifically movement over the top of ground surfaces. Importantly, this movement model is also central in enabling very fast pathfinding. PathEngine's movement model is based on what we call 'ground meshes'. These meshes describe the ground surfaces of the world, and connectivity between those surfaces for agent movement. Obstacles can be placed on these ground surfaces, and a shape assigned to pathfinding agents, and some trickery known as 'minkowski expansion' is then used to turn this all into a set of 2D boundaries over the ground mesh. Working purely with point and line queries against 2D boundaries is what makes everything fast. Note that this approach differs importantly from the 'navigation mesh' techniques which are quite common these days, because obstacles can be placed on top of the mesh and included in the pathfinding, and because multiple agent shapes can be used against a single PathEngine ground mesh. More detail about the fundamental technical approach can be found in this section, in our online documentation. Do you feel your product works best when combined with other middleware? Above all PathEngine is designed to be modular and our aim is to provide an SDK that integrates as effectively as possible with other game components whether these are in-house or middleware. What are some of the more notable examples of the product's use? Granado Espada, an MMORPG by IMC Games, is best known in Asia but is now also starting to make waves here in the West [where it is known as Sword Of The New World]. They recently won 'game of the year' in Korea. In the West, Titan Quest by Ironlore Entertainment is quite a successful PathEngine licensed title. Elsewhere, Alpha Prime, an FPS by Black Element Software, is worth a look, and the Pirates of the Burning Seas MMORPG by Flying Lab Software is currently in open beta and coming up to a final release and also looking pretty good. Who is currently using the PathEngine SDK? In addition to Granado Espada, we've been licensed for a whole lot of Korean MMOs, with some big name Korean companies having licensed the SDK being Nexon, NCSoft, and Webzen, but are also being licensed for a wide variety of other genres in a lot of different territories. And we're now selling quite a lot licenses across the next-gen consoles, with console licensees including Dimps Corporation, in Japan, for Mobile Suit Gundam - Operation: Troy, Avalanche Studios, creators of Just Cause, inXile Entertainment for Hei$t, and The Creative Assembly (creators of the Total War series). For more information about people using the SDK, please refer to this page, on our website. What do you see as the next evolution of the product? We're currently consolidating an important big step in the content-side integration of the SDK, namely the addition of '3D content processing'. This enables the SDK to be applied to a scene without any explicit markup generation. 3D content processing is currently being applied on a number of projects and we're working through various tweaks to ensure this all works as effectively as possible. We're then looking at the possibility to extend the 3D content process to be applied to worlds of unlimited size in the same way as the 2D content process, which is pretty exciting. In terms of the core SDK, there are some more big improvements on the table for our dynamic obstacle mechanisms, in addition to continued work on optimization and memory footprint reduction. And look for other big improvements as we continue to talk to clients and evaluators in detail about what they really need to do to move their games forward, and how we can best address those requirements!