Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

Dark GDK / WIP A* Pathfinding Algorithm

Author
Message
luke810
17
Years of Service
User Offline
Joined: 4th Sep 2006
Location: United States
Posted: 13th Sep 2009 23:16 Edited at: 23rd Oct 2009 05:23
Link
This is a work in progress thread for an implementation of the A* pathfinding algorithm I'm working on in DarkGDK. I thought there might be some people interested in the forum so here it is:

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 that demonstrate different program features
- Optimization of internal geometry functions

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"


Attachments

Login to view attachments
Back to top
Profile PM
luke810
17
Years of Service
User Offline
Joined: 4th Sep 2006
Location: United States
Posted: 13th Sep 2009 23:22 Edited at: 23rd Oct 2009 05:19
Link
IGNORE: SCREENSHOT ATTACHED

Attachments

Login to view attachments
Back to top
Profile PM
luke810
17
Years of Service
User Offline
Joined: 4th Sep 2006
Location: United States
Posted: 14th Sep 2009 02:54 Edited at: 23rd Oct 2009 05:20
Link
IGNORE: SCREENSHOT ATTACHED

Attachments

Login to view attachments
Back to top
Profile PM
Mireben
15
Years of Service
User Offline
Joined: 5th Aug 2008
Location:
Posted: 14th Sep 2009 21:54
Link
This is certainly a very useful project. I'll be interested to see how you use the projected polygons in the pathfinding algorythm.
Back to top
Profile PM
luke810
17
Years of Service
User Offline
Joined: 4th Sep 2006
Location: United States
Posted: 14th Sep 2009 23:56 Edited at: 23rd Oct 2009 05:13
Link
Quote: "I'll be interested to see how you use the projected polygons in the pathfinding algorithm.
"


The edges of the projected polygons act as the projection points for the individual way-points in the "grid." I just project a specified object size out from the polygons vertices and create waypoints there. Although there is a little more collision checking involved to determine the viabilty of each point as a waypoint because it might be too close to another polygon.

You can probably find something about it online because it looks as though the DBP addon DarkAI does it this way also, but I don't have any references to specific websites.

Attachments

Login to view attachments
Back to top
Profile PM
luke810
17
Years of Service
User Offline
Joined: 4th Sep 2006
Location: United States
Posted: 22nd Sep 2009 06:39 Edited at: 23rd Oct 2009 05:20
Link
IGNORE: SCREENSHOT ATTACHED

Attachments

Login to view attachments
Back to top
Profile PM
luke810
17
Years of Service
User Offline
Joined: 4th Sep 2006
Location: United States
Posted: 29th Sep 2009 23:40 Edited at: 23rd Oct 2009 05:14
Link
A new screenshot. The two next to each other show the effects of the waypoint route optimization. I don't think that the DarkAI pathfinding does this, but it removes any routes the would never happen, such as a route between to corners in a 4 way corridor.

Attachments

Login to view attachments
Back to top
Profile PM
Mireben
15
Years of Service
User Offline
Joined: 5th Aug 2008
Location:
Posted: 1st Oct 2009 23:29
Link
Nice work! It's impressive how the extra routes are removed with optimization.

I'm interested in understanding the method and later, hopefully applying it in a program. That may be far in the future since I haven't reached that point in any game yet when an AI would be needed, but it's a "good to know" thing.
Back to top
Profile PM
SFCBias
14
Years of Service
User Offline
Joined: 8th Aug 2009
Location: Hephzibah, GA, USA
Posted: 2nd Oct 2009 02:27
Link
How much would this cost? Or will it cost?
Back to top
Profile PM
luke810
17
Years of Service
User Offline
Joined: 4th Sep 2006
Location: United States
Posted: 2nd Oct 2009 05:01
Link
No, I intend for it to be free but it will probably be another week at least before I get the "beta" version ready for testing. All I have left in order to make it functional is the actual pathfinding algorithm implementation but I have alot of tests coming up in school. I'm glad you're interested

@ mireben

I was impressed with how many paths got removed after checking the angles of the waypoint routes too. I saw a paper on line in which someone had noted that certain paths would never happen if a path was the shortest it could be, and after some work I noticed that any point with a "line of sight" on both side of the other vertex would never need a path to the vertex in question because it could already see everywhere it needed to.

