Range-finding

range_finding_header Range-finding is the process of finding all points within a certain range of a goal point. Here is a typical scenario that requires it: In a turned-based grid game, the player can only move a certain number of cells. You need to find out which cells the player can move to at each turn – to display it or prevent illegal moves. Range finding share many features with path finding (and you should examine that tutorial before reading this one). Let’s first look at the function definition:

public static Dictionary<TPoint, float> Algorithms.GetPointsInRangeCost<TCell, TPoint>(
   IGrid<TCell, TPoint> grid,
   TPoint start,
   Func<TCell, bool> isAcessible,
   Func<TPoint, TPoint, float> getCellMoveCost,
   float moveRange)
      where TPoint : IGridPoint

And a typical call:

public static Dictionary<TPoint, float> Algorithms.GetPointsInRangeCost<TCell, TPoint>(
   grid,
   start,
   cell => true,
   (p, q) => 1,
   3);

The function returns a list of points, in the case above all points that are within 3 units of the start cell. Most arguments and steps are exactly the same as for path finding. Here is a summary of the steps:

[dropcap style=”dark”]1[/dropcap]Implement a cell that supports the necessary functionality for the type of range-finding you want to do.

[dropcap style=”dark”]2[/dropcap]Work out what types all your parameters should be. These are the same as for path finding, except for the range parameter (which can either be an int or float, depending on whether your distance metric uses ints or floats).

[dropcap style=”dark”]3[/dropcap]Write a method or lambda expression to decide whether a cell is accessible or not.

[dropcap style=”dark”]4[/dropcap]Write a lambda expression or method for determining the true cost of reaching two points if they are neighbors. (Since there is no heuristic cost involved with range finding, you need not worry about that). As with path finding, you get different results depending on the distance metric and your neighbor setup. Below is an example for some of the different options.

 Grid distance

 screen_32  screen_35  screen_38
 Main and Diagonals  Main  Diagonals

Euclidean distance

 screen_33  screen_36  screen_39
 Main and Diagonals  Main  Diagonals

Weighted paths

 screen_34  screen_37  screen_40
 Main and Diagonals  Main  Diagonals

Download

An example scene: RangeFinding.unitypackage.

Leave a Reply

Your email address will not be published. Required fields are marked *

Scroll to Top