Jump to content
  • Advertisement

MCHammer

Member
  • Content Count

    6
  • Joined

  • Last visited

Community Reputation

100 Neutral

About MCHammer

  • Rank
    Newbie
  1. MCHammer

    Pathfinding on staggered maps

    Uhhm, I made some mistakes trying to convert coordinates and changing other stuff based on the wrong coordinates. Also I didn't change (or in a wrong way) g-cost at some point. So after all it was some messed up code an that's why i had i look at some a*-tutorials and tried to understand, before I got back programming. My lession: Learn from the beginning, before you try to fix / change third-party code. So here it is (Z-Index needs to get fixed ):
  2. MCHammer

    Pathfinding on staggered maps

    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)
  3. MCHammer

    Pathfinding on staggered maps

    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.
  4. MCHammer

    Pathfinding on staggered maps

    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; }
  5. MCHammer

    Pathfinding on staggered maps

    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.
  6. 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. I would really appreciate your help. Thanks!
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!