Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (523)
Games in Android Showcase (127)
games submitted by our members
Games in WIP (591)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Pathfinding?  (Read 2857 times)
0 Members and 1 Guest are viewing this topic.
Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Posted 2008-12-08 21:45:05 »

I want to use Dijkstra for my game. I tried BFS but it returned me ugly paths. Yes, I know, I'm very picky  Undecided

I do have Dijkstra implemented already, but my implementation is way too big for a 4K game, 180 lines...which I could probably optimize down to 140 lines quite easily as I've not done any optimization on it.

The data structures is really what is taking up lots of space. Having to maintain a sorted open list and also a closed list takes up some space. Not to mention performing operations on those! (check if in open/closed, add, remove).


So, what I wanted to discuss here are good ways to implement something like a 4K-pathfinder (Dijkstra preferred) that can be applied on a tile[cols][rows] map.

What have people done here in the past?

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 836
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2008-12-08 22:34:33 »

Can't you get away with floodfill? It's extremely small to implement and 'fast enough'.

Walk over an int[w*h] for every iteration, and set the value of the empty cells next to the 'last age' to 'current age'. Extremely inefficient, but maybe 3 or 4 lines of code to find the target - then a few lines to trace back. Smiley

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Reply #2 - Posted 2008-12-08 22:50:06 »

Can't you get away with floodfill? It's extremely small to implement and 'fast enough'.

Walk over an int[w*h] for every iteration, and set the value of the empty cells next to the 'last age' to 'current age'. Extremely inefficient, but maybe 3 or 4 lines of code to find the target - then a few lines to trace back. Smiley

For my game the path quality does matter. Flood-fills doesn't return me the shortest path. ?

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Morre

JGO Knight


Medals: 2
Projects: 10


I'm Dragonene on IRC.


« Reply #3 - Posted 2008-12-08 22:57:38 »

BFS will find optimal paths. Since you've a relatively small grid, I can't see why you wouldn't want to use that?

Offline timfoden

Junior Devvie


Projects: 2



« Reply #4 - Posted 2008-12-09 08:15:58 »

For my game the path quality does matter. Flood-fills doesn't return me the shortest path. ?

Yes it does.  As Riven said, once the fill has found the destination, you backtrack to find the path.  I.E. from the destination square, move to an adjacent square with the lowest iteration (or cost) number.  Keep doing this until you get back to the start.  You've just followed one of the shortest paths.

BTW, what criteria are you using to define which path is shortest through the grid?  For instance do you prefer diagonal movements over up/down?  Can you move at different speeds along the path?

If we knew a bit more about the path finding problem you want to solve maybe we'd be able to give some more specific help.

Cheers, Tim.

Try Pipe Extreme -- can you get to the end of the pipe?
Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Reply #5 - Posted 2008-12-09 09:35:33 »

Yes it does.  As Riven said, once the fill has found the destination, you backtrack to find the path.  I.E. from the destination square, move to an adjacent square with the lowest iteration (or cost) number.  Keep doing this until you get back to the start.  You've just followed one of the shortest paths.

BTW, what criteria are you using to define which path is shortest through the grid?  For instance do you prefer diagonal movements over up/down?  Can you move at different speeds along the path?

If we knew a bit more about the path finding problem you want to solve maybe we'd be able to give some more specific help.

Cheers, Tim.

Ok, I'll take a look at it.

I prefer diagonal movement where it applies, e.g. going from bottom-left to top-right.

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline timfoden

Junior Devvie


Projects: 2



« Reply #6 - Posted 2008-12-09 13:32:56 »

