Changes for release 6.01
Fixes a bug with missing synchronisation for iAgent::getPosition().
Calling iAgent::getPosition() while the agent was being moved by another thread was then a race condition, and could result in an invalid position being returned.
Also, since the getConnectedRegionForAgent() methods on iMesh, iCollisionContext and iObstacleSet all call on to iAgent::getPosition() internally, calling these methods for an agent that is being moved by another thread (before this bugfix) could result in an invalid position being passed on to the core getConnectedRegionFor() code, and then a crash or infinite loop.
Fixes an issue with getConnectedRegionForAgent() methods leaking an external API reference to the agent shape.
Fixes an issue with the testbed drawAgentsInObstacleSet() and drawAgentsInContext() methods leaking agent external API references.
API Object lifetime management
PathEngine_ShutDownCP3D() has been removed, in favour of reference counted lifetime for iContentProcessing3D.
API object release() methods have been made const. (So you can now call release() on const pointers to API objects.)
An addExternalRef() method has been added to each non-root API object. You can use this to take multiple external references for API objects, and this can then be used essentially as an alternative to external reference counting with std::shared_ptr (or similar), in situations where multiple references to an API object are desired.
Helper methods cPath::refMesh() and cAgent::refMesh() have been added. There are similar to the existing cPath::getMesh() and cAgent::getMesh() methods, but return a reference instead of a pointer to the mesh, and do not increment the mesh API object reference count.
The testbed has been updated to use reference counting with respect to iMesh objects, properly. So now iTestBed::setMesh() and setMeshAtSlot() both result in reference counts being added to the mesh (as long as the mesh pointer is held), and iTestBed::getMesh() and getMeshAtSlot() each add an external reference count for the iMesh pointer passed out.
You can now change the testbed rendering background colour.
Helper methods have been added for directly translating, and saving and loading the testbed camera position.
Changes for release 6.00
Fixes a bug where the TestBed drawPreprocessedGeometryAtPosition() method was rendering the geometry at negative z positions, on Windows platforms. (Wasn't noticed previously because the examples that used this were all rendering agents on the zero plane.)
Fixes a bug with the TestBed error message box not being displayed correctly on Windows 64 bit native TestBed builds.
Custom integer typedefs (tSigned32, tUnsigned32 etc.) have been replaced by standard integer typedefs (int32_t, uint32_t etc.) throughout. (The custom typedefs are still defined in i_pathengine.h, in case you are using these in client code, but these typedefs should be considered deprecated.)
The lifetime management and ownership model for API obstacles has been reworked based on a reference counted mechanism, with some interface refactoring around methods affected by this change.
Some methods that previously had to return pointers to internal PathEngine data, without reference counting, have been reworked to avoid this (with the introduction of new face vertex mesh and solid object builder interfaces).
Detailed discussion of the API changes for this release can be found here.
CLR and JNI interop
The wrapper code for CLR (.net languages) and JNI (java virtual machine) now cover all methods in the PathEngine API, without exception.
New example project
A new example project has been added, 'LotsOfAgentsAndHardCollision', to show one approach for minimising collision and agent update in this kind of situation.
Maximum side check in shape validation
Shape validation now requires that number of sides is less than 100. (A sanity check, not actually a technical limitation.)
Mesh federation tile origin
Mesh federation tiles now store coordinates for tile origin, which can then be queried with the (newly added) iMesh::getOrigin() method.
Please note, however, that federation tile meshes generated previously to this release will not have these origin coordinates set, and origin coordinates will then default to 0,0.
(If you need correct mesh origin coordinates, regenerate your mesh federation tiles.)
Preexpanded 2D obstacle sets
A custom content path has been added for mesh federation generation in situations with large numbers of obstacles that require unobstructed boundary optimisations.
The basic idea is that chunks of obstacles can be pre-combined, (so including minkowski expansion and a potential boundary optimisation step), and the resulting boundaries then added to multiple mesh federation tiles.
(Get in touch, if you would like more details about this!)
Alternative pathfind preprocess type
Initial support has been added for working with an alternative pathfind preprocess type. (See iMesh/generatePathfindPreprocess6For() . )
(Again, get in touch if you want to know more about this.)
Performance improvements for pathfinding and line collision with dynamic obstacles, and significantly reduced overhead for changes to dynamic obstacle state, on all platforms.
Very significant performance improvements for dynamic queries on Linux.
Changes for release 5.36
Fixes a couple of (rare) pathfind preprocess crash issues.
Significant improvements in BSP 3D content processing memory useage and timings.
Construct mesh around boundaries
Additional mesh building functionality has been added for the case where you have obstructions in some arbitrary boundary representation and want to build a mesh around these boundaries.
(See the API reference for the new iPathEngine::buildMeshAroundObstructionBoundaries() method for more details.)
Mesh code refactoring throughout the BSP 3D content processing pipeline.
Visual Studio 2010 is no longer supported.
Changes for release 5.35
Fixes a bug in translation between tiles for federations constructed from a world mesh (introduced in 5.33).
Fixes a bug where setting the overlay connection cost for off-mesh connections was not actually disabling the connections, just setting connection cost to the maximum possible value (so these connections could then still be traversed in certain situations where no other route is available).
The major interface version number on the iPathEngine and iContentProcessing3D root interfaces have been incremented (so calling code will need to be recompiled when updating to this version).
The tiling model for mesh federations has been changed for this release. iMeshFederation objects will need to be reconstructed from suitable parameters, and federation tile meshes regenerated from source data.
The iMeshFederation method for looking up the tile mesh relevant to a query from query start position has been replaced with queries based on the query range (or centre of query range) and so query dispatch code will need to be updated to calculate this range for each query being dispatched (by calculating minimum and maximum x and y coordinates of pathfinding start and end points, for example). Methods relating to tile 'handled region' have been removed.
Meshes containing burnt-in 2D obstacles (a new feature in this release) are not backward compatible, and cannot be loaded by old versions of the SDK.
The iMesh::getBurntInObstacleVertex() method has been changed to return world coordinates.
The mesh federation tiling model has been optimised for better placement of tiles at world edges, and to significantly reduce total overlap.
Translation to and from source tiles
The mesh federation API has been extended to include support for converting between positions on federation tiles and on the original source tiles.
Support has been added for '2D obstacles', where no root position is required for placement, and then the obstacle is applied on all ground surfaces that overlap the obstacle horizontally.
This can be useful where you know that an obstacle won't overlap multiple ground layers, and you want to avoid the need to resolve a root position, or where you need to 'bridge' obstacle across multiple pieces of ground mesh.
Addition of some helper methods for tile location and range querying in the iSourceTiling interface.
Addition of a helper method for clearing all anchors placed on a mesh.
Unobstructed space boundary rendering support for obstacle set boundaries.
Mesh federations code refactoring.
Changes for release 5.34
The major interface version number has been changed with this release, so calling code will need to be recompiled.
There's some (fairly minor) interface refactoring for this release, and application side code will need to be updated in most cases to compile against the new headers.
Changes are as follows:
- array passing has been made consistent
- array out arguments are now passed through an 'array receiver' mechanism
- 3d points and colliding line data are now passed explicitly, instead of by pointer to buffer
- some floating point versions of point query methods, which were just casting to integer internally, have been removed
- callback parameter types have been made consistent
- iAgent userdata has been changed from void* type to tSigned64
- error handler actions are now named constants instead of class enumeration values
- the upgradeProcessL() helper has been removed from the iProgressCallBack interface
- custom allocators must now supply an expand() method.
There are no semantic changes, and updating existing application code for these changes is pretty straightforward, with a detailed walkthrough of the changes required provided in this page (in the SDK docs).
Prefix added for shared object targets
Shared object targets are now prefixed by 'lib' in the python build scripts. (So when building PathEngine as a shared object, the generated shared object file is now named 'libPathEngine.so' instead of just 'PathEngine.so'.)
Fixes a very rare issue in the BSP 3D processing with maximum slope settings for terrain and non-terrain potentially being inverted for certain faces. (Only occurs in cases where separate maximum slope settings are being applied for terrain and non-terrain, and then only for faces that share exactly the same plane origin and normal.)
Fixes a potential deadlock in certain situations where one thread is advancing an agent along a path while another thread performs collision queries on a context that includes the agent.
Ground height lookup improvements
Ground height lookup accuracy has been improved.
New 3D processing attribute
3D processing source geometry can now be marked with a PE_FaceAttribute_CP3D_ExcludeFromSteepSlopeFilter attribute, to force the geometry to be walkable regardless of slope.
Automatic Query Logging
Automatic query logging is now also supported on Linux, with a query logging version of the PathEngine runtime as a shared object.
Some performance improvements.
Improved memory allocation patterns (with 'expand' support in custom memory hooks).
Changes for release 5.33
Preprocess file compatibility
The pathfind preprocess major version number has been incremented, so any stored pathfind preprocess persistent data will need to be regenerated for this release.
Ground mesh file compatibility
Face attribute default values in ground mesh files have been changed
to make these consistent with default attributes in source content objects
(where all attribute values default to -1).
Ground mesh files are versioned and the loading code is backwardly compatible, i.e. PathEngine reads files generated by previous releases correctly, and this change should be transparent to most users.
Ground mesh files generated from this release also remain compatible with the loading code in previous releases, but it is important to be aware that in this case (generating ground meshes with new code and then loading into previous releases), some surfaceType and userData ground attributes values may then be set incorrectly by that old loading code.
Fixes an issue with bad unobstructed space boundaries being generated (and possible subsequent assert and crash) when boundary modifying options (such as unobstructed space optimisation) are used for base unobstructed space generation and the preprocessed obstacle sets feature is being used.
Fixes a very hard to repeat crash in pathfind preprocess generation (only repeated with certain specific geometry _and_ with unobstructed space optimisation turned on).
Fixes an issue with ground above the max slope constraint not being stripped out correctly in certain specific situations where voxel 3D content processing is being applied and is split across a source tiling.
Fixes an issue with bad boundary generation if the removeSmallUnobstructedRegionsWithRange generation option was specified for a preprocessed obstacle set, with incremental generation. (Incremental generation is now disabled if the removeSmallUnobstructedRegionsWithRange option is specified.)
The PC build is now set to use the SSE2 instruction set, i.e. with the /arch:SSE2 Visual Studio build option. (This has been modified in the the build config for older version of Visual Studio, but it looks like this is actually now the default setting in Visual Studio 2012.)
This release includes memory optimisations which very significantly reduce the total memory cost in most cases:
- 20 to 30% reductions in memory cost for our benchmark meshes
- (increasing to 40% reductions in memory cost for meshes with a lot of ground detail, e.g. when terrain height detail is not being stripped out of the ground mesh)
- around 30% reductions, also, in pathfind preprocess memory cost for our 'thainesford' benchmark
- (increasing to 40% reductions in certain cases where there are a lot of off-mesh connections being placed in the scene)
Content processing improvements
The external edge optimisation code (used by both the 2D and 3D content processing) has been rewritten for this release, with the new version of this code being both more robust (in particular with regards to large error threshold values) and also more effective at optimising consistently in all content situations (e.g. cases with sliver triangles, and 'spinning' geometry).
Changes for release 5.32
The major interface version number on the iPathEngine and iContentProcessing3D root interfaces have been incremented (so calling code will need to be recompiled when updating to this version).
Unobstructed space and pathfind preprocess major version numbers have been incremented, so any unobstructed space or pathfind preprocess persistent data will need to be regenerated for this release.
The external API headers for PathEngine have been moved from 'SDKRoot/interface' to 'SDKRoot/code/externalAPI' (so in cases where these are included directly from the SDK directory include paths or directives will need to be updated).
Due to the path length metric change (see below), there may be issues with paths loaded from path persistence data generated by previous releases, so if path persistence data is being stored across releases (probably not the common case) then this data should be regenerated for this release.
Fixes a problem with paths around soft obstacles not working correctly in quite a lot of situations (specifically, with individual obstacle traverse costs not being taken into account).
Fixes an issue with (fairly hard to repeat) crashes in obstacle set unobstructed space incremental update.
Fixes a (hard to repeat) issue with incorrect path generation around dynamic obstacles (not shortest path), in certain specific situations.
Testbed and example projects ported to x64 and Linux
The testbed and the SDK example projects are now portable, and can be used on Linux and on both x86 and x64 architectures.
Package organisation changes
The organisation of the SDK release packages has changed, notably with the addition of a binary distribution for Windows x64.
Essentially, the key changes are as follows:
- A 'base' SDK package replaces the 'TestBed only' archive from previous releases, other archives then add to this base package
- This base package now includes both Windows-x86 and Windows-x64 binaries
- Binary distributions with the stand alone PathEngine and 3D content processing dlls are then available for both Windows-x86 and Windows-x64, for installation on top of the base package
- Source code distructions are now provided independantly for each supported target platform
Please refer to this page (in the online documentation) for more details.
The 'SDKRoot/bin' directory has been removed, in favour of separate directories with batch files or base scripts to launch the SDK examples on each supported platform.
Memory tracking methods removed from API
The memory tracking methods related methods totalMemoryAllocated(), maximumMemoryAllocated() and resetMaximumMemoryAllocated() have been removed from the API.
The memory allocation customisation mechanism (with SetDefaultAllocator()) should now be used if you need to obtain these kind of memory statistics. (And this will then also give you a lot more flexibility about exactly what statistics are tracked!)
See the MemoryBenchmark example application (which has been updated to use SetDefaultAllocator() in this release), for a working example.
Pathfinding graph optimisations
Algorithmic optimisations in the pathfinding graph core mean:
- very significant improvements in performance for pathfinding around dynamic obstacles in open spaces (where the cost of connection to static graph components can now be completely avoided in many cases),
- very significant improvements in performance for pathfinding queries involving soft obstacles (where these now benefit from the same kind of delayed graph attachment strategy as 'hard obstacles'),
- and significant improvements, in general, for a lot of other situations involving pathfinding queries around dynamic obstacles (due to a more efficient general approach to dynamic obstacle graph attachment).
Other optimisation for this release include:
- significant reductions in run-time memory use, for situations with a lot of dynamic obstacles placed
- reductions in mesh loading times, for certain situations
Path length metric changed
The path length metric has been changed slightly in order to make pathfinding well defined with respect to certain situations where alternative paths exist with approximately equivalent length.
Specifically, the length values calculated for each path segment are now rounded up instead of down after the square root calculation.
(Prior to this change, it was possible for the pathfinding to return a path with length one unit longer than the optimum path, in certain specific situations.)
Because of this change path length values will now be reported as slightly higher, for most paths, with this release.
Visual Studio 2012 project files
This release adds Visual Studio 2012 project configuration, (in parallel with the existing project setup, in Visual Studio 2008 format).
Example project organisation
The example projects have been reorganised, to make them more consistent with internal SDK code, and the source code for these projects has been moved under 'SDKRoot/code'.
Changes for release 5.31
Fixes a bug in iMesh::findClosestUnobstructedPositionEx(), with incorrect results in certain situations where a connectivity constraint is being applied and dynamic obstacles are included in the query.
Fixes a crash in mesh partitioning generation in certain (very rare) situations where geometry is repeated over many overlapping vertical ground layers.
(Encountered in a case with BSP 3D processing, against polygon soup source geometry, with the extrude height value set much too low.)
Fixes a bug with pathfinding passing through dynamic obstacles in certain very rare situations.
Fixes a couple of (very hard to repeat) crash bugs in unobstructed space preprocess generation.
The free() method in the iAllocator interface class (for custom allocators) has been renamed to deallocate().
(This is to avoid problems in cases where clients want to use certain third party memory tracking tools with the PathEngine source code.)
This is not a major interface version change, but the code for custom allocator implementations will need to be updated in order to compile with the header this release.
PathEngine on Android
PathEngine has been ported to Android.
(For more information, or to try out the SDK on an Android platform, please get in touch.)
Unobstructed space optimisation
PathEngine now includes a feature for optimisation of unobstructed space boundaries.
This works by removing detail vertices in the boundaries within a specified horizontal range, and is separate from and complementary to the small convex split 'pathfinding space optimisation' (which works by splitting whole boundary components out from a core pathfinding space representation, and was extended significantly in the previous SDK release).
(See this page, in the online documentation, for more information about this optimisation.)
Incremental obstacle set preprocess update
The unobstructed space update for preprocessed obstacle sets now uses an incremental update mechanism
where only one obstacle has been removed or added since the last update.
(This unobstructed space update was the most costly part of connected regions preprocess update, so it is now much cheaper to do things like tracking connectivity changes for objects like doors.)
Connected region querying through collision contexts
Connected region queries are now also provided through the iCollisionContext interface.
These queries will be either forwarded on to a preprocessed obstacle set, if one has been added to the collision context, or otherwise to base mesh connected region preprocess.
Using findClosestUnobstructedPositionEx() with preprocessed obstacle set connected region preprocess
If a preprocessed obstacle set is included in the collision context passed in to findClosestUnobstructedPositionEx,
and a connectivity constraint is supplied,
then the connected region preprocess from the preprocessed obstacle set will be used for this connectivity constraint
(as opposed to base mesh connected region preprocess).
So findClosestUnobstructedPositionEx() can now be used to find a position with connectivity that takes changing obstacle state into account.
Other performance optimisations
Very significant speedups for find closest unobstructed position queries, in many situations.
Group pathfinding example code
A new group movement example project has been added, demonstrating a approach to group pathfinding based on preventing agent overlap in common situations.
There is also some tidying up, simplification, and UI improvements in the existing 'CollapsibleGroup' formation movement example project.
'ThreadPerMesh' example project added, to show multithreading in a very straightforward threading set up (one thread per iMesh instance).
Changes for release 5.30
The major interface version numbers for iPathEngine and iTestBed have been incremented with this release, so calling applications will need to be recompiled.
Base mesh preprocess generation has been rationalised and refactored, with generateUnobstructedSpaceFor replacing the existing iMesh generateCollisionPreprocessFor method, and with preprocess for connected region queries now also managed separately from unobstructed space or pathfind preprocess. (Further details below.)
iMesh::shapeCanPathfind() now takes a collision context argument (since pathfinding queries can now be performed without base mesh preprocess in some circumstances).
The maximum permitted value for the extrudeHeight 3D content processing parameter has been reduced by one.
Additive blending in the testbed has been changed so that only one transition to additive blending mode is allowed per rendering frame,
with primitives after the transition then all drawn with additive blending.
(Testbed application which use this rendering mode may need to reorganise the order of rendering calls appropriately.)
Preprocess API change details
The preprocess component previous referred to as 'collision preprocess' is now referred to as 'unobstructed space'.
Preprocess management methods (generation, save/load, etc.) have been changed accordingly.
Unobstructed space generation can now either be 'combined' or 'uncombined', with combined unobstructed space required for further preprocess generation.
Most of the preprocess options previously relating to collision preprocess or pathfind preprocess
now relate specifically to unobstructed space generation.
The "resolvePositionNearObstructedEndPoints" is an exception, and is now the only option relating specifically to pathfind preprocess generation.
The "connectOverlappingShapeExpansions" preprocess generation attribute is no longer supported. (A full combined unobstructed space generation operation is now significantly faster than the code that was being used to detect overlapping expansions, in the benchmarked cases.)
The legacy "split_with_circumference_below" preprocess generation attribute spelling is no longer supported (use "splitWithCircumferenceBelow").
Connected regions information is now managed as a separate (and independant) preprocess component
(where previously this could be added on to either collision or pathfind preprocess, depending on the
preprocess generation options used).
Preprocess management methods (e.g. generation, save / load) have been added for this new preprocess component.
Preprocessed obstacle sets work in essentially the same way as before, except that
where connected region preprocess was previously controlled by the options passed in to
preprocessed obstacle set construction, preprocessed obstacle sets now always support connected region queries
(with the preprocess for this generated separately from pathfind preprocess, and on demand).
Preprocessed obstacles sets using the "markedForPreprocessing_ConnectedRegionsOnly" option work are still supported, and work essentially as before.
Preprocess persistence files from previous SDK releases cannot be loaded by this release, and new preprocess files will need to be generated.
Fixes an issue with the find closest unobstructed position query returning incorrect results in certain specific situations involving overlap between base obstacle and mesh external edge expansions.
Fixes some potential issues with correctness of the built-in advance along path functionality, and a related (hard to repeat) assertion about range issues in the debug build.
Fixes a fairly hard to repeat assertion in curved path generation, in certain situations where both start and end vectors are being supplied.
Fixes a bug with the line coordinates in the collision info returned by the first collision query not corresponding to the actual first point of collision, in certain specific query circumstances.
Extended findClosestUnobstructedPosition query version
An extended findClosestUnobstructedPosition query version iMesh/findClosestUnobstructedPositionEx() has been added, together with an extended supporting position resolution method ( iMesh/resolvePositionsNear3DPoint() ).
Together with the supporting position resolution method, this extended query version can:
- Find positions in unobstructed space close to arbitrary 3D points (i.e. without a root ground position being required), with both sides of gaps taken into account correctly
- Support arbitrary query regions (not necessarily centred on the target position)
- Include application of a 'connectivity constraint'
The connectivity constraint can be important in situations where a target position is close to multiple pieces of disconnected unobstructed space, and you want to find a position that is in the same reachable space as another agent.
Memory allocation customisation
Applications can now pass in custom allocator objects for handling internal SDK memory allocations, with all internal memory allocations now being routed through this mechanism.
(So this essentially makes arbitrary memory allocation customisation possible in all situations, including static linkage against the SDK, where previously dynamic linkage was required.)
Extension of the 'small convex split' mechanism (see below) very significantly reduces times for pathfind preprocess, and run-time pathfinding queries, with order of magnitude improvements in certain specific situations.
Significant speedups in find closest unobstructed position queries (over 30% reductions in timings for some benchmarks).
Significant speedups in line collision queries (around 20% reductions in timings for many cases).
Significant speedups in point collision queries.
Pathfinding query speedups.
Very significantly reduction of pathfind preprocess memory footprint from the extended 'small convex split' mechanism in certain specific situations.
Very significant improvements in preprocess memory footprint for preprocess that supports both pathfinding and connected region queries (certain underlying data structures for supporting these two types of queries have now been combined).
The number of blocks allocated has been reduced significantly for situations where large numbers of burnt in shapes are placed, or preprocess generated for large obstacle sets.
Extended small convex split optimisation
The 'small convex split' mechanism for optimising local obstructed regions out of effective pathfinding space, which previously only applied to convex expanded shape regions, has been now been extended to also split off small non-convex regions, on the condition that the region's convex hull is unobstructed by other region boundaries, and does not cross outside the mesh.
The small convex split optimisation is an important optimisation because this enables us to reduce
core pathfinding complexity very significantly in certain situations with high visibility
(and therefore high pathfinding graph connectivity).
The extension to this optimisation in this release then signficantly reduces the constraints for applying this optimisation and enables the optimisation to be applied in many more situations.
The small convex split extension can be turned on with the new 'smallConvex_WrapNonConvex' unobstructed space generation option, and it is also possible to specify a maximum range for split regions using the new 'smallConvexMaxRange' option (in addition to the existing maximum circumference constraint).
(See this page, in the online documentation, for more information about PathEngine's small convex split optimisation.)
Testbed linkage changes and modularisation
The testbed has been reorganised, for this release, to remove direct linkage from the testbed into runtime library internal code.
Testbed rendering is now implemented completely through methods provided through the main PathEngine API.
For this, a bunch of rendering code previously implemented directly in the testbed has now been moved into the main API, and is available to applications for debug rendering and visualisation in other graphical environments.
This also means that the testbed is now much more useful as an example of how to implement debug rendering of PathEngine elements and functionality in third party code.
Other Testbed changes
Some internal caching has been removed from the testbed when rendering agents and agent expansions, which can mean slowdowns in certain situations where large numbers of agents are being drawn.
A more general mechanism for recording and replaying rendering operations has been added, however,
with the possibility to cache arbitrary sequence of direct object rendering calls for subsequent rendering without geometry generation and GPU resource allocation overheads.
This mechanism can then be applied to speed things up again in situations where rendering times are an issue.
The testbed window can now be resized and toggled to and from full screen mode.
Other changes and improvements
There is some fairly significant refactoring of the SDK internal source code for this release, in particular with respect to the relationship between 'unobstructed' and 'pathfind' space, and dependency relationships between different preprocess elements.
It is now possible to use the 'preprocessed obstacle set' mechanism to generate pathfinding preprocess and dispatch pathfinding queries without pathfinding queries being supported in base mesh preprocess (can mean quite a significant memory saving in some situations).
Changes for release 5.29
Line collision tests are no longer supported with the 'allowCollisionQueriesWithoutPreprocess' option, only point collision tests.
Fixes an issue relating specifically to pathfinding requests with multiple start positions and with a restricted horizontal range specified, where incorrect path results could sometimes be returned for certain queries where some of the start positions are already outside of the specified range.
Fixes an issue where connected region queries were returning valid connected region indices
for positions inside shapes factored out as non-overlapping during preprocess generation
(e.g. for pathfind preprocess generation with the small convex obstacles optimisation).
The same value is now returned for these cases as for other obstructed positions.
Fixes a (very hard to repeat) bug in mesh external edge optimisation, where the resulting bad mesh geometry could then cause problems further down the content processing pipeline.
Fixes a (hard to repeat) pathfinding crash bug in certain situations where static off-mesh connections are being chained together (i.e. the target endpoints of connections are reused as source endpoints of other connections), and where there are dynamic soft obstacles placed in the scene.
Temporarily ignoring agents
A feature has been added for temporary removal of agents from collision and pathfinding state without invalidation of cached collision or pathfinding data corresponding to that state, through the following new methods:
The primary use case for this feature is when a small number of agents need to be temporarily removed from an obstacle set or collision context for certain queries, and then restored after the queries have been performed, for example to implement behaviours where the target of the behaviour should not be considered as an obstacle, or to implement certain 'what-if' queries.
In situations where these kinds of behaviours are being implemented in terms of the existing removeAgent() and addAgent() methods, and where there are a significant number of agents included in the collision context that is being modified in this way, simply replacing removeAgent() with temporarilyIgnoreAgent() and addAgent() with restoreTemporarilyIgnoredAgent() can potentially make a very significant difference to performance.
Fast connectivity queries against changing state
Support has been added for performing fast connectivity queries against changing collision state, through the preprocessed obstacle set mechanism.
Essentially, it is now possible to mark an obstacle set for preprocessing (as used for pathfinding against 'semi-dynamic obstacles'), but with only the preprocess components for fast connected region queries being generated.
This is much faster than full pathfind preprocess generation and, (with other optimisations in this release) this obstacle set preprocess update is something that can now be generated in real time (i.e. without the need for a background thread), in many situations.
See this page (in the online documentation) for some more information about this functionality.
Other performance optimisations
Significant speedups for connected region queries, in most cases (a faster query method is now being used, except in cases where extra partitioning has been added to PathEngine's internal 2D mesh).
Significant speedups in the generation of collision preprocess, and collision preprocess with support for connected region queries.
Other changes and improvements
The updateCollisionPreprocessFor() methods on iCollisionContext and iObstacleSet now have no effect,
and these methods are depreciated.
(This is because collision queries can early out in many situations, and avoid the need to regenerate cached data, and so removing these methods can actually sometimes significantly improve performance for very dynamic situations.)
Source code refactoring, dependency reduction and streamlining of PathEngine dll project code set.
Changes for release 5.28
Fixes an issue with ground attributes being passed through incorrectly into the ground result by the voxel 3D processing method, in some situations.
Fixes a bug where ground attributes could be remapped incorrectly to the federation tile mesh result, in iMeshFederation::buildTileMeshFromLocalGroundTiles(), in certain circumstances where source tiles are partially overlapped by the represented region for the federation tile being built.
Fixes a very hard to repeat crash in mesh external edge expansion (e.g. in collision preprocess generation).
Fixes a very hard to repeat crash in pathfind preprocess generation.
Very significant improvements (between around 30 and 50% reductions in timings) for:
- Collision queries with lots of dynamic obstacles (timings halved for certain benchmarks)
- Static pathfind preprocess generation (generation times halved for some meshes)
- Pathfinding queries with lots of dynamic obstacles
- Obstacle set pathfind preprocess regeneration (e.g. for double-buffered semi-dynamic obstacles)
- Closest unobstructed position queries (in both static and dynamic situations)
- Voxel 3D processing
- Ground management queries
- Collision preprocess loading for environments with lots of burnt in obstacles
Some significant improvements also (up to around 30% reductions in timings) for:
- Static collision preprocess generation
- Line collision test queries
- Point collision test queries
- Connected region queries
- BSP 3D processing
- Ground mesh loading times
Additional platform specific performance improvements specifically on the Xbox 360 platform.
(Note that the data changes to reduce memory footprint in 5.26 and 5.27 resulted in a performance hit relative to previous releases for certain situations, on this platform. The underlying causes for these slowdowns have been addressed and release 5.28 is now significantly faster than those previous releases, without increases in memory footprint.)
Memory management has been improved very significantly for meshes with lots of burnt in obstacles to replace a lot of small memory allocations with larger shared buffers.
A lot of small memory allocations in pathfind preprocess generation have been replaced by a smaller number of (larger) block allocations, which are then reused.
BSP 3D processing improvements
The BSP 3D processing now supports external edge optimisation with the 'optimiseWithThreshold' processing attribute.
(This can result in some quite significant reductions in memory footprint and speedups in run-time queries, in addition to the optimisations described above.)
Voxel 3D processing improvements
The voxel processing now applies the external edge optimisation thresholds when processing exactly axis aligned edges, to avoid height detail being stripped out along these edges.
Support has been added to the voxel 3D processing for marking ground attribute regions in the ground mesh result based on agent height clearance.
Support for optimising boundaries between ground mesh attribute regions
The content processing now includes support for optimising boundaries between ground mesh attribute regions (supported with all content processing methods, i.e. 2D content processing, BSP 3D processing and Voxel 3D processing).
Compiler setting tweaks on the PC and Xbox 360 platforms.
Refactoring to consolidate the data structure changes in 5.26 and 5.27, and removing some obsolete data structures.
(The SDK code footprint is significantly reduced in this release, compared to those two releases.)
Support for minkowski expansion with a ground mesh result
has been added for cases where
minkowski expansion of a ground mesh is desired, but with
the result of the expansion also in the form of a 3D ground mesh
(as opposed the minimal expanded boundary representation used by PathEngine
This can be used, for example, to take advantage of PathEngine's robust content processing and expansion operations whilst generating ground mesh data for a custom or third party pathfinding runtime.
Changes for release 5.27
Fixes a bug where the built-in advance along path functionality could incorrectly report collision when advancing along an unobstructed path, with certain very rare configurations of mesh external edge geometry.
Fixes a very hard to repeat crash bug in the 2D or voxel content processing pipelines when edge optimisation is turned on.
Fixes a bug with the built-in advance along path functionality skipping to the end of path segments in certain very hard to repeat sitations.
Edge optimisation improvements
The algorithm used to optimise ground mesh edges during content processing
(i.e. when the 'optimiseWithThreshold' processing option is specified)
has been significantly improved, in particular for cases where there is a lot
of sliver geometry around the edge of a ground mesh that could previously
prevent vertices being collapsed.
(Where this is being applied to complex geometry, the resulting reductions in ground mesh complexity can potentially then make a significant difference to the memory footprint and run-time query performance.)
An additional content processing option has been added ('optimiseThreshold_Vertical') to enable the horizontal and vertical thresholds for mesh edge optimisation to be set separately, e.g. where more height detail is desired whilst still optimising out horizontal edge detail.
Voxel 3D processing improvements
The voxel 3D processing is much better at handling situations where small faces exceed maximum slope without the actual local vertical displacement exceeding maximum step height.
An additional option has been added to the voxel 3D processing for application of ground subdivision only within a supplied set of axis aligned region.
Some quite significant optimisations in the core SDK run-time, in particular:
- Significant reductions in mesh loading memory footprint (around 25% for benchmark meshes).
- Significant reductions in mesh loading times.
- Significant reductions in collision preprocess generation times.
- Significant reductions in find closest unobstructed position query times.
- Some smaller reductions in other query times, throughout the API.
Some speedups in the 3D content processing pipelines.
Root point resolution has been improved, in iMesh::placeProjected3DObstruction(), to fix an issue with obstacle placement failing in certain circumstances for obstacles that extend out from the edge of the local ground mesh and have geometric mid-point also outside of the mesh.
Changes for release 5.26
Fixes a bug where iPath::renderOnGround() would stop rendering in certain cases where paths
include off-mesh connections.
(Note that this method would previously render lines projected onto the mesh for off-mesh connection segments, but now skips rendering for these segments.)
Fixes a hard to repeat bug with failure to find a path around certain configurations of dynamic obstacles.
Fixes an issue with bad paths being generated around off-mesh connections, in certain circumstances.
Fixes an issue with the 3D content processing not removing 'sloped steps' in certain situations where there are adjacent vertical steps that intersect the sloped steps and are below the maximum step height.
Generation of agent unobstructed space representation has been completely reworked, giving us big speedups for collision preprocess generation (up to 50% reductions in preprocessing times) and also pathfind preprocess generation when there are a lot of burnt in shapes included in the preprocess.
Very significant reductions in memory footprint on ground mesh load.
Very significant reductions in position resolution query times.
Significant reductions in ground mesh load times.
Source code reorganisation, changes to project setup. Explicit project setup supplied for building PathEngine as a (single) static lib.
Source code projects moved up to Visual Studio 2008.
Changes for release 5.25
Fixes a bug where iMesh::placeProjected3DObstruction() was calling the vertexIndex() method of the supplied face vertex mesh object with indices higher
than the specified number of faces (and then also vertexX() and vertexY() for the returned vertex index).
(This was in interface checking code, and did not then effect the actual functionality of the method.)
A mesh data versioning issue in previous SDK releases means that certain meshes created by PathEngine 5.25 and later cannot be loaded by those previous SDK releases.
This relates specifically to federation tile meshes built with the
i.e. when using 'tile by tile' federation construction from 3D content.
Loading these meshes into SDK versions prior to 5.25 will then result in a hang.
The issue does not currently apply to meshes built against SDK 5.25 in other ways (i.e. not using iMeshFederation::buildTileMeshFromLocalGroundTiles()), and there is no compatibility issue in the other direction, i.e. all ground meshes created by or loadable by SDK release 5.24 can also be loaded into 5.25 without any problems.
Significant reductions in ground mesh data sizes when building mesh federation tiles with iMeshFederation::buildTileMeshFromLocalGroundTiles(), particularly in situations where the tile size parameter used for the initial 'source tiling' is large with respect to the final mesh federation tile size.
Big speedups for pathfinding in situations where lots of dynamic obstacles are being placed.
Memory optimisations to significantly reduce the number of allocations in large BSP 3D content processing operations.
Very significant optimisation of the 3D processing 3D convex hull generation code to remove bottlenecks in certain situations involving solid object source elements with very large point sets.
Reductions in 3D processing times.
Reductions in ground mesh loading times.
Reductions in collision and pathfinding preprocess generation times.
Significantly reduced overhead for pathfinding and collision context changes.
Speedups in core pathfinding and collision test queries.
An extra mesh loading option has been added
for forcing additional
partitioning in PathEngine's internal 2D mesh mapping.
(This can be important in certain situations where a lot of stuff is being placed as shapes on meshes with big open areas without holes.)
The new option enables vertices to be added in a regular grid arrangement, and is designed for use when the positions of placed shape detail is not know at ground mesh generation time.
A helper method has been added, iPathEngine::buildMeshAroundTiledObstructions(), for building ground mesh around tiled obstruction data. (This can be useful for setting up 'terrain stand-in' geometry based on terrain that is flagged as obstructing.)
A helper method
has been added for looking up ground mesh vertex indices.
(You shouldn't normally need this, but in certain cases, if it is necessary to reconstruct the ground mesh connectivity externally, this can save some messing around.)
Top level progress reports have been added to the voxel 3D processing.
Generation of an internal 2D mesh (or 'mapping') is now not supported when linking with the 2D content processing stubs lib.
(So, when linking against this lib, any meshes being loaded should already include a mapping.)
DebugDLL and ReleaseDLL configurations have been added to the PC platform Visual Studio configuration, for DLL runtime library linkage.
Changes for release 5.24
The pathfind preprocess major version number has been incremented, so pathfind preprocess will need to be regenerated when updating to this version.
Fixes an issue with spurious connections across a step that is over maximum step height, in certain specific cases where tile by tile 3D processing is being used and the step falls exactly on a source tiling boundary.
Fixes a crash bug when querying path connection IDs for paths that cross run-time off mesh connections, and that were generated against collision contexts that contain both run-time off mesh connections and dynamic obstacles.
Fixes a bug in the built-in advance along path functionality where the distance advanced was not correct in certain situations where multiple path segments are passed in a single advance along path call.
Some decent speedups for pathfinding and collision tests when lots of dynamic obstacles are placed.
Graph search optimisations resulting in pathfinding speedups, in general, and particularly in situations where a lot of connections are being considered (e.g. long paths, or paths to unreachable positions).
Some reduction in code size.
Paths from multiple start positions
An additional pathfinding method has been added,
for cases where there are multiple potential start positions for pathfinding
(e.g. where multiple agents can all potentially move to a specified target).
This method can also be applied in reverse, in some cases, for situations with multiple pathfinding targets.
Improvements to curved path generation
Significant improvements to the curved path functionality for cases where both start and end vector constraints are supplied.
Helper methods have been added to iAgent for access to the shape vertices, in all cases, whether or not there is an associated iShape object.
Changes for release 5.23
Fixes a (hard to repeat) bug in the voxel 3D content processing with assertion failure followed by hang.
Fixes a (hard to repeat) bug which could cause iMeshFederation::buildMeshFromLocalGroundTiles() or iPathEngine::buildMeshFromGroundTiles() to fail in certain situations with lots of overlapping ground layers and small source tiling tile sizes.
Fixes an issue with holes in the BSP 3D content processing result in certain pathological situations where excluded and non excluded faces in the source geometry overlap or touch and are exactly on-plane.
The collision and pathfind preprocess major version numbers have been incremented (so preprocess will need to be regenerated when updating to this version).
Persistence for mesh related data structures
An extended version of the mesh save method has been added, iMesh::saveGroundEx, to provide control over exactly which mesh related data structures are saved out with the mesh data.
(These data structures were previously always constructed on mesh loading, with this construction process being quite fast, but it is now possible to specify that these should be stored and restored from persistence, for faster loading at the cost of larger mesh file sizes.)
The partitioning mechanism used for resolving 3D points to the ground mesh has been replaced with a much more efficient data structure, with key benefits being:
- big reductions in the base mesh loading memory footprint, for large meshes,
- much faster construction means significant reductions in mesh loading times,
- smaller mesh file sizes when the partitioning is being saved to persistence,
- run-time lookup performance is better, in general (although this can vary with the actual mesh data being processed).
A helper method has been added for stripping out parts of a ground mesh not reachable from a specified set of 'root positions'.
Interface checks have been added for the start position precondition on pathfinding queries (start position must not be obstructed by base mesh or burnt in obstacles).
The position near 3D point methods (i.e. iMesh::positionNear3DPoint() and similar) have been changed to return the actual closest ground position, in most cases, instead of just the closest in terms of horizontal distance.
Building from physics scene data
Example code has been added for running the 3D content processing directly against 3rd party scene data.
(Currently Havok and PhysX.)
(See this page for more information.)
Testbed lighting coefficients have been reduced to avoid an issue with final rendered textures saturating on some machines.
Changes for release 5.22
Collision preprocess compatibility
There was an issue, in release 5.21, with collision preprocess files being incompatible across platforms with different byte ordering.
This meant that collision preprocess files generated on the x86 or x64 based platforms could not then be loaded into power PC based platforms (e.g. Xbox 360 or Cell BE / PS3).
This issue is fixed in this release.
Collision preprocess files generated on x86 or x64 platforms with release 5.21 do not need to be regenerated, and can now be loaded on power PC platforms with this release.
Any collision preprocess files generated on power PC platforms should be discarded, and regenerated, however.
A bug with dynamic off-mesh connection handle management, causing a crash on dynamic off-mesh connection removal, has been fixed.
A deadlock has been fixed when using findPathAway() methods simultaneously with other pathfinding methods from multiple threads and against a single shared iMesh instance.
A bug has been fixed with thread synchronisation problems in the direct path construction methods (iMesh::constructPath_Reversed() and iMesh::constructPath()) causing these to crash in some situations when used across multiple threads.
A bug has been fixed with preprocess generation failing in certain specific situations with
- the small convex optimisation enabled and
- surface type traverse costs burnt into the mesh.
A bug has been fixed with preprocess generation failing in certain specific situations with
- the "connectOverlappingShapeExpansions" collision preprocess option enabled and
- multiple placed shapes being present with exactly identical geometry (and not overlapping any other placed shapes, or the external edge expansion).
Very big speedups for all methods writing data to tokenised xml format (mesh file save, preprocess save, etc.).
Significant performance improvements for run-time queries on the PC platform, across the board.
(Very significant speedups, in particular, in point and line collision testing, and findClosestUnobstructedPosition().)
Some speedups for these run-time queries, also, on other platforms.
Significant reductions in memory load and amount of fragmentation for BSP 3D processing.
Reductions in the mesh loading memory footprint.
Mesh loading and collision preprocess generation time and memory footprint significantly reduced when working with meshes with extra partitioning.
3D Content Processing
Special case handling for solid object with all points are on a plane has been improved, to avoid the need for the addition of extra points, unless the plane is exactly vertical.
An API method has been added for direct access to the pathfinding movement cost function
This can be used wherever it reactive 'generate and test' style code needs to take this movement cost function into account.
3D content processing is now supported on Windows x64, with Visual Studio projects added to the x64 platform archive for the 3D processing static library and dll.
Build setup such as build target locations and naming has been standardised and rationalised throughout both
the Visual Studio project files and the python build scripts.
See the source code build documentation for more information.
The code for translation between related meshes has been significantly refactored, with the (complicated) 'mesh with tracked transform' mechanism now no longer used.
Code for working with 'axis fractions' for intersection points has been refactored to standardise.
Changes for release 5.21
The major interface version number on the iPathEngine root interface has been incremented (so calling code will need to be recompiled when updating to this version).
The collision and pathfind preprocess major version numbers have been incremented (so preprocess will need to be regenerated when updating to this version).
A bug has been fixed that could potentially cause significant slowdowns for pathfinding queries in certain specific situations where
- the small convex optimisation is in use (with a significant number of obstacles then being split of as small convex) and
- dynamic obstacles are included in the queries, and overlap one or more small convex obstacles.
A bug has been fixed where the mesh federation tile index values associated with a mesh were not being restored correctly on loading from persistence, in certain situations.
A bug has been fixed with bad height calculations when querying against iMesh instances created by
This bug affected direct height queries and position resolution queries that depend on the mesh height function, but only for the actual iMesh instance returned by buildTileMeshFromLocalGroundTiles(). Height calculations after saving the mesh and loading back from persistence were unaffected by this bug.
The SPU collision core 'compiled' boundary representation is now used throughout the API in place of a linked element representation, so:
- A whole bunch of small boundary element allocations are now replaced by a single 'compiled' data buffer.
- Memory footprint and persistent file size for this boundary data are very significantly reduced.
- Save and load times for the boundary data, in particular, are drastically reduced (since per element save logic is now replaced by essentially just one single buffer read/write).
(These points mostly relate to collision preprocess, but this can relate to pathfind preprocess, also, in certain preprocessing setups with connected region queries enabled specifically in the pathfind preprocess.)
Very significant reductions in point and line collision query times.
Some reductions, also, in find closest unobstructed position queries, and in position conversion from 3D.
An API method has been added for generation of PathEngine obstruction shapes from 3D geometry
This can be used at content time or run-time, and returns an iAgent object with the same set of constraints as iMesh::placeLargeConvexObstacle().
The iMesh::buildCollideAndSlidePath() method has been removed.
iShape interface object pointer arguments have been made const throughout the API.
The iRender3DLinesCallBack::startVertex() method now takes a terrain layer argument,
to support rendering of lines flush with external terrain height map data.
(If you use rendering callbacks then you'll need to add the extra parameter in to your rendering definition to make this compile. Just ignore this new parameter if you don't care about rendering ground lines on height maps.)
3D content processing on the GCCx64 platform
There are a bunch of minor fixes and edits to make the 3D content processing code build under the python build setup, on the GCCx64 platform.
Voxel 3D processing vertical range
Geometry is now offset during voxel 3D processing in order to get the best use of the available Z range.
In the case of tile by tile 3D processing, this offset is calculated per tile, with each tile then effectively having its own Z range.
Python build setup
Preprocessor defines for assertions and range checking have been added to the debug builds when building under the python build setup.
Changes for release 5.20
The behaviour of source tiling objects with regards
to the exact tile regions generated for a given set of tiling parameters has changed slightly.
If you are using tiled 3D content processing then you should either:
- Verify that the exact tile ranges being generated by your source tiling objects are unchanged after updating, tweaking tiling parameters slightly as necessary. or
- Delete any existing ground result tiles, or otherwise force the regeneration of all ground result tiles after updating.
Fixes a run-time crash in pathfinding queries in certain situations where obstacles with cost to traverse are being used and with the small convex optimisation turned on.
Fixes the 3D content processing crashing in some empty mesh cases resulting from content being marked as excluded, and with 2D overlap analysis enabled.
Fixes an issue with the disconnects in certain circumstances where the 'excludeDownwardFacingFromGroundResult' option is set, and downward facing tris are being supplied as stair risers.
Fixes a hard to repeat 3D content processing hang in certain situations where tile size is small with respect to the sizes of polygon data being passed.
Voxel based 3D processing added
PathEngine now includes a voxel based 3D processing code path, in addition to the existing BSP 3D processing.
The voxel based code path runs against exactly the same source content data as the existing BSP processing code path, generates exactly the same run-time mesh format, and includes essentially the same feature set, including support for 'tile by tile' processing, and integration with PathEngine's mesh federation functionality.
Voxel processing is then significantly faster against complex scene data, but at the cost of some aliasing to the voxel grid.
The 3D processing demo has been updated, and is switchable between the two content processing methods.
Refer to the 3D processing documentation for more details.
More intelligent dynamic pathfinding state management means significant reductions in the overhead for certain
kinds of pathfinding state changes.
(There is now virtually no overhead for changes to connection cost overlay penalties, for example, and reduced overhead for changes to dynamic surface type based traverse costs or traverse cost directions.)
Manyfold reduction in ground mesh and preprocess file save times.
Base mesh preprocess generation operations are now non-blocking across shapes, so that preprocess generation for multiple shapes can be performed in parallel (against a single iMesh instance).
Reductions in BSP 3D content processing times.
Memory management improvements in the BSP 3D content processing to avoid large block allocation requests.
Support for completely dynamic off-mesh connections
Support has been added for including completely dynamically determined off-mesh connection movement possibilities
(i.e. with endpoints not known at content or preprocess generation time)
in the pathfinding graph.
This is managed through the iCollisionContext interface, and adds to existing functionality for modifying statically determined movement possibilities.
(Dynamically determined connections can be useful for getting AI agents to follow the player after a jump, and for stuff like dynamically placed ladders or bridges.)
Formation movement example added
A formation movement example project has been added, demonstrating an implementation of formation movement with minimal pathfinding calls, just one set of agent shape preprocess, and very low per agent update cost.
Documentation for this example project can be found here.
Other API changes
Mesh checksum or shape mismatch during collision preprocess loading has been changed from a fatal to non fatal error.
iTestBed::preprocessFaceVertexMeshExternalEdges() has been added (to enable large face vertex mesh objects to be outlined with much less overhead than iTestBed::preprocessFaceVertexMeshEdges()).
Changes for release 5.19
A bug fix (see below) changes the id string assigned to named obstacles in the case of either:
- Tile by tile mesh federation construction from 2D content (with iMeshFederation::buildTileMeshFromContent()) or
- Invocations of iMesh::addAnchorsAndShapes() with a non-empty ID prefix
In the case of federation tile construction, each named obstacle is now prefixed by the corresponding content chunk section ID value, followed by the single character ':'.
In the case of iMesh::addAnchorsAndShapes(), the specified ID prefix is now being applied to named obstacle IDs in addition to anchor IDs.
If you are using named obstacles with either of the above then code may need to be updated to expect prefixed ID strings.
Fixes a (fairly hard to reproduce) crash or endless loop bug in vertical face processing, in the 3D content processing.
Fixes a bug with shape validation not catching the (very rare) non-convex case where the last two and first vertices of the shape form exactly inline edges.
Fixes a bug with id prefixes not being applied to named obstacle IDs when adding anchor and shape components in the 2D content processing, in either iMeshFederation::buildTileMeshFromContent() or iMesh::addAnchorsAndShapes().
Very significant speedups in the 3D content processing.
(In many situations the 3D processing now runs through in less than half the time taken in release 5.18.)
A 3D processing option has been added to control the way terrain source geometry is applied.
By default, terrain geometry is now considered to obstruct any other geometry directly below, avoiding the need to represent the underside of the terrain, and potentially speeding up processing of certain situations quite significantly (in addition to the general optimisation mentioned above).
To take advantage of this optimisation it's important for section ID attributes to be set correctly for any terrain geometry.
In cases where ground surfaces are required beneath the terrain a 'groundGoesBelowTerrain' attribute should now be specified with value 'true'.
3D processing memory allocation optimisations.
2D content processing usability improvements
When placing pinned shapes through the iAnchorsAndPinnedShapes interface class PathEngine will now
attempt to resolve situations with invalid shape root positions by generating positions based on shape boundary coordinates and traversal through the ground mesh.
In practice this means that, in many situations, the constraint that pinned shapes root positions be inside the shape polygon can be ignored, and in many cases a single anchor will now suffice to root clusters of such shapes.
The building entrance portal connection feature (in the 2D content processing) now supports portals with building external shapes but no internal floor.
This makes it much more straightforward to apply the building external shape mechanism as a kind of generalised 'cookie cutter' for cutting arbitrarily shaped obstruction boundaries out of the base mesh.
Access to Testbed command line arguments
Other API changes
Mesh federation tile meshes now remember their federation tile index on construction, this can be queried with iMesh::getFederationTileIndex.
A helper method has been added to iPath to get hold of a pointer to the owning iMesh instance.
Helper methods have been added to iCollisionContext to check the state of overlay connection penalties.
Source code changes
Some refactoring of the Collision Core with a cleaner object construction paradigm and the possibility to switch index limits on and off at compilation.
Buildscripts modified for consistent application of -fPIC, as opposed to -fpic, for linux shared object builds.
Changes for release 5.18
Fixes a bug in collision preprocess loading for some (fairly rare) situations with obstructed space boundaries that turn directly back on themselves.
Fixes a hard to repeat bug in the tokenised xml processing relating specifically to the collision/pathfind preprocess loading code paths.
Fixes a hard to repeat crash in the findPathAway query, in certain situations with the small convex optimisation turned on.
Fixes an issue with downward facing geometry being generated by the 3D processing for vertical faces with certain vertex winding order, resulting in disconnects in the ground result.
iPath::renderOnGround() has been updated to eliminate repeated vertices at path corners.
Very significant optimisation of the 3D content processing for most situations involving terrain, or terrain-like surfaces.
(This optimisation fundamentally changes the way the 3D processing scales with respect to terrain surface detail, and can result in order of magnitude reductions in processing times and peak memory load in certain situations where detailed terrain geometry is being passed into the 3D processing.)
Methods have been added to support loading 3D content snapshots (in iContentProcessing3D), e.g. to rerun generation from a given snapshot, to modify snapshots, or to examine snapshots in custom or 3rd party content applications.
Support has been added for saving and loading iObstacleSet pathfind preprocess.
The 'PE_FaceAttribute_CP3D_ExcludeFromGroundResult' attribute value has been added, to support 3D source geometry components which need to be considered as potentially obstructing other surfaces, but which should never themselves generate walkable ground mesh.
The 'excludeDownwardFacingFromGroundResult' 3D content processing option has been added,
to automatically exclude downward facing tris from the ground result.
(This is off by default, but should probably be turned on in most cases where tri-mesh 3D source geometry is being used, after verifying that source geometry vertex winding order is set appropriately.)
The core run-time interface is now available together with iContentProcessing3D, when linking with the 3D content processing dll.
(Use DLLExport_CP3D_GetInterfaces to get both interfaces on dll loading.)
Source code changes
The mechanism for static linkage with the 3D content processing has been updated to be consistent with the rest of the API.
You can now use PathEngine_InitialiseCP3DAndObtainInterface (after initialising the root interface) to obtain exactly the same interface as used with dll linkage.
Changes for release 5.17
The major version numbers for saved collision and pathfind preprocess have been incremented in this release, so preprocess will need to be regenerated.
Fixes an infinite loop bug in pathfinding in the case where path start and goal positions have identical start and goal coordinates but are in different 'cells'.
Fixes an infinite loop bug in collision preprocess generation for certain very rare situations where linear cut connection between mesh layers coincide exactly with the edges of 'convex external faces'.
Fixes an issue where PathEngine was not considering the possibility to 'take off' from an off mesh connection immediately after 'landing' at that connection.
Very significant optimisation of the preprocess persistence mechanisms in this release:
- Preprocess save file sizes down to a fraction of the sizes for the release 5.16.
- Greatly reduced pathfind preprocess loading times (more than twice as fast as in 5.16, in common cases).
- Even larger reductions in preprocess save times.
- Big speedups in collision preprocess loading times, also.
- Very significant speedups in the traditional XML loading code paths (although tokenised XML is still recommended for performance critical applications).
Executable code size footprint reduction.
New collision preprocess generation options
There is now an option to combine any overlapping base obstacles shapes with the expanded mesh external edge representation, during (base) collision preprocess generation, which then opens up the possibility to also generate 'connected regions' preprocess, for fast reachibility detection.
When connected regions preprocess is generated, there is also now an option to remove (or close) small disconnected regions in unobstructed space (e.g. small unobstructed areas in and around stacks of detail objects).
Attempting to load collision preprocess with incompatible versioning attributes no longer triggers automatic regeneration. If required, this can be done on the application side, instead.
Source code changes
Significant refactoring of loading code paths, to completely remove handler-based XML loading in favour of stream based mechanisms.
The 'Expat' 3rd party XML loading library is no longer required, and has been removed.
Support for full text searching has been added to the documentation .chm.
Changes for release 5.16
(Interface versioning changes in this release require calling applications to be rebuilt.)
Fixes a crash on collision query dispatch against collision contexts with four or more attached obstacle sets.
Fixes a bug with first collision queries reporting collision geometry that collides but is not the first geometry intersected, in certain situations with lots of detail shapes placed.
Fixes a memory leak in the 3D content processing (only occurring after a certain level of source geometry complexity).
Fixes a very hard to reproduce crash in pathfind preprocess generation.
Very significant 3D content processing speedups.
Very significant speedups in the SPU collision core code paths.
Big speedups in mesh loading and partitioning generation times for large meshes.
Big speedups in find closest unobstructed position queries.
Speedups in first collision queries.
Speedups in point collision queries.
Some additional caching has been added to collision contexts to significantly speed up pathfinding in situations where surface type based traverse costs are being used together with dynamic obstacles.
Exception handling has now been turned off by default for the 'PC' platform.
(While this does give us some noticeable performance improvements, the most significant improvement is a reduction in executable size.)
The iMesh::getCollisionPreprocessAttributes() and iMesh::getPathfindPreprocessAttributes() methods have been removed.
Attempting to load pathfind preprocess with incompatible versioning attributes no longer triggers automatic regeneration. If required, this can be done on the application side, instead.
iMesh::positionIsBlockedBySurfaceTypeTraverseCosts() has been added, as a fast early out for certain situations where blocking surface type based traverse cost values are being used.
iMesh::buildCollideAndSlidePath() has been added, for direct generation of paths based on movement in a constant direction with sliding against obstruction boundaries.
iPathEngine::save2DContentSnapshot() has been added as a replacement for iPathEngine::saveContentData()
(with saveContentData() still included in the API but depreciated).
The new method saves 2D content processing options along with the snapshot.
Additional checking has been added for options supplied to 2D and 3D content processing, mesh loading, and preprocess generation, with warnings now emitted for any unrecognised options.
Source code changes
The additional platform codes GCCx86_SO and GCCx64_SO have been added for building shared objects on platforms where this requires position independant code generation.
Changes for release 5.15
Fixes a crash in iMesh destruction in the case where multiple sets of pathfinding preprocess have been generated against burnt in surface type traverse costs.
Fixes some very hard to reproduce collision and pathfinding preprocess generation crashes.
Fixes a hard to reproduce crash in tile by tile 3D content processing, for certain situations involving geometry exactly touching tile boundaries.
Very significant optimisation of the pathfind preprocess loading code paths (for 'tokenised XML'), with order of magnitude speedups in preprocess loading for meshes with high intervisibility (such as the 'Thainesford' benchmark mesh).
Significant optimisation of the mesh loading code paths (for 'tokenised XML').
Some speedups for tokenised XML file parsing, in general.
Platform specific optimisations on the PC, resulting in some very significant performance improvements on this platform.
3D Content Processing
A "maxSlopeOnTerrain" 3D content processing option has been added,
to enable a different maximum slope value to be specified for terrain areas.
A value of -1 can now be used (either for this additional option, or for the existing maxSlope parameter) to turn off steep face removal completely.
Cell processor platform specific optimisation
The 'Cell' platform specific code archive now includes a customised set of collision data structures and code
paths with very agressive memory and code footprint optimisations applied.
This makes it possible to load an independant PathEngine 'collision core' into the SPU local store for some fairly large meshes (e.g. for our 'Thainesford' benchmark mesh), and to then perform asynchronous dispatch of PathEngine's core pathfinding agent line collision test functionality purely on the SPU.
(Refer to this page, in the online documentation, for more details.)
Changes for release 5.14
This release adds some important bugfixes in the 3D content processing,
and is a recommended update for anyone working with this 3D process.
There are no major issues with the core SDK, but other clients can nevertheless benefit from significant performance improvements throughout the SDK.
A fairly hard to reproduce bug has been fixed that could cause the 3D content processing to fail when the 'clipToTile' option is being supplied (i.e. when using tiled 3D content processing).
A bug has been fixed that could cause collision preprocess generation to fail in certain (very rare) situations.
A bug has been fixed where bad connections across ground result pieces could cause failure in the mesh result generation stage of tiled 3D content processing.
A bug has been fixed where holes could be left in the 3D content processing result, in certain situations, due to incorrect tracking of face slope across the result approximation stage.
Big speedups pretty much across across the board, with faster preprocess generation, speedups in pathfinding and other core queries, and some very significant reductions in 3D content processing times.
Memory footprint reductions.
Constraints on manually generated ground meshes
Certain conditions that should only occur in manually generated ground mesh XML are now disallowed,
in order to simplify mesh loading.
Specifically, each vertex supplied with a ground mesh must be assigned to at least one edge, and it is not permitted for vertices to be 'split' between multiple disconnected tri fans.
These conditions were previously being fixed up by special code in the ground mesh loading process, but will now result in fatal errors.
A 'PATHENGINE_SINGLE_THREADED' preprocess define has been added to remove some synchronisation logic when only single threaded operation is desired.
Changes for release 5.13
Fixes a bug with the shortest path not being found in certain situations where options have been added to turn on additional partitioning (with then either a longer path returned, or else no path found, depending on the exact circumstances).
Fixes a bug in generation of 'drop type' connection candidates, in the automatic off-mesh connection generation setup.
Fixes 3D content processing failure in certain situations where the strip terrain height option is turned on and the extrusion of geometry marked as terrain results in vertical faces.
Fixes a bug that was causing bad geometry to be generated around the borders of 3D content processing tiles in certain cases where the edges of source geometry elements fall exactly on these borders.
Fixes a (small) memory leak in the case where errors are encountered during XML parsing.
Fixed an issue with calls to getVersionAttributes() resulting in (one-time) memory allocations, that were not then being freed by calls to PathEngine_ShutDown().
A 'Fatal' error is now emitted in the case of errors in XML parsing during mesh instance construction, where previously it was possible to continue after a 'NonFatal' error, but with unpredictable results.
There are very significant improvements in partitioning generation times for the specific case of
meshes with large amounts of external edge detail.
This affects loading times for these kinds of meshes in the case where a 'mapping to 2D' has not been saved out with the mesh, and also generation of these kinds of meshes from content, with either the 2D or 3D content processing.
The 3D content processing has been modified to avoid issues with memory failures on Windows systems without the 'Physical Address Extension' enabled, when running against heavyweight source data, due to very large contiguous blocks being allocated.
Some reduction in the memory cost for loading ground meshes, particularly in the case of meshes with lots of ground tris.
Some significant reductions in the memory footprint for collision preprocess on meshes with lots of external edge detail.
A speedup for resolving ground position from 3D points.
3D Content Processing
The maximum step height parameter is now taken into account during steep slope removal (in addition to vertical face processing), to address an issue with meshes not connecting as desired across certain step-like features with non-vertical faces.
When the 'stripTerrainHeightDetail' option is turned on, the 3D processing now also strips out any
inline external terrain vertices.
(This can make a big difference to load and run time processing times in situations where tiled 3D content processing is being applied with a fine tiling to environments with lots of ground detail.)
Source code changes
A stub library has been added (to the full source archive) to enable the 2D content processing code footprint to be removed in cases where run-time storage is at a premium and where the 2D content processing is not being used at run-time. (Refer to this page, in the online documentation, for more details.)
Changes for release 5.12
This key features of this release are probably dynamic control of off-mesh connection costs
and support for 'connected region' queries.
The automatic removal of disconnected fragments is also quite an important improvement for the overall 3D content process, in certain situations.
And example code for 'semi-dynamic obstacle' management has been added, in the form of the 'SemiDynamicObstacles' example project, together with supporting optimisations in the SDK synchronisation mechanisms.
Fixes a fairly hard to repeat bug in the advance along path mechanism for certain situations involving very long path segments.
Fixes a subtle bug in generating the pathfinding preprocess associated with a preprocessed obstacle set that could cause pathfinding queries on that preprocess to hang or to crash in certain (fairly rare) situations.
Speedups for pathfinding against large numbers of dynamic obstacles.
Reduction in memory footprint for meshes with large numbers of faces.
iTestBed::drawAgentExpansion() now caches rendering information internally for faster rendering of obstacle expansions in scenes with large numbers of obstacles.
There have been significant improvements in the syncronisation mechanisms used across multiple collision contexts and obstacle sets for a given iMesh, resulting in greatly reduced blocking for operations across collision contexts or obstacle sets.
Preprocess generation attributes
The 'split_with_circumference_below' attribute is no longer recognised for collision preprocess generation,
and must be passed in to pathfind preprocess generation instead.
Passing the 'split_with_circumference_below' attribute into collision preprocess generation will cause a non fatal error to be emitted.
when working with 'preprocessed obstacle sets', all attributes passed into obstacle set creation now also get passed on to
any subsequent preprocess generation.
If the small convex optilisation is desired for this preprocess then a 'split_with_circumference_below' attribute should be included with these creation attributes.
(Previously, this attribute was cached with the base collision preprocess, and copied through from that preprocess.)
Fast connectivity determination
This release adds support for very fast connectivity checking.
This needs to be turned on by adding the relevant
pathfind preprocess attribute
The pathfind preprocess will then analyise the set of obstructed space boundaries for the agent shape being processed,
assigning unique indices to each connected region of unobstructed space for that agent.
iMesh::getConnectionRegionFor returns the connected region index for a given point.
Dynamic control of off-mesh connection costs
This release adds support for run-time modification of the penalty values associated with off-mesh connections.
See setOverlayConnectionPenalty(), for details.
Automatic removal of obstructed ground fragments
The 2D and 3D content processing methods now accept an option for the removal of completely obstructed ground fragments, as determined for a minimum agent shape passed in with the option.
Semi-dynamic obstacles example project
An example project has been added, demonstrating a technique based on double buffered preprocessed obstacle sets for fast pathfinding against large numbers of 'semi-dynamic obstacles'.
Methods have been added to the testbed to enable render preprocess to be generated for a given shape and height combination,
and then drawn at multiple locations.
This can greatly speedup rendering in situations where large numbers of dynamic agents need to be drawn.
Helper methods iObstacleSet::clear(), iTestBed::drawAgentsInObstacleSet() have been added, for convenience.
Testbed text display (with iTestBed::printTextLine()) has been modifified to make this text more visible
on high resolution desktops - the text size has been increased and the text background has been changed
to a solid black.
iTestBed::printText8by16() is depreciated.
Other API changes
Collision context (iCollisionContext) arguments have been made const throughout the API,
for API methods that do not modify the context,
to enable application code to meaningfully add const qualifiers to iCollisionContext pointers.
(This is not an interface breaking change.)
Source code changes
This release includes some significant refactoring of the SDK source code, with, in particular, a complete removal of 'external faces' throughout the various difference mesh processing components for a consistent treatment of external borders.
The linkage requirements in the case of static linkage with the SDK have been reduced to a single function call
for SDK initialisation, returning the root interface pointer.
An example project with static linkage has also been provided.
See this page for details.
The function signatures used in the case of Linux shared object linkage
have been changed, in line with the new static linkage setup,
and an example project is also provided for this case.
See this page for details.
Changes for release 5.11
The main thrust of this release is the addition of support for 'tiled 3D content processing', but prototype functionality for auto-generation of off-mesh connections has also been added, as well as some important bug fixes.
Fixes a (fairly hard to repeat) crash bug for path away queries against certain configurations of base obstacles.
Fixes a hard to repeat crash bug in preprocess generation.
Fixes 3D content processing failure for certain pathological situations involving solid object point clouds that reduce to a line.
Fixes a bug involving incorrect attributes getting passed through the 3D content processing from solid source geometry.
Fixes a bug with the 3D content processing taking a long time and consuming excessive memory during vertical face processing in certain situations where large objects with vertical sides are cut by complicated terrain.
Fixes a bug with manual content chunk edge connection failing in cases where the geometry concerned is outside PathEngine's world range. (This can be valid in the case of tile by tile mesh federation construction.)
Fixes a bug with incorrect connection generation in the specific case of multiple edge connection markers stacked vertically and at exactly the same horizontal position, when explicit edge connections are turned on.
Fixes a bug with mesh federation interface objects not being cleaned up in iPathEngine::deleteAll().
3D content processing changes
The result of the 3D content processing is now well defined with respect to coplanar source geometry with different face attributes.
There are some significant reductions in 3D content processing times for most data sets (even before taking the effects of the new tiled 3D content process into account).
Methods have been added to iContentProcessing3D and iTestBed to support visualisation of the convex hulls for solid geometry elements passed in to the 3D content processing.
'Tiled 3D Content Processing'
This release adds support for 'tiled 3D content processing',
a process based on splitting the 3D content processing source data into
tiled chunks which can be treated independantly,
with the resulting ground pieces then combined back together again for run-time pathfinding.
This page , in the online docs, provides an overview of tiled 3D content processing, with the 3D content processing demo also having been moved into the SDK examples, and updated to use this setup.
Obstructed off-mesh connection endpoints
An option has been added to enable nearby unobstructed positions to be resolved for obstructed off-mesh connection endpoints during pathfinding preprocess generation.
Prototype auto off-mesh connection generation framework
method has been added to the iMesh interface to provide prototype functionality for
automatic generation of off-mesh connection candidates across gaps between ground mesh pieces
and at points where agents may be able to drop off the mesh edge onto ground below.
This functionality is currently subject to review, and may be changed in future releases.
Other API changes
There is a minor change to the way mesh federation width and height are derived from the range passed into
(Width is now calculated as maxX - minX + 1 instead of maxX - minX and likewise for height.)
In certain boundary cases this can affect the tiling generated for a given range. If you need to work with existing tile sets then this can be avoided by subtracting one from the maximum x and y values passed in to iPathEngine::buildMeshFederation_TilingOnly().
A minor change to the mechanism for explicit edge to edge connection management means that some edge connections that were previously permitted may now fail.
Helper methods have been added to the iMesh interface to support application-side rendering of obstacles burnt in to the mesh. (getNumberOfBurntInObstacles(), getBurntInObstacleRoot(), getBurntInObstacleVertices(), and getBurntInObstacleVertex())
An option ('terrainHeight')has been added to iMeshFederation::buildTileMeshFromContent(), enabling the base height of terrain stand-in geometry to be specified.
An option ('applyExternalShapeZInTerrain') has been added to the 2D content processing to specify that the heights of vertices added to terrain stand-in geometry during the processing of portal and external shape connections should be taken from the external shape being cut, as opposed to being interpolated in the existing stand-in geometry.
Changes for release 5.10
Improvements in pathfinding performance across the board.
Very significant improvements, in particular, in performance for pathfinding queries against dynamic obstacles.
Reduction in memory footprint for pathfinding preprocess for environments with lots of burnt in obstacles.
Fixes a crash bug in curved path generation across off-mesh connections.
Fixes a problem with path length not being updated correctly after advancing across off-mesh connections.
Fixes a crash bug in the automatic edge connection feature of the 2D content processing in certain situations where the scene contains multiple matches for an edge connection.
Fixes various issues with pathfinding preprocess generation on meshes with surface type traverse costs with certain configurations of cost boundaries causing crashes or incorrect pathfinding results.
Fixes a problem with bad (downward facing or zero area) tris being generated by the 3D content processing, for certain situations where sliver tris are generated and near zero, before approximation.
Fixes a problem with the internal mesh checksum after large convex obstacle placement not matching the mesh checksum after subsequent saving and loading, causing preprocess to fail to load.
The benchmark SDK example project has been improved, with the addition of a benchmark for pathfinding with dynamic obstacles.
The standard platform for building on Windows platforms has been updated from
Visual Studio 2003 to Visual Studio 2005.
All supplied solutions are now in Visual Studio 2005 format, and the static libraries supplied with the interface layer package are built in Visual Studio 2005.
TestBed moved to DirectX 9
The TestBed has been moved to DirectX 9.
This means that DirectX 9 SDK is now required in order to build the TestBed (or dependant applications), and the DirectX 9 run-time is now required in order to run the TestBed (or dependant applications).
Memory failure reporting
Memory allocation failure is now checked for by the memory tracking instrumentation (which is built into the standard dll release build), and reported through the error handler mechanism.
Changes for release 5.09
Fixed a memory leak in the 3D content processing.
Fixed a bug which could cause the 3D content processing to fall over in cases where face/vertex source data includes certain kinds of sliver faces.
Fixed a bug where certain configurations of user generated ground meshes could crash PathEngine's mesh loader.
Fixed a bug where the TestBed geometry picking mechanism would fail to function correctly if ZoomExtents() had not been called.
The API headers now use typedefs instead of built-in types for integer type parameters.
Support for dll linkage with the 3D content processing
It's now possible to use dll linkage for calling into the 3D content processing.
Refer to this page (in the online documentation) for more details.
Other API changes
The array of integers passed in for the solid object components of the 3D content processing has been replaced by
an iSolidObjects interface class.
(See this page for details.)
This makes it possible to apply attributes to these solid objects, and these attributes will be passed through, together with any attributes in mesh source data components into the final ground mesh result.
An option has been added to enable terrain height detail to be stripped out of
the ground mesh generated by the 3D content processing,
so that PathEngine's terrain callback mechanism can then be applied for that mesh.
(See this page for details.)
A reduction in memory footprint for pathfind preprocess generated with the small convex optimisation.
Some improvements in query times.
Changes to build scripts
There have been minor changes to the environment variables required by the buildScripts, on GCC based platforms.
Refer to this page for details.
Changes for release 5.08
A bug has been fixed where PathEngine would attempt to allocate large amounts of memory in situations where large values were being supplied for the sectionID face attribute.
A bug has been fixed where the internal checksum generated for a mesh output by the content processing
would in some cases fail to match the checksum generated after subsequent saving and loading of the mesh,
causing preprocess generated directly after content processing to fail to load.
This would only happen where a mapping to 2D was not being saved out with the mesh.
iMesh::placeLargeStaticObstacle() has been added, to enable obstacle shapes to be placed without being subject to the range constraint that otherwise applies to agent shapes.
iPathEngine::largeStaticObstacleShapeIsValid() has been added to enable the vertices for large static obstacles to be prevalidated.
A range constraint on cMesh::findClosestUnobstructedPosition() and cAgent::findClosestUnobstructedPosition() has been removed.
A range constraint on cMesh::findPathAway() and cAgent::findPathAway() has been removed.
A range constraint on cMesh::generateRandomPositionLocally() has been removed.
A range constraint on cTestBed::drawSquareBounds() has been removed.
Other API changes
iMesh::addAnchorsAndShapes() has been added, as an alternative to adding pinned shapes manually (in situations where the content chunks functionality is not being used).
Content-side handling of large shapes
When processing anchors and shapes, the 2D content processing will automatically detect when shapes are too large to be placed as standard obstacles and will add these shapes as 'large static obstacles'.
Source code changes
Some significant refactoring of the source code, particularly with respect to the way polygons are represented and handled by PathEngine internally.
Changes for release 5.07
A bug has been fixed where spurious geometry was generated for content chunk instances with more than one connecting edge.
A bug has been fixed in the advance along path functionality where agents would jump to the end of a path segment in certain very rare situations.
A bug has been fixed where Z was being ignored when resolving matches for edge to edge connections (in the 2D content processing).
The edge to edge connection feature in PathEngine's 2D content processing now permits the edge connection case where the vertices across the connection match exactly (i.e. with no bridging faces generated).
Global functions for debug break and abort are no longer required (and should not be defined) when statically linking directly against PathEngine's internal libs.
Changes for release 5.06
This release fixes some hard to repeat bugs specifically relating to the building portal connection
functionality of PathEngine's 2D content processing.
This includes crash bugs for certain rare cases where building portals are placed right up flush with a mesh edge (but not actually touching), and for cases where ground geometry contained inside a building external shape boundary 'bridges' back over that boundary.
Interface breaking API changes
interface class has been added for improved client-side management of placed content chunk instances.
The existing instantiation methods on iContentChunk have been replaced with methods that return an iContentChunkInstance object, with methods for then querying geometry pointers from that instance object.
Horizontal ranges previously represented in the form of 4 integers throughout the API have been replaced with a cHorizontalRange interface class.
Support for 'tile by tile' mesh federation construction
An extremely scalable and effective solution
for the content side of PathEngine's existing mesh federations
the tile by tile approach to federation construction
removes various arbitrary constraints placed on this functionality by the requirement for
a pregenerated world mesh.
Refer to this page (in the online docs) for more details about this approach.
Other API changes
Some additional constraints have been added to disallow the creation of empty content chunks.
Content chunks without either a ground or anchors and shapes component are disallowed, and where these components are supplied they must then be non-empty.
Mesh federation tile meshes are now clipped to the federation's world bounds.
positionFor3DPoint_ExcludeTerrain() has been added, to support position resolution in cases where it may not be possible to access terrain detail.
Default resolution of non-terrain portal markers (in the 2D content processing)
has been modified slightly so that these markers do not resolve to terrain stand-in geometry.
This is now controlled by a 'numberOfTerrainLayers' content processing option, which enables the client application to request the old portal resolution behaviour in case this is desired.
The upper limit on the extents of the range supported by iTestBed::drawRangeBounds() has been removed.
Changes for release 5.05
Fixed a significant bug in pathfinding preprocess handling for 'preprocessed obstacle sets' which meant that pathfinding against semi-dynamic obstacles in preprocessed obstacle sets was running much slower than it should have been.
Fixed a (hard to reproduce) bug where the advance along path methods could erroneously report collision ahead of actual contact, for a dynamic obstacle further along the path segment being traversed.
Adds 3D content processing!
Documentation for this major new feature can be found here .
getRepresentedRegionsOverlapped() has been added to the mesh federation interface, to support placement of arbitrary dynamic obstacles against individual federation tile meshes.
The default window size for the TestBed has been increased from 640,480 to 800,600.
Fixed a problem with missing additional dependencies in projects in the interface layer archive.
Changes for release 5.04
The SDK now includes support for pathfinding across 'federated' arrays of overlapping
Refer to this page, (in the online documentation), for an overview of the functionality provided.
An example project has been added to the samples workspace, to provide a reference implementation and to demonstrate this feature in action.
have been added for curved path generation with the desired agent orientation
at the end of the path taken into account.
Passing a null pointer into the base path parameter in the generate curved path methods is now handled.
In this case the curved path generation methods will simply return a null pointer for the resulting path.
A method has been added to the testbed for drawing the boundaries of two dimensional ranges.
Fixed a bug in the TestBed where iTestBed::zoomExtents() would not take effect until the end of the frame in which it is called.
Changes for release 5.03
Fixed a bug with the anchor and shapes components of content chunks not being loaded.
Fixed a bug that was causing the positions of agents advancing along paths to jitter,
in certain situations where the contexts used for advancing along the paths included obstructions
not present in the original pathfinding query.
(When using the advance along paths methods with precision components, these precision components would effectively cancel the jitter, and you wouldn't notice this problem.)
Fixed a bug where multiple calls to the PathEngine DLL entrypoint were not being handled gracefully.
(In most cases this would just result in some wasted memory, but using interface objects across calls could result in undefined behaviour.)
Fixed a bug that was resulting in surface types costs being ignored if set for surface type values greater than the number of faces in a mesh.
Fixed a bug that could cause iMesh::positionNear3DPoint() (and related methods) to fail to find a nearby point for certain pathological situations.
This release makes some very significant reductions in memory footprint.
Importantly, the number of allocations made by the SDK on mesh loading and preprocess generation
have also been significantly reduced.
There are also significant speedups for mesh loading, and some general performance improvements across the board.
Obtaining the PathEngine dll entrypoint by name is now depreciated. This should now be done by ordinal.
Refer to this page, (in the online documentation), for details.
The rules for resolution of matching pairs of connecting edges
has been tweaked slightly.
Previously, one of the vertices of the target edge had to fall within the resolve range. Now both vertices of the target edge must fall within this resolve range.
Some additional interface asserts have been added in iMesh::positionNear3DPoint() (and similar) to catch cases where the combination of position horizontal coordinates and horizontal range overflow the support range.
Equality and inequality operators have been added to the cPosition class, in the API heaper. (This may cause compile errors in cases where these are also defined externally.)
Source code packages
The source packages now include Visual Studio solutions (in addition to project files).
The 'Interface Debug' configuration has been removed. This configuration is no longer required now that debug binaries are supplied with the interface layer archive.
A platform specific source archive has been added for Windows x64 platforms.
Source code for the Maya exporter has been added to the full source package.
The Testbed now emits more useful error messages in case of problems loading or starting the Testbed application dll.
Changes for release 5.02
This release adds direct support for split content chains where
objects (such as buildings, bridges and so on) are created on one content platform,
and then later instanced in separate content application.
Refer to this page, (in the online documentation), for details.
iMesh::positionInSectionInShape() has been added to help with resolving a position for object placement, in the case where an obstacle needs to be placed but the natural object origin is off the edge of the mesh.
Changes for release 5.01
Fixed a bug that could cause pathfind preprocess generation to crash for certain situations with off-mesh connections placed.
A bug has been fixed where certain cases involving pathological sliver tris at the edges of a mesh would cause the edge optimisation feature of the content processing to fall over.
A bug has fixed where the content processing would crash in certain cases involving more than one
'non-manifold connection' error.
The content processing will now handle these cases gracefully.
Fixed some memory leaks when working with 'burnt-in' traversal costs.
Fixed a bug that could case pathfinding to hang in certain situations where both dynamic surface type based traversal costs and off-mesh connections are being used.
A bug has been fixed where PathEngine was incorrectly regenerating some pathfinding preprocess
even when the dynamic obstacles included in a context had not been changed.
(This fix will result in slightly faster queries when pathfinding against dynamic obstacles.)
Preprocessed obstacle sets
This release adds support for 'burning in' multiple different sets of obstacles.
Refer to this page, (in the online documentation), for details.
Other API changes
Building entrances may now be marked as 'terrain portals'
(for the content processing functionality).
This makes it easier to place buildings against 'proxy' terrain geometry, or against terrain geometry where stripping out height detail would otherwise make it difficult to ensure that portal markers intersect that geometry.
Refer to this page, (in the online documentation), for details.
Significant performance improvements for first collision queries, and for advancing along paths.
Slightly reduced query overhead across the board.
Changes for release 5.00
Interface breaking changes
Pathfinding queries now return a null pointer in the case of failure, instead of an empty path.
A number of methods have been renamed or removed, to tidy up the interface. A detailed list of the changes made can be found on this page (in the online documentation).
Fixes a bug where the advance along path functionality could be blocked by geometry included in the original pathfinding query, in certain very rare circumstances.
Other API changes
An iObstacleSet interface has been added, for free standing obstacle sets that can then be combined together
by collision contexts.
This makes it easier to manage groups of dynamic obstacles, and also some collision preprocess is cached with each obstacle set, which can be an important performance optimisation for certain situations involving large numbers of dynamic obstacles.
Methods have been added to iMesh to support direct path construction and reversal.
iPath::getConnectionIndexArray() has been added to complement iPath::getPositionArray()
A number methods throughout the API have now been made const, as appropriate in order to provide a consistent and useful constness paradigm at the API level.
Data and preprocess compatability
The path persistence major version has been incremented in this release, so path persistence saved out by previous releases cannot be loaded.
The mesh format generated by releases prior to 4_52 is no longer supported.
Legacy face attribute strings are also unsupported.
(Apart from these caveats, release 5 is fully compatible with existing data files.)
Direct path construction and reversal
Methods have been added to iMesh to support direct path construction and reversal.
Big reductions in memory footprint for pathfinding preprocess on meshes where the 'small convex obstacle' optimisation is being applied.
There are also significant performance improvements across the board.
Changes for release 4_69
Fixes a hard to repeat bug that could result in the following error
getting incorrectly generated when parsing tokenised XML:
"Error parsing tokenised XML, unsupported attribute type."
This was purely a parsing bug and was not indicative of any problem in the data itself.
Fixes a couple of bugs that were causing pathfind preprocess generation to freeze for certain very rare configurations of obstacles.
Release number 4_68
Release 4_68 was an internal release only.
Changes for release 4_67
Fixes a couple of hard to repeat crashes in the automatic building connection feature of the content processing and in pathfind preprocess generation.
Changes for release 4_66
Fixes a serious bug, introduced in release 4_65, in the advance along path functionality.
This bug meant that collisions could be ignored by the built-in advance along path methods.
Fixes a (fairly rare) crash bug in the automatic building connection feature of the content processing.
Changes for release 4_65
Fixed a crash bug that occurred when generating preprocess for certain (fairly rare) configurations of agent shape and internal partitioning.
A wrapper dll is now provided for automatic logging of calls in and out of the API.
Refer to Query Logging (in the online documentation) for more details about this logging functionality.
Changes for release 4_64
Fixed a crash bug that occurred for certain (very rare) configurations involving base obstacles placed with their centre exactly on external vertices.
Fixed a bug where the checksum generated for meshes that are built from content or loaded from a file that does
contain a mapping to 2d differed from the checksum generated when a mapping is loaded.
(This could cause collision preprocess generated prior to saving out a mapping to later fail to load.)
The checksum generated for meshes built or loaded without mapping has been fixed to match the checksum generated for meshes loaded with mapping.
The automatic building connection feature of the content processing has been extended to support 'adjacent portals'.
Refer to this page (in the online documentation) for more details about the automatic building connection feature.
There have been a number of changes to ensure that the source code builds against both GCC 3.3 and GCC 4.0 (on strict settings).
The 'PointTraits' internal static library has been merged into the 'Geometry' internal static library.
Changes for release 4_63
Several crash bugs in the automatic building connection feature of the content processing have been fixed.
A bug has been fixed with the 3DS Max exporter setting the 'userData' face attribute to -1
as instead of the default value of zero.
This was resulting in unecessary data being included in the ground meshes saved out by this exporter.
The exporter has been fixed to set this attribute to the default value.
Significant performance improvements for collision queries on contexts with very large numbers of dynamic obstacles.
An option has been added to iPathEngine::loadMeshFromBuffer_WithOptions() for generating additional partitioning to speed up heightAtPosition() queries (and similar) in the case where ground surfaces contain a lot of internal height detail and the terrain callback mechanism cannot be used.
method has been added to enable content data to be streamed off into a standard snapshot format.
The resulting content snapshots can be included when reporting a bug in the content processing to enable the bug to be repeated very easily.
Changes for release 4_62
There was a bug in release 4_61 that meant that the 'sectionID' and 'userData' face attribute channels were getting switched on mesh save. This has been fixed.
iMesh::clearOffMeshConnectionsAndEndPoints() has been added.
Surface type based regions may now be assigned a cost of -1 to indicate that the regions are impassible.
This may be combined with a direction for the cost to traverse to make regions impassible in the specified direction.
Some performance improvements for pathfinding with limited query scope.
Changes for release 4_61
A bug has been fixed where certain configurations of geometry could cause the content processing to generate zero-area faces when cutting out building external shapes, and then fail.
Support has been added for early termination of the findPathAway() pathfinding query.
The following helper methods have been added for querying the state of off-mesh connections stored with a mesh:
A user data attribute has been added to 3d mesh faces.
Refer to Setting Face Attributes for details about face attributes.
Methods relating to terrain layers have been renamed to reflect the fact that the 'terrainlayer'
attribute has been renamed to 'sectionID'.
The old methods are still included in the API, but have been depreciated and warnings will be issued when calling these methods.
The following methods have been added to support converting to ground position where the section ID for the desired position is known:
Changes for release 4_60
A bug has been fixed that was causing pathfind preprocess generation to fail in certain rares cases involving base obstacles placed with their centre exactly on external vertices.
A bug has been fixed where path lengths were not being correctly loaded from path persistence.
It is now possible to place endpoints and specify that it is possible for agents to move 'off-mesh'
between these endpoints.
The testbed now consumes less CPU time and pauses when minimised.
Changes for release 4_59
Small convex boundaries are now split at pathfind preprocess generation as opposed to
collision preprocess generation.
The attribute may still be specified at collision preprocess generation time, and will be passed through.
iTestBed::drawSmallConvexExpansions() now requires pathfind preprocess to be generation (or will return with no effect).
It is now possible to perform collision queries without agent shape specific preprocess.
Refer to this page (in the online documentation) for details.
Support has been added for aborting pathfinding queries part way through.
Refer to this page for details.
Support has been added for restricting the geometric scope of pathfinding queries.
Refer to this page for details.
The memory footprint for collision preprocess is very significantly lower in this release,
particularly on meshes with lots of base obstacles.
There is also a significant reduction in total footprint for collision + pathfind preprocess.
There is a very significant reduction in collision preprocess generation times.
There is a decent general improvement in collision query times against meshes with lots of base obstacles and against dynamic obstacles.
Changes for release 4_58
A number of hard to repeat bugs involving preprocess failure for rare situations involving jagged mesh edges and large agent shapes have been fixed in this release.
A bug has been fixed where iMesh::positionNear3DPoint() was incorrectly using the value specified for vertical range also for the y component of horizontal range.
A bug has been fixed where iTestBed::drawAgentExpansion() was not correctly drawing the expanded shape for the agent.
There has been a significant speedup for collision preprocess generation in this release.
The collision preprocess major version number has been incremented so stored preprocess will need to be regenerated with this release.
The methods iPathEngine::collisionPreprocessVersionIsCompatible() and iPathEngine::pathfindPreprocessVersionIsCompatible() have been added to enable the client application to determine whether preprocess needs to be resaved after updating to a new release of the SDK.
Changes for release 4_57
A bug has been fixed where preprocess was being shared (behind the scenes)
when generated for iShape instances with identical coordinates.
This was causing problems because releasing preprocess for one of the iShape instances would cause preprocess to also become unavailable for any other instances with identical coordinates.
This issue has been fixed simply by removing preprocess sharing between iShape instances.
In cases where iShape instances are known on the application side to have identical coordinates, these should now be replaced by a single iShape instance.
A bug has been fixed where PathEngine was not recognising the legacy face attribute names:
'surfacetype' and 'terrainlayer'.
(These were renamed to 'surfaceType' and 'sectionID' in the recent mesh format change.)
This meant that face attributes in legacy meshes were being ignored.
These legacy face attributes should now be recognised correctly.
(But note that support for both the legacy mesh format and these legacy face attribute names will be removed in version 5.)
A bug has been fixed where preprocess generation could fail in certain (rare) situations.
Changes for release 4_56
A bug has been fixed where iMesh::generateRandomPositionLocally() could consistently fail in certain situations where the range specified was much smaller than the sizes of the faces local to the request.
Some issues with building the interface layer source code have been addressed.
The 'Interface Debug' configuration has been modified to link against debug builds of the core components, which are now included as binaries in the interface layer package archive.
The configuration suffixes have been modified to include an initial underscore.
Changes for release 4_55
A bug has been fixed where preprocess generation would crash in the case where an expanded base obstacle completely contained the ground on which it was placed. (In practice this would be most likely to happen if you are generating meshes in a way that results in the creation of small and unconnected fragments of mesh.)
Significant improvements in the time taken to generating 'mappings to 2d',
particularly for large meshes.
Improvements, also, in preprocessing times.
Changes for release 4_54
A bug has been fixed where iMesh::findClosestUnobstructedPoint() and iAgent::findClosestUnobstructedPoint() would crash if a 0 was passed in for the context argument.
iPathEngine::loadMeshFromBuffer_WithOptions() has been added, to enable options to be passed in to affect the mesh loading process.
PathEngine now supports 2D mappings with internal vertices.
This solves a problem where performance could suffer for meshes where the external edge detail does not generate sufficient partitioning. (For example in the case of a simple big square mesh with lots of base obstacles.)
Options can be provided to iPathEngine::loadMeshFromBuffer_WithOptions() to partition the 2D mapping by base obstacle centres, or to build a mapping directly from the 3d base mesh partitioning.
Changes for release 4_53
Interface breaking changes
A subtle change has been made to the geometric model applied at face boundaries
and external edges of meshes with this release.
This enables the simplification of some key algorithms and significant benefits in terms of reductions in both code complexity and performance.
The practical and immediate implication of this change from an application point of view is
that some stored cPositions may be invalided by this version.
If you are using cPositions persistently then any saved positions may have been invalided (for some cases where the positions fall exactly on face boundaries). In general, then, saved positions will need to be converted to the new model. A convertLegacyPosition method has been added to the iMesh interface in this release to provide this conversion.
It is possible, also, for positions of content features saved out with release 4_52 to be invalidated by this change. If so then you will be warned about this on loading, and will need to resave or regenerate the relevant mesh from content.
Pathfind preprocess stored from release 4_52 will need to be regenerated for this release.
The content processing functionality behind the 3DS Max exporter has now been moved into
the main API.
For situations where ground meshes need to be generated programmatically this provides a much more elegant and efficient way of achieving this, whilst at the same time providing a lot of additional functionality including the possibility to automate connections between mesh pieces.
Refer to Content Processing Functionality (in the online documentation), for details about the new functionality.
Constraints on 'burnt in' obstacles removed
All constraints on burnt in obstacles have been removed with this release.
(Previously it was not possible to burn in large obstacles that completely enclose features such as holes in the mesh. Now obstacles placed at any position may be burnt in for preprocess generation.)
A hard to repeat bug which could cause a crash in pathfinding queries against
certain situations with small convex obstables has been fixed.
A bug that would cause collision preprocess generation to crash for certain configurations of base obstacles has been fixed. Constraints on burnt in obstacles were not being checked correctly in release 4_53. This is no longer a problem because these constraints have now been removed (see above).
The documentation has been significantly updated and reorganised for this release.
Changes for release 4_52The focus of release 4_52 is a redesign of the mesh file format, but this also introduces some changes to the way automatic building connections are processed, and includes some optimisations.
Interface breaking changes
The mesh file format has been changed for this release,
resulting in some very significant reductions in file size.
Base meshes can be loaded from the legacy format by this release and then saved into the new format, but content information such as base obstacles and anchors will be stripped during this process, so if you are using this kind of content then you will need to reexport or regenerate meshes from content.
The path persistence and saved preprocess major version numbers have been incremented with this release, So paths and saved preprocess will need to be regenerated.
Significant reduction in mesh file sizes.
Significant reduction in code size for the pathengine dll.
Improvements in preprocessing and query times for meshes with lots of building external shapes.
Release numbers 4_50 and 4_51
Releases numbers 4_50 and upwards will be used to make a serious of interface breaking changes in preparation for release 5.0.
Releases 4_50 and 4_51 were internal releases only.
Release numbers 4_34 through 4_49
Reserved for upgrades to a stable branch based on release 4_33.
Changes for release 4_33
Helper functions have been added to support accessing information about the underlying 3d mesh.
( iMesh::get3DFaceAtPosition() , and iMesh::getGroundNormal() )
Changes for release 4_32
A (difficult to repeat) bug was fixed where accessing paths from multiple threads could cause a crash.
A bug was fixed where generating curved paths in multithreaded applications could cause a deadlock.
(Neither of these would affect you if you are not using multithreading.)
No error was being generated when parsing a truncated tokenised XML file.
(The parser would then silently close all open elements at the point of truncation.)
An error is now generated correctly for this case.
Helper functions have been added to support drawing paths and lines along the surface of
the 3d ground mesh.
(Enabling visualisation similar to provided in the testbed to be added to your own 3D engine.)
(See iMesh::renderLineOnGround() , and iPath::renderOnGround() for details.)
Changes for release 4_31
Fixes some multithreading bugs relating to adding or removing agents simultaneously to or from a context shared between threads. (This would not affect you if you are not using multithreading, or if you are not sharing collision contexts between threads.)
Changes for release 4_30
Fixes a hard to repeat bug in findClosestUnobstructedPoint.
Fixes a couple of multithreading bugs for situations with multiple threads operating on a shared collision context. (This would not affect you if you are not using multithreading, or if you are not sharing collision contexts between threads.)
A helper function was added for obtaining the number of terrain layers allocated for a given mesh.
The source is now built in VC.net, so source packages now include VC.net rather than VC6 project files.
Changes for release 4_29
Fixes a bug in releases 4_27 and 4_28 when storing 'named obstacles'
with ground meshes AND saving into tokenised xml.
Any tokenised xml meshes saved out by these versions will need to be re-exported.
Fixed a bug (also in releases 4_27 and 4_28) where named obstacles in meshes saved by code prior to release 4_27 were being incorrectly loaded as soft obstacles.
Fixes a bug where if no anchors were placed then fixed obstacle would not be saved.
Interface layer source package
This package now also includes a full debug build of the PathEngine dll.
Changes for release 4_28
Fixes a difficult to repeat bug which meant that findClosestUnobstructedPoint() could get stuck in an infinite loop for certain rare combinations of obstruction geometry and underlying mesh structure.
Changes for release 4_27
Support has been added for representing regions with cost to traverse.
These can be added as 'soft obstacles', or directly associated with regions in the base mesh.
It is possible to associate a direction with a traverse cost.
The following methods have been added to support this functionality:
Changes for release 4_26
PathEngine is now completely threadsafe,
and some important multithreading guarantees have been made with respect to blocking.
Changes for release 4_25
Fixed a bug related to collision preprocess generation for certain very rare configurations of obstacles.
Fixed a bug where zero length path sections could be generated for certain situations with small convex obstacles turned on.
The movement overhead for agents that are included in pathfinding contexts has been drastically reduced.
Very significant reduction in the memory footprint for large meshs or meshes with lots of detail objects.
Changes for release 4_24
Fixed another hang in the curved path generation.
The iPath methods
are now replaced with
The old versions have been left in place, but are depreciated.
Changes for release 4_23
A bug was fixed where curved path generation would hang in some situations where the start vector was exactly opposite to the first path segment in the base path.
A subtle bug in mesh was fixed in traversal through 3d meshes. This would have caused an assertion to be triggered in certain (pretty rare) circumstances when using the testbed drawline.
Changes for release 4_22
Methods added for saving and loading mesh related preprocess to and from persistence:
iMesh::saveCollisionPreprocessFor() , iMesh::savePathfindPreprocessFor() , iMesh::loadCollisionPreprocessFor() , and iMesh::loadPathfindPreprocessFor() .
Source for the XML and tokenised XML parsing libraries have been added to the interface layer package.
Playable demo source code
The source code for the playable demo is now provided.
Changes for release 4_21
A bug has been fixed where iMesh::positionFor3DPoint() would sometimes fail to resolve points exactly on the right edge of a face.
In previous releases
would crash if it was called after iMesh::preprocessGenerationCompleted().
A note about this constraint has been added to the documentation and an interface check has been added to the method.
Some speedups in iPathEngine::loadMeshFromBuffer() , in particular for the case where tokenised xml is being used.
Changes for release 4_20
A bug has been fixed where iAgent::testCollisionTo_XY() and iMesh::testLineCollision_XY() were not correctly handling the case where the end coordinates passed in were exactly equal to the agent's current position.
A bug has been fixed where shape validation was not catching shapes with in-line edges.
Methods added to the testbed for loading and displaying splash images.
Changes for release 4_19
Support has been added to the API for representing terrain detail outside of
The behaviour of iAgent::advanceAlongPath()
has been changed slightly.
The methods now advance across path sections, instead of stopping at the end of each path section.
This can significantly improve the quality of movement for the case where large units are chosen for PathEngine coordinates.
has been added.
This is useful for straightforward implementation of various behaviours based on random selection and assessment of nearby points.
is depreciated as of this release, and will be replaced by
which returns a floating point result.
A version taking additional float arguments for extended precision, iMesh::heightAtPositionWithPrecision()
Testbed performance improvements
An optimisation was added to significantly speed up the rendering of stationary agents.
Changes for release 4_18
A bug has been fixed where iAgent::testCollisionAgainstShape() would return incorrect results.
A bug has been fixed where
would return incorrect results for some situations involving dynamic obstacles overlapping small convex obstacles.
was not checking for the (fairly rare) circumstance where an agent contains a loop in the external shape of the mesh.
This checking has now been added.
If you attempt to load a mesh that was generated before this checking was added and that had circuits burnt in that were affected by this rare circumstance, you'll get a non fatal error telling you to re-export the mesh and the base circuits will be ignored.
A bug has been fixed that was causing curved paths to be leaked if you didn't delete them explicitly.
A bug affecting the quality of movement resulting from iAgent::advanceAlongPath() was fixed.
Significant performance improvements in iMesh::findClosestUnobstructedPoint() and iAgent::findClosestUnobstructedPoint() for queries on contexts that change frequently.
This does the same thing as iAgent::advanceAlongPath() , but provides extra precision components of the agent's position.
Adding this extra precision when rendering can improve the perceived quality of movement when the units chosen for pathfinding coordinates are quite large.
This is functionally equivalent to the methods above, but doesn't require the creation of an iAgent.
Note, however, that you are recommended to use iAgent wherever appropriate to take advantage of future optimisations based on caching information with the iAgent.
Added some testbed methods, also, to include extra precision when drawing agents and setting camera position.
Changes for release 4_17
Change to collision model
The collision model for dynamic obstacles has been changed subtly for this release.
The change specifically relates to the way that the influence of obstacles overlapping the edge of a mesh is applied to the surrounding mesh.
Previously, the base shape of a dynamic obstacle was used to determine whether or not nearby pieces of a mesh are influenced. Now this is determined by the obstacle's expanded shape.
In practice this change is very unlikely to have any effect in real situations. The reason for the change is that this eliminates the need for dynamic obstacles to be 'expanded' against the mesh after the set of containing faces has been resolved. This then makes it possible for the dynamic obstacle collision to run a lot faster.
for resolving points near to but not directly above the ground mesh.
This is useful for resolve targets from clicked points, managing interactions between pathfinding agents and objects moving under full 3d collision, and so on.
There is some speedup with this release for pathfinding with dynamic obstacles, but note that the code does not yet fully take advantage of the collision model change and this will lead to more significant improvements in the future.
Changes for release 4_16
A bug was fixed where the queries returning the cell at the end of a line would crash if the line exited the mesh.
A bug was fixed where the intersecting line in iCollisionInfo could be incorrect in certain cases.
A bug was fixed with iAgent::testCollisionAt() returning incorrect results in some circumstances where the agent a member of the context being applied.
Added getAllAgentsOverlapped() query to iMesh and iAgent.
This makes it more convenient to drive logic based on agents overlapping each other, for example agents being over floor switches and so on.
Added the ability to save placed agents out with meshes in the same way as anchors.
This supports a 'fixed obstacles' feature in the max exporter and can be used in the same way with custom content editors.
Added the ability to iterate through the sets of anchors and fixed obstacles associated with a mesh.
Added support for a basic chase camera.
Added support for additive blending.
Added a check for whether the mesh is obstructing the camera.
Changes for release 4_15
There are significant performance improvements for collision queries against dynamic obstacles.
Specifically the overhead for regenerating collision preprocess after dynamic obstacles are moved has been greatly reduced.
You can now specify the window size as a parameter when starting the testbed, for example: "testbed.exe windowsize=800,600".
Changes for release 4_14
The signature for iMesh::getSurfaceType has been corrected from:
virtual long getSurfaceType(cPosition& position)=0;
virtual long getSurfaceType(const cPosition& position)=0;
This should not have any affect on backward linkage to version 4_13.
Methods iMesh::storeAnchor() and and iMesh::retrieveAnchor() have been added to enable named positions to be associated with meshes during content generation.
Helpers iPathEngine::shapeIsValid() and iPathEngine::getErrorHandler() added.
Changes for release 4_13
Polygons in ground meshes can now be assigned surface types.
iMesh::getSurfaceType() has been added to query this value for a given position.
This release makes significant performance improvements pretty much across the board.
In particular, the point collision queries are now a great deal faster for contexts including a number of dynamic obstacles.
Changes for release 4_12
A bug has been fixed where PathEngine would crash in some situations where the small convex optimisation was turned on and dynamic obstacles were placed around small convex obstacles.
A bug has been fixed where iMesh::getRandomPosition() would (very rarely) return an invalid position.
A bug has been fixed where PathEngine would crash for certain (very rare) configurations of obstacles.
A bug has been fixed where the point collision queries could return incorrect results for rare configurations of obstacles.
Stress test added
A stress test has been added to the example projects
('pathstress' in the samples workspace that comes with the SDK).
Helper method iTestBed::drawAgentsInContext() added.
iPathEngine::newShape() has been changed to emit non-fatal errors and return zero if the shape passed in does not pass the validation constraints.
Changes for release 4_11Note that pathengine.dll in release 4_11 as originally uploaded was broken.
The bad version of pathengine.dll had the build string "2004-01-15 16:07:23 190".
The fixed version has the build string "2004-01-18 20:04:30 911".
(Use iPathEngine::getVersionAttributes() to check the build string.)
A bug has been fixed where iCollisionContext::getCollidingAgent() would always return zero. This bug was causing the agents in the swarm example to get stuck.
A bug has been fixed where findPathAway() would crash on some maps.
iMesh::positionFor3DPoint() and iMesh::positionFor3DPointF() are now much faster on large meshes.
Significant reductions in the memory footprint for pathfinding preprocess.
Improvements in the way pathfinding queries scale with respect to the number of
dynamic obstacles placed.
findPathAway() now scales much better with respect to mesh size and visibility.
Meshes load a lot faster. Preprocess generation is bit faster.
Changes for release 4_10
A bug was fixed where findPath() or findPathAway() would hang if the end of a path was inside the expanded region for a small convex obstacle (and if the small convex optimisation was turned on).
A bug was fixed that would have caused problems in some situations where dynamic obstacles were placed around small convex obstacles (with the small convex optimisation turned on).
Changes for release 4_9
Fixed a major bug with the small convex optimisation in release 4_8 where
small convex boundaries were getting split off but not later taken into
account correctly in some collision and pathfinding queries.
This bug didn't affect functionality when the small convex optimisation was not being used.
Added helper methods to later query the set of attributes used when generating preprocess. See iMesh::getCollisionPreprocessAttributes() and iMesh::getPathfindPreprocessAttributes() (in the online docs), for details.
Peformance for point and line collision queries is improved when called with a context including dynamic obstacles.
Changes for release 4_8
New versions of the preprocess generation methods have been added to allow
arbitrary sets of attributes to be passed in to control the preprocess generation.
See iMesh::generateCollisionPreprocessFor() and iMesh::generatePathfindPreprocessFor() (in the online docs), for details.
Memory tracking instrumentation has been added in the standalone dll.
An optimisation that targets situations with lots of obstacles but open visibility
is now available and controlled by passing an attribute when generating collision preprocess.
Preprocessing times in general for complex maps have been significantly improved.
Burning obstacles in to a mesh's 'base circuits'
It is now possible to burn obstacles in to a mesh's 'base circuits' before generating preprocess.
Obstacles burnt in in this way are treated as permanent obstructions and included in the preprocess.
The cost of pathfinding around these obstacles will then be similar to the cost of pathfinding around obstacles manually cut out of a mesh.
Random position generation
A method has been added to iMesh for generating random positions and a method added to iPathEngine for seeding an internal pseudo-random sequence.
The speed benchmark has been changed to use random position generation
instead of a predefined set of positions.
In addition to 'flatshead_dungeon', the benchmark now also runs against the basic 'mesh1' and against a new mesh taken from Mutable Realms' forthcoming MMORPG.
A memory benchmark has been added ('memory' project in the samples workspace).
Testbed performance improved
The iTestBed methods drawMeshEdges(), drawMeshExpansion() and drawBaseCircuits() run a lot faster in this release.
Changes for release 4_7
An internal release.
A bug has been fixed where PathEngine would crash after reporting the error, in the case of an error parsing XML during mesh loading.
A bug has been fixed where iTestBed->positionAtMouse() would return invalid positions if called more than once per frame.
The findClosestUnobstructedPoint() queries (in interfaces iMesh and iAgent) have been reworked, and are now much more robust and also a lot faster.
Changes for release 4_6
This release marks a shift of focus towards performance.
A simple benchmark has been added and some core functionality is now running at a reasonable speed.
Pathfinding is running a lot faster now, and scales better to larger maps.
A simple benchmark has been added to the samples.
Currently this focuses on calling findPath() for long distance paths, without any dynamic obstacles added.
A bug has been fixed where PathEngine would sometimes ignore invalid connections without reporting this as an error.
The samples are now in a (VC6) workspace.
Changes for release 4_5
A bug has been fixed where iMesh->findShortestPath() would crash for very large meshes.
A bug has been fixed where PathEngine could crash if you deleted the shape used to place an agent before deleting that agent.
A bug has been fixed where iMesh->heightForPosition(), iMesh->positionFor3DPoint() and iMesh->positionFor3DPointF() could crash in certain rare situations.
Mesh constraints removed
Two of the main constraints on ground meshes have been removed.
This removes a lot of hassle from the process of creating ground meshes.
The constraint on external angles has now been completely removed.
Height differences are now permitted across connections, which enables explicit representation of staircases.
XML files may now be passed in to PathEngine in tokenised form. This greatly reduces the size of the files and buffers required.
saveGround() added to iMesh
This essentially just saves the ground mesh with which the iMesh object
It is possible to save the ground mesh in tokenised form, and to record a 'mapping to 2d' for that mesh, which ensures that cPositions for that mesh will not be invalidated when new versions of PathEngine generate that mapping differently.
Generation of mapping to 2d changed
This essentially means that cPositions obtained from previous versions
of PathEngine will be invalidated.
In future you will be able to use the saveGround() function above if it is necessary to prevent this happening.
Preprocess generation now runs a lot faster,
and scales better with larger maps.
Performance for pathfinding and collision queries is also improved.
(But note that much bigger speedups are expected in the near future.)
Since version 4_4, the PathEngine code base has benefitted from application
to various real world situations.
In particular, application to a massive world (for a MMORPG) has provided some very good stress testing.
The regression sets have grown significantly since version 4_4, and the core functionality should now be very robust.
Testbed camera control
Panning has been improved to work like dragging the mesh around with the mouse.
Also, camera target distance is set after panning corresponding to the dragged point. (So subsequent rotation is more intuitive.)
Changes for release 4_4
iMesh::findPathAway() and iAgent::findPathAway() were pretty badly broken in 4_2 and 4_3 :( Fixed now, and regression tests added.
Fixed a bug in the integer maths that resulted in PathEngine behaving badly for meshes close to the maximum allowed size.
The generateCurvedPath() function has been added to the iMesh and iAgent interfaces.
Tutorial 3 has been modified slightly to use the generateCurvedPath() method.
Validation errors that can occur in iMesh::loadMeshFromBuffer() have all been made NonFatal.
This makes the function much more useful for reporting feedback about validation errors.
Changes for release 4_3
Fixed a bug where iTestBed::positionAtMouse() would incorrectly return positions on overlapping geometry (but at the same x,y as the correct position).
Iterating through agents in a context
Helper functions were added to iCollisionContext for iterating through agents in a context.
Changes for release 4_2
findClosestUnobstructedPoint() query added
This query has not yet been exhaustively tested and will be fairly slow at the moment.
The query is made available in this release because it represents important functionality for
Fixed a bug where the array returned by iPath::getPositionArray() would be invalid after advancing along a path a large number of times.
Fixed a bug where certain configurations of agents touching corner to corner were incorrectly reported to be in collision.
iPath objects were not being automatically destroyed when the mesh they were created
on was destroyed,
or when iPathEngine->deleteAllObjects() was called.
This has been fixed.
A certain number of paths are now cached in a pool to avoid allocation on the heap.
Each path also reserves a certain number of points.
The method iPathEngine::setPathPoolParameters has been added to provide control of this behaviour.
Associating user data with cAgent
Functions have been added for setting and retrieving void pointer user data for
a given agent.
Testbed camera control
Added dollying (hold left shift and '3').
Also a cross is now displayed at the camera target whilst camera control is active.
Better camera controls will follow, but these changes do make the camera a lot more useable for zooming right up to the mesh.
Changes for release 4_1
Another maintainence release.
Minor release numbers added
This makes it easier to talk about the next 'major' release.
The number returned by getReleaseNumber() and in the "release" attribute returned by getVersionAttributes() now describes the 'major' release.
getVersionAttributes() now also returns a "minor_release" attribute.
Large ground meshes
iMesh::loadMeshFromBuffer() was extremely slow for very large meshes.
(For a ground mesh with something on the order of 10000 tris for example.)
This has been much improved for this release.
Note however that performance for large meshes is still far from target performance and this will continue to improve.
Fixed a bug where iMesh::positionFor3DPoint would sometimes return a bad position.
Fixed a bug where certain (rare) combinations of mesh and agent shape would cause a crash.
pathengine.dll will now abort following return from the error handler for a 'Fatal' error.
The dll for earlier releases would enter an infinite loop.
The testbed error handler has been improved.
You can now tell the error handler to ignore by error code.
A warning has been added to catch floating point values for vertex coordinates in a mesh file.
Vertex coordinates are treated as integers by PathEngine.
This file has been removed from the bin directory.
Instead you can now run testbed.exe without direct input by passing "notdinput" as a command line argument.
Changes for release 4
Release 4 is essentially a maintainence release and contains no significant new functionality.
A bug where certain combinations of collision queries and placing and removing agents would cause a crash has been fixed.
A bug where certain (rare) mesh configurations would expand incorrectly has been fixed.
Coordinates range for the mesh is increased to 18 bits (-131071 to 131071)
Maximum edge length constraint is added. Range for edges is set to 14 bits (-8191 to 8191). (This is to enable boolean operations involving faces to be performed exactly in 128 bits.)
Coordinate range for agent shapes is set to 14 bits (-8191 to 8191).
In release 3, the distance parameter for this function was being truncated internally to an integer before being applied.
So actual speed of movement along the path was limited to integer values. And at speeds less than 1, the agent would not move at all.
This parameter is no longer truncated internally, so the advanceAlongPath() function will behave a lot better for low speeds.
Checking whether an agent is in a context
The function iCollisionContext::includes(iAgent*) has been added to the interface.
This function tells you whether the specified agent is currently included in the specified context. This saves the client application from having to record this information.
Testbed performance has been improved.