AI pathfinder for large maps - 2nd try. This is a unique approach and is fastest version I have to date. Submitted for your suggestions & feedback. Well commented. If anyone has seen an approach like this, please let me know. I would like to compare distance & heuristic calculations. Unlike most pathfinders, this one does not require fixed objects and can be used for quickly plotting paths btwn moving objects. For those of you that have personally requested to be updated on improvements to this code, I have sent you a personal copy. For all others, I have re-posted this project simply because the update produces a significantly faster result & is far more accurate to providing a shorter path. I'm sure this project can be tweaked to provide even faster results, but keep in mind the trade-off between speed and overtasking memory resources. Updated again for to allow user-defined accuracy and speed (use the AccuracyPct variable in routine: CreatePaths) 1 Feb 20:10 CST -- Now can find shortest path 100% of time & quickly.
Note: Due to the size or complexity of this submission, the author has submitted it as a .zip file to shorten your download time. Afterdownloading it, you will need a program like Winzip to decompress it.Virus note:All files are scanned once-a-day by Planet Source Code for viruses, but new viruses come
out every day, so no prevention program can catch 100% of them. For your own safety, please:
Re-scan downloaded files using your personal virus checker before using it.
NEVER, EVER run compiled files (.exe's, .ocx's, .dll's etc.)--only run source code.
Scan the source code with Minnow's Project Scanner
If you don't have a virus scanner, you can get one at many places on the net
including:McAfee.com
Terms of Agreement:
By using this code, you agree to the following terms...
You may use
this code in your own programs (and may compile it into a program and distribute it in compiled format for languages that allow it) freely and with no charge.
You MAY NOT redistribute this code (for example to a web site) without written permission from the original author. Failure to do so is a violation of copyright laws.
You may link to this code from another website, but ONLY if it is not wrapped in a frame.
You will abide by any additional copyright restrictions which the author may have placed in the code or code's description.
As mentioned in the leading remarks within the class module, I have not attempted to go diagonal & that is not a priority of mine. If anyone wants to provide a diagonal routine, feel free. Glad you like it. (If this comment was disrespectful, please report it.)
Updated & now am satisified with speed & shortest path accuracy. Have fun. Don't think you'll find a faster path finder that works on non-tiled maps. (If this comment was disrespectful, please report it.)
Major modification uploaded. You can define level of "speed" vs "shortest path accuracy" by setting the AccuracyPct variable in the CreatePath routine. Now a flexible class. (If this comment was disrespectful, please report it.)
Again, if you want to be kept up to date on progress, send me a line. I'll send you the updated class. Am tweaking often to get the fastest, most reliable result. Currently tweaked again, to have class automatically adjust the AccuracyPct value based on the path length as they are found. Seems to provide same result & faster than hardcoding the variable to 100% accuracy. (If this comment was disrespectful, please report it.)
great news, man! keep working hard at it! Wish you shooting more and more directions with great quality;)
p.s. your class is full of comment and it takes me a long long time to read through;)
You can just keep working hard at it and upload it to PSC so that all us can improve it together;) (If this comment was disrespectful, please report it.)
It seems that less people interest in AI(such as Path Finding) than in Games(such as the current top 1 rank in this month's list). sad :( (If this comment was disrespectful, please report it.)
I still think that if you allow it to go diagonally, that would be better. Maybe an option(property) ;) (If this comment was disrespectful, please report it.)
Improvement suggestion: once the shortest path has been found, look fastest path to the second corner with a more complex routine. Gives a more realistic movement for the ones who want to actually use the code in a game or do a game test using this routine. And this suggestion is not only for the original creator :) (If this comment was disrespectful, please report it.)
Vesa, I think I understand your suggestion & the only issue for gamers would be the added time to "reduce" the number of turns. For those that desire diagonals--extremely difficult to accomplish using a pixel by pixel pathfinding routine as calculations to achieve this would most likely add much more time to return a path. If you want to try it yourself, I would suggest creating a polyregion containing the 4 pts of a diagonal & test for inter-section of obstacles; adjust the pts & try again until success, etc. (If this comment was disrespectful, please report it.)
Some time ago I started building this lil robot, run by a 486 laptop. Had the controls worked out, everything worked fine, except the "AI" I built for it to find it's way around was exceptionally poor! Thanks, man! You've just made me ditch several months worth of coding! This is brilliant! I especially love the fact that now I can throw moving objects into the mix! (If this comment was disrespectful, please report it.)
hmm... I used something slightly different when I made a snake game to 'a' route to an apple. It didn't find the shortest but it did find one fairly quickly. You might want to sake a look at "Snake game with demo ai" (If this comment was disrespectful, please report it.)
Eric, thanx; but doesn't help. That game uses tiles (HxW) as a block. My goal is to create something at the pixel level for very large maps. Therefore, my tiles would be 1x1 blocks & large maps prevent traditional ways of pathfinding via the use of (MapHxMapW) arrays to track progress. In addition to the massive memory resources needed, those traditional algorithms would be extremely time consuming. I have updated my routines, to improve accuracy, but still can't get to 100% shortest path--yet. (If this comment was disrespectful, please report it.)
Theres a Few Bug but all and All it derserves 500000000000000000000000000000000000000000000000000000000000000 Golbes, Dam voting system only allows 5 Well you Need anything you can get. (If this comment was disrespectful, please report it.)
Theres a Few Bug but all and All it derserves 500000000000000000000000000000000000000000000000000000000000000 Golbes, Dam voting system only allows 5. (If this comment was disrespectful, please report it.)
Thank you for the code! 5 globes for you! GREAT CODE NEEDS 90E999 globes but alas, only five are allowed so 90E999/90E999 = 5/5! (If this comment was disrespectful, please report it.)
Contest winner? This was a surprise. Kinda like hitting a homer without trying. My main intent was only to get feedback & maybe work with others trying to accomplish the same thing. Thax to all of you that voted. P.S. I know these routines aren't perfected, but am still working on different routines or variations thereof. (If this comment was disrespectful, please report it.)
Updated SuperBowl Sunday. New routines run a bit slower but now guarantee 100% shortest path accuracy. Future improvements still on the back burner. (If this comment was disrespectful, please report it.)
Oops-My Bad! When converting array to UDT, forgot to redimension array. Your copy can lock up in BuildReturnArray. The offending lines are in CreatePaths when I am initializing the vPaths() array. So sorry; it's fixed. P.S. Found scenario where restrictor of 20 & 30% not good 'nuf. Suggest upping to .5 in JoinPaths. See class lead remarks if needed. (If this comment was disrespectful, please report it.)
^^ Yep & now with a more recent submission by Stavros Sirigos, maybe attack it from a different angle. My goal for speed is now secondary to shortest path accuracy. Once that has been proven, then speed can be achieved thru better/faster calculations I hope. (If this comment was disrespectful, please report it.)
LaVople, As always your code rocks! Thanks for sharing this and enhancing the collective knowledge of the PCS community...TerriTop (If this comment was disrespectful, please report it.)
Add Your Feedback
Your feedback will be posted below and an email sent to
the author. Please remember that the author was kind enough to
share this with you, so any criticisms must be stated politely, or they
will be deleted. (For feedback not related to this particular code, please
click here instead.)
Download code
12/3/2003 2:09:20 AM: 