Back to top
Profile PM
SFCBias
14
Years of Service
User Offline
Joined: 8th Aug 2009
Location: Hephzibah, GA, USA
Posted: 3rd Oct 2009 16:58
Link
Yes, im VERY interested in a project like this because i cant figure out anything this complex so anyone that is willing to make it easier for all of us is O.K. in my book
Back to top
Profile PM
luke810
17
Years of Service
User Offline
Joined: 4th Sep 2006
Location: United States
Posted: 9th Oct 2009 19:58
Link
I've just updated the first post with the new pictures. Finally got the path finder component completed, so I will be finalizing and working out some of the major bugs tonight and tomorrow. I'm going to try and post a beta version up tomorrow for bug testing if I get that much done. Sorry the path is hard to see, but unlike darkAI's pathfinding I haven't really put any effort into making a graphical display of the program's internal stuff.

Attachments

Login to view attachments
Back to top
Profile PM
SFCBias
14
Years of Service
User Offline
Joined: 8th Aug 2009
Location: Hephzibah, GA, USA
Posted: 10th Oct 2009 17:26
Link
lol I dont care , im going to try to be the first to test it
Back to top
Profile PM
Hassan
14
Years of Service
User Offline
Joined: 4th May 2009
Location: <script> alert(1); </script>
Posted: 10th Oct 2009 19:28
Link
the project seems cool

Back to top
Profile PM Website
luke810
17
Years of Service
User Offline
Joined: 4th Sep 2006
Location: United States
Posted: 10th Oct 2009 22:14 Edited at: 10th Oct 2009 22:17
Link
OK, I've uploaded my most current version of the pathfinder. Although there's still a ton of work to be done on optimization and other features, the basic functionality of the program can be tested if you want to test it. I appreciate any feedback, the download is attached to the first post.

Back to top
Profile PM
SFCBias
14
Years of Service
User Offline
Joined: 8th Aug 2009
Location: Hephzibah, GA, USA
Posted: 11th Oct 2009 02:19 Edited at: 11th Oct 2009 02:39
Link
Great , Im dl now.

EDIT: I get a nice APPCRASH when i try to run it .
EDIT EDIT: I just debugged it and it ran fine
EDIT EDIT EDIT: Very Impressive , runs smoothly it seems somewhat(but not too ) complicated as far as implementation.

if(You.AddCode.toPost)TGC.Users.CanHelp = true;
else return NoCodeMessage;
Back to top
Profile PM
luke810
17
Years of Service
User Offline
Joined: 4th Sep 2006
Location: United States
Posted: 13th Oct 2009 06:42 Edited at: 15th Oct 2009 03:46
Link
(removed)

Back to top
Profile PM
luke810
17
Years of Service
User Offline
Joined: 4th Sep 2006
Location: United States
Posted: 18th Oct 2009 22:44
Link
Version 1.1 has been posted for download, it includes two new functions and a bug fix. New examples will be posted including the new functions in the next version.

Documentation on function usage is still in progress but will be available soon. Until then, the example programs show basic usage of the pathfinder and the header file functions include a short description of usage and purpose.

Back to top
Profile PM
SFCBias
14
Years of Service
User Offline
Joined: 8th Aug 2009
Location: Hephzibah, GA, USA
Posted: 19th Oct 2009 04:32
Link
I see how this would work on a little area with object(such as the one in the example) but how would this be put into use in a level that has its own obstacles, such as a .x or .dbo etc.

if(You.AddCode.toPost)TGC.Users.CanHelp = true;
else return NoCodeMessage;
Back to top
Profile PM
luke810
17
Years of Service
User Offline
Joined: 4th Sep 2006
Location: United States
Posted: 19th Oct 2009 05:02
Link
That's why got rid of the GPC component for convex polygons. I plan to rewrite the frame generator so that multiple polygons can be generated for a certain height range on an object. This would allow simple maps with built in obstacles to generate an environment for the pathfinder. Of course there's always the option of loading the level into darkGDK, and using a program to manually create the avoidance zones using non-object linked polygons, then saving the data to be loaded as needed.