Here's a quick example implementation of using a flood fill to find the shortest path.  It's not been optimised for size.  Smiley

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
class PathFinder
{
   public static void main( String[] args )
   {
      final int W = 20;
      final int H = 15;
      final int SIZE = W * H;

      int[]   grid = new int[SIZE];

      // mark edges of grid.
      for( int i = 0; i < W; i++ )
         grid[i] = grid[SIZE - W + i] = -1;
      for( int i = 0; i < H; i++ )
         grid[i * W] = grid[W - 1 + i * W] = -1;

      int START = 1 + 1 * W;   // bottom left.
      int END   = (W - 2) + (H - 2) * W;   // top right.

      // grid offsets for the 8 main directions.
      final int[] OFFS = { -1, 1, -W, W, -1-W, 1-W, -1+W, 1+W };

      // add in some random obstacles...
      for( int i = 0; i < SIZE / 4; i++ )
         grid[(int)(Math.random() * SIZE)] = -1;

      // initialise dist for start.
      grid[START] = 1;
      grid[END]   = 0;

      // flood fill
      boolean changed = true;
      int count;
      for( count = 2; changed; count++ )
      {
         changed = false;
         for( int from = 0; from < SIZE; from++ )
         {
            if( grid[from] == count - 1 )
            {
               for( int dir = 0; dir < 8; dir++ )
               {
                  int to = from + OFFS[dir];

                  if( grid[to] == 0 || count < grid[to] )
                  {
                     grid[to] = count;
                     changed = true;
                  }
               }
            }
         }
      }

      // adjust count (started from 1, counted 1 extra -- need to subtract 2)
      count -= 2;

      if( grid[END] == 0 )
      {
         // failed to reach end.
         System.out.println( "Failed to find a path from START to END" );
      }
      else
      {
         // backtrack to get one of the shortest paths.
         int[] path = new int[count];
         int from = END;
         path[--count] = from;
         while( count > 0 )
         {
            // search for lowest value.
            int best = END;
            for( int dir = 0; dir < 8; dir++ )
            {
               int to = from + OFFS[dir];
   
               if( grid[to] > 0 && grid[best] > grid[to] )
               {
                  best = to;
               }
            }
   
            from = best;
            path[--count] = from;
         }

         // dump path.
         for( int i = 0; i < path.length; i++ )
         {
            System.out.format( "%02d: (%2d, %2d)\n", i, path[i] % W, path[i] / W );

            // update grid to show path.
            grid[path[i]] = 99;
         }
      }

      // dump grid.
      System.out.println();
      for( int y = H - 1; y >= 0; y-- )
      {
         System.out.printf( "%2d ", y );
         for( int x = 0; x < W; x++ )
         {
            int i = x + y * W;
            if( i == START )
               System.out.print( " S " );
            else if( i == END )
               System.out.print( " E " );
            else if( grid[i] == 99 )
               System.out.print( " @ " );
            else if( grid[i] < 0 )
               System.out.print( "###" );
            else
               System.out.print( " - " );
//               System.out.printf( "[%02d]", grid[i] );
         }
         System.out.println();
      }
      System.out.print( "  " );
      for( int x = 0; x < W; x++ )
      {
         System.out.printf( " %02d", x );
      }
      System.out.println();
   }
}

Try Pipe Extreme -- can you get to the end of the pipe?
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 836
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #7 - Posted 2008-12-09 17:18:16 »

If a diagonal step is as fast as a straight step, floodfill will do the trick.

I'll try to post a minimalistic floodfill impl tonight.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Reply #8 - Posted 2008-12-10 16:10:17 »

From what I've read it seems to be BFS with visit-cost added. And then a slightly different traversal code to return the path once goal is found.

The default flood-fill algorithm is DFS, which is not good for pathfinding. I'll need a queue, to explore on breadth.

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Gibbo3771 (10 views)
2014-11-24 19:59:16

trollwarrior1 (35 views)
2014-11-22 12:13:56

xFryIx (73 views)
2014-11-13 12:34:49

digdugdiggy (52 views)
2014-11-12 21:11:50

digdugdiggy (46 views)
2014-11-12 21:10:15

digdugdiggy (40 views)
2014-11-12 21:09:33

kovacsa (66 views)
2014-11-07 19:57:14

TehJavaDev (70 views)
2014-11-03 22:04:50

BurntPizza (68 views)
2014-11-03 18:54:52

moogie (83 views)
2014-11-03 06:22:04
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!