How to find a route with a given start/end point

[revraz]

Not sure if this is better suited in the Math forum or here, feel free to move if it's better in the Math forums.

 

Say I have a database with 100 locations, 1 - 100.

 

Each location has a reference to other locations it directly connects to, ie

 

1 - 5,8,15

2 - 7,9,12

3 - 80,70,40

4 - 15, 19, 90

5 - 100, 60, 20, 35

 

etc... all the way to 100

 

Just by looking at that table, if i wanted to go from point 1 to point 100, I could go to

1 - 5 - 100

 

But how to do this with code?  If I enter a starting point and a ending point, I am not sure what logic/math to use in order to find a route to 100.  It could be a few points away or a lot more.

[.josh]

How are those references stored?  That is, 1 has 5,8,15 associated with it.  Is "5,8,15" stored as a string or something? Also, if 1 directly connects to 5, how come 1 isn't in 5, as well?

[revraz]

I haven't determined that yet, but I can store them any way that is easy.  I was thinking of storing them in a single DB field seperated by commas, that way I don't have to read multiple columns in a DB.

 

I figured I would try to get the logic down first then store them in a way that works the best.

[Mark Baker]

1 - 5,8,15

2 - 7,9,12

3 - 80,70,40

4 - 15, 19, 90

5 - 100, 60, 20, 35

Just by looking at that table, if i wanted to go from point 1 to point 100, I could go to

You're basically talking about walking a node map, right?

The method used by Satnavs and routefinder software to determine the quickest/shortest route between A and B

[revraz]

Yep, that's the logic I'm looking for.

[Mark Baker]

Not particularly efficient, but it sort of works

<?php

