|
LaVolpe PathFinder IV: Non-Tiled Graphs
|
Email
|
| Submitted on: |
4/21/2007 8:14:04 PM |
| By: |
LaVolpe
|
| Level: |
Advanced |
| User Rating: |
By 38 Users |
| Compatibility: |
VB 6.0 |
| Views: |
20574 |
|
(About the author) |
|
|
|
[No code update; only added the missing RTF file]. Fastest non-tiled graph path finder. Extended my unique approach & believe it is 100% accurate and still very fast. This approach uses window regions to process open space very quickly. Where A* & Dijkstra require known distances between nodes, this project kinda explores on the fly, creating the needed link structure as it explores. Give it a go & if you want to discuss better logic/routines, please email me. P.S. Sorry about the large screenshot: wanted to show you the size of a graph & it's potential speed. Thanx goes to Stavros Sirigos for getting me re-interested in this project. Updated: a bit faster & fixed routine to recognize when start/end nodes in same regional rectangle. Updated 18Jun: added efficiency tweaks & correct path error that occurs maybe 1 out of 1000 paths.
|
 |
| |
|
 Download code
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.
|
Other 72 submission(s) by this author
|
|
Report Bad Submission
|
Your Vote
|
| |
Other User Comments
|
 6/11/2005 11:43:56 PM: Peter Wilson
