shortest path single destination

This is a discussion on shortest path single destination within the Game Programming forums, part of the General Programming Boards category; Hi, I am trying to code a version of liquid wars, but am getting stuck on the algorithm used. It ...

  1. #1
    Registered User
    Join Date
    Jul 2009
    Posts
    3

    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

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by steaky1212 View Post
    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.

  3. #3
    Registered User
    Join Date
    Jul 2009
    Posts
    3
    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?

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,687
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by steaky1212 View Post
    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.

  6. #6
    Registered User
    Join Date
    Jul 2009
    Posts
    3
    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?

  7. #7
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,687
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Single destination shortest path
    By dpp in forum Game Programming
    Replies: 12
    Last Post: 05-11-2009, 11:01 PM
  2. Shortest Path Maze Solver (Breadth Search Help)
    By Raskalnikov in forum C Programming
    Replies: 5
    Last Post: 04-07-2009, 07:41 PM
  3. shortest path algorithm prob
    By Marrah_janine in forum C Programming
    Replies: 2
    Last Post: 10-14-2007, 09:06 PM
  4. Shortest path problem
    By Digitalxero in forum C++ Programming
    Replies: 0
    Last Post: 10-25-2005, 05:32 PM
  5. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21