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

Quote:

---

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?

Like so?
Flood fill - Wikipedia, the free encyclopedia

Quote:

---

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?

Of course there's a way! :)

Recursion is just a disguised loop, so when you feel the need to recurse, you just "save" something and loop. When you get to the end of the loop, you "restore" something and carry on.