A* Pathing Algorythm

C++, C#, Java, PHP, ect...
Post Reply
ShawnSwander
Posts: 53
Joined: Thu May 17, 2012 12:31 am

A* Pathing Algorythm

Post by ShawnSwander »

I couldn't find a decent pathing algorythm on the internet the last time I wrote one it took me days I don't know if it's just the way I think or if I'm dyslexic or what. But I have the code I figured I would share it and also I'm probably going to improve it a bit and make it a little more flexible for people to use in their games.

I"ve never seen an A* algorythm that was concide and easy to read... To me this is close. I'm not the best coder in the world though and I think this is one of the more complex snippets of my game.

This code paths on a grid that looks like this
(pseudocode) in my game it's actually path = Array(49) not 7 arrays of 7

Code: Select all

[00,01,02,03,04,05,06]
[07,08,09,10,11,12,13]
[14,15,16,17,18,19,20]
[21,22,23,24,25,26,27]
[28,29,30,31,32,33,34]
[35,36,37,38,39,40,41]
[42,43,44,45,46,47,48]

Here's the code:

Code: Select all

<script>
var z =  0;
	function pathTo(goal){
		var createPath = function (goal){
			var createNode = function(i){
				this.id = i;
				this.g = Infinity;
				this.f = Infinity;
				this.parent = null;
				this.open = null;
			};
			
			this.nodes = Array(49);
			for(i=0;i<this.nodes.length;i++){
				this.nodes[i] = new createNode(i);
			}
			this.start = this.nodes[24];
			this.start.g = 0;
			this.currentNodeId = 24;
			this.goal = this.nodes[goal];
			this.bestPath = null;
		};//end createPath
		var path = new createPath(goal);
		var getBestNeighbor = function(nodeId){

			var getG = function(parentG){
				//here you can check the map for water, sand, and ruins penalties
				/*
					default = 1
					path = .9
					water = 3
				*/

				return (parentG + 1);
			};
			var closeNode = function (node){
				node.open = false;
			};//end closeNode
			var getF = function(startId,endId,g){
				var startX = startId % 7;
				var startY = (startId - startX) / 7;
				var endX = endId % 7;
				var endY = (endId - endX) / 7;
				var h = Math.sqrt( Math.pow((startX - endX) , 2 ) + Math.pow(( startY - endY ), 2 ) );
				return (h + g);
			};//end getF
			var tracePath = function(tracedNode){
				path.bestPath = [];
				while(tracedNode != path.start){
					path.bestPath.unshift(tracedNode.id);
					tracedNode = tracedNode.parent;
				}
				return path.bestPath;
			};//end tracePath
			var getNeighborNodeId = function(x,y,currentId){return currentId + (y*7) + x;};//end getNeighborNodeId
			debugger;
			z++
			if(z>50){throw z}
			if(path.bestPath === null){
				var neighborNode = {};
				var bestNode = {f: Infinity};
				if(nodeId == path.goal.id){//may need to pass path
					return tracePath(path.nodes[nodeId]);
				}else{
					for(y=-1;y<=1;y++){
						for(x=-1;x<=1;x++){
							var nnId = getNeighborNodeId(x,y,nodeId); 
								if( ( !(x==0 && y==0) && ( nnId>=0 && nnId<=48))){
									var neighborNode = path.nodes[nnId];
									if(path.nodes[nodeId].parent!=neighborNode){
										if(neighborNode.open === null){ neighborNode.open = true; }
										if(neighborNode.open === true ){//don't check closed neighbors
											if(typeof neighborNode === "object"){
												neighborNode.parent = path.nodes[nodeId]
												neighborNode.g = getG(neighborNode.parent.g);
												neighborNode.f = getF(neighborNode.id , path.goal.id , neighborNode.g);
												if( neighborNode.f < bestNode.f){
													bestNode = neighborNode;
												}//endif
											}//endif
										}
									}//endif Note: if the node isn't null or true, it's false.
								}
						}//endfor
					}//endfor - Note: Here we should have the best neighbor
					if(bestNode.f >= 50){ //limit crazy pathing errors.
						closeNode(path.nodes[nodeId]);//need escape for no possible path
						return;
					}else{
						path.currentNodeId = bestNode.id;
						getBestNeighbor(bestNode.id);
					}//endelse
				}//endelse
			}//endif
		};//end getBestNeighbor
		while(path.bestPath === null){
			getBestNeighbor(path.currentNodeId);
		}//end while
		return path.bestPath;
	}//end pathTo
	myPath = pathTo(41);  //testing with 6
	console.log("path2:"+myPath);
