Gudradain


«
Posted
20110119 02:55:55 » 

Hello, Just finish my astar pathfinding : you can check the demo here : DemoLeft 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); } } 




loom_weaver


«
Reply #1  Posted
20110119 03:22:29 » 

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




Gudradain


«
Reply #2  Posted
20110119 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!


Jono


«
Reply #3  Posted
20110119 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.




Nate


«
Reply #4  Posted
20110119 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.




Jono


«
Reply #5  Posted
20110119 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.




Gudradain


«
Reply #6  Posted
20110119 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.




Gudradain


«
Reply #7  Posted
20110119 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...)




Jono


«
Reply #8  Posted
20110119 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 gridworld 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.




Gudradain


«
Reply #9  Posted
20110119 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!


Jono


«
Reply #10  Posted
20110119 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.




Gudradain


«
Reply #11  Posted
20110119 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...)




Eli Delventhal


«
Reply #12  Posted
20110119 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.




pjt33


«
Reply #13  Posted
20110119 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); 




princec


«
Reply #14  Posted
20110120 00:18:39 » 

Or even this 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;
public int getCost(int from, int to) { if (from == to) { return 0; }
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); 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 { bias *= 0.5f; difficulty >>= 1; } if (map.isAttacking(tx, ty)) { cost += FPMath.FOUR; }
if (diagonal) { if (steps == 2) { 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; } } else { if (steps == 1) { return FPMath.fpValue(bias) + cost + FPMath.fpValue(difficulty); } else { assert steps == 2; return (int) (cost * DIAGONAL_FACTOR) + FPMath.fpValue(DIAGONAL_FACTOR * bias) + FPMath.fpValue(difficulty * DIAGONAL_FACTOR); } } } 
Cas




CommanderKeith


«
Reply #15  Posted
20110120 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.




Jono


«
Reply #16  Posted
20110120 09:46:22 » 

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.




pjt33


«
Reply #17  Posted
20110120 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.




Roquen


«
Reply #18  Posted
20110120 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)




pjt33


«
Reply #19  Posted
20110120 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?




Jono


«
Reply #20  Posted
20110120 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 bestfirst (and the heuristic is nonadmissible). 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).




Eli Delventhal


«
Reply #21  Posted
20110120 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. 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.





martin
Senior Newbie


«
Reply #23  Posted
20110410 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 GridPath aPath = pathfinding.getPath(mouse.getStart(), mouse.getEnd(), draw.getMap()); Any suggestion to have the demo running?! It seems great! Cheers Martin




Gudradain


«
Reply #24  Posted
20110410 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.




martin
Senior Newbie


«
Reply #25  Posted
20110419 12:44:16 » 

That's what I did :/ I will tell you if I find the reason. Cheers, Martin




