A* with NO diagonals

My implementation of A* works great, but I have one problem with it: I need to avoid all diagonals.

Like this:

Currently it acts like this:

Any insights?

When checking for squares to add to the open list, only check the ones directly north/east/south/west of it to eliminate diagonals. However, this will make your path still look similar to your second picture, only going right up right up right up instead. In order to make the path tend to be straight like how your first picture is, increase the cost of turning or changing a direction in the path.

For my A* i did pretty much what adamkingdom suggested, and it looks exactly how he describes it.

if(cell.xpos - 1 >= 0) {
	adjacentCell = grid[cell.xpos - 1][cell.ypos];
	if(adjacentCell.cellType != FILLED && closedList.indexOf(adjacentCell) == -1) {
		adjacentCells.push(adjacentCell);
	}
}

if(cell.ypos - 1 >= 0) {
	adjacentCell = grid[cell.xpos][cell.ypos - 1];
	if(adjacentCell.cellType != FILLED && closedList.indexOf(adjacentCell) == -1) {
		adjacentCells.push(adjacentCell);
	}
}

if(cell.xpos + 1 <= gridWidth) {
	adjacentCell = grid[cell.xpos + 1][cell.ypos];
	if(adjacentCell.cellType != FILLED && closedList.indexOf(adjacentCell) == -1) {
		adjacentCells.push(adjacentCell);
	}
}

if(cell.ypos + 1 <= gridHeight) {
	adjacentCell = grid[cell.xpos][cell.ypos + 1];
	if(adjacentCell.cellType != FILLED && closedList.indexOf(adjacentCell) == -1) {
		adjacentCells.push(adjacentCell);
	}
}

Only checks cell’s that are to the immediate left,right,up and down of it. Also makes sure it doesn’t have a tile there already and that its not in the closed list.

Yeah, that’s my problem. I can’t do the zig-zagging either. It has to be as straight as possible, only turning when it needs to.

I think I will have to follow your second suggestion, adam, and increase the cost of turning.

How would I go about doing such a thing?

ATM I’m using the euclidian heuristic model.

Hmm. To implement the cost of turning in A* you need to provide movement direction to the solver, and you need to put movement direction when you add another cell to the array. And then you separately calculate additional cost for each of the neighboring cells based on their direction from the current cell and the direction where did we just enter that cell from.

Setting ‘any’ positive value for the turning cost should solve the basic problem (as this value tends to infinity, the choice of path depends more on minimising the number of turns). This is done in A* by incrementing the g cost for a node in the instance that its direction differs from its predecessor’s (i.e. (node(n).x - node(n-1).x) != (node(n-1).x - node(n-2).x), or similarly for y, assuming that we are only working in the cardinal directions – no ordinal directions as you’ve hinted in your diagram). Recall that g is determined before the node is added to the open list. Your h cost ‘should’ now incorporate a cost for the minimum number of turns required to reach the destination (i.e. either 0 or 1 in any case).

http://www.kongregate.com/forums/4/topics/120784#posts-2637220

No, it’s only 0 or 1 if the grid is devoid of obstacles.

That’s not the point of heuristic calculation

Think about how you would assign the h cost using your method

I figured it out! For anyone wondering, I used this heuristic function:

public static function diagonalHeuristic(node:INode, destinationNode:INode, cost:Number = 1.0, diagonalCost:Number = 1.0):Number {
	var dx:Number = Math.abs(node.x - destinationNode.x);
	var dy:Number = Math.abs(node.y - destinationNode.y);
	
	var diag:Number = Math.min( dx, dy );
	var straight:Number = dx + dy;
	
	return diagonalCost * diag + cost * (straight - 2 * diag);
}

And then I just increased the cost of traveling diagonally.

Just increasing the cost wouldn’t work if you add walls.

Something like the below would return a path, which you wouldn’t want.

S..X
..X.
-X..
X..G

S = start, G = goal, .=walkable, X = wall

Can’t you just skip checking diagonal neighbours (like mentioned above)?

Originally posted by someone93:

Just increasing the cost wouldn’t work if you add walls.

Something like the below would return a path, which you wouldn’t want.

S..X
..X.
-X..
X..G

S = start, G = goal, .=walkable, X = wall

Can’t you just skip checking diagonal neighbours (like mentioned above)?

I do that as well.

Ah, I read the topic more closely now. You mean diagonal as in one step north then one step east, rather than one step north-east? My bad for missing that.

Simple. Don’t use Euclidean distance on a grid. Instead, use weighted Manhattan distancce (abs(x) + abs(y) + epsilon * abs(y)).
Epsilon should be so low, it doesn’t overestimate costs by more than one unit, so the path is still optimal.