TripPlanner/aPathFinder.php at master · zarankumar/TripPlanner · GitHub

1
2
3
4
5
6
7
8
9
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
<?php
include'config.php';
include'functions.php';

$openList=array();
$closeList=array();
$came_from=array();
error_reporting(0);

function bestTravelRoute($start,$end)
	{
	$openList[$start]='0';// insert into Start place to Open List
	$gScore=0;
	// save start and end places in session
	$_SESSION['start']=$start;
	$_SESSION['end']=$end;

	do{
		$current_place=bestMove($openList); // find best place move
		if(!isset($current_place))
			{
			$current_place=$end;
			$came_from[$current_place]=$next_place;
			//echo"Now came array:";print_r($came_from);

			//$openList[$current_place]=20;

			}
	//	echo "</br>Current Best Move: ".$current_place;
		$current_g_val=(int)$openList[$current_place];
		//echo $current_g_val;
		$closeList[]=$current_place;// add to close list
		//echo "Current Close List:</br>";print_r($closeList);
		$openList = array_diff_key($openList, array($current_place=>'$current_g_val'));// remove current place from openlist
		//echo "</br>Open List ";print_r($openList);


			if(strcmp($current_place,$end)==0)
				{
			//	echo "destination reached";
			// return pathFinder($current_place);
			 return reconstruct_path($came_from,$current_place);
			     }

			$adjucent_places=nearest($current_place);// find nearest places

			foreach($adjucent_places as $next_place)
				{
			//	echo "</br>Next Place Now : ".$next_place;
					if(in_array($next_place,$closeList))// if place in close list
					{
				//	  echo " Its in Close List Continueing..</br>";
					  continue;
					}
					if(!(isset($openList['$next_place'])))// if place is not in open list
					{
				//	echo"</br>Not in OpenList";
					$openList[$next_place]=(int)$current_g_val+(int)distance($next_place,$end);
					//$parent[]=$next_place=>$current_place;
					$came_from[$next_place]=$current_place;
					//$came_from['$next_place']='$current_place';
				//	echo "</br>added to open list</br>Now Open List: </br>";
				//	print_r($openList);echo "</br>";

					}

					//echo "parent :";
					//print_r($parent);


				}


	}while(!empty($openList));

	}


		function reconstruct_path($came_from, $current_node)
{
//echo "<br/>fn called ";
    if(isset($came_from[$current_node]))
	{
	//echo "<br/>in array";
        $p = reconstruct_path($came_from,$came_from[$current_node]);
		//echo "<br/>P=".$p;
        return ($p."|".$current_node);
    }
	else
     {
	// echo "<br/>else part";
	    return $current_node;
		}
}


?>