Tag Archives: Pathfinding

Using GoalMaps in RogueSharp

RogueSharp has had GoalMaps since version 1 however they never performed as well as I had hoped so I didn’t promote the feature. As of version 3.0.0-pre the feature has been cleaned up and I’m now ready to present a sample application of their use. The GoalMap feature was originally inspired by The Incredible Power of Dijkstra Maps post on RogueBasin.

GoalMapSample

GoalMap Sample

Sample GoalMap Application

The code for the Sample GoalMap application is on Bitbucket:

https://bitbucket.org/FaronBracy/roguesharprlnetsamples/src/0cbcd866875e64f6456d5fe08c86602d5f9591b9/?at=GoalMap

Commands

Left Click – Set the start location for the Goal Map Calculation
Right Click – Toggle a Goal on/off
O – Toggle obstacle on/off
A – Toggle between Goal avoidance and Goal seeking
C – Clear all Goals, Paths and Obstacles

Definitions

GoalMap – The GoalMap class is used in RogueSharp for assigning weights to Cells on the Map which can then be used for finding paths or building desire-driven AI

Goal – The Goals in a GoalMap represent weighted locations on the Map that will be used when calculating paths for either seeking or avoiding Goals. The smaller the weight the more desirable the location will be to either seek or avoid. When finding paths both the distance to the Goal and the weight of the Goal will be taken into account.

Obstacle – An Obstacle is a location that a Path must not pass through when calculating paths with GoalMaps. Examples of possible obstacles could be an ally, an enemy, water, or anything that we don’t want to pass through. By default any Map Cells that are not marked as walkable will be Obstalces. For instance, there will be no need to set Obstacles for each wall in the Map.

GoalMapSampleApp

GoalMap Demo Application

Code Sample

// Create a new map that only has a wall around the border
var map = Map.Create( new BorderOnlyMapCreationStrategy
<Map>( 50, 50 ) );

// Create a new GoalMap for the map
var goalMap = new GoalMap( map );

// Add a Goal at X=10, Y=25 with a weight of 10
// Lower weights are more desirable
goalMap.AddGoal( 10, 25, 10 );

// Add a second Goal at X=40, Y=15 with a weight of 10
goalMap.AddGoal( 40, 15, 10 );

// Add an obstacle at X=1, Y=2
// An obstacle is something that a Path must not go through
// Examples: an ally, an enemy, water, etc.
goalMap.AddObstacle( 1, 2 );  

// Find a "best" path to a Goal based on Goal weight and distance to the Goal
// Start the path from X=1, Y=1
// The path will not pass through obstacles
Path path = goalMap.FindPath( 1, 1 );

// Find a "best" path away from or avoiding Goals based on Goal weight and distance
// Start the path from X=20, Y=20
// The path will not pass through obstacles
Path pathAvoiding = goalMap.FindPathAvoidingGoals( 20, 20 );

RogueSharp 3.0 Pre-Release – Goal Maps

Version 3.0.0-pre of RogueSharp was just released

This is considered a pre-release version. In order to obtain it via Nuget make sure to choose “Include Prerelease” packages from the Nuget Package Manager.

IncludePrerelease

Include Prerelease

Any feedback regarding this pre-release version is appreciated!

RogueSharp 3.0-pre NuGet Package
RogueSharp 3.0-pre Source Code

New features:

  • Added Path class to provide a type with more functionality than simple IEnumerable
    • Returned from GoalMap and PathFinder classes
  • Reworked GoalMap interface to be more consistent with Pathfinder class
    • Ability to add and remove obstacles
    • Ability to remove Goals once they are added
  • Numerous bug fixes to GoalMap class
    • Fixed possible infinite recursion in some edge cases
    • Avoidance algorithm now will never choose  a Path through a Goal that is being avoided
  • FxCop clean up

Breaking changes:

  • Pathfinder now returns Path type instead of IEnumerable
  • GoalMap now returns Path type instead of IEnumerable
  • Map creation algorithms moved to their own namespace
  • DiceNotation “Type” renamed to “TermType” to avoid being a keyword

GoalMap / Path Example:

// Create a new map that only has a wall around the border
var map = Map.Create( new BorderOnlyMapCreationStrategy
<Map>( 50, 50 ) );

// Create a new GoalMap for the map
var goalMap = new GoalMap( map );

// Add a Goal at X=10, Y=25 with a weight of 10
// Lower weights are more desirable
goalMap.AddGoal( 10, 25, 10 );

// Add a second Goal at X=40, Y=15 with a weight of 10
goalMap.AddGoal( 40, 15, 10 );

// Add an obstacle at X=1, Y=2
// An obstacle is something that a Path must not go through
// Examples: an ally, an enemy, water, etc.
goalMap.AddObstacle( 1, 2 );  

// Find a "best" path to a Goal based on Goal weight and distance to the Goal
// Start the path from X=1, Y=1
// The path will not pass through obstacles
Path path = goalMap.FindPath( 1, 1 );

// Get the number of steps in the path
// Output = 34 
Console.WriteLine( path.Length );

// Get the start of the path
// Output = 1:1
Console.WriteLine( "{0}:{1}", path.Start.X, path.Start.Y );

// Get the end of the path
// Output = 10:25
Console.WriteLine( "{0}:{1}", path.End.X, path.End.Y );

// Take a step forward along the path
Cell nextStep = path.StepForward();
// Output = 2:1
Console.WriteLine( "{0}:{1}", nextStep.X, nextStep.Y );

// Take a backward along the path
Cell previousStep = path.StepBackward();
// Output = 1:1
Console.WriteLine( "{0}:{1}", previousStep.X, previousStep.Y );

// Iterate through each Step along the Path
// Output = 1:1 - 2:1 - 2:2 - 2:3 - 2:4 - 2:5 - 2:6 - 2:7 - 2:8 - 2:9 - 2:10 - 
// 2:11 - 2:12 - 2:13 - 2:14 - 2:15 - 2:16 - 2:17 - 2:18 - 2:19 - 2:20 - 2:21 - 
// 2:22 - 2:23 - 2:24 - 2:25 - 3:25 - 4:25 - 5:25 - 6:25 - 7:25 - 8:25 - 9:25 - 10:25 -
foreach ( Cell step in path.Steps )
{
   Console.Write( "{0}:{1} - ", step.X, step.Y );
}