php/javscript/game coders v.experiment with A* path finding algorithm

Discussion in 'OT Technology' started by durondude, Dec 5, 2009.

  1. durondude

    durondude OT Addict

    Joined:
    May 7, 2001
    Messages:
    24,062
    Likes Received:
    5
    Location:
    Earth, The Planet
    Written in fucking php/javascript :rofl:

    http://tech-mafia.com/test/findpath.php

    Will be implementing into new iphone/ipod touch game once, it's perfected.

    - Having some issues with parentNodes dropping off early in the trace back if path is too long but this might have something to do with either javascript array size limits or javascript timeout limits.

    - Right now, it's using a simple manhattan algorithm to estimate distance to target. Trying to see if I can use different methods.

    - Might try implementing quad tree if there's enough time.
    Code:
    <?php
    $rows = 30;
    $cols = 30;
    ?>
    <html>
    <style>
    td
    {
    	width: 20px;
    	height: 20px;
    	border: 1px solid #777;
    	font-size: 10px;
    	color: #FFF;
    }
    
    .blank
    {
    	background-color: #DDD;
    }
    
    .start
    {
    	background-color: #0F0;
    }
    
    .end
    {
    	background-color: #F00;
    }
    
    .wall
    {
    	background-color: #777;
    }
    
    .highlight
    {
    	background-color: #aaF;
    }
    
    .path
    {
    	background-color: #00F;
    }
    </style>
    <script src="jquery.min.js"></script>
    <script language="javascript">
    //Global stuff
    var rows = <?php echo $rows; ?>;
    var cols = <?php echo $cols; ?>;
    var types = new Array(4);
    types[0] = 'blank';
    types[1] = 'wall';
    types[2] = 'start';
    types[3] = 'end';
    
    var nodes = new Array(<?php echo $cols; ?>);
    <?php
    for($c=0; $c<$cols; $c++)
    {
    	echo "nodes[".$c."] = new Array(".$cols.");\n";
    	for($r=0; $r<$rows; $r++)
    	{
    		echo "nodes[".$c."][".$r."] = new Node();\n";
    		echo "nodes[".$c."][".$r."].SetPoint(".$c.",".$r.");\n";
    		echo "nodes[".$c."][".$r."].SetScore(0);\n";
    		echo "nodes[".$c."][".$r."].SetType(0);\n";
    	}
    }
    ?>
    
    var startPoint = new Point();
    var endPoint = new Point();
    var openNodes = new Array();
    var closedNodes = new Array();
    
    //arrow images
    arrows = new Array();
    arrows[0] = 'downright.png';
    arrows[1] = 'down.png';
    arrows[2] = 'downleft.png';
    arrows[3] = 'left.png';
    arrows[4] = 'upleft.png';
    arrows[5] = 'up.png';
    arrows[6] = 'upright.png';
    arrows[7] = 'right.png';
    
    //Point class
    function Point()
    {
    	var x;
    	var y;
    	
    	this.SetPoint = function(x,y)
    	{
    		this.x = x;
    		this.y = y;
    	}
    }
    
    //Node class
    function Node()
    {
    	var point;// = new Point();
    	var score;
    	var type;
    	var parentNode;// = new Node();
    	
    	this.SetPoint = function(x, y)
    	{
    		this.point = new Point();
    		this.point.SetPoint(x, y);
    	}
    	this.SetScore = function(score)
    	{
    		this.score = score;
    	}
    	this.SetType = function(type)
    	{
    		this.type = type;
    	}
    	this.SetParentNode = function(parentNode)
    	{
    		this.parentNode = parentNode;
    	}
    }
    
    function markBlock(x,y)
    {
    	var block = $('#type').val();
    	nodes[x][y].type = block;
    	$('#console').append(nodes[x][y].type+' set at '+x+','+y+'\n');
    	
    	//remove all classes
    	$('#node-'+x+'-'+y).removeClass('blank');
    	$('#node-'+x+'-'+y).removeClass('wall');
    	$('#node-'+x+'-'+y).removeClass('start');
    	$('#node-'+x+'-'+y).removeClass('end');
    	$('#node-'+x+'-'+y).removeClass('path');
    	$('#node-'+x+'-'+y).css('background-image', '');
    	
    	$('#node-'+x+'-'+y).addClass(types[block]);
    	
    	if( block == 2 ) //start
    	{
    		if( startPoint.x >= 0 )
    		{
    			startX = startPoint.x;
    			startY = startPoint.y;
    			$('#node-'+startPoint.x+'-'+startPoint.y).removeClass('start');
    			$('#node-'+startPoint.x+'-'+startPoint.y).addClass('blank');
    			nodes[startX][startY].type = 0;
    		}
    		startPoint.SetPoint(x, y);
    		//alert(startPoint.x+','+startPoint.y);
    	}
    	
    	if( block == 3 ) //end
    	{
    		if( endPoint.x >= 0 )
    		{
    			endX = endPoint.x;
    			endY = endPoint.y;
    			$('#node-'+endPoint.x+'-'+endPoint.y).removeClass('end');
    			$('#node-'+endPoint.x+'-'+endPoint.y).addClass('blank');
    			nodes[endX][endY].type = 0;
    		}
    		endPoint.SetPoint(x, y);
    		//alert(endPoint.x+','+endPoint.y);
    	}
    };
    
    function defaultNodes()
    {
    	//Define defaults
    	startPoint.SetPoint(1,1);
    	endPoint.SetPoint(28,28);
    	nodes[1][1].type = 2;
    	nodes[28][28].type = 3;
    	for(var c=0; c<25; c++)
    	{
    		nodes[10][c].type = 1;
    	}
    	for(var c=5; c<rows;c++)
    	{
    		nodes[20][c].type = 1;
    	}
    };
    
    function resetNodes()
    {
    	for( y = 0; y < rows; y++ )
    	{
    		for( x = 0; x < cols; x++ )
    		{
    			$('#node-'+x+'-'+y).removeClass('blank');
    			$('#node-'+x+'-'+y).removeClass('wall');
    			$('#node-'+x+'-'+y).removeClass('start');
    			$('#node-'+x+'-'+y).removeClass('end');
    			$('#node-'+x+'-'+y).removeClass('path');
    
    			$('#node-'+x+'-'+y).addClass(types[nodes[x][y].type]);
    			$('#node-'+x+'-'+y).css('background-image', '');
    			
    			nodes[x][y].score = 0;
    			nodes[x][y].parentNode = new Node();
    			
    			openNodes = new Array();
    			closedNodes = new Array();	
    		}
    	}
    };
    
    function clearNodes()
    {
    	if( confirm( 'Clear board?') )
    	{
    		for( y = 0; y < rows; y++ )
    		{
    			for( x = 0; x < cols; x++ )
    			{
    				nodes[x][y].score = 0;
    				nodes[x][y].type = 0;
    				nodes[x][y].parentNode = new Node();
    				startPoint = new Point();
    				endPoint = new Point();
    				
    				$('#node-'+x+'-'+y).removeClass('blank');
    				$('#node-'+x+'-'+y).removeClass('wall');
    				$('#node-'+x+'-'+y).removeClass('start');
    				$('#node-'+x+'-'+y).removeClass('end');
    				$('#node-'+x+'-'+y).removeClass('path');
    				$('#node-'+x+'-'+y).css('background-image', '');
    
    				$('#node-'+x+'-'+y).addClass('blank');
    
    				openNodes = new Array();
    				closedNodes = new Array();	
    			}
    		}
    	}
    };
    
    function drawNodes()
    {
    	//alert('draw nodes');	
    	for( y = 0; y < rows; y++ )
    	{
    		for( x = 0; x < cols; x++ )
    		{
    			$('#node-'+x+'-'+y).removeClass('blank');
    			$('#node-'+x+'-'+y).removeClass('wall');
    			$('#node-'+x+'-'+y).removeClass('start');
    			$('#node-'+x+'-'+y).removeClass('end');
    			$('#node-'+x+'-'+y).removeClass('path');
    
    			$('#node-'+x+'-'+y).addClass(types[nodes[x][y].type]);
    		}
    	}
    };
    
    function LowestScoreOpenNode()
    {
    	if( openNodes.length > 0 )
    	{
    		var lowestScore = openNodes[0].score;
    		var retNode = openNodes[0];
    		if( openNodes.length > 1 )
    		{
    			for( var c=0; c<openNodes.length; c++ )
    			{
    				if(openNodes[c].score < lowestScore)
    				{
    					lowestScore = openNodes[c].score;
    					retNode = openNodes[c];
    				}
    			}
    		}
    		return retNode;
    	}
    };
    
    function RemoveFromOpenNodes(node)
    {
    	for(var c=0; c<openNodes.length; c++)
    	{
    		if(node.point.x==openNodes[c].point.x && node.point.y==openNodes[c].point.y)
    		{
    			//$('#console').append('Removed node('+node.point.x+','+node.point.y+') from openList.\n');
    			openNodes.splice(c,1);
    			break;
    		}
    	}
    };
    
    function InClosedNodes(node)
    {
    	//$('#console').append('Checking closed nodes('+closedNodes.length+')\n');
    	if( closedNodes.length > 0 )
    	{
    		for(var c=0; c<closedNodes.length; c++)
    		{
    			//$('#console').append('- closed node('+closedNodes[c].point.x+','+closedNodes[c].point.y+') - against('+node.point.x+','+node.point.y+')\n');
    			if(node.point.x==closedNodes[c].point.x && node.point.y==closedNodes[c].point.y)
    			{
    				//$('#console').append('- Found!\n');
    				return true;
    			}
    		}
    	}
    	//$('#console').append('- NOT Found!\n');	
    	return false;
    };
    
    function TracePath(node)
    {
    	//alert('in trace');
    	//alert('drawPath starting from ('+node.point.x+','+node.point.y+')');
    	parentNode = node.parentNode;
    	//alert(parentNode.point.x+','+parentNode.point.y);
    	//alert('parent ('+parentNode.getX()+','+parentNode.getY()+')')
    	while( node.point.x!=startPoint.x && node.point.y!=startPoint.y )
    	{
    		//alert('drawing path');
    		$('#node-'+node.point.x+'-'+node.point.y).addClass('path');
    		//$('#console').append('Drawing path @ '+node.point.x+','+node.point.y+' ');
    		//$('#console').append('parent is ('+parentNode.point.x+','+parentNode.point.y+')\n');
    		
    		node = parentNode;
    		parentNode = node.parentNode;
    		
    		//$('#console').append('next is ('+node.point.x+','+node.point.y+') ');		
    		//$('#console').append('parent is ('+parentNode.point.x+','+parentNode.point.y+')\n');
    	}
    	//alert('done!');
    };
    
    function findPath()
    {
    	if( startPoint.x == null || endPoint.x == null )
    	{
    		alert('Must have start and end points!');
    		return;
    	}
    	resetNodes();
    	drawNodes();
    	
    	//Add starting node to open list and start
    	openNodes.push(nodes[startPoint.x][startPoint.y]);
    	
    	count = 0;
    	endFound = false;
    	
    	while( openNodes.length > 0 && endFound == false )
    	{
    		currentNode = LowestScoreOpenNode();
    
    		closedNodes.push(currentNode);
    		RemoveFromOpenNodes(currentNode);
    		
    		/*
    		if( count++ > 900 )
    		{
    			break;
    		}
    		*/
    		//$('#console').append('Working with smallest node ('+currentNode.point.x+','+currentNode.point.y+'):'+currentNode.score+'\n');
    		
    		surroundPoints = new Array();
    		x = currentNode.point.x;
    		y = currentNode.point.y;
    		
    		surroundPoints[0] = new Point(); //top left
    		surroundPoints[1] = new Point(); //top
    		surroundPoints[2] = new Point(); //top right
    		surroundPoints[3] = new Point(); //right
    		surroundPoints[4] = new Point(); //bottom right
    		surroundPoints[5] = new Point(); //bottom
    		surroundPoints[6] = new Point(); //bottom left
    		surroundPoints[7] = new Point(); //left
    		surroundPoints[0].SetPoint(x-1, y-1); //top left
    		surroundPoints[1].SetPoint(x, y-1); //top
    		surroundPoints[2].SetPoint(x+1, y-1); //top right
    		surroundPoints[3].SetPoint(x+1, y); //right
    		surroundPoints[4].SetPoint(x+1, y+1); //bottom right
    		surroundPoints[5].SetPoint(x, y+1); //bottom
    		surroundPoints[6].SetPoint(x-1, y+1); //bottom left
    		surroundPoints[7].SetPoint(x-1, y); //left
    		
    		//Check surrounding points and add to openNodes
    		for(var c=0; c<8; c++)
    		{
    			var cx = surroundPoints[c].x;
    			var cy = surroundPoints[c].y;
    			
    			//Check bounds
    			if( cx>=0 && cx<cols && cy>=0 && cy<rows )
    			{
    				if( endPoint.x==cx && endPoint.y==cy )
    				{
    					//alert('End Found!');
    					TracePath(currentNode);
    					endFound = true;
    				}
    				else
    				{
    					//Check block type
    					if( nodes[cx][cy].type == 0 )
    					{
    						//Check if closed nodes list is empty or node in closed nodes list
    						if( closedNodes.length == 0 || InClosedNodes(nodes[cx][cy]) == false )
    						{
    							//Check if score is 0
    							if( nodes[cx][cy].score == 0 )
    							{
    								//Now we're good to go!
    								//$('#console').append('Working with '+cx+','+cy+' : '+nodes[cx][cy].score+'\n');
    
    								nodes[cx][cy].SetParentNode(currentNode);
    
    								//Calculate score
    								if( c==1 || c==3 || c==5 || c==7 )
    								{
    									var A = (currentNode.score+1);
    								}
    								else
    								{
    									var A = (currentNode.score+1.414213562373095);
    								}
    								var B = ( Math.abs(cx-endPoint.x) + Math.abs(cy-endPoint.y) );
    								nodes[cx][cy].score = (B + A);
    
    								openNodes.push(nodes[cx][cy]);
    
    								//$('#console').append('- Score for node('+cx+','+cy+') = '+nodes[cx][cy].score+'\n');
    
    								$('#node-'+cx+'-'+cy).css( 'background-image', 'url('+arrows[c]+')');
    							}
    						}
    					}
    				}
    			}
    		}
    		//$('#console').append('DONE with node('+x+','+y+'):'+currentNode.score+', moving to next. Open: '+openNodes.length+',Closed: '+closedNodes.length+'\n');
    	}
    };
    //debug
    //alert(nodes[3][4].point.x+','+nodes[3][4].point.y);
    </script>
    <body>
    	<table cellspacing="1px" cellpadding="0px">
    	<?php
    	for( $row = 0; $row < $rows; $row++ )
    	{
    		echo '<tr>';
    		for( $col = 0; $col < $cols; $col++ )
    		{
    			echo '<td class="blank" id="node-'.$col.'-'.$row.'" onClick="markBlock('.$col.','.$row.');"></td>';
    		}
    		echo '</tr>';
    	}
    	?>
    	</table>
    	Block type:
    	<select name="type" id="type">
    		<option value="1">wall</option>
    		<option value="0">blank</option>
    		<option value="2">start</option>
    		<option value="3">end</option>
    	</select>
    	<br>
    	<input type="button" value="clear" onClick="clearNodes()">
    	<input type="button" value="reset" onClick="resetNodes()">
    	<br>
    	<input type="button" value="Find Path" onClick="setTimeout('findPath()',0)">
    	<br>
    	<textarea readonly="readonly" id="console" cols="50" rows="10"></textarea>
    </body>
    <script language="javascript">
    defaultNodes();
    drawNodes();
    </script>
    </html>
    Any hints?:x:
     
  2. Limp_Brisket

    Limp_Brisket New Member

    Joined:
    Jan 2, 2006
    Messages:
    48,422
    Likes Received:
    0
    Location:
    Utah
  3. durondude

    durondude OT Addict

    Joined:
    May 7, 2001
    Messages:
    24,062
    Likes Received:
    5
    Location:
    Earth, The Planet
  4. durondude

    durondude OT Addict

    Joined:
    May 7, 2001
    Messages:
    24,062
    Likes Received:
    5
    Location:
    Earth, The Planet
    Updated with animation now to demonstrate object following path after path has been discovered.
     
  5. ge0

    ge0 New Member

    Joined:
    Oct 31, 2005
    Messages:
    8,398
    Likes Received:
    0
    Location:
    JERSEY
    WHy ole Why are you doing this in a scripting language?

    Nice, AI has ALWAYS been a fancy of mine. Did you use any huristics to find the path? I didn't look at the code.

    Did you factor sight distance? Learned Paths?
     
  6. durondude

    durondude OT Addict

    Joined:
    May 7, 2001
    Messages:
    24,062
    Likes Received:
    5
    Location:
    Earth, The Planet
    I used javascript because it was the most familiar to me. I'm just using it to understand the concept before attempting to implement it in object-c for the iphone platform. I used a simple manhattan formula for calculating node scores. Not using any learned paths and such although that might be a plus since the game i'm going to use it for will have a lot of static objects. I suppose if an object ever came across a known path, it could follow that path until it ran into a wall or an object then just compute the rest. The only problem I can see with that is, if the old path was completely sealed off. Time would be wasted following the path to a dead end first. I am trying to find a way to maybe do quad trees. Shouldn't be too bad since most of the time, paths will be calculated first before the object even appears on the screen.
     
  7. ge0

    ge0 New Member

    Joined:
    Oct 31, 2005
    Messages:
    8,398
    Likes Received:
    0
    Location:
    JERSEY

    That OLD path being sealed off is where the visible distance comes into to play.. How many squares can the computer see ahead of its next move? Enough to make an educated decision?
     
  8. durondude

    durondude OT Addict

    Joined:
    May 7, 2001
    Messages:
    24,062
    Likes Received:
    5
    Location:
    Earth, The Planet
    Is this the same as line of sight, or just calculating ahead to a certain degree to see if the same spot several nodes ahead can be reached quicker?
     

Share This Page