Not logged in, Join Here! or Log In Below:  
News Articles Search    

Submitted by Thomas Young, posted on November 20, 2012

Image Description, by Thomas Young

Great to see flipcode active again!

I posted an IOTD many years ago in the early days for PathEngine (link) and I thought it could be cool to show a bit about how things have moved on since that post.

Here are a couple of screenshots, then, showing a new feature we just added to PathEngine (unobstructed space optimisation).

Both screenshots show part of the pathfinding environment as represented by PathEngine for our 'Thainesford' benchmark mesh.

(This benchmark mesh was actually taken from the MMORPG project 'Wish', many years ago, and it's quite cool, I think, that the SDK still works against this benchmark mesh, although with much smaller memory footprint and faster query times. In the screenshots you can see a graveyard, some buildings with interiors, and part of the Thainesford city walls.)

The top screenshot shows what pathfinding boundaries look like with the new feature turned on, i.e. with boundaries optimised. The bottom screenshot shows the same boundaries without optimisation.

PathEngine's unobstructed space boundaries are essentially just an expansion of the various environmental features that are intended to obstruct agent movement (mesh external edges and placed obstruction shapes), by a kind of 'minkowski sum' expansion operation. The advantage of this kind of expanded representation is that PathEngine's core runtime collision and pathfinding queries can then be performed for points at agent origin (and lines in the case of linear agent movement), which makes things a lot easier to implement (and faster!).

By default PathEngine performs an exact expansion, with the unobstructed space boundaries then actually being an exact set of positions at which the specified agent shape can be placed without overlapping obstruction features. For some use cases this exact expansion can be quite an important feature, but in other situations this may not be necessary.

In the Thainesford mesh quite a lot of obstacles have been placed into the environment by world creators, essentially by hand, and don't tend to line up exactly, so the exact expansion includes quite a lot of detail corners that may not strictly be desirable at a behavioural level. PathEngine does a reasonable job of optimising this kind of detail for fast pathfinding (e.g. with 'silhouette' optimisations), but these extra corners do inevitably add complexity to run time data structures and operations.

When enabled, the optimisation works by building a 2D mesh representation of the unobstructed space and then repeatedly collapsing vertices on this mesh representation, where this can be done without invalidating the unobstructed space (e.g. introducing self overlapping) and within a specified maximum error threshold.

The devil is in the details however, and it turns out that this is something that is very tricky to implement robustly, in particular because:

* many unobstructed space corners are actually line intersections, which need to be either represented exactly, or approximated (see the following page for some discussion of this point)

* pathological configurations of unobstructed space where expanded obstacle boundaries touch exactly but do not overlap need to be handled correctly

* obstacles placed around overlapping ground layers need to be handled correctly and the resulting optimised unobstructed space must remain valid with respect to overlapping ground layers

Some benchmarks for the Thainesford mesh with and without unobstructed space optimisation can be found here) (Turning on the optimisation currently gives us about 40% reduction in agent shape preprocess memory footprint and about 30% reduction in run time pathfinding query times for this mesh.)

Note that there's another important optimisation, the 'small convex obstacle optimisation', also visible in the screenshots. In this case, a bunch of boundary loops (shown here in yellow) are split off from the rest of the unobstructed space and treated separately. These small convex regions are excluded from PathEngine's core pathfind space representation, and from the pathfinding search graph, with paths coming out of the search pushed around the regions as a subsequent post process operation. (This is something that was extended earlier in the year to also apply to clumps of obstacles that form together into local boundary loops, and some such clumps can be seen in the screenshot.)

Also visible in the screenshots, note that the position representation is independant from the state of placed obstacles and agent unobstructed space, and exactly the same position values are then being used in both cases.

Some more details about the optimisation can be found on the following page (in the PathEngine online docs)

(More details about the small convex optimisation can be found here)

A 'testbed only' version of the SDK is still publically available on the PathEngine website, with source code for the demos and examples, so it is still possible to play around with this stuff to some extent without an official evaluation account for the SDK.

Image of the Day Gallery


Message Center / Reader Comments: ( To Participate in the Discussion, Join the Community )

November 21, 2012, 03:51 AM

Cool its good to see a new image of the day again.


December 11, 2012, 07:50 PM

Image sucks. Blue screens are so sold. Move on etc.

This thread contains 2 messages.

If you'd like to post a comment on this discussion thread, please log in or create an account.

Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.