$nodeArray = array ( 1 => array( 2, 4, 5),
				 2 => array( 1, 3, 6),
				 3 => array( 2, 4, 7),
				 4 => array( 1, 3, ,
				 5 => array( 1, 6, ,
				 6 => array( 2, 5, 7),
				 7 => array( 3, 6, ,
				 8 => array( 4, 5, 7)
			   );

$startPoint = 1;
$destination = 5;

$visited = array();

$length = 1;
recursive($length,$startPoint,$destination);

function recursive($length,$startPoint,$destination) {
global $nodeArray, $visited;

echo '<br />'.$startPoint;
$visited[] = $startPoint;
foreach($nodeArray[$startPoint] as $nextLeg) {
	//	Daddy, are we nearly there yet?
	if ($nextLeg == $destination) {
		echo ' ---> '.$nextLeg;
		return $destination;
	}
	//	Don't cross our own path
	if (!in_array($nextLeg,$visited)) {
		echo ' ---> '.$nextLeg;
		//	Length prevents us getting into an endless loop
		if ($length <  {
			return recursive($length+1,$nextLeg,$destination);
		}
	}
}
}

?>

I'm sure I can track down some better algorithms given time.

[revraz]

What is $length doing there?  Is it looking for only 1 node away?

[Mark Baker]

What is $length doing there?  Is it looking for only 1 node away?

Nope, the initial setting of $length is just that, an initial setting. It's incremented every time the recursive() function calls itself, and there's a check to abort if it gets too high (currently set to 8 levels) to prevent the script running away if there happens to be no route between $startPoint and $destination.

Basically, if it takes more than 8 hops to get from A to B, the script gives up trying.

[.josh]

no. It's in there to prevent an infinite loop. 

 

if ($length <

 

makes it stop after there are no more elements in $nodeArray.  That 8 should be changed to a count($nodeArray) for more flexibility.

[Mark Baker]

Really, you should run recursive (filtering out previous results) several times.... and then compare the route lengths to find the shortest route.

[revraz]

I'll give it a go.  There will always be a route, so I'll just change it to the number of points that I'll use.

 

I'm not worried if it's the shortest route, as long as it's a valid route.

 

Thanks for the time you spent on this.

[Mark Baker]

I'll give it a go.  There will always be a route, so I'll just change it to the number of points that I'll use.

 

I'm not worried if it's the shortest route, as long as it's a valid route.

Thats what I set the check as: 8 points, so a limit of 8 steps.

There's logic in there to stop it doubling back on itself, so if a route is possible, it should always find it... the check was more in case my first pass logic had any boo-boos that put it in an infinite loop than for setting any real restriction

 

Thanks for the time you spent on this.

No problem. It's only a simplistic "mouse in a maze" algorithm, knocked up in PHP in a few minutes, so it's not the most efficient I could do... I'll pull some of my old C++ code and recast an old algorithm I have there into PHP over the weekend.

It's more interesting if you factor in distance between the nodes and speed in crossing different terrain types (guess what my old C++ code was for)... maybe even add an image generator to render the nodes graphically and step through each path of the route in turn.

 

[Mchl]

Google A* (or A-star)

It's hard to grasp on the first go, but after a while it makes sense.

 

Although... it might not be the best in your case... hmm...

 

[Mark Baker]

Google A* (or A-star)

It's hard to grasp on the first go, but after a while it makes sense.

 

Although... it might not be the best in your case... hmm...

I'm missing something here I think, I get a list of links on a wide range of subjects from Leotards to recruiting teachers by way of buying stars.

 

I was looking at a PHP implementation of Dijikstra's Shortest Path Algorithm

[Mchl]

Yeah... it seems 'A* pathfinding' gives better results

http://en.wikipedia.org/wiki/A*

[revraz]

This will be for sectors in space, so no terrain calc's are required.

[Mark Baker]

PHP implementation of my old C++ pathfinder code using the dijkstraBFS() algorithm.

 

<?php

$nodeArray = array ( 1 => array( 2, 4, 5),
				 2 => array( 1, 3, 6),
				 3 => array( 2, 4, 7),
				 4 => array( 1, 3, ,
				 5 => array( 1, 6, ,
				 6 => array( 2, 5, 7),
				 7 => array( 3, 6, ,
				 8 => array( 4, 5, 7)
			   );

$startPoint = 1;
$destination = 8;


function buildCostArray($nodeArray) {
$nodeCount = count($nodeArray);
$fullGrid = array();
for($x = 1; $x <=$nodeCount; ++$x) {
	for($y = 1; $y <=$nodeCount; ++$y) {
		if ($y == $x) {
			//	No cost when your startpoint is the destination
			$fullGrid[$x][$y] = 0;
		} elseif (in_array($y,$nodeArray[$x])) {
			//	Standard step cost is always 1 (no weighting or distance)
			$fullGrid[$x][$y] = 1;
		} else {
			//	No direct route from X to Y, so set a blocked marker
			$fullGrid[$x][$y] = 'x';
		}
	}
}
return $fullGrid;
}


function dijkstraBFS($nodeArray, $source, $destination) {
//	Initialisation
foreach($nodeArray as $vKey => $vValue) {
	$distance[$vKey]	= 2147483647;		//	Set initial distances to "Infinity"
	$previous[$vKey] = 0;
	}

$distance[$source] = 0;
$nodeList = array_keys($nodeArray);
while (count($nodeList) > 0) {
	sort($nodeList);
	$u = array_shift($nodeList);

	//	We've reached the destination, so build the list of steps
	if ($u == $destination) {
		$routeSteps = array();
		print_r($previous);
		while (array_key_exists($u,$previous)) {
			array_unshift($routeSteps,$u);
			$u = $previous[$u];
		}
		return $routeSteps;
	}

	foreach($nodeArray[$u] as $v => $vCost) {
		if (in_array($v,$nodeList)) {
			if ($nodeArray[$u][$v] != 'x') {
				//	Route from U to V isn't blocked, so check distance
				$alt = $distance[$u] + $nodeArray[$u][$v];
				if ($alt < $distance[$v]) {
					$distance[$v] = $alt;
					$previous[$v] = $u;
				}
			}
		}
	}
}
return $previous;
}


//  Build a full cost grid from the basic node array
$costArray = buildCostArray($nodeArray);
//  Find the route
$route = dijkstraBFS($costArray, $startPoint, $destination);


echo '<h3>Route</h3><pre>';
print_r($route);
echo '</pre><hr />';

?>

 

If I get a chance over the weekend, I'll take a look at the A-Star algorithm. It looks quite interesting. Thanks for the heads-up.... I guess I've been away from game programming methodologies for too long.

[Mark Baker]

And remember to get rid of my spurious

print_r($previous);

line in the actual dijkstraBFS() function

 

[sasa]

or

<?php
$nodeArray = array ( 1 => array( 2, 4, 5),
				 2 => array( 1, 3, 6),
				 3 => array( 2, 4, 7),
				 4 => array( 1, 3, ,
				 5 => array( 1, 6, ,
				 6 => array( 2, 5, 7),
				 7 => array( 3, 6, ,
				 8 => array( 4, 5, 7)
			   );

$startPoint = 7;
$destination = 3;
$path = array($startPoint => $startPoint);
$new_nodes = array($startPoint);
while (count($new_nodes) and !isset($path[$destination])){
$tmp =array();
foreach ($new_nodes as $node){
	foreach ($nodeArray[$node] as $nnoode){
		if (!isset($path[$nnoode])){
			$tmp[] = $nnoode;
			$path[$nnoode] = $path[$node]. " -> $nnoode";
		}
	}
}
$new_nodes = $tmp;
}
echo $path[$destination];
?>

[revraz]

This is pretty interesting

 

http://lab.polygonal.de/2007/06/13/data-structures-example-the-graph-class/

 

 

If I get a chance over the weekend, I'll take a look at the A-Star algorithm. It looks quite interesting. Thanks for the heads-up.... I guess I've been away from game programming methodologies for too long.

[Mark Baker]

Nice method sasa. Don't know if it's faster than my original recursive method or not (initial tests suggest there's not much difference); but it's definitely neater and always seems to return the route with the fewest hops (while my recursive method simply returns the first valid route that it finds without concern for length).

 

It doesn't take hop length into account, which is where the Dijkstra benefits, because it can identify the shortest route when hops may be of different length... but Dijkstra takes 10 times longer to execute.

 

BTW

Fix to the dijkstraBFS function because it wasn't sorting the hop-length correctly:

function dijkstraBFS($nodeArray, $source, $destination) {
//	Initialisation
foreach($nodeArray as $vKey => $vValue) {
	$distance[$vKey] = 1073741823;		//	Set initial distances to "half way to Infinity"
	$previous[$vKey] = 0;
	}

$distance[$source] = 0;
$nodeList = array_keys($nodeArray);
while (count($nodeList) > 0) {
	asort($distance);
	foreach($distance as $dKey => $dValue) {
		$shortest = $dKey;
		break;
	}
	$u = $shortest;
	unset($nodeList[$u-1]);

	//	We've reached the destination, so build the list of steps
	if ($u == $destination) {
		$routeSteps = array();
		print_r($previous);
		do {
			array_unshift($routeSteps,$u);
			$u = $previous[$u];
		} while (array_key_exists($u,$previous));
		return $routeSteps;
	}

	foreach($nodeArray[$u] as $v => $vCost) {
		if (in_array($v,$nodeList)) {
			if ($nodeArray[$u][$v] != 'x') {

				//	Route from U to V isn't blocked, so check distance
				$alt = $distance[$u] + $nodeArray[$u][$v];
				if ($alt < $distance[$v]) {
					$distance[$v] = $alt;
					$previous[$v] = $u;
				}
			}
		}
	}
	$distance[$dKey] = 2147483647;		//	Set calculated distance to "Infinity"
}
return $previous;
}