Find the answer to your Linux question:
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 know-it-alls who think they have the perfect ...
Enjoy an ad free experience by logging in. Not a member yet? Register.
  1. #1
    Linux User
    Join Date
    Dec 2011
    Location
    Turtle Island West
    Posts
    362

    Has anyone dabbled in 2D pathfinding with obstacles?


    At first I started, as I usually do, completely on my own, so I don't get my perspective biased by a bunch of know-it-alls who think they have the perfect answer. I usually try brute force first just to see if it works, and then finesse things into shape. This, however, seems to not apply to my normal approach. So I started doing a fair bit of research, and it all tends to lead to Astar, Dijkstra’s algorithm, fringe searches and whatnot. They all skip the 2 most important initial steps:

    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;
    }
    Then you plot the line and see if you encounter obstacles.

    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 bucket-fill routine. Also fast as light, and if target is not encountered during the bucket-fill, 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 bucket-fill 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);
                    }
                }
            }
        }
    }
    3. Then we have to get fancy. We know there IS a solution, but how to find the best one?

    Any clever advice? It seems like a simple elimination puzzle that has been over-complicated by multitudinous grad theses.

  2. #2
    Linux User
    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.

  3. #3
    drl
    drl is online now
    Linux Engineer drl's Avatar
    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 on-line as well as all the code (in ruby). Chapter 2 has a number of different algorithms for searching.

    Best wishes ... cheers, drl

    Clever Algorithms: Nature-Inspired Programming Recipes: Jason Brownlee: 9781446785065: Amazon.com: Books
    Welcome - 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, AMD-64 3000+, ASUS A8V Deluxe, 1 GB, SATA + IDE, Matrox G400 AGP )

  4. #4
    Linux User
    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 smart-ass tweaks to the bucket-fill and checking for unblocked straight-line paths, I've got myself a pretty good pathfinder, zig-zagging around obstacles, bee-lining for the target, and knowing exactly when to quit.

    As a proto-project (path-0.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 straight-lines, bucket-fills, and advice your mother gave you, but you forgot, damnit.

    Peace and Cheer, and, hey, happy Mother's Day.
    Attached Images Attached Images

  5. #5
    drl
    drl is online now
    Linux Engineer drl's Avatar
    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, drl
    Welcome - 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, AMD-64 3000+, ASUS A8V Deluxe, 1 GB, SATA + IDE, Matrox G400 AGP )

  6. #6
    Linux User
    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 0-7, the 8 cardinal compasspoints. 0 would normally be pointing top-left:

    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 = 0-7
        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 table pv, but nature, is right handed. That is, it chooses right before left. But if I set p_flip boolean, it becomes left handed. That way I can try both ways to see which one works the best (least cost).

    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 pre-block 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 right-handed 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 Left-handed one is missing. Oh well. Now we know. Next time I'll try better compression.
    Attached Images Attached Images

  7. #7
    Linux User
    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 non-rambling path(type1-4). 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).
    Attached Images Attached Images

  8. #8
    Linux User
    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;
        }
    }
    Here's a jpg that shows the result. In .0002 seconds it reduced 538 moves to 313 and the cost went from 6490 to 3796. Again, essentially instantanious. The time at the bottom includes the path creation, plus the reduction. It's the difference between the entry and exit time from path_calc(). That's still only 7usec/move.
    Attached Images Attached Images

  9. #9
    Linux User
    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.
    Attached Images Attached Images

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •