Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (539)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (603)
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  
  Astar Pathfinding  (Read 13129 times)
0 Members and 1 Guest are viewing this topic.
Offline Gudradain
« Posted 2011-01-19 02:55:55 »

Hello,

Just finish my astar pathfinding : you can check the demo here : Demo

Left click to put the starting point.
Right click to put the end point.

The source code is on the demo page.

It's very simple to use this pathfinding. All you need to do is call the method getPath() in Pathfinding. Here is the signature of this method :

1  
public Path getPath(Location start, Location end, Map map);


Currently only the pathfinding for an 2D grid map is implemented. The signature for this one is as follow :

1  
public GridPath getPath(Location start, Location end, Map map);


The location and the map need be respectively GridLocation and GridMap. Here is an example of how to build an 2D grid map :

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
     map = new GridMap(sizeX, sizeY);
     for(int i=0; i<sizeX; i++){
          for(int j=0; j<sizeY; j++){
               int value;
               if(Math.random() > 0.32){
                    value = 1;
               }else{
                    value = GridMap.WALL;
               }
               map.set(i, j, value);
          }
     }
Offline loom_weaver

JGO Coder


Medals: 17



« Reply #1 - Posted 2011-01-19 03:22:29 »

Nice demo.

However, it often takes a square route instead of diagonals around tight corners.

Offline Gudradain
« Reply #2 - Posted 2011-01-19 03:44:05 »

However, it often takes a square route instead of diagonals around tight corners.

That's the wanted behavior. The unit that will move around the corner have a certain size so it's not suppose to go diagonals.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Jono
« Reply #3 - Posted 2011-01-19 09:33:36 »

Just a minor note. You'll need to change to something other than Manhattan distance as a heuristic if you want to guarantee the shortest path when you allow diagonal moves. Euclidean distance is the best you can do for grid worlds with uniform movement costs.
Offline Nate

« JGO Bitwise Duke »


Medals: 158
Projects: 4
Exp: 14 years


Esoteric Software


« Reply #4 - Posted 2011-01-19 09:36:21 »

For "visitedMap", why not use boolean[][] rather than GridDouble's ArrayList<ArrayList<Double>>? You could also use a boolean[] and index it like array[y * width + x]. Even better, if you use int[][] then you can avoid calling reset(0). Instead you use an int "currentID". At the beginning of each path finding, you increment currentID. Then during path finding, if the int[x][y] != currentID you treat it as unset, else you treat it as set.

Offline Jono
« Reply #5 - Posted 2011-01-19 09:53:10 »

... and someone put a nice binary heap implementation up at one point. Quicker than scanning through the whole open list each time you add items.
Offline Gudradain
« Reply #6 - Posted 2011-01-19 14:46:18 »

Just a minor note. You'll need to change to something other than Manhattan distance as a heuristic if you want to guarantee the shortest path when you allow diagonal moves. Euclidean distance is the best you can do for grid worlds with uniform movement costs.

I'm aware that Manhattan doesn't return necessarly the best path, but I failed to see why Euclidean would return the best one.

This pathfinding is suppose to find a ''good'' path even with non uniform movement cost in theory but I don't think it is the case with the current Heuristic.
Offline Gudradain
« Reply #7 - Posted 2011-01-19 14:52:10 »

For "visitedMap", why not use boolean[][] rather than GridDouble's ArrayList<ArrayList<Double>>? You could also use a boolean[] and index it like array[y * width + x]. Even better, if you use int[][] then you can avoid calling reset(0). Instead you use an int "currentID". At the beginning of each path finding, you increment currentID. Then during path finding, if the int[x][y] != currentID you treat it as unset, else you treat it as set.

Yeah I was lazy on that one... Do you think there is a big difference in speed between ArrayList<ArrayList<Double>> and double[][]?

Usually I prefer avoiding design that require currentID (what if currentID become greater than Integer.MAX_VALUE? ok stupid reason...)
Offline Jono
« Reply #8 - Posted 2011-01-19 14:57:17 »

I'm aware that Manhattan doesn't return necessarly the best path, but I failed to see why Euclidean would return the best one.

This pathfinding is suppose to find a ''good'' path even with non uniform movement cost in theory but I don't think it is the case with the current Heuristic.

To guarantee the shortest path the heuristic has to always be lower than the actual distance. So an ideal heuristic is one that is as high as possible but never quite goes over the actual distance to the goal.

For the grid-world the difference between Manhattan's estimate an the actual distance is worst when the goal is on a direct diagonal path from the current location. The Euclidean distance will be exactly the same as the real distance in this case, and will be lower than the actual distance in all other cases. Because the Euclidean distance gets estimates that are close to the real distance, the search will expand fewer nodes than a heuristic that gives lower values (e.g. a stupid heuristic that always guesses zero will still give the best path, but will expand lots more nodes).

What you might see with the Manhattan heuristic is that the search will try a diagonal move that will make a big jump in the heuristic, and then never have a chance to come back to try a horizontal or vertical move that is actually on a shorter path.
Offline Gudradain
« Reply #9 - Posted 2011-01-19 15:03:46 »

Hey thx for the explication Jono. I guess I will add Euclidian.

What you might see with the Manhattan heuristic is that the search will try a diagonal move that will make a big jump in the heuristic, and then never have a chance to come back to try a horizontal or vertical move that is actually on a shorter path.

Now I'm using an Heuristic that is always a bit bigger than the shortest path, won't it be slower if I use one that is always smaller?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Jono
« Reply #10 - Posted 2011-01-19 15:09:22 »

Hey thx for the explication Jono. I guess I will add Euclidian.

Now I'm using an Heuristic that is always a bit bigger than the shortest path, won't it be slower if I use one that is always smaller?

Yep, it'll be slower but it will be guaranteed to find the shortest path. I had a play with the demo to find an example of what I was talking about:



The one on the left is what is returned by the Manhattan heuristic (current implementation). The one on the right is a shorter path that isn't found. Notice the early diagonal move that confuses the search on the left.
Offline Gudradain
« Reply #11 - Posted 2011-01-19 15:21:20 »

I guess it's a tradeoff. Thx again.

I might be using this code inside a bigger pathfinding module for an RTS like game (still lot of work...)
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #12 - Posted 2011-01-19 22:28:27 »

Hey thx for the explication Jono. I guess I will add Euclidian.

Now I'm using an Heuristic that is always a bit bigger than the shortest path, won't it be slower if I use one that is always smaller?

Yep, it'll be slower but it will be guaranteed to find the shortest path. I had a play with the demo to find an example of what I was talking about:



The one on the left is what is returned by the Manhattan heuristic (current implementation). The one on the right is a shorter path that isn't found. Notice the early diagonal move that confuses the search on the left.
If your heuristic is overestimating the distance then of course the pathfinding will not actually work. You've got to have an admissible heuristic.

So yeah, in your case a Euclidean heuristic is necessary.

See my work:
OTC Software
Offline pjt33
« Reply #13 - Posted 2011-01-19 23:08:57 »

So yeah, in your case a Euclidean heuristic is necessary.
There are other admissible heuristics. E.g. max(abs(x - x0), abs(y - y0)).

Edit: or
1  
2  
3  
4  
int dx = x - x0; if (dx < 0) dx = -dx;
int dy = y - y0; if (dy < 0) dy = -dy;
int max = dx > dy ? dx : dy;
int heuristic = max + (dx + dy - max) / (2 * max);
Offline princec

« JGO Spiffy Duke »


Medals: 434
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #14 - Posted 2011-01-20 00:18:39 »

Or even this  Grin
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  
   private static final float DIAGONAL_FACTOR = 1.4142135623730950488016887242097f;
   private static final int CLUMP_DISTANCE_THRESHOLD = 5 * 5; // Only worry about clumping when < 5 squares away

   public int getCost(int from, int to) {
      if (from == to) {
         return 0;
      }

      // Bias gidrahs away from turrets
      int sx = getX(from);
      int sy = getY(from);
      int tx = getX(to);
      int ty = getY(to);
      boolean wraith = gidrahFeature.isWraith();
      boolean angry = gidrahFeature.isAngry();
      float bias = SPEED_SCALE * (wraith ? 0.0f : Math.max(0.0f, map.getDanger(tx, ty) - gidrahFeature.getArmour())) * gidrahFeature.getBrain().getAvoidanceFactor() * (angry ? 0.5f : 1.0f) * (1.0f - movement.getSpeedupRamp());
      int cost = wraith ? NORMAL_COST : map.getCost(tx, ty);
      int difficulty = wraith ? 0 : map.getDifficulty(tx, ty);
      int steps = Math.abs(tx - sx) + Math.abs(ty - sy);
      int tileX = gidrah.getTileX();
      int tileY = gidrah.getTileY();
      int basicDistance = (tileX - tx) * (tileX - tx) + (tileY - ty) * (tileY - ty);
      // Prevent clumping nearby
      if (cost == NORMAL_COST) {
         if (!wraith && basicDistance < CLUMP_DISTANCE_THRESHOLD) {
            int occupiedCount = 0;
            if (map.isOccupied(tx, ty)) {
               occupiedCount ++;
            }
            if (map.isOccupied(tx + 1, ty)) {
               occupiedCount ++;
            }
            if (map.isOccupied(tx, ty + 1)) {
               occupiedCount ++;
            }
            if (map.isOccupied(tx - 1, ty)) {
               occupiedCount ++;
            }
            if (map.isOccupied(tx, ty - 1)) {
               occupiedCount ++;
            }
            if (map.isOccupied(tx + 1, ty + 1)) {
               occupiedCount ++;
            }
            if (map.isOccupied(tx - 1, ty - 1)) {
               occupiedCount ++;
            }
            if (map.isOccupied(tx - 1, ty + 1)) {
               occupiedCount ++;
            }
            if (map.isOccupied(tx + 1, ty - 1)) {
               occupiedCount ++;
            }
            if (occupiedCount >= 4) {
               cost += FPMath.ONE;
            }
         }
      } else {
         // Roads mean we worry much less about danger or difficulty
         bias *= 0.5f;
         difficulty >>= 1;
      }
      if (map.isAttacking(tx, ty)) {
         cost += FPMath.FOUR;
      }

      if (diagonal) {
         if (steps == 2) {
            // Diagonal
            return FPMath.fpValue(bias) + cost + FPMath.fpValue(difficulty);
         } else {
            assert steps == 1;
            return (int) (cost * DIAGONAL_FACTOR + FPMath.fpValue(DIAGONAL_FACTOR * bias)  + FPMath.fpValue(difficulty * DIAGONAL_FACTOR)) * 5; // Really discourage horiz/vert movement with x5 multiplier to cost
         }
      } else {
         if (steps == 1) {
            return FPMath.fpValue(bias) + cost + FPMath.fpValue(difficulty);
         } else {
            assert steps == 2;
            // Diagonal
            return (int) (cost * DIAGONAL_FACTOR) + FPMath.fpValue(DIAGONAL_FACTOR * bias) + FPMath.fpValue(difficulty * DIAGONAL_FACTOR);
         }
      }
   }


Cas Smiley

Offline CommanderKeith
« Reply #15 - Posted 2011-01-20 00:44:38 »

Very cool, seems to work well for big maps. How does memory allocation go for even bigger maps?

It'd be interesting to see the frame rate, and make it so that the end point was draggable and the path formed straight away, and also to make it so that walls can't be selected as an end point.

For "visitedMap", why not use boolean[][] rather than GridDouble's ArrayList<ArrayList<Double>>? You could also use a boolean[] and index it like array[y * width + x]. Even better, if you use int[][] then you can avoid calling reset(0). Instead you use an int "currentID". At the beginning of each path finding, you increment currentID. Then during path finding, if the int[x][y] != currentID you treat it as unset, else you treat it as set.

This currentID method is ingenious, worked really well for me. No need to clear states all the time.

Offline Jono
« Reply #16 - Posted 2011-01-20 09:46:22 »

Quote
So yeah, in your case a Euclidean heuristic is necessary.
There are other admissible heuristics. E.g. max(abs(x - x0), abs(y - y0)).

True, bad wording on my part.

Is there a mistake in the second heuristic though? Won't
1  
int heuristic = max + (dx + dy - max) / (2 * max);

just be equal to max because of integer rounding?

With diagonal moves costing sqrt(2) rather than 1, perhaps it could be:
1  
2  
3  
4  
int dx = x - x0; if (dx < 0) dx = -dx;
int dy = y - y0; if (dy < 0) dy = -dy;
int max = dx > dy ? dx : dy;
double heuristic = max - (dx + dy - max) + Math.sqrt(2) * (dx + dy - max);

Ok, so not coded to be efficient any more, but it dominates the Euclidean distance this way and is guaranteed to expand fewer nodes.
Offline pjt33
« Reply #17 - Posted 2011-01-20 14:02:24 »