Back to top
Profile PM
SFCBias
14
Years of Service
User Offline
Joined: 8th Aug 2009
Location: Hephzibah, GA, USA
Posted: 19th Oct 2009 05:06
Link
Great sounds promising..(aka: idk what your talking about..lol);

if(You.AddCode.toPost)TGC.Users.CanHelp = true;
else return NoCodeMessage;
Back to top
Profile PM
luke810
17
Years of Service
User Offline
Joined: 4th Sep 2006
Location: United States
Posted: 23rd Oct 2009 05:02 Edited at: 23rd Oct 2009 05:27
Link
Version 1.2 now available for download from the first post. There are 3 new example program and the original one has been redone. The style of the example programs is based on the darkAI example, so if you've seen it you'll notice they're similar looking. ( although darkAI is probably better... ) I've mostly just done some internal work on this release, although I fixed a major issue relating to the floating point precision errors building up from calculations beginning at the base polygons and turning into program killing demons at runtime.

Please test it out, and any feedback would be great. I'll probably redo the screenshots on the main post in the next few days with shots from the example programs so be on the look-out if you're too lazy to download.

EDIT: Sorry about the random screenshot pictures attached to posts, but I just started uploading them over old ones.

I'm still workin' away on the non-convex polygon generation, but I'll implementing the height range clipping for concaves at the same time which will make generating bounds for level-style objects easier.

Back to top
Profile PM
tmd13
14
Years of Service
User Offline
Joined: 16th Sep 2009
Location:
Posted: 13th Nov 2009 15:55
Link
This is an amazing project luke810. Would it be possible to use this algorithm into a program that I am doing in Dark GDK or it can only be used in what you have done.

Thanks in advance
Back to top
Profile PM
Matty H
15
Years of Service
User Offline
Joined: 7th Oct 2008
Location: England
Posted: 13th Nov 2009 16:09
Link
This looks pretty cool, would you allow us to use this in the DarkGDK open source project?
Back to top
Profile PM Email
luke810
17
Years of Service
User Offline
Joined: 4th Sep 2006
Location: United States
Posted: 13th Nov 2009 16:16 Edited at: 13th Nov 2009 16:17
Link
Sure, there are bugs though

Back to top
Profile PM
Matty H
15
Years of Service
User Offline
Joined: 7th Oct 2008
Location: England
Posted: 16th Nov 2009 15:19
Link
Thanks dude, there are always bugs lol.
Back to top
Profile PM Email
Outscape
15
Years of Service
User Offline
Joined: 23rd May 2008
Location:
Posted: 20th Dec 2009 22:29 Edited at: 20th Dec 2009 22:33
Link
hey, sorry to say this, but i tryed implementing this into the sparky sliding collision demo to see if i could get it working with sparky and if it also worked on the Y axis.


sarcasm says it went well.
im not a c++ whizz and im not sure what all that means, and i have reviewed your code and i cant see why it isnt working.


my code is only 130 lines long, and most of it is your code, so ill post it here:



thanks in advance

object 1 = map.
object 2 = player.
object 3 = ai.


Huge List of Ways to Increase FPS
Back to top
Profile PM Email Website
tmd13
14
Years of Service
User Offline
Joined: 16th Sep 2009
Location:
Posted: 11th Mar 2010 08:07
Link
Can somebody tell me how to implement this method into a project that I have so I can create my own path with this. I am new in this and Would like to know from scratch how I can implement it.

I have read everything related to this so please dont send me to read the tutorial again. I understand the method, how it works and everything.

But what i dont know first of all is how to create the famous square grid to establish the nodes where my object will move from and to.

How I call all those movements and things like that. I hope you undeerstand what im saying and i can solve this issue.

thanks in advanced.
Back to top
Profile PM
luke810
17
Years of Service
User Offline
Joined: 4th Sep 2006
Location: United States
Posted: 20th Mar 2010 05:13
Link
This is Point to Point pathfinding, not grid based. I've assimilated this project into a larger AI project in DirectX 10 anyway so It's not being worked on anymore.

Back to top
Profile PM
haliop
User Banned
Posted: 28th Apr 2010 10:19
Link
hi man , im about the use this plugin.
i will tell you if its all working or not
Back to top
Profile
Back to top

Login to post a reply

Server time is: 2024-04-25 12:34:26
Your offset time is: 2024-04-25 12:34:26