Dauntless.be

When searching for a path, Astar should ignore certain tiles. The most basic example are tiles that aren’t walkable (fe. walls). To remove those tiles from the list of possibilities, analyzers are used. You can add Analyzers to the Astar instance or to a PathRequest using the addAnalyzer() method for both classes. Analyzers that are added to the Astar instance will be used for all future path request, while analyzers that are added to a PathRequest will only be used for that particular path request.

All analyzers are added to a chain. The neighbors that pass the first analyzer are passed to the next analyzer, etc. If you add analyzers to both the PathRequest and to Astar, the neighbors will first be passed to the analyzers of the Astar instance and then to the analyzers of the PathRequest.

The most basic Analyzer is the WalkableAnalyzer. This analyzer makes sure you won’t go through tiles that aren’t walkable:

package be.dauntless.astar.basic2d.analyzers  
{
	import be.dauntless.astar.basic2d.IWalkableTile;
	import be.dauntless.astar.core.Analyzer;
	import be.dauntless.astar.core.IAstarTile;
	import be.dauntless.astar.core.PathRequest;
 
	/**
	 * The WalkableAnalyzer eliminates tiles that aren't walkable. If ignoreEnd is true, the end node (PathRequest.isTarget(tile)) doesnt have to be walkable
	 * @author Jeroen
	 */
	public class WalkableAnalyzer extends Analyzer {
		private var _ignoreEnd:Boolean;
		public function WalkableAnalyzer(ignoreEnd:Boolean = false) {
			super();
			_ignoreEnd = ignoreEnd;
		}
 
		override public function analyzeTile(tile: IAstarTile, req:PathRequest):Boolean
		{
			if(_ignoreEnd && (req.isTarget(tile))) return true;
 
			return (tile as IWalkableTile).getWalkable();	
		}
 
		override protected function analyze(mainTile : IAstarTile, allNeighbours:Vector.<IAstarTile>, neighboursLeft : Vector.<IAstarTile>, req:PathRequest) : Vector.<IAstarTile>
		{
			var newLeft:Vector.<IAstarTile> = new Vector.<IAstarTile>();
			for(var i:Number = 0; i<neighboursLeft.length; i++)
			{
				var currentTile : IAstarTile = neighboursLeft[i];
				if((currentTile as IWalkableTile).getWalkable() || (_ignoreEnd && req.isTarget(currentTile))) newLeft.push(currentTile);
			}
			return newLeft;
		}
	}
}

To be able to use this analyzer, your tiles have to implement the IWalkableTile interface. Astar itself doesn’t know anything about the tiles it it using. Only the analyzers (and/or map) are aware of the properties of a tile.

Creating custom analyzers

The WalkableAnalyzer is an example of a custom analyzer. Each analyzer will extend the Analyzer class and override the analyze() and analyzeTile() methods.

The analyzeTile() method is used to see if the start and/or end tile are valid tiles. It takes two arguments: the tile to analyze and the pathrequest that is being executed. If ignoreEnd (the parameter for the WalkableAnalyzer constructor) is set to true, the end tile can be unwalkable. This situation can happen when you allow your character to go sit on a chair, which is of course a non-walkable tile.

The analyze() method is used to trim down the list of neighbors during the A* search. Every analyzer receives a list of the tile who’s neighbors are being analyzed, the neighbors that have passed the other analyzers, a full list of neighbors and the PathRequest that is being handled. The analyzer should trim out any other neighbors that don’t pass its test and return the remaining neighbors.

Another example of an analyzer is the AvoiderAnalyzer. For example, if you want your hero to find a path from A to B while avoiding C, you could do something like this:

package
{
	import be.dauntless.astar.basic2d.IPositionTile;
	import be.dauntless.astar.core.Analyzer;
	import be.dauntless.astar.core.IAstarTile;
	import be.dauntless.astar.core.PathRequest;
 
	import flash.geom.Point;
 
	/**
	 * @author Jeroen
	 */
	public class AvoiderAnalyzer extends Analyzer
	{
		private var toAvoid : Point;
		private var distance:Number;
		public function AvoiderAnalyzer(toAvoid:Point, distance:Number)
		{
			this.toAvoid = toAvoid;
			this.distance = distance;
			super();
		}
 
		override public function analyzeTile(tile: IAstarTile, req:PathRequest):Boolean
		{
			var pos:Point = (tile as IPositionTile).getPosition();
			return (Math.abs(pos.x - toAvoid.x) + Math.abs(pos.y - toAvoid.y) > distance);
		}
		/**
		 * Nodes that are too close to the given tile are removed from the neighbors list and will not be used in the path.
		 */
 
		override protected function analyze(mainTile : IAstarTile, allNeighbours:Vector.<IAstarTile>, neighboursLeft : Vector.<IAstarTile>, request : PathRequest) : Vector.<IAstarTile>
		{
			var newLeft:Vector.<IAstarTile> = new Vector.<IAstarTile>();
			for(var i:Number = 0; i < neighboursLeft.length; i++)
			{
				var currentPos : Point = (neighboursLeft[i] as IPositionTile).getPosition();
				var currentDistance:Number = Math.abs(toAvoid.x - currentPos.x) + Math.abs(toAvoid.y - currentPos.y);
				if(currentDistance > distance) newLeft.push(neighboursLeft[i]);
			}
			return newLeft;
		} 
 
		public function getToAvoid() : Point
		{
			return toAvoid;
		}
 
		public function setToAvoid(toAvoid : Point) : void
		{
			this.toAvoid = toAvoid;
		}
 
		public function getDistance() : Number
		{
			return distance;
		}
 
		public function setDistance(distance : Number) : void
		{
			this.distance = distance;
		}
	}
}

You can then add it to the PathRequest’s analyzer list, so that only your hero will avoid the given point:

req.addAnalyzer(new AvoiderAnalyzer(new Point(1,4), 2));

Using the basic example from the Overview page, you will get the following solution:

Example analyzers

I’ve included a bunch of example analyzers that can be found in the be.dauntless.astar.basic2d.analyzers and be.dauntless.astar.basic3d.analyzers packages. Here’s a quick overview:

• FullClippingAnalyzer: Diagonal tiles are removed
• SmartClippingAnalyzer: Diagonal tiles will be removed if the horizontal or vertical tile next to it is not walkable.
• HeightAnalyzer: Tiles that don’t meet certain height requirements are removed. It can remove tiles that are to high/low (“your hero won’t have oxygen on tiles higher than 10″) or tiles that can’t be reached from the current tile (“your hero can only jump 3 high”)
• IOccupationTile: Eliminates tiles on which there isn’t enough room to walk upon (“Only one character on each square”)

But as I said before, these are just examples and you should definitely try creating your own.