Results 1 to 9 of 9
At first I started, as I usually do, completely on my own, so I don't get my perspective biased by a bunch of knowitalls who think they have the perfect ...
Enjoy an ad free experience by logging in. Not a member yet? Register.

 05092013 #1
 Join Date
 Dec 2011
 Location
 Turtle Island West
 Posts
 362
Has anyone dabbled in 2D pathfinding with obstacles?
1. Does a straight line work? If so, use it. Done. Simple algorithm, fast as light.
Code:GList *line_calc(int xstart, int ystart, int xend, int yend ) { /* This calculates a straight line from one point to another. * The resulting GList includes both ends. * More or less stolen from cppGraphicsHandbook or something. */ GList *nlist = NULL; int reverse = FALSE; int dx, dy, i, x, y, x_sign, y_sign, decision; int xs, ys, xe, ye; xs = xstart; ys = ystart; dx = abs(xend  xs); dy = abs(yend  ys); if (((dx >= dy) && (xs > xend))  ((dy > dx) && (ys > yend))) { // reverse them if they go right to left reverse = TRUE; xe = xs; xs = xend; ye = ys; ys = yend; } else { xe = xend; ye = yend; } if (dx == 0) { // vertical line for (i = ys; i <= ye; i++) { nlist=add_point(nlist,xe,i); } } else if (dy == 0) { // horizontal line for (i = xs; i <= xe; i++) { nlist=add_point(nlist,i,ye); } } else { y_sign = (ye  ys) / dy; x_sign = (xe  xs) / dx; if (dx >= dy) { // diagonal or more x travel than y travel for (x = xs, y = ys, decision = 0; x <= xe; x++, decision += dy) { if (decision >= dx) { // bump the y decision = dx; y += y_sign; } nlist=add_point(nlist,x,y); } } else { // more y than x for (x = xs, y = ys, decision = 0; y <= ye; y++, decision += dx) { if (decision >= dy) { // bump the x decision = dy; x += x_sign; } nlist=add_point(nlist,x,y); } } } if ( reverse ) // so it gets drawn from the source to target nlist = g_list_reverse(nlist); return nlist; }
2. If straight line does NOT work, is there a solution at all. We have to eliminate this one next, because why waste time chewing on a big grid on an unsolvable problem. The answer to this is found in the classic bucketfill routine. Also fast as light, and if target is not encountered during the bucketfill, the problem is not solvable, and we just report that. It means either the source is jailed, or the target, or both.
Code:static int target=0; void map_fill_spot ( int x, int y ) { // x and y are the starting point /* this fills the map, like bucketfill and stops when it cannot fill anymore */ /* It very quickly determines if the dest can be found, or is jailed */ int i, j; for ( i = 1; i < 2; i++ ) { for ( j = 1; j < 2; j++ ) { if ( x+i >= 0 && (x+i) < pg.bw && y+j >=0 && y+j < pg.bh ) { /* all you have to do is make map[x][y] something other than 0 * and it becomes an obstacle and not walkable. */ if ( ! map[x+i][y+j] ) { // walkable if ( pg.dx == (x+i) && pg.dy == (y+j) ) { target++; // BANG! Found it. } map[x+i][y+j] = 2; map_fill_spot(x+i,y+j); } } } } }
Any clever advice? It seems like a simple elimination puzzle that has been overcomplicated by multitudinous grad theses.
 05102013 #2
 Join Date
 Dec 2011
 Location
 Turtle Island West
 Posts
 362
I don't get to code much these days. Maybe a couple hours in the evenings, and occasionally, a good run in the middle of the night (with caffeine!) if I don't have to work the next day. Anyway, that's my excuse, and I'm sticking to it.
I figured out the solution:
The answer to the path finding problem lies *in* the classic bucket fill. You just need to make it smarter. Instead of rambling all over the place until it accidentally stumbles upon the target, you just get it to try to make smart choices every step of the way. Instead of brainless for() loops, we start with the correct directions. Smartens up the bucket fill pretty quick.
 05112013 #3
 Join Date
 Apr 2006
 Location
 Saint Paul, MN, USA / CentOS, Debian, Slackware, {Free, Open, Net}BSD, Solaris
 Posts
 1,286
Hi.
I'm not sure that this relates to your question, but here is a book we used in a local IEEE study group. The page at Amazon shows how you can get a free pdf of the book online as well as all the code (in ruby). Chapter 2 has a number of different algorithms for searching.
Best wishes ... cheers, drl
Clever Algorithms: NatureInspired Programming Recipes: Jason Brownlee: 9781446785065: Amazon.com: BooksWelcome  get the most out of the forum by reading forum basics and guidelines: click here.
90% of questions can be answered by using man pages, Quick Search, Advanced Search, Google search, Wikipedia.
We look forward to helping you with the challenge of the other 10%.
( Mn, 2.6.n, AMD64 3000+, ASUS A8V Deluxe, 1 GB, SATA + IDE, Matrox G400 AGP )
 05132013 #4
 Join Date
 Dec 2011
 Location
 Turtle Island West
 Posts
 362
Thank you for that link drl. As I have no money to spare, I scored the pdf. So far I've had a quickie scan of it and it seems to contain a multitude of, well, clever algorithms. At 436 pages, I think it'll take me a while to work through. And ruby is pretty straightforward.
So far, by working in smartass tweaks to the bucketfill and checking for unblocked straightline paths, I've got myself a pretty good pathfinder, zigzagging around obstacles, beelining for the target, and knowing exactly when to quit.
As a protoproject (path0.1), I'm using ncurses as the interface. It's easy to work with and doesn't get in my way while I'm bashing at the core. At this point I'm not even using cost analysis on mutliple pathways at all (that'll be v0.2), and it still does a pretty good job.
Here's a couple tiny (and ugly) screengrabs. I've never attached jpgs to a forum post, so please forgive me if something goes wrong. They're less than 32k between them. And they look like they're from some crappy game from 1983.
The first jpg, you can see how if finds DD, but muddles around before heading in. The second jpg, you can see that it barely diverts from straight line path to DD. Anyway, it's a fun diversion. This is what I came up with to amuse myself after I finished my last coding project.
The cool thing about it, is that this is an age old conundrum, and goes back to the stone age. What *IS* the best path to a destination. The answer falls into this kind of thing: Whatever works in that time and place. The variables are infinite. What are *you* trying to do? What are *they* trying to do? What kind of random crap pops up while you're trying to do what you're trying to do, and they're trying to do what they're trying to do?
And it's all based upon the straightlines, bucketfills, and advice your mother gave you, but you forgot, damnit.
Peace and Cheer, and, hey, happy Mother's Day.
 05132013 #5
 Join Date
 Apr 2006
 Location
 Saint Paul, MN, USA / CentOS, Debian, Slackware, {Free, Open, Net}BSD, Solaris
 Posts
 1,286
Hi.
The jpgs look fine to me.
Keep us posted ... cheers, drlWelcome  get the most out of the forum by reading forum basics and guidelines: click here.
90% of questions can be answered by using man pages, Quick Search, Advanced Search, Google search, Wikipedia.
We look forward to helping you with the challenge of the other 10%.
( Mn, 2.6.n, AMD64 3000+, ASUS A8V Deluxe, 1 GB, SATA + IDE, Matrox G400 AGP )
 05202013 #6
 Join Date
 Dec 2011
 Location
 Turtle Island West
 Posts
 362
Right handed and Left handed routines.
We have our traveling node, *ppt, who is constantly tracking the direction to the target, *dpt. This is direction 0 of 07, the 8 cardinal compasspoints. 0 would normally be pointing topleft:
0 1 2
7 X 3
6 5 4
At first ppt tries dir 0, but if that fails, it tries right, then left, then hard right, then hard left, then behind right, behind left, then finally, the opposite direction, as per this lookup table:
Code:typedef struct _p_vector { int xv; int yv; } pvec; pvec pv[8][8] = { // pv[targetdir][k] // primary 1(right) 2(left) 3(rright) 4(lleft) 5(rbehind) 6(lbehind) 7(opposite) { { 1, 1 }, { 0, 1 }, { 1, 0 }, { 1, 1 }, { 1, 1 }, { 1, 0 }, { 0, 1 }, { 1, 1 } }, // top left { { 0, 1 }, { 1, 1 }, { 1, 1 }, { 1, 0 }, { 1, 0 }, { 1, 1 }, { 1, 1 }, { 0, 1 } }, // top center { { 1, 1 }, { 1, 0 }, { 0, 1 }, { 1, 1 }, { 1, 1 }, { 0, 1 }, { 1, 0 }, { 1, 1 } }, // top right { { 1, 0 }, { 1, 1 }, { 1, 1 }, { 0, 1 }, { 0, 1 }, { 1, 1 }, { 1, 1 }, { 1, 0 } }, // right { { 1, 1 }, { 0, 1 }, { 1, 0 }, { 1, 1 }, { 1, 1 }, { 1, 0 }, { 0, 1 }, { 1, 1 } }, // bot right { { 0, 1 }, { 1, 1 }, { 1, 1 }, { 1, 0 }, { 1, 0 }, { 1, 1 }, { 1, 1 }, { 0, 1 } }, // bot center { { 1, 1 }, { 1, 0 }, { 0, 1 }, { 1, 1 }, { 1, 1 }, { 0, 1 }, { 1, 0 }, { 1, 1 } }, // bot left { { 1, 0 }, { 1, 1 }, { 1, 1 }, { 0, 1 }, { 0, 1 }, { 1, 1 }, { 1, 1 }, { 1, 0 } } // left }; void path_get_vector ( int k, int *xv, int *yv ) { // k = 07 if ( k < 8 ) { if ( p_flip ) { if ( k == 1  k == 3  k == 5 ) k++; else if ( k == 2  k == 4  k == 6 ) k; } *xv = pv[targetdir][k].xv; *yv = pv[targetdir][k].yv; } }
The initial routine still kinda rambles around, but once it finds dpt, it's a simple matter to follow ppt>parent back to the source.
Being a grid, it should be slightly more expensive to move to a diagonal square than horizontal or vertical, but still cheaper than moving 1 horizontal and 1 vertical. So, each move costs 10, and diagonal 14 (roughly root of 2). Tally costs, pick the cheapest, and apply it.
For amusement, here's 6 jpgs showing the results.
#1. Right handed, no cleanup.
#2. Right handed, cleanup A. This cleanup routine zips ahead in straight line until it finds blockage, plots a line to the point right before the block, and then jumps to that point.
#3. Right handed, cleanup B. This cleanup routine does the same as cleanup A, but works meticulously point by point instead of jumping to the plotted preblock point.
#4, #5, #6. Same, but Left handed. You can see significant differences. To begin with, it looks much more costly, but turns out to be the cheapest. 109 moves for $1220, vs. 127 moves for $1536 with the righthanded version.
Ah yes. Perfect. The jpgs are ~50kb each, and the site let me upload 5, to the tune of about 250kb. There's the attachment cap. So the last Lefthanded one is missing. Oh well. Now we know. Next time I'll try better compression.
 06022013 #7
 Join Date
 Dec 2011
 Location
 Turtle Island West
 Posts
 362
Getting a little fancier #0.
I started making the maps crazy and complicated, and found out that at a certain point something went into infinite loop when I tried to refine the crude path (type0) to a proper nonrambling path(type14). I have a few different algorithms that I try for this purpose.
Here's a jpg of a type0 path. It found it's way of course, but it took 538 moves for a total cost of 6490. The grid is only 80x55(=4400).
That may seem bad, but it did it in .002 seconds. That equals 3usec/move, so it's basically instantanious. That's good.
The source is up in the top right (SS) and the dest in the bottom right (DD).
 06022013 #8
 Join Date
 Dec 2011
 Location
 Turtle Island West
 Posts
 362
What is discovered was that I was trying to *perfect* the path too fast. It doesn't need to be perfect. If you see all those clumps of ramblings where it's trying to get past stuff, if you just buzz a straight line through, occasionally some leftovers point right back into the straight line. Therefore the infinite loop.
After thinking about this, I woke up at 1 in the morning with an idea. "Just zip through the line and eliminate unnecessary neighbors!" Just clean the type 0 path into a type 1. I tried it, it worked, and I have not seen the infinite loop since then.
Here's the simple routine:
Code:void path_reduce ( void ) { // now work our way back to start, eliminating unneccessary ppts. ppt *jpt, *spt = pg.dd; while ( spt ) { jpt = spt>parent; while ( jpt ) { // zip down the line finding neighbors if ( (abs(jpt>x  spt>x)<2) && (abs(jpt>y  spt>y))<2 ) spt>parent = jpt; // and link to them jpt = jpt>parent; } spt = spt>parent; } }
 06022013 #9
 Join Date
 Dec 2011
 Location
 Turtle Island West
 Posts
 362
Path type 4
So far this is the best I've devised at perfecting a path. It's thorough, but slow. It straightens and finds shortcuts. It reduced 313 moves to 294, cost from 3796 to 3458, but it took almost a second and a half to pull the trick off. That's 4905usec/move! We're getting into diminishing returns here.
What this makes me realize is this:
Keep your quick & dirty path. It's a rough guide to the destination. Paths change in a changing world. If unit#1 is traveling this path, it only needs to think 1 move ahead. Say it can use 80 points in a turn, it only needs to perfect the path 80 points ahead. By then, something will have moved, the path will change, and there's no point in perfecting a long path far in advance of when it's needed. So save your path perfections for the short jumps. And even if DD becomes unreachable, still keep working the quick & dirty path until something better comes along.
Here's the jpg. It's kinda neat to compare it to the previous one. In this rambling maze it's not so obvious, but with less clutter you can really see it's strengths. V0.2 will have multiple paths and cost analysis. Coming soon.