Mirrored Results Algorithm

benbox

Hey all,

I've written a little maze script to solve a maze, however I'm trying to refine its result.

I have it so that it finds a path to the goal co-ordinates from a given starting position, however it outputs a path which occasionally backtracks itself in places. For example: -

south
west
west
[COLOR=Blue]west
west
north
north
south
south
east
east[/COLOR]
south
south
east
east
[COLOR=Blue]east
east
east
north
north
north
south
south
south
west
west
west[/COLOR]
south
south

In blue I have highlighted such paths, where it goes one direction, then steps back on itself. I understand that where these occurs, the opposite result is immediately after.. for example, north followed by south.

And I think this means that I can remove them in pairs, so as an example.. in the first block of blue above, I could remove the middle north/south.. which would leave west/north/south/east where I can then remove north/south and finally west/east.

That's the theory anyway!

But I'm stuck on how to implement it.. at the moment, the above list is using a stack.. however it could be anything, such as a string or array.. once I know the algorithm it should be easy to adapt to either.

Does anyone have any ideas that they can help me with please? 😃

Many thanks,
Ben

Oersoep

So... You want to reduce the stack-usage by walking from intersection to intersection instead of walking through each coordinate?

Or... You want to remove the backtraces in the final route display?

I guess you use a recursive function for this. Can you show it?

benbox

Well, I'm actually doing this in Java.. but I'm newish to Java, so I'd work it out in php then convert.. also these forums are awesome, I don't know of any java equivalent! but technically the coding principles should be the same.. as far as I know anyway..

Ideally the main recursive bit which calculates the directions as above would somehow remove the unnecessary moves (in the blue) as it goes along.. but because I'm not entirely sure what I'm doing, so I thought I'd do it afterwards becauce the output is correct. It's just not as short as it could be, because you're moving forward and backwards cancelling out your steps unnecessarily.

So I guess to try and make myself clear, I hope I am.. although I seem to never get to the point!

I want to search say, an array, for consequtive oppositions.. namely: -

north
south

south
north

east
west

west
east

And remove it completely from the array.. so if I had { "north", "east", "west", "north" }
I would end up with { "north", "north" }

I think I am right in saying there are just those 4 combinations.

Thank you!

laserlight

Notice that if you get a north-south pair, you can immediately remove it.
Likewise, if you get an east-west pair, you can immediately remove it.
So, if you scan the directions and remove each negating pair, you get a resulting set of directions that is a little less redundant. Repeat this iteration until there are no negating pairs left.

benbox

Yes! that is the theory of what I'm trying to do.. but I can't seem to get it right.. could you possibly give a quick code example to how that would be done? (assuming each direction is in its own value in an array)

This help is appreciated muchly 😃

Oersoep

If you find the route recursively, then why do you record the trace realtime?
Why not only print out the successful path?
If you come from the north, and run into a dead end, why turn around if you're living in the magical computerworld in which you can undo almost anything? Just hop back out of the function until you're on a spot with yet unexplored exits?

a simple solution:
- log each coordinate into an array
- if you reach a coordinate where you've been before, delete all values from the array after the last time you were there. Just remember which directions you had already tried.

laserlight

could you possibly give a quick code example to how that would be done? (assuming each direction is in its own value in an array)

Well, yes, but Oersoep does have a point that you might want to look into.

function isNegatingPair($a, $b) {
	return ($a == "north" && $b == "south")
		|| ($a == "south" && $b == "north")
		|| ($a == "east" && $b == "west")
		|| ($a == "west" && $b == "east");
}

// let $directions be array of directions
do {
	$elimination_flag = false;
	$size = count($directions);
	$max = $size - 1;
	$array = array();
	for ($i = 0; $i < $size; ++$i) {
		if ($i == $max || !isNegatingPair($directions[$i], $directions[$i+1])) {
			$array[] = $directions[$i];
		} else {
			$elimination_flag = true;
			++$i;
		}
	}
	$directions = $array;
} while ($elimination_flag);

Weedpacket

Heh, here's my first cut:

$paths = array('north', 'east', 'west', 'north', 'south', 'west', 'east', 'north', /*...*/); 
$letters = '';
foreach($paths as $path)
	$letters.=$path[0];
$letters = strtolower($letters);
$oldlen = 0;
$len = strlen($letters);

$backtracks = array('ns','sn','ew','we');
while($len!=0 && $len!=$oldlen)
{
	$letters = str_replace($backtracks,'',$letters);
	$oldlen = $len;
	$len = strlen($letters);
}

$mappings=array('n'=>'north', 's'=>'south', 'w'=>'west', 'e'=>'east');
$paths = array();
for($i=0; $i<$len; ++$i)
	$paths[] = $mappings[$letters[$i]];

benbox

Ahh, awesome 😃 I'm getting somewhere now, thank you very much all!

I would prefer Oersoep's idea, as it would be more efficient. However it doesn't really matter which way it is done at the moment, so I've just taken the afterwards/easier route. I may look into it later though, as it would be good practice for working out algorithms!