</script>
this is made for a player standing in the middle of a 7x7 grid so there are some numbers hard coded in. It's designed for a server based game so it assumes the player can't access the entire map and players and AI will use the area they can see

I'm also going to change the function so you input a start and a finish this assumes you start in the center of the 49 tiles which is the 25th tile "path.node[24]"

I wrote it so it's really easy to make a plugin since it just outputs the id of a tile that can easily my converted into data for any tile based game.

The code still has debugging lines in it too it's 2am and I started coding it at 7 this morning while stopping to watch my infant daughter.
User avatar
a_bertrand
Posts: 1537
Joined: Mon Feb 25, 2013 1:46 pm

Re: A* Pathing Algorythm

Post by a_bertrand »

I can share my Typescript class here:

Code: Select all

interface PathStep extends PathPoint
{
    steps: number;
    path: PathStep[];
    distance?: number;
    operations: number;
}

interface PathPoint
{
    x: number;
    y: number;
}

class PathSolver
{
    private visitedStep: PathStep[] = [];
    private todoStep: PathStep[] = [];
    private width: number;
    private height: number;
    private goalX: number;
    private goalY: number;
    private operations: number = 0;
    private canWalkOn: (x: number, y: number) => boolean;
    private maxDistance: number;

    public static Solve(startX: number, startY: number, goalX: number, goalY: number, maxDistance: number, canWalkOn: (x: number, y: number) => boolean): PathPoint[]
    {
        var solver = new PathSolver(startX, startY, goalX, goalY, maxDistance, canWalkOn);
        var path = solver.solve();
        if (!path)
            return null;

        var result: PathPoint[] = [];
        for (var i = 0; i < path.path.length; i++)
        {
            result.push({
                x: path.path[i].x, y: path.path[i].y
            });
        }
        // Add the goal too
        if (result.length > 0)
            result.push({ x: goalX, y: goalY });
        return result;
    }

    constructor(startX: number, startY: number, goalX: number, goalY: number, maxDistance: number, canWalkOn: (x: number, y: number) => boolean)
    {
        this.visitedStep = [];
        this.todoStep = [];

        this.goalX = goalX;
        this.goalY = goalY;
        this.operations = 0;
        this.canWalkOn = canWalkOn;
        this.maxDistance = maxDistance;

        var a = startX - this.goalX;
        var b = startY - this.goalY;

        this.todoStep = [
            { x: startX, y: startY, steps: 0, path: [], operations: 0, distance: Math.sqrt(a * a + b * b) }
        ];
        this.visit(this.todoStep[0]);
    }

    private solve(): PathStep
    {
        while (this.todoStep.length > 0 && this.operations < 500)
        {
            this.operations++;
            var res = this.calcStep();
            if (res != null)
                return res;
        }
        return null;
    }

    private addCoordinate(coord: PathStep, x: number, y: number): PathStep
    {
        var x = coord.x + x;
        var y = coord.y + y;

        var path = coord.path.concat();
        path[path.length] = coord;

        var a = x - this.goalX;
        var b = y - this.goalY;

        return { x: x, y: y, steps: coord.steps + 1, path: path, distance: Math.sqrt(a * a + b * b), operations: this.operations };
    }

    private isVisited(coord: PathStep): boolean
    {
        for (var i = 0; i < this.visitedStep.length; i++)
            if (this.visitedStep[i].x == coord.x && this.visitedStep[i].y == coord.y)
                return true;
        return false;
    }

    private visit(coord: PathStep): void
    {
        this.visitedStep[this.visitedStep.length] = coord;
    }

