|
|
metadata
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?
|
|
|
|
|
metadata
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.
|
|
|
|
|
metadata
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.
|
|
|
|
|
metadata
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.
|
|
|
|
|
metadata
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.
|
|
|
|
|
metadata
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](http://en.wikipedia.org/wiki/A*_search_algorithm) 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](http://en.wikipedia.org/wiki/A*_search_algorithm) ‘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](http://www.kongregate.com/forums/4/topics/120784#posts-2637220)
|
|
|
|
|
metadata
No, it’s only 0 or 1 if the grid is devoid of obstacles.
|
|
|
|
|
metadata
That’s not the point of heuristic calculation
Think about how you would assign the [h cost](http://en.wikipedia.org/wiki/A_star) using your method
|
|
|
|
|
metadata
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.
|
|
|
|
|
metadata
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)?
|
|
|
|
|
metadata
> *Originally posted by **[someone93](/forums/4/topics/310013?page=1#posts-6559650):***
>
> 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.
|
|
|
|
|
metadata
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.
|
|
|
|
|
metadata
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.
|
 "MoonlaughMaster"){kind=small}
 "adamkingdom"){kind=small}
 "BraydenBlack"){kind=small}
 "vesperbot"){kind=small}
 "Dealmaster13"){kind=small}
 "someone93"){kind=avatar}
 "pl0xz0rz"){kind=small}