I don't get impressed easily, but this is very impressive. You need to write a game using this code. I suspect you are reaching the limits of what VB has to offer.
(If this comment was disrespectful, please report it.)
|
6/12/2005 1:43:45 AM: Greyling
Could this be turned into Printed Circut Board maker? Like draw the chip placements and let this thing find the traces (?)
(If this comment was disrespectful, please report it.)
|
6/12/2005 3:09:27 AM: LaVolpe
Greyling, kinda the reason I developed routines for (job related); they need more work but it is feasible.
(If this comment was disrespectful, please report it.)
|
6/12/2005 4:34:21 AM: Vasilis Vasileiadhs
and once again you succeded to surprise us!
5 globes for you...
P.S(.C) Keep up good work...
(If this comment was disrespectful, please report it.)
|
6/12/2005 3:30:06 PM: LaVolpe
This prj has long way to go for what I need it to do. Constantly tweaking to trim ms. If you want a more current copy; email me. Otherwise, will only update if a significant change is made. My most current version is about 15-30ms faster on longer paths than this one (tweaks)
(If this comment was disrespectful, please report it.)
|
6/13/2005 1:54:58 AM: Peter Wilson
Hmmm.... you've got me thinking. I might try and submit my own version of this idea...
(If this comment was disrespectful, please report it.)
|
6/13/2005 7:15:47 AM: Phantom Man
Hi Keith
Nice Submission. Glad To See Your Back.
Gary
(If this comment was disrespectful, please report it.)
|
6/13/2005 12:36:49 PM: Jim Jose
Hi Lavolpe;
You again came with unbounded logic. Your realy won to get it amazingly fast. All the very best to your 'Long Way' ;-))
You got 5 ***** planets from me
Jim Jose
(If this comment was disrespectful, please report it.)
|
6/13/2005 12:47:00 PM: Zirro Tolerance
One way to speed this up would be to make a long rgnRectUbound to speed up the loops some.
(If this comment was disrespectful, please report it.)
|
6/13/2005 1:29:53 PM: LaVolpe
^^ answered offline. Avoiding ReDim'ing arrays would increase speed a little, but the potential memory cost of oversizing arrays is not an option for me. Several arrays I have no way of knowing how big they can grow; others can be calculated but in reality would never reach their max UBound & that would waste memory. IMO the minor hit on speed in this case is acceptable in favor of less memory usage. I gotta think "big, big" graphs > 20x30"
(If this comment was disrespectful, please report it.)
|
6/13/2005 1:56:03 PM: T304PK
Thanks God you are back! and with a nice addition to PSC :) ooooo
(If this comment was disrespectful, please report it.)
|
6/13/2005 2:03:01 PM: LaVolpe
Thanx for the compliment. I was never gone; just put PSC on hold for 30-45 days while tackling a tough project at work. Nice to be back & have the time for fun-coding ;)
(If this comment was disrespectful, please report it.)
|
6/13/2005 4:36:11 PM: Smurftra
the ubound comment, i think he means to replace:
For X = 0 To UBound(rgnRect) - 1
with
Y=UBound(rgnRect) - 1
For X = 0 To Y
this would speed up things. Also, im not sure, but keeping a long like rngrect_NB(for every array) and updating it everytime you redim, and then using that long instead of ubound could speed things up. It depends if you read ubound() more than you redim. (depending on situation, you could also calculate the long after mroe than 1 redim if you dont need to read the ubound in between)
(If this comment was disrespectful, please report it.)
|
6/13/2005 5:17:29 PM: LaVolpe
^^ not so sure. Try this snippet & you will see in a For:Next the end value is read only once (afterwards X=28 & Y=0)y=27:for x=1 to y:y=y-1:next:? x,y
>>Agree ref'ing other way is faster, but it took over 3million loops to see a slight difference.
(If this comment was disrespectful, please report it.)
|
6/14/2005 3:10:26 AM: Bal Mukunda Shrestha
this is cool. which i am looking for.
thanks for it. 5 from me.
(If this comment was disrespectful, please report it.)
|
6/14/2005 9:10:10 AM: Frédéric Côté
I got a strange result while playing with this. I set the targets close to each other, with no obtacles between them. And the path doesn't go directly from one target to the other. Bug or invisible obtacle? I have a screenshot if you want one.
(If this comment was disrespectful, please report it.)
|
6/14/2005 12:49:20 PM: LaVolpe
Thanx Frederic. The fix is easy & I simply forgot to add a check in the routine. The source & target are in the same regional rectangle. When this happens the routine needs to return a straight line (2pts) path. Updated & added a feature to view the region rects
(If this comment was disrespectful, please report it.)
|
6/14/2005 3:30:47 PM: LaVolpe
More than one has asked for more details. I have put together an rtf doc that explains some of the more complicated logic in more detail with images for examples. If you would like a copy, please email me. Zipped is 81kb; unzipped is 4.5mb (w/images).
(If this comment was disrespectful, please report it.)
|
6/15/2005 9:33:40 AM: Light Templer
Hi Keith,
maybe this trick is (new) for you:
To get balance on resizing arrays (not oversized, no redim every new element) you work with an aditional counter (current last element) e.g. lCurIndex and add CHUNKS on redim, e.g.:
Redim Preserve MyArray( 1 to Ubound(MyArray) + 50)
To add an element at the end use:
MyArray(lCurIndex) = New Element
lCurIndex = lCurIndex + 1
When all is said and done shrink to fit the array with
Redim Preserve MyArray( 1 to lCurIndex)
Thats not much overhead and with a good chunk size (50 here, depends heavily to the app) your time overhead for Redim goes to "nearly unimportant" ;-)
Regards
LiTe
(If this comment was disrespectful, please report it.)
|
6/15/2005 2:59:17 PM: LaVolpe
LiTe, not new to me & implemented already wherever the exact UBound is not needed for other functions. Also chunking not used where the UBound is expected to be really small. Resizing arrays is not a speed concern; a better algorithm to calculate edge-to-edge connectivity or better region rectangle reduction algorithms will speed up routines dramatically. Better logic in terminating longer paths earlier would do the trick. Ideally, calculating true distances moving from edge to edge between turn-points would reduce path finding > 50% & up to 90% for longer paths, but that is impossible since the next turnpoint (i.e., X,Y coordinate) is never known in advance.
(If this comment was disrespectful, please report it.)
|
6/17/2005 12:45:52 AM: Daniel M
You are my idol! Sad that I quit programming in VB though... Started learning C++! Good job on this though.
(If this comment was disrespectful, please report it.)
|
6/17/2005 2:04:10 PM: Matthew R. Usner
You da man, what else is there to say. I'm gonna have to go back to college just to figure this out, and I expect you to pay the tuition. :-)
(If this comment was disrespectful, please report it.)
|
6/18/2005 2:32:57 AM: Evilgenious
LaVolpe, standing on the edge of vb.
Dont step + 1 or you will falldown.
(If this comment was disrespectful, please report it.)
|
6/20/2005 10:32:53 PM: Stavros Sirigos
Congratulations, LaVolpe, and lots of thanks for this magnificent algorithm! :) It is really amazing how well different ideas and implementation strategies are put together! Definitely a huge improvement over the previous algorithm.
A possible little addition could be to allow users to provide a custom bit-map as input ;)
Kudos! You did it again!
PS.I would be interested in any updates/documentation you may have.
(If this comment was disrespectful, please report it.)
|
6/21/2005 5:10:13 AM: David K Richmond
LaVolpe : I had no problems reading and understanding your code lots of comments to explain the action. 5 from me for that and for the diversity of the subject. =[8-)
(If this comment was disrespectful, please report it.)
|
6/21/2005 10:29:31 AM: Eric O''Sullivan
good to see that you're still working on this ;-) 5 g
(If this comment was disrespectful, please report it.)
|
6/22/2005 10:08:06 PM: Wong Yat Seng
read backwards:
evif a evresed uoy .ecin yrev si siht
(If this comment was disrespectful, please report it.)
|
6/23/2005 2:58:29 PM: Richard Mewett
The fastest complex path finding I've tested! This appears largely due to the efficient data structures which are very well executed (who says VB cant do linked lists). Do you have any plans to use this in a "real" application? 5*
(If this comment was disrespectful, please report it.)
|
6/23/2005 3:48:03 PM: LaVolpe
^^Hope so. Answered offline.
(If this comment was disrespectful, please report it.)
|
7/6/2005 6:10:01 PM: Matthew R. Usner
Congrats LaVolpe! If you melted down all your contest winner bitmaps you could buy a new car... :-)
(If this comment was disrespectful, please report it.)
|
7/26/2005 6:02:36 AM: Robert Kaltenbach
Congratulations! That's smashing! And finally it's sovereign accurate.. But why does it only support rectangles??
(If this comment was disrespectful, please report it.)
|
7/26/2005 8:30:10 AM: LaVolpe
^^Robert. It supports any shape, use CreateEllipticRgn, CreatePolygonRgn to test other shapes. FYI: Rectangles will produce faster results over hundreds of other non-rectangular shapes.
(If this comment was disrespectful, please report it.)
|
4/21/2007 4:51:23 PM: Mark J.
i think i found a bug,
if one of the objects is partially over a shape, it doesnt find a path at all :(
(If this comment was disrespectful, please report it.)
|
4/21/2007 7:31:27 PM: LaVolpe
Discussed off-line. The target was straddling a solid-block. It's center was inside the block which prevented path from being found - no bug; can't find paths when one object is inside a block.
(If this comment was disrespectful, please report it.)
|
4/23/2007 2:52:00 PM: JC
LaVolpe, you are incredible...Very nice work!!!!
Regards,
(If this comment was disrespectful, please report it.)
|
4/24/2007 10:17:34 PM: A. G. Violette
I gained my programming skills about 20 years ago using Pascal. At that time our course used a text called "Algorithms" by Robert Segwick, 1983, ISBN 0-201-06672-6. I remember several sections in this book that dealt with shortest paths, graph theory, trees and linked lists that are all applicable to your application. If you already have it, then excuse this, otherwise I know you would find the book interesting. Maybe you could get around the use of an array with the information from there. Sorry I can't be of more help. Great project though, ***** from me!
(If this comment was disrespectful, please report it.)
|
4/25/2007 9:51:39 AM: LaVolpe
^^ I appreciate the thought, but don't want to re-write the project. When compiled, this finds most paths within 30ms, on average, and many paths within 10ms. Considering the overall graph is comparable to a 1x1 tiled graph (400k tiles), I have surpassed my original goal regarding speed. And this project was meant as a "proof of concept" that one could use non-square rectangles/regions to path find, but grew a bit to see how accurate/fast I can make it. Its logic was actually used in a robotic application by another coder.
(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.)
To post feedback, first please login.
|
