Results 1 to 4 of 4

Thread: How is the destination path calculated in strategy games? (Dijkstra's algorithm)

  1. #1
    hakermania's Avatar
    hakermania is offline Τώρα ξέρεις τι γράφω εδώ!
    Join Date
    Aug 2009
    Location
    Greece
    Beans
    1,705
    Distro
    Ubuntu Development Release

    Question How is the destination path calculated in strategy games? (Dijkstra's algorithm)

    Most strategy games let you choose one or more characters and point with your mouse to a specific point. When you click at this point, then your character(s) move, taking the shortest possible path.

    How is this implemented into games? I've thought of the Dijkstra's algorithm (http://en.wikipedia.org/wiki/Dijkstra's_algorithm) but, then, there are maps out there that their grid points (in every strategy game your character moves into a grid) should exceed the million by far. So, including each of these points inside this algorithm should take ages to calculate the shortest distance. Consider your character(s) being on the one side of the map and you choose to move them to the other side. How many possible paths have to be calculated?

  2. #2
    Join Date
    Feb 2009
    Beans
    1,469

    Re: How is the destination path calculated in strategy games? (Dijkstra's algorithm)

    NetHack's sources are available online, but I don't know whether that is any particular named algorithm (I only glanced through it). If memory serves, though, it's not truly shortest-path.

    If I were asked to write such an algorithm, I'd probably try to guess my way through most of it. Perhaps if you broke the grid into chunks and tried to create a travel path through each chunk (basically running the same algorithm on the super-grid and then on each individual sub-grid within a chunk). It wouldn't be strictly shortest-path, but most maps exhibit patterns that would make it indistinguishable from a true shortest-path algorithm if you were merely casually examining it.

  3. #3
    Join Date
    Apr 2005
    Beans
    105

    Re: How is the destination path calculated in strategy games? (Dijkstra's algorithm)

    Was it "A* algorithm" or something like that? Anyway, I don't think they calculate the entire path at once.

  4. #4
    Join Date
    Apr 2008
    Location
    Australia
    Beans
    276
    Distro
    Ubuntu

    Re: How is the destination path calculated in strategy games? (Dijkstra's algorithm)

    Quote Originally Posted by mehaga View Post
    Was it "A* algorithm" or something like that? Anyway, I don't think they calculate the entire path at once.
    Yes, A* is right. Basically think of it as a the first best path. It doesn't calculate all possible paths, I think it calculates a certain number of possible paths, and goes with the shortest of those.

    Thinking back to a game like the original Age of Empires, I think this is how the "Advanced Pathfinding" option worked, just boosting the number of possble paths checked.

    I would guess that Dijkstra's algorithm would give *THE* shortes route, at the cost of taking a lot longer.
    Last edited by dagoth_pie; September 5th, 2012 at 01:19 PM.
    By the people, for the people.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •