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.

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 is 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:
Found path while avoiding position

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.

Using multiple analyzers

All analyzers that are added to the Astar class (or PathRequest class) are added to a chain. This means that if you want to check both for Walkability and FullClipping, you use the following code:

myAstar.addAnalyzer(new WalkableAnalyzer());
myAstar.addAnalyzer(new FullClippingAnalyzer());

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.

Also note that you only have to add the Analyzers once for each instance. You should normally only have one Astar instance and therefore you should only add the WalkableAnalyzer once in your entire application. The analyzers are not cleared after a path has been found. If you add an analyzer to your Astar instance every time you do a search, your will experience performance loss. Of course, PathRequests are usually not cached and every time you create a new PathRequest, you should add the analyzers that are specific for your PathRequest. A nice way of doing this is by having (fe) a separate “class BigEnemyPathRequest extends PathRequest” that adds all the relevant analyzers in the constructor.

13 Responses to “Analyzers”


  1. 1 Martin

    Hi,
    Thanks for the great AS3 framework for A* algorithm

    I have a question – let’s say we have an archipelago with islands and water areas between them. The player can move either on land or water, but water has penalty when moved onto (the player moves slower). How to include logic that finds a way between two islands that contains as few water tiles as possible?

    As far as I can see this is not what the AvoiderAnalyzer is for. I’m not sure even if any analyzer would do.

    Thank you

  2. 2 Martin

    I just figured out how to do this. By giving higher cost to tiles that have penalty 🙂

  3. 3 Dauntless

    (Edit — Oops, hadn’t seen your second comment)

    Hi Martin,

    You can do this by giving water a higher cost in your map. In the example with the basic tile (http://www.dauntless.be/astar/overview/) the first argument is the cost of that tile. If you make it higher for water than land, it will prefer to walk on land.

  4. 4 T

    For your Clipping analyzers, I had to add

    if (!currentTile) continue;

    right after currentTile is declared and set (or not), otherwise I occasionally get an error, depending on the map layout and size. Not sure exactly why, but that fixes the issue for me.

  5. 5 Dauntless

    I’m not sure if this is an error in the library, or if you aren’t filling in the map right.

    I also forgot to approve your comment, sorry for that. Do you remember what the problem was?

  6. 6 no-jo

    Hi,
    Thanks for sharing this great pathfinding solution but I seem to be having trouble with the FullClippingAnalyser.

    It doesn’t seem to calculate the correct route. see example below:

    8 x 8 grid pathfinding from 0,7 to 7,0.

    mapArray:
    0,0,0,0,0,0,0,0
    0,0,0,0,0,0,0,0
    1,1,0,0,0,0,1,1
    0,0,0,0,0,0,0,0
    0,0,0,1,1,1,1,1
    0,0,0,0,0,0,0,0
    1,1,1,1,1,0,0,0
    0,0,0,0,0,0,0,0

    result with FullClippingAnalyser:

    (x=0, y=7)
    (x=0, y=6) – This is wrong straight away
    (x=1, y=6)
    (x=1, y=5)
    (x=2, y=5)
    (x=2, y=4)
    (x=3, y=4)
    (x=3, y=3)
    (x=4, y=3)
    (x=5, y=3)
    (x=5, y=2)
    (x=5, y=1)
    (x=6, y=1)
    (x=7, y=1)
    (x=7, y=0)

    result with WalkableAnalyser (which works fine):
    (x=0, y=7)
    (x=1, y=7)
    (x=2, y=7)
    (x=3, y=7)
    (x=4, y=7)
    (x=5, y=6)
    (x=4, y=5)
    (x=3, y=5)
    (x=2, y=4)
    (x=3, y=3)
    (x=4, y=2)
    (x=5, y=1)
    (x=6, y=1)
    (x=7, y=0)

    This is how I’m calling it from hero position to mouse click:

    private function request(evt:Event):void
    {
    //create a new PathRequest
    req = new PathRequest(IAstarTile(map.getTileAt(new Point(Math.floor(hero.x / 40), Math.floor(hero.y / 40)))), IAstarTile(map.getTileAt(new Point(Math.floor(mouseX / 40), Math.floor(mouseY / 40)))), map);
    trace(“MOUSE X: ” + Math.floor(mouseX / 40));
    trace(“MOUSE Y: ” + Math.floor(mouseY / 40));
    //a general analyzer
    astar.addAnalyzer(new FullClippingAnalyzer());
    astar.getPath(req);
    }

    Any help would be appreciated.

    Thanks

  7. 7 Dauntless

    The path seems fine, but it depends how you programmed your axis.

    However, I have the feeling that you’re only adding the FullClippingAnalyzer WITHOUT adding the WalkableAnalyzer? The analyers are meant to be chained together, so if you don’t add the Walkable analyzer, your hero will just go through walls. You can simply add one after the other:

    astar.addAnalyzer(new FullClippingAnalyzer());
    astar.addAnalyzer(new WalkableAnalyzer());

    The WalkableAnalyzer makes sure you don’t go through walls, while the FullClippingAnalyzer restricts how the hero can move (only vertical/diagonal)

    You also appear to add a new analyzer every time you create a request. That’s not necessary. Once an analyzer is added to the Astar instance, it will be used for all future requests. If you keep adding analyzers, they will all get chained together and your game will go slower and slower with every path request.

    Let me now if it works 🙂

  8. 8 no-jo

    Yes that worked!

    I didn’t realise you needed to add both.

    Many thanks for the speedy response.

    Thanks

  9. 9 ed

    Hello..

    Please let me know how to set no clipping at walkable analyzer ??

    Thanx

  10. 10 Dauntless

    You have to chain them together. Put BOTH these lines in your code:
    myAstar.addAnalyzer(new WalkableAnalyzer());
    myAstar.addAnalyzer(new FullClippingAnalyzer());

  11. 11 grain miller

    Hi Dauntless,

    Great job there and thanks for sharing.
    Do you plan on a feature to simulate like ‘worm holes’ so you go in in one tile in one part of the map and come out to the other end on the map for example. Maybe this can be done by setting 1 more neighbor to the ‘worm hole’ tile?

    Again thanks for sharing.

  12. 12 Dauntless

    Hey Grain,

    You can implement this yourself. Your Map should just give the “wormhole tile” along with the other neighbours of a specific tile. There’s just one catch: you can’t use a Heuristic. (You can set it to NO_HEURISTIC somewhere, but I forgot where exactly). That’s because the player can’t know which direction will bring him closer to his target, since there is no logic in the wormholes. (Ie: You might have to move further away from the target first, even though you can go straight at it).

    Let me know if you can’t get it to work 🙂

  13. 13 Konstantin

    Wow! This is totally awesome, man! You really saved me a lot of time, thank you very much!

Leave a Reply

*