Astar Pathfinding

[Gudradain]

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 :

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 :

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 :

     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]

Nice demo.

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

http://square.png

[Gudradain]

@loom_weaver

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.

[Jono]

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]

For “visitedMap”, why not use boolean[][] rather than GridDouble’s ArrayList<ArrayList>? 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]

… 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]

@Jono

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]

@Nate

For “visitedMap”, why not use boolean[][] rather than GridDouble’s ArrayList<ArrayList>? 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> and double[][]?

Usually I prefer avoiding design that require currentID (what if currentID become greater than Integer.MAX_VALUE? ok stupid reason…)

[Jono]

@Gudradain

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.

[Gudradain]

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

@Jono

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?

[Jono]

@Gudradain

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:

http://www.cs.auckland.ac.nz/~jteu004/aStarExample.png

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]

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…)

[Demonpants]

@Jono

@Gudradain

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:

http://www.cs.auckland.ac.nz/~jteu004/aStarExample.png

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]

@Eli Delventhal

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

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]

Or even this ;D

	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

[CommanderKeith]

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.

@Nate

For “visitedMap”, why not use boolean[][] rather than GridDouble’s ArrayList<ArrayList>? 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]

@pjt33

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

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:

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]

@Jono

Is there a mistake in the second heuristic though? Won’t

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]

Why bother with sqrt or max/min? Euclidean distance squared is an equivalent metric to euclidean distance. (if aa > bb, then |a| > |b|)

[pjt33]

@Roquen

Why bother with sqrt or max/min? Euclidean distance squared is an equivalent metric to euclidean distance. (if aa > bb, then |a| > |b|)

And then use the square of each edge weight?