Hi!
I'm using a staggered style map to display my isometric tiles and i quite can't get my pathfinding to work correctly. It works perfectly in diamond-mode, as you can see here:
I tried to translate movement, wich works fine when i move tile-by-tile using keyboard-commands, but still, pathfinding won't work with that conversion (and some other experiments, found in this forum). See vid (first seconds walking, 0:14 pathfinding in diamond-style zig-zagging north): http://www.youtube.c...player_embedded
One thing iIdidn't try: Setting different costs for diiagonaly/horizontaly, cause the 4 pathfinding-algorithms [all (lite) a*] I tried dont support it or I just can't find it, cause I'm not really farmiliar with it. The game is programmed in javascript, so maybe anyone can help me with that, an pseudocode example or anything like that.
A* doesn't care about how the tiles are represented since it works on a graph. The tiles are the nodes and the ways to go from one tile to another are the connections. What you need is to figure out how to represents the same transitions from one model to the next.
For example, in diamond-mode, the tile down is (+1, +1). In staggered, it's (0, +2). The only thing that should change in your code is when you are adding unexplored nodes. Instead of getting the tile (+1, +1) to get the one below, you get the tile (0, +2). Do this for all 8 directions and it should work.
Developer for Novus Dawn : a [s]Flash[/s] Unity Isometric Tactical RPG - Forums - Facebook - DevLog
I've tried that and it works for the 4 basic directions. But you have to remember, that each diagonal move depens on the tile you're currently standing on: http://www.abload.de...rgleich8qlk.png
If you're standing on tile 37-25 the next tile directed north-west is 38-24 = 1 -1
If you're standing on tile 38-26 the next tile directed north-west is 38-25 = 0 -1
Altough I'm accounting tor that case in all 4 diagonal directions, pathfinding does strange stuff: http://www.youtube.c...h?v=SMrtITYXCTo
As I told i already said I'm already that kind of conversion to move the player tile-to-tile, which works perfect.
How do you calculate the cost to move from a tile to the other? If you base it on the coordinates, that's the problem. It should be independent of the coordinate system and rely on the actual distance between 2 tiles.
Developer for Novus Dawn : a [s]Flash[/s] Unity Isometric Tactical RPG - Forums - Facebook - DevLog
function heuristic(current_node, destination)
{
//Find the straight-line distance between the current node and the destination. (Thanks to id for the improvement)
//return Math.floor(Math.sqrt(Math.pow(current_node.x-destination.x, 2)+Math.pow(current_node.y-destination.y, 2)));
var x = current_node.x-destination.x;
var y = current_node.y-destination.y;
return x*x+y*y;
}
function heuristic(current_node, destination)
{
//Find the straight-line distance between the current node and the destination. (Thanks to id for the improvement)
//return Math.floor(Math.sqrt(Math.pow(current_node.x-destination.x, 2)+Math.pow(current_node.y-destination.y, 2)));
var x = current_node.x-destination.x;
var y = current_node.y-destination.y;
return x*x+y*y;
}
Why are you not sqrting the return statement anymore? Won't this mess up stuff once you add the heuristic to the actual distance from start?
Also if you are rounding it down, players will favor moving diagonally in most situations even if their distance may not be best; though it usually will be.
edit: I think you should run in debug and step through it also. I'm surprised by how many people don't do this as it often makes problems super obvious.
Might be a dumb question but are you actually evaluating the 8 directions opposed to 4 directions? You have to alter your A* algorithm to take into account the 8 possible movement directions from the current location instead of just the 4. This can cause the zig-zagging movement. Also (as stated above) the costs can cause this as the A* thinks that zig zagging costs less than just moving once. Usually A* counts a diagonal movement as the cost of 1.4 times a regular square. So if moving in the regular 4 directions costs 10, moving in the additional 4 will cost 14. Another problem (related to costing) that may be happening is your algorithm is not taking into account previously traversed costs. You already know where you traveled from based on your parents.parent...etc so do not use a heuristic to estimate the distance from the start, actually calculate it based on the parents.
Hope this helps.
Remember to mark someones post as helpful if you found it so.
First thanks for all your help, I really appreciate it. I already tried 2 thing wich havn't worked, but I'm a little busy right now which is why I can't answer in detail right now.
I'll notify you, when I've tried all your tips and hopefully we will get it to work. Maybe I should upload the whole a*-algorithm.
I got it finally working \o/ Thanks for all your help.
Here's the complete Code:
//a* path-calculation
function astar(start, destination, board, cols, rows)
{
//create start and destination as true nodes
start = new node(start.x, start.y, -1, -1, -1, -1);
destination = new node(destination.x, destination.y, -1, -1, -1, -1);
//list of open nodes (nodes to be inspected)
var open = [];
//list of closed nodes (nodes we've already inspected)
var closed = [];
//cost from start to current node
var g = 0;
//cost from current node to destination
var h = heuristic(start, destination);
//cost from start to destination going through the current node
var f = g + h;
//push the start node onto the list of open nodes
open.push(start);
//keep going while there's nodes in our open list
while (open.length > 0)
{
//open list sorted lowest to highest (lowest f-value at index 0)
var bestCost = open[0].f;
var bestNode = 0;
for (var i = 1; i < open.length; i++)
{
if (open.f < bestCost)
{
bestCost = open.f;
bestNode = i;
}
}
//set it as our current node
var currentNode = open[bestNode];
//check if we've reached our destination
if (currentNode.x == destination.x && currentNode.y == destination.y)
{
//initialize the path with the destination node
var path = [destination];
//go up the chain to recreate the path
while (currentNode.parentIndex != -1)
{
currentNode = closed[currentNode.parentIndex];
path.unshift(currentNode);
}
return path;
}
//remove the current node from our open list
open.splice(bestNode, 1);
//push it onto the closed list
closed.push(currentNode);
//expand our current node (look in all 8 directions)
var oldPos = {x: currentNode.x, y: currentNode.y};
var newPos = new Array(9);
newPos[0] = utilGetNewPos("north", oldPos);
newPos[1] = utilGetNewPos("northEast", oldPos);
newPos[2] = utilGetNewPos("east", oldPos);
newPos[3] = utilGetNewPos("southEast", oldPos);
newPos[4] = utilGetNewPos("south", oldPos);
newPos[5] = utilGetNewPos("southWest", oldPos);
newPos[6] = utilGetNewPos("west", oldPos);
newPos[7] = utilGetNewPos("northWest", oldPos);
newPos[8] = oldPos;
for (var i = 0; i < newPos.length; i++)
{
//if the new node is open or the new node is our destination
if (board[newPos.x][newPos.y] == 0 || (destination.x == newPos.x && destination.y == newPos.y))
{
//see if the node is already in our closed list. if so, skip it.
var found_in_closed = false;
for (var j in closed)
{
if (closed[j].x == newPos.x && closed[j].y == newPos.y)
{
found_in_closed = true;
break;
}
}
if (found_in_closed)
continue;
//see if the node is in our open list. If not, use it.
var found_in_open = false;
for (var j in open)
{
if (open[j].x == newPos.x && open[j].y == newPos.y)
{
found_in_open = true;
break;
}
}
if (!found_in_open)
{
var newNode = new node(newPos.x, newPos.y, closed.length-1, -1, -1, -1);
function cost(currentNode, newNode)
{
var score = null;
var direction = utilGetDirection(currentNode, newNode);
if (direction == "north" || direction == "east" || direction == "south" || direction == "west")
score = 14;
else
score = 10;
return score;
}
//an a* heurisitic must be admissible, meaning it must never overestimate the distance to the goal.
//in other words, it must either underestimate or return exactly the distance to the goal.
function heuristic(currentNode, destination)
{
//find the straight-line distance between the current node and the destination.
return Math.floor(Math.sqrt(Math.pow(currentNode.x-destination.x, 2)+Math.pow(currentNode.y-destination.y, 2)));
}
function node(x, y, parentIndex, g, h, f)
{
/*
each node will have six values:
x position
y position
index of the node's parent in the closed array
cost from start to current node
heuristic cost from current node to destination
cost from start to destination going through the current node
*/
![http://www.abload.de...rgleich8qlk.png]("http://www.abload.de/image.php?img=vergleich8qlk.png"){kind=link}