Liquidedust

hmmm, there as some odd behaviour in the pathfinder need to locate what I did wrong (if you spot anything poke me about it)

Its pretty simple so far, but this is how far I have gotten so far: Any input and suggestions appreciated function reconstruct_path( $came_from , $current_node , $failsafe ) { if( $failsafe < 1000 ){ if( isset( $came_from[ $current_node ] ) ) { $new_failsafe = $failsafe+1; $p = reconstruct_path( $came_from , $came_from[ $current_node] , $new_failsafe ); return $p." =>\r\n".$current_node; } else { return null; } } else { return null; // killed pathfinding, infinite loop or more then 1000 iterations } } function h_distance( $current , $target ) { $this_current = explode("," , $current); $this_target = explode("," , $target); $H_score = 10 * ( abs($this_current[0]-$this_target[0]) + abs($this_current[1]-$this_target[1]) ); return $H_score; } function min_F_score( $openset , $f_score) { foreach( $openset as $value) { if( isset( $lowest_f ) ) { if( $f_score[$value] < $lowest_f ) { $lowest_f = $f_score[$value]; $lowest_key = $value; } } else { $lowest_f = $f_score[$value]; $lowest_key = $value; } } return $lowest_key; } function neighbor_nodes($pos) { $pos = explode( "," , $pos ); $neighbors = array(); if( $pos[0] != 1 ) { $neighbors[] = ($pos[0]-1).",".$pos[1]; } if( $pos[0] != 10 ) { $neighbors[] = ($pos[0]+1).",".$pos[1]; } if( $pos[1] != 1 ) { $neighbors[] = $pos[0].",".($pos[1]-1); } if( $pos[1] != 10 ) { $neighbors[] = $pos[0].",".($pos[1]+1); } return $neighbors; } /////////////////////////////////////////////////////////////////////////////// //// $start_coords and $goal_coords are in 'x,y' format //// //// $grid_g_scores is an array with all possible co-ordinates and how //// //// hard each grid is to traverse //// //// $infinity is the variable that defines if a certain value //// //// in $grid_g_scores is impossible to pass //// /////////////////////////////////////////////////////////////////////////////// function A_star( $start_coords , $goal_coords , $grid_g_scores , $infinity ) { // The set of nodes already evaluated. $closedset = array(); // The set of tentative nodes that still need to be evaluated $openset = array($start_coords => $start_coords); // Distance from start along the optimal path. $g_score = array($start_coords => 0 ); // the heuristic for each grid based of the Manhattan Method $h_score = array($start_coords=>h_distance($start_coords,$goal_coords)); // Estimated total distance from start to goal through y. $f_score = array($start_coords => $h_score[$start_coords] ); // array used to store the optimal path $came_from = array(); while( !empty( $openset ) ) { // Set $x to the node in openset having the lowest f_score[] value $x = min_F_score( $openset , $f_score ); // Check if we are at the goal co-ordinates end if so return the path if( $x == $goal_coords ) { return $start_coords .reconstruct_path($came_from,$goal_coords,0); } unset( $openset[$x] ); $closedset[$x] = $x; foreach( neighbor_nodes($x) as $y ) { // if $y isn't in closed set run the following if( !array_key_exists( $y , $closedset ) ) { $tentative_g_score = $grid_g_scores[$x] +h_distance($x,$y); $tentative_is_better = false; // if this grid is traversable continue if( $tentative_g_score < $infinity ) { // if $y isn't in $openset add it and give it a // h_score(based off Manhattan Method) if( !array_key_exists( $y , $openset ) ) { $openset[$y] = $y; $h_score[$y] = h_distance( $y , $goal_coords ); $tentative_is_better = true; } elseif( $tentative_g_score < $g_score[$y] ) { $tentative_is_better = true; } if( $tentative_is_better == true ) { $came_from[$y] = $x; $g_score[$y] = $tentative_g_score; $f_score[$y] = $g_score[$y] + $h_score[$y]; } } } } } return "no path to target can be found!"; } $the_map = array( '1,10' => 4, '2,10' => 4, '3,10' => 4, '4,10' => 400, '5,10' => 4, '6,10' => 4, '7,10' => 4, '8,10' => 400, '9,10' => 4, '10,10' => 4, '1,9' => 4, '2,9' => 400, '3,9' => 4, '4,9' => 400, '5,9' => 4, '6,9' => 400, '7,9' => 4, '8,9' => 400, '9,9' => 4, '10,9' => 400, '1,8' => 4, '2,8' => 400, '3,8' => 4, '4,8' => 400, '5,8' => 4, '6,8' => 400, '7,8' => 4, '8,8' => 400, '9,8' => 4, '10,8' => 400, '1,7' => 4, '2,7' => 400, '3,7' => 4, '4,7' => 400, '5,7' => 4, '6,7' => 400, '7,7' => 4, '8,7' => 400, '9,7' => 4, '10,7' => 400, '1,6' => 4, '2,6' => 400, '3,6' => 4, '4,6' => 400, '5,6' => 4, '6,6' => 400, '7,6' => 4, '8,6' => 400, '9,6' => 4, '10,6' => 400, '1,5' => 4, '2,5' => 400, '3,5' => 4, '4,5' => 400, '5,5' => 4, '6,5' => 400, '7,5' => 4, '8,5' => 400, '9,5' => 4, '10,5' => 400, '1,4' => 4, '2,4' => 400, '3,4' => 4, '4,4' => 400, '5,4' => 4, '6,4' => 400, '7,4' => 4, '8,4' => 400, '9,4' => 4, '10,4' => 400, '1,3' => 4, '2,3' => 400, '3,3' => 4, '4,3' => 400, '5,3' => 4, '6,3' => 400, '7,3' => 4, '8,3' => 400, '9,3' => 4, '10,3' => 400, '1,2' => 4, '2,2' => 400, '3,2' => 4, '4,2' => 400, '5,2' => 4, '6,2' => 400, '7,2' => 4, '8,2' => 400, '9,2' => 4, '10,2' => 400, '1,1' => 4, '2,1' => 400, '3,1' => 4, '4,1' => 4, '5,1' => 4, '6,1' => 400, '7,1' => 4, '8,1' => 4, '9,1' => 4, '10,1' => 400 ); /////////////////////////////////////////////////////////////////////////////// ///////// start position , end position , map_array , infinity ///////// ///////// (infinity = grid value impossible to traverse) ///////// /////////////////////////////////////////////////////////////////////////////// echo "<pre>\r\n"; print_r ( A_star('1,1','10,1',$the_map,400) ); echo "</pre>\r\n"; [attachment deleted by admin]

Quite diffrent from what I need to apply this to myself but yeah nice with a practical application of code, oh and remind me to never go from Liverpool to Heathrow via the tube. Also thanks

Odd cannot seem to edit my posts in this thread, what I meant with Djikstra acting stupid is not due to the path it takes (since its almost optimal if the path exists) meant more that it does cycles that aren't really needed.

Well never really implemented something like A* or Djikstra's myself so would be good to how someone else went about implementing it to get the basics framework down, and even Djikstra is a great start for what I am doing (though Djikstra can act pretty stupid at times which is why I was primarily interested in A*). So most certainly interested in seeing how you implemented Djikstra's if that you'd be willing to show me

Well since I am going to need to pass some stuff through a pathfinder in something I code currently I started to look around and see if there were any pre-built A* algorithm libraries for PHP out there and pretty much came up with silch (A* is an evil term to search for just so you know ). So really just wondering if someone knows of a pre-made library that implements A* or that I will be stuck in making my own library for it? This since it feels kind silly to recreate the wheel if it has already been made. http://en.wikipedia.org/wiki/A*_algorithm Thanks in advance (realized this might be in the wrong section, but just move as you seem fit in that case - this is math after all)

I think we have come as far as we can get now, unless you have any other ideas one might try to make it more elegant and run faster Latest Version: $lake_mountain_offset_output = array(); foreach($the_lakes as $lake_value) { // calculate the distance between each lake and each mountain - this loops through all lakes $lake_coord_index = key($lake_value).",".$lake_value[key($lake_value)]; // get the current lake co-cordinates so we doesn't have to recalculate them more then once per loop foreach($the_mountains as $mountain_value) { // This loops through all mountains for each lake and compares the distances $mountain_coord_index = key($mountain_value).",".$mountain_value[key($mountain_value)]; // get the current mountain co-cordinates // get the offset between the objects by passing the relevant variables to object_distance() $current_offset = object_distance( key($lake_value) , $lake_value[key($lake_value)] , key($mountain_value) , $mountain_value[key($mountain_value)] ); if( isset($lake_mountain_offset_output[$lake_coord_index]) ) { // checks to see if the current lake is in $lake_mountain_offset_output array $check_explode = explode("|", $lake_mountain_offset_output[$lake_coord_index]); // get the currently inserted mountains distance from the current lake in the $lake_mountain_offset_output array if($check_explode[1] > $current_offset ){ // check if this mountain is closer to the lake then the value currently in $lake_mountain_offset_output array $lake_mountain_offset_output[$lake_coord_index] = $mountain_coord_index."|".$current_offset; // if its closer update the $lake_mountain_offset_output array with this mountains co-ordinates and distance from the lake } } else { // if the current lake isn't present in the $lake_mountain_offset_output array, insert it $lake_mountain_offset_output[$lake_coord_index] = $mountain_coord_index."|".$current_offset; } } }

In the end I went with this solution to the problem, slightly more readable and elegant I think $lake_mountain_offset_output = array(); foreach($the_lakes as $lake_key => $lake_value) { // calculate the distance between each lake and each mountain - this loops through all lakes $lake_coord_index = key($lake_value).",".$lake_value[key($lake_value)]; // get the current lake co-cordinates so we doesn't have to recalculate them more then once per loop foreach($the_mountains as $mountain_key => $mountain_value) { // This loops through all mountains for each lake and compares the distances $mountain_coord_index = key($mountain_value).",".$mountain_value[key($mountain_value)]; // get the current mountain co-cordinates // some Pythagoras theorem to calculate the distance between the current lake and current mountain $a_distance = key($lake_value) - key($mountain_value); $b_distance = $lake_value[key($lake_value)] - $mountain_value[key($mountain_value)]; $current_offset = sqrt( pow($a_distance,2) + pow($b_distance,2) ); if( isset($lake_mountain_offset_output[$lake_coord_index ]) ) { // checks to see if the current lake is in $lake_mountain_offset_output array $check_explode = explode("|", $lake_mountain_offset_output[$lake_coord_index ]); // get the currently inserted mountains distance from the current lake in the $lake_mountain_offset_output array if($check_explode[1] > $current_offset ){ // check if this mountain is closer to the lake then the value currently in $lake_mountain_offset_output array $lake_mountain_offset_output[$lake_coord_index ] = $mountain_coord_index."|".$current_offset; // if its closer update the $lake_mountain_offset_output array with this mountains co-ordinates and distance from the lake } } else { // if the current lake isn't present in the $lake_mountain_offset_output array, insert it $lake_mountain_offset_output[$lake_coord_index ] = $mountain_coord_index."|".$current_offset; } } }

Hmm, you mean to change this: foreach($find_lakes as $key => $lake_value) { // calculate the distance between each lake and each mountain $exploded_lake = explode(",", $lake_value); foreach($find_mountains as $mountain_value) { $exploded_mountain = explode(",", $mountain_value); // some Pythagoras theorem to calculate the distance between the objects $a_distance = $exploded_lake[0] - $exploded_mountain[0]; $b_distance = $exploded_lake[1] - $exploded_mountain[1]; $lake_mountain_offset[$lake_value][$mountain_value] = sqrt( pow($a_distance,2) + pow($b_distance,2) ); } } into something like this: foreach($find_lakes as $key => $lake_value) { // calculate the distance between each lake and each mountain $exploded_lake = explode(",", $lake_value); foreach($find_mountains as $mountain_value) { $exploded_mountain = explode(",", $mountain_value); // some Pythagoras theorem to calculate the distance between the objects $a_distance = $exploded_lake[0] - $exploded_mountain[0]; $b_distance = $exploded_lake[1] - $exploded_mountain[1]; if( isset($lake_mountain_offset_output_v2[$lake_value]) ) { $check_explode = explode("|", $lake_mountain_offset_output_v2[$lake_value]); if($check_explode[1] > sqrt( pow($a_distance,2) + pow($b_distance,2) )){ $lake_mountain_offset_output_v2[$lake_value] = $mountain_value."|".sqrt( pow($a_distance,2) + pow($b_distance,2) ); } } else { $lake_mountain_offset_output_v2[$lake_value] = $mountain_value."|".sqrt( pow($a_distance,2) + pow($b_distance,2) ); } } } Or something along those lines?

So sitting here coding a map populator in php and had to come up with a solution determining what the closest mountain on the map was in relation to the lakes the code spit out and ploink down on the map. So while twiddling around I came up with the following but it feels very clunky and not quite such an elegant solution, so my question would be if you could wrap your heads around the code and maybe find a more elegant solution to what I am doing. For reference the $mapdimensional_gridtypes array just looks like: [x-coordinates][y-coordinates] => type of grid foreach($mapdimensional_gridtypes as $key => $value) { // grab all mountains and lakes and their respective co-ordinates from the $mapdimensional_gridtypes array foreach($value as $value_key => $value_value) { if($value_value == "lake") { $find_lakes[] = $key.",".$value_key; } if($value_value == "mountains") { $find_mountains[] = $key.",".$value_key; } } } foreach($find_lakes as $key => $lake_value) { // calculate the distance between each lake and each mountain $exploded_lake = explode(",", $lake_value); foreach($find_mountains as $mountain_value) { $exploded_mountain = explode(",", $mountain_value); // some Pythagoras theorem to calculate the distance between the objects $a_distance = $exploded_lake[0] - $exploded_mountain[0]; $b_distance = $exploded_lake[1] - $exploded_mountain[1]; $lake_mountain_offset[$lake_value][$mountain_value] = sqrt( pow($a_distance,2) + pow($b_distance,2) ); } } foreach($lake_mountain_offset as $key => $value) { // grab the nearest mountain and its key (co-ordinates) for every lake and output in an array with the following format [lake co-ordinate]["mountain co-ordinates => distance"] (each record in the array will look something like [2,3] => "1,8 => 2") asort($value); $lake_mountain_offset_output[$key] = key($value)." = > ".min($value); } I mean the above code works and everything, but having a complete brianfart when it comes to improving it right now. I am somewhat stumped if this really is such a good solution to the problem since this feels very clunky code-wise. So basically just want a second opinion on it all more or less and any suggestion on what could be done in a better and/or more elegant way. Oh yeah, the reason I need to calculate this is that I need to populate the map with rivers after this. I want each river to flow from a mountain to a lake and always take the shortest distance possible. Therefore need to know which mountain is closest to each lake before I draw the rivers.

Not sure. I haven't seen any for a few years to be honest. In worst case I have to think up a new solution I guess, know anything besides image map that can draw polygon object into page

Hehe well they sorta have gone extinct I guess, but use them in a transparent image that overlays as isometric map so was sorta an easy solution to my problem, e.g. have to define the isometric rollover grids somehow and since they aren't square an image map with poly co-ordinates was the cleanest solution to the problem. Firebug doesn't handle area shapes that well does it?

Sorta odd question maybe. Debugging a page the auto-generates image maps for a project I am using and ran into some issues with the positioning (not a big deal really just have to tweak the code). However it is very tedious to bugcheck the shapes of the areas within the map since I cannot physically see them in the browser window, so my question is! Is there any way to outline the <area> shapes with a border during development to easier see where they do not line up properly?