    private static SortDistance(sa: PathStep, sb: PathStep): number
    {
        if (sa.steps == sb.steps)
            return sa.distance - sb.distance;
        else
            return sa.steps - sb.steps;
            //return (sa.steps + sa.distance * 2) - (sb.steps + sb.distance * 2);
    }

    private calcStep(): PathStep
    {
        this.todoStep.sort(PathSolver.SortDistance);
        var s = this.todoStep.shift();

        //if (Math.abs(s.x-this.goalX) <= this.speed && Math.abs(s.y-this.goalY) <= this.speed)
        //if (s.distance < this.speed)
        if (s.distance == 0)
        {
            s.operations = this.operations;
            return s;
        }

        if (this.todoStep.length > 5000)
        {
            this.todoStep = [];
            return null;
        }

        if (s.steps > 500)
            return null;

        var newCoords = [
            this.addCoordinate(s, -1, 0),
            this.addCoordinate(s, 0, -1),
            this.addCoordinate(s, 1, 0),
            this.addCoordinate(s, 0, 1),

            this.addCoordinate(s, -1, -1),
            this.addCoordinate(s, -1, 1),
            this.addCoordinate(s, 1, -1),
            this.addCoordinate(s, 1, 1),
        ];
        for (var i = 0; i < newCoords.length; i++)
        {
            var c = newCoords[i];
            if (c == null)
                continue;
            if (!this.isVisited(c) && c.distance < this.maxDistance)
            {
                this.visit(c);
                if (this.canWalkOn(c.x, c.y))
                    this.todoStep[this.todoStep.length] = c;
            }
        }
        return null;
    }
}
I can say how far it can go with the path finding (to avoid to eat too much CPU for example) and pass a "can walk" function to see if this cell is walkable or not.
Creator of Dot World Maker
Mad programmer and annoying composer
ShawnSwander
Posts: 53
Joined: Thu May 17, 2012 12:31 am

Re: A* Pathing Algorythm

Post by ShawnSwander »

that's good to know I hadn't thought of how I'm going to implement obstacles.

I could either write it to prefer certain tiles or always avoid some.

For example a shark no matter what the situation is should always avoid land (unless it's in a tornado) :D

However an orc might prefer not to stand in fire. but if he has no choice he'll tough it out and move to your tile if it's on fire.

Thanks for sharing your script.
User avatar
a_bertrand
Posts: 1537
Joined: Mon Feb 25, 2013 1:46 pm

Re: A* Pathing Algorythm

Post by a_bertrand »

No problem. BTW that's the exact code I use in my Dot World Maker engine. The code presented here is in Typescript, but it's roughly the same which comes out in JS. If you want I can just compile you that one so you see how it look like in pure JS. Again I strongly suggest to use TS instead of JS ;)
Creator of Dot World Maker
Mad programmer and annoying composer
ShawnSwander
Posts: 53
Joined: Thu May 17, 2012 12:31 am

Re: A* Pathing Algorythm

Post by ShawnSwander »

Here is the code with collision detection implemented. The 7x7 grid is hard coded in but anyone could change the 49 and 7s to their own numbers or add some variables to pass into those values. It also throws an example of a wall in your way

Code: Select all

