Pathfinding on staggered maps

This topic is 2682 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

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

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.

I would really appreciate your help.
Thanks!

Share on other sites
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.

Share on other sites
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:
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:

As I told i already said I'm already that kind of conversion to move the player tile-to-tile, which works perfect.

Share on other sites
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.

Share on other sites
Eehm, currently i guess it's calculated that way:

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;
}

Share on other sites

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.

Share on other sites
- Determine the orientation to the target tile
- Assign a score based on the orientation : N/E/S/W : 1, NE/NW/SE/SW : 1.4

Note that this only works with adjacent tiles, but that's all you should have when working with A*.

Share on other sites
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.

Share on other sites
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.

Share on other sites
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); newNode.g = currentNode.g + cost(currentNode, newNode); newNode.h = heuristic(newNode, destination); newNode.f = newNode.g + newNode.h; map[newNode.x+"-"+newNode.y].f = f; open.push(newNode); } } } } return []; } 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 */ this.x = x; this.y = y; this.parentIndex = parentIndex; this.g = g; this.h = h; this.f = f; }

(0 == walkable)

• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 9
• 13
• 9
• 9
• 15
• Forum Statistics

• Total Topics
634077
• Total Posts
3015359
×