I posted this same thread in the DarkGDK forum awhile ago looking for feedback, but its gotten only a few responses there so I thought I would try the WIP forum. Basically It's just what the title says, a 3D pathfinder for DarkGDK that projects object's onto the XZ-Plane and generates a node network to be used with the A* algorithm. Feedback or testing would be great and much appreciated.
Current Version: V1.2
- Revamped the debug system. Now uses cloggy's 3d line drawing program and updates debug images in real-time with negligible lag
- Fixed several floating point precision problems that resulted in improper path calculations along polygon boundaries
- Rewrote and created 4 new example programs (modeled off the DarkAI plugin example program) that demonstrate different program features
- Optimization of internal geometry functions
DOWNLOAD
V1.1 Updates:
- Added a getValidLocation function to validate a point inside a polygon and enable sliding collision for objects travelling along sharp edges.
- Added an overloaded function updateObjectConvexFrame( int object, float low, float high ) that generates a bounding polygon for the region from low to high.
- Fixed the bug in the private function AstarFind that resulted in longer than required paths
Note: The GPC addons have been phased out because of implementation issues. As a result, non-convex frames cannot be generated. This feature will be reimplemented later using my own algorithm.
Below is a list of general features and the status:
= done with no extensive testing or nearly complete
= in progress
= haven't begun
= phased out
polygon projection for objects
support for different object FVF types
user specifiable polygons for objects
non-object linked polygons allowed
polygon for object based on convex hull polygon
waypoint generation from object's polygon frames
waypoint viability checking
inter-waypoint mapping
waypoint optimization
( removal of illogical connections )
Pathfinding algorithm ( working great
)
multiple radius grid generation
force start/target point out of polygon
( Doesn't work with overlapped polygons )
specifiable height range to check for collision
with objects ( convex only )
forced basic polygon frames
( ie. set frame to box/circle/ellipse)
automatic input polygon direction detection
( cw obstacles / ccw bound )
non-convex polygon generation
inclusion of multiple polygons for single objects
user level manipulation/addition of map points
ability to include object limbs in frame generation
generate convex hull for clusters of objects
setup binary heap for pathfinder's sorted list
gpc implementation
Download:
The OFFICIAL V1.2 download is available below. From this point, any subsequent release of V1.x will be compatible with the original V1.0 release. To use the pathfinder in your own projects, you must include the pathfinding.h header file as demonstrated in the example. The program has had no extensive testing and is not guaranteed to work as intended on other systems.
Reported Bugs:
Entities following a path along a bounding polygon edge are recognized as inside the polygon, as such attempts to find paths result in longer than required paths or a null return route.
Collinear vertex removal fails to remove certain vertices
When finding a path along a polygon boundary the entity recognizes the target node as visible
Screenshots:
"Real-Time Debug Display"
"Individual Object Display"
"Multiple Radius Grids"
"Height Range Clipping"
