Jump to content
  • Advertisement
  • 09/15/99 05:16 PM
    Sign in to follow this  

    Range Sight Algorithm

    General and Gameplay Programming

    Myopic Rhino
    Someone asked me about an algorithm that, given a location of a unit, would tell you what locations can be reached in the next turn. I'm assuming you have a MovementCost function that tells you how hard it is to walk from one space to another. You can use Dijkstra's algorithm to find this area.

    Let Costs be an array (as big as your map) of integers, init. value = -1

    Function Find(UnitLocation)
    Let Open be a priority queue of locations /* sorted by Costs[x] */
    Let Closed be a set of locations

    Put Location in Open

    While Open isn't empty:
    Remove a location X from Open
    Add X to Closed
    If Costs[X] is less than the Movement Limit:
    For each Y that is a neighbor of X:
    NewCost = Costs[X] + MovementCost(from X to Y)
    If Costs[Y] is -1 or NewCost is less than Costs[Y]:
    Set Costs[Y] to NewCost
    Add Y to Open if it's not already in Open

    Let Results be a list of locations
    For each X in Closed:
    If Costs[X] is less than the Movement Limit:
    Add X to Results
    Set Costs[X] to -1

    (It's important to keep Costs outside the Find function; otherwise the initialization time for that big array would slow down the whole algorithm. The algorithm restores Costs to -1 at the end so that you can use it the next time you want to Find.)

    This algorithm should be pretty fast. In practice the number of things that go into Open should be the area (which are spaces you can reach) + the perimeter (which are spaces just out of reach), which is not too high as long as the unit's movement is pretty limited.

      Report Article
    Sign in to follow this  

    User Feedback

    There are no comments to display.

    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!