function pathTo(start, goal, collisionMap){
		var createPath = function (start, goal,collisionMap){
			var createNode = function(i){
				this.id = i;
				this.g = Infinity;
				this.f = Infinity;
				this.parent = null;
				this.open = null;
			};
			this.nodes = Array(49);
			for(i=0;i<this.nodes.length;i++){
				this.nodes[i] = new createNode(i);
			}
			this.start = this.nodes[start];
			this.start.g = 0;
			this.currentNodeId = start;
			this.goal = this.nodes[goal];
			this.bestPath = null;
			var colissionKey = ["none","wall","water","path"]//later you can change this to be more data efficient
			for(var i=0;i<collisionMap.length;i++){
				switch ( colissionKey[ collisionMap[i] ] ) {
					case "none":this.nodes[i].collisionPenalty = 0; break;
					case "wall":this.nodes[i].collisionPenalty = Infinity; break;
					case "water":this.nodes[i].collisionPenalty = 1; break;
					case "path":this.nodes[i].collisionPenalty = -0.1; break;
				}
				if(this.nodes[i] == this.goal){ //if your goal is a bad square the game will allow you to attempt to reach it.
					this.nodes[i].collisionPenalty = 0;
				}
			}
		};//end createPath
		
		var path = new createPath(start,goal,collisionMap);
		var getBestNeighbor = function(nodeId){

			var getG = function(parentG,collisionPenalty){
				return (parentG + 1 + collisionPenalty);
			};
			var closeNode = function (node){
				node.open = false;
			};//end closeNode
			var getF = function(startId,endId,g){
				var startX = startId % 7;
				var startY = (startId - startX) / 7;
				var endX = endId % 7;
				var endY = (endId - endX) / 7;
				var h = Math.sqrt( Math.pow((startX - endX) , 2 ) + Math.pow(( startY - endY ), 2 ) );
				return (h + g);
			};//end getF
			var tracePath = function(tracedNode){
				path.bestPath = [];
				while(tracedNode != path.start){
					path.bestPath.unshift(tracedNode.id);
					tracedNode = tracedNode.parent;
				}
				return path.bestPath;
			};//end tracePath
			var getNeighborNodeId = function(x,y,currentId){return currentId + (y*7) + x;};//end getNeighborNodeId
			if(path.bestPath === null){
				var neighborNode = {};
				var bestNode = {f: Infinity};
				if(nodeId == path.goal.id){//may need to pass path
					return tracePath(path.nodes[nodeId]);
				}else{
					for(y=-1;y<=1;y++){
						for(x=-1;x<=1;x++){
							var nnId = getNeighborNodeId(x,y,nodeId); 
								if( ( !(x==0 && y==0) && ( nnId>=0 && nnId<=48))){
									var neighborNode = path.nodes[nnId];
									if(path.nodes[nodeId].parent!=neighborNode){
										if(neighborNode.open === null){ neighborNode.open = true; }
										if(neighborNode.open === true ){//don't check closed neighbors
											if(typeof neighborNode === "object"){
												neighborNode.parent = path.nodes[nodeId]
												neighborNode.g = getG(neighborNode.parent.g,neighborNode.collisionPenalty);
												neighborNode.f = getF(neighborNode.id , path.goal.id , neighborNode.g);
												if( neighborNode.f < bestNode.f){
													bestNode = neighborNode;
												}//endif
											}//endif
										}
									}//endif Note: if the node isn't null or true, it's false.
								}
						}//endfor
					}//endfor - Note: Here we should have the best neighbor
					if(bestNode.f >= 50){ //limit crazy pathing errors.
						closeNode(path.nodes[nodeId]);//need escape for no possible path
						return;
					}else{
						path.currentNodeId = bestNode.id;
						getBestNeighbor(bestNode.id);
					}//endelse
				}//endelse
			}//endif
		};//end getBestNeighbor
		while(path.bestPath === null){
			getBestNeighbor(path.currentNodeId);
		}//end while
		return path.bestPath;
	}//end pathTo
	emptyGrid = 
	[
		0,0,0,0,0,0,0,
		0,0,0,0,0,0,0,
		0,0,0,0,0,0,0,
		0,0,0,0,0,0,0,
		0,0,0,0,0,0,0,
		0,0,0,0,0,0,0,
		0,0,0,0,0,0,0,
		]
	emptyGrid[18] = 1;
	emptyGrid[25] = 1;
	emptyGrid[32] = 1;
	p = pathTo(24,41,emptyGrid)
ShawnSwander
Posts: 53
Joined: Thu May 17, 2012 12:31 am

Re: A* Pathing Algorythm

Post by ShawnSwander »

I've never heard of type script before I was a computer science dropout and went into IT instead. :P

The logic of your code is easy to follow though. I wish I would have asked for help yesterday when I was pulling my hair out but I always feel like a heel asking for help with code.
Post Reply

Return to “Coding”