Is there a mistake in the second heuristic though? Won't
1  
int heuristic = max + (dx + dy - max) / (2 * max);

just be equal to max because of integer rounding?
Yes, oops. Works for doubles, though. The logic there was

sqrt(x^2 + y^2) = sqrt(max^2 + min^2) = max sqrt(1 + (min/max)^2) < max (1 + 0.5 (min/max)^2) = max + min^2 / (2 max) <= max + min / (2 max)

The last step was just to save a multiplication, and isn't valid with double inputs.
Offline Roquen
« Reply #18 - Posted 2011-01-20 14:18:11 »

Why bother with sqrt or max/min?  Euclidean distance squared is an equivalent metric to euclidean distance. (if a*a > b*b, then |a| > |b|)
Offline pjt33
« Reply #19 - Posted 2011-01-20 15:05:09 »

Why bother with sqrt or max/min?  Euclidean distance squared is an equivalent metric to euclidean distance. (if a*a > b*b, then |a| > |b|)
And then use the square of each edge weight?
Offline Jono
« Reply #20 - Posted 2011-01-20 15:23:44 »

Why bother with sqrt or max/min?  Euclidean distance squared is an equivalent metric to euclidean distance. (if a*a > b*b, then |a| > |b|)
The problem is that you actually need to combine the results of the heuristic with the cost so far. So if just using the square of the heuristic you'd have f(x) = g(x) + h(x)*h(x), which for heuristic values greater than 1 would make the search tend to a best-first (and the heuristic is non-admissible).

Taking the square of the cost so far doesn't fix it either, because g(x)*g(x) + h(x)*h(x) still doesn't have the same metric properties as g(x) + h(x).
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #21 - Posted 2011-01-20 17:03:04 »

So yeah, in your case a Euclidean heuristic is necessary.
There are other admissible heuristics. E.g. max(abs(x - x0), abs(y - y0)).

Edit: or
1  
2  
3  
4  
int dx = x - x0; if (dx < 0) dx = -dx;
int dy = y - y0; if (dy < 0) dy = -dy;
int max = dx > dy ? dx : dy;
int heuristic = max + (dx + dy - max) / (2 * max);

Yes, I should have clarified, I meant between Manhattan and Euclidean distances. Smiley

In my game Sinuosity because it's a maze where you can never go diagonally Manhattan distance works excellently. I would imagine that if you allowed diagonals you could just do a smarter version of Manhattan where you use sqrt(2) for the diagonals and 1 for direct angles. That is, if you consider a diagonal to cost more than u/d/l/r, considering it is in fact a longer distance.

See my work:
OTC Software
Offline appel

JGO Wizard


Medals: 68
Projects: 4


I always win!


« Reply #22 - Posted 2011-01-21 16:10:03 »

Few years ago I worked on a pathfinder project.

If you're interested you can see it here: http://gamadu.com/temp/stuff/Pathfinder.zip

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

Senior Newbie





« Reply #23 - Posted 2011-04-10 13:37:16 »

Hi,
When running the applet from the browser, the path does not start after the two clicks.
When building and running from sources, the pathfind returns a null path at the following call Sad

GridPath aPath = pathfinding.getPath(mouse.getStart(), mouse.getEnd(), draw.getMap());

Any suggestion to have the demo running?! It seems great!
Cheers Smiley
Martin
Offline Gudradain
« Reply #24 - Posted 2011-04-10 18:27:08 »

Just test it and it still work fine. You need to do a right click and a left click and you need to click on empty space.
Offline martin

Senior Newbie





« Reply #25 - Posted 2011-04-19 12:44:16 »

That's what I did :/
I will tell you if I find the reason.
Cheers,
Martin
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.

rwatson462 (33 views)
2014-12-15 09:26:44

Mr.CodeIt (23 views)
2014-12-14 19:50:38

BurntPizza (51 views)
2014-12-09 22:41:13

BurntPizza (84 views)
2014-12-08 04:46:31

JscottyBieshaar (45 views)
2014-12-05 12:39:02

SHC (59 views)
2014-12-03 16:27:13

CopyableCougar4 (58 views)
2014-11-29 21:32:03

toopeicgaming1999 (123 views)
2014-11-26 15:22:04

toopeicgaming1999 (114 views)
2014-11-26 15:20:36

toopeicgaming1999 (32 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

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
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!