Thread: shortest path single destination

Hi,

I am trying to code a version of liquid wars, but am getting stuck on the algorithm used.

It is a custom shortest path single destination algorithm, but I dont quite understand it and wondered if there was a better/faster one out there.

Imagine I have a 10x10 array and I want to get EVERY element to a selected position I would have a simple...

Code:

new_grid[x, y] = abs(position[0] - x) + abs(position[1] - y);

and go through every element.

But this doesnt handle walls every well (ie at all). I wanted something that would generate something similar to below, with each element in the array giving the "walking distance" to the x, whilst being fairly quick. Its for the Wii so not a quadcore 10GHz monster.


05 4 4 4 4 4 4 w 5 5
05 4 3 3 3 3 3 w 4 5
05 4 w 2 2 2 2 3 4 5
05 5 w 1 1 1 2 3 4 5
06 6 w w x 1 2 3 4 5
07 7 7 w 1 1 2 3 4 5
08 8 8 w w 2 2 3 4 5
09 9 9 9 w 3 3 3 4 5
10 9 8 8 w 4 4 4 4 5
10 9 8 7 w 5 5 5 5 5


Thanks in advance

Originally Posted by steaky1212

Hi,

I am trying to code a version of liquid wars, but am getting stuck on the algorithm used.

It is a custom shortest path single destination algorithm, but I dont quite understand it and wondered if there was a better/faster one out there.

Imagine I have a 10x10 array and I want to get EVERY element to a selected position I would have a simple...

Code:

new_grid[x, y] = abs(position[0] - x) + abs(position[1] - y);

and go through every element.

But this doesnt handle walls every well (ie at all). I wanted something that would generate something similar to below, with each element in the array giving the "walking distance" to the x, whilst being fairly quick. Its for the Wii so not a quadcore 10GHz monster.


05 4 4 4 4 4 4 w 5 5
05 4 3 3 3 3 3 w 4 5
05 4 w 2 2 2 2 3 4 5
05 5 w 1 1 1 2 3 4 5
06 6 w w x 1 2 3 4 5
07 7 7 w 1 1 2 3 4 5
08 8 8 w w 2 2 3 4 5
09 9 9 9 w 3 3 3 4 5
10 9 8 8 w 4 4 4 4 5
10 9 8 7 w 5 5 5 5 5


Thanks in advance

This looks suspiciously flood-fill-like to me.

flood fill? I now know something i didnt.

is there an easy way to implement this? the ways I have seen fan out from the centre and "fill" with the same value. plus it would appear I need to use the queue method if i had a way on incrementing the value.

any ideas?

Originally Posted by steaky1212

flood fill? I now know something i didnt.

is there an easy way to implement this? the ways I have seen fan out from the centre and "fill" with the same value. plus it would appear I need to use the queue method if i had a way on incrementing the value.

any ideas?

Sooooooo, don't fill with the same value, but (value that you used to have + 1), and don't change the value if it was a smaller number already in the square.

right, I've done the recursive one but it caused the video to go screwy and then crash :S
I'm guessing a stak overflow (though it just crashed as in stopped, and not a ode dump !). It there a way of manually implimenting a stack - or using a queue instead?