Here’s a little example that shows a how a basic setup would work. You can find more information on analyzers, maps and pathrequests in the corresponding sections.

package 
{
	import be.dauntless.astar.basic2d.BasicTile;
	import be.dauntless.astar.basic2d.Map;
	import be.dauntless.astar.basic2d.analyzers.WalkableAnalyzer;
	import be.dauntless.astar.core.Astar;
	import be.dauntless.astar.core.AstarEvent;
	import be.dauntless.astar.core.IAstarTile;
	import be.dauntless.astar.core.PathRequest;
 
	import flash.display.Sprite;
	import flash.geom.Point;
 
	public class GeneralTest extends Sprite
	{
 
		private var dataMap:Array;
		private var map : Map;
		private var astar : Astar;
 
		private var req:PathRequest;
		public function GeneralTest()
		{
			dataMap = [ [0,0,1,1,1,0],
						[0,0,0,0,1,0],
						[0,1,1,0,0,0],
						[0,0,0,0,1,0],
						[0,1,1,0,1,0],
						[1,1,0,0,0,0] ];
 
			//create a new map and fill it with BasicTiles
			map = new Map((dataMap[0] as Array).length, dataMap.length);
			for(var y:Number = 0; y< dataMap.length; y++)
			{
				for(var x:Number = 0; x< (dataMap[y] as Array).length; x++)
				{
					map.setTile(new BasicTile(1, new Point(x, y), (dataMap[y][x]==0)));
				}
			}
 
			//create the Astar instance and add the listeners
			astar = new Astar();
			astar.addEventListener(AstarEvent.PATH_FOUND, onPathFound);
			astar.addEventListener(AstarEvent.PATH_NOT_FOUND, onPathNotFound);
 
			//create a new PathRequest
			req = new PathRequest(IAstarTile(map.getTileAt(new Point(0, 0))), IAstarTile(map.getTileAt(new Point(5, 5))), map);
 
			//a general analyzer
			astar.addAnalyzer(new WalkableAnalyzer());
			astar.getPath(req);
		}
 
		private function onPathNotFound(event : AstarEvent) : void
		{
			trace("path not found");
		}
 
 
		private function onPathFound(event : AstarEvent) : void
		{
			trace("Path was found: ");
			for(var i:int = 0; i<event.result.path.length;i++)
			{
				trace((event.result.path[i] as BasicTile).getPosition());
			}
		}
	}
}

This will return

Path was found:
(x=0, y=0)
(x=0, y=1)
(x=0, y=2)
(x=1, y=3)
(x=2, y=3)
(x=3, y=4)
(x=4, y=5)
(x=5, y=5)

Or, graphically:

Found path

21 Responses to “Overview”


  1. 1 Andrew

    Hi!
    Say please, how me create pathfind without diagonal transition?

  2. 2 Dauntless

    Hi Andrew,

    You have to add the FullClippingAnalyzer as documented on http://www.dauntless.be/astar/analyzers. It could be a little more clear though, so I’ll change this documentation page a little.

  3. 3 Andrew

    Thank you, very much!
    But if i change analyzer on FullClippingAnalyzer, path go over ocuped tiles. Thus, the path is solved incorrectly. (

  4. 4 Dauntless

    You don’t have to change it from one to another, you have to add them both:

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

  5. 5 Andrew

    O! Thank you.
    I am try.

  6. 6 frank

    how can i change a tile in retrospect, if the whole map already built???
    i´d tried it with:

    map.setTile(new BasicTile(1, new Point(target.x, target.y), false));

    but the tile is walkable further…

  7. 7 Dauntless

    That should work, although it’s probably better to request the existing tile with getTileAt and change it’s walkability.

    Your problem may be that you have ‘true’ as the caching parameter for the Astar instance. When you use new Astar(true); it caches the found paths and you can only use that if you have a static (= non changing) map. If your map can change, you should use new Astar()

  8. 8 Matthew

    How do I account for dynamic obstacles, ie NPCs walking around and getting in the way?

  9. 9 Dauntless

    The easiest way would be to recalculate the path when you run into an obstacle. Here’s a little more information: http://theory.stanford.edu/~amitp/GameProgramming/MovingObstacles.html

    As described there, if their movement is predictable, you can hack my classes and have it give the current path length as an argument to the Map class so that it can calculate if a tile will be walkable after x steps.

    Another way would be to have cooperative path finding where every unit that searches for a path is aware of the paths of all the other units, but that’s quite a big step from my current implementation.

  10. 10 Edward

    I have to say this is awesome!
    Thanks for sharing~

  11. 11 Jay Armstrong

    Hi Dauntless,
    This is a really fantastic resource – thank you so much!
    I’m having an issue however in which over time each new route takes longer and longer to calculate until the point in which the game completely freezes.
    I wondered whether there was some best practice examples for controlling a number of units and whether there are things that need to be removed or cleared after each path is found.
    I’ve tried with astar caching to false and it hasn’t made any difference.
    Thanks again for posting such a brilliant tool!
    Jay

  12. 12 Dauntless

    If anyone else is having this problem: Jay’s error was that he added all the analyzers to Astar on each subsequent path request. This if not necessary since Analyzers that are added to an Astar instance are kept forever. If some analyzers should only be used by some units, they should be added to the PathRequest. By adding them each time, the list became longer and longer upon each request.

  13. 13 francisco chong

    Hey Dauntless,
    I love your Astar classes.
    how does map.getDistance work ?

    Im not sure how to interpret if its 1 or 1.4 what does it mean?
    I though this would output like tiles to get to target tile.

    Or if i could use this to validate if the unit should keep searching for a path for the hero?

    The problem im having is that they keep searching forever, thus hampering the performance of the game.

    i need to keep the search alive is the hero is moving.
    so i keep doing “astar.getPath”.

    Basically i wanna know if on your map class is there a way to know if the hero is unreachable.

  14. 14 Dauntless

    Hi Francisco,

    The getDistance() method is a heuristic. That means that it’s a “guess” about what the distance to the target is. The closer this distance is to the real distance, the faster the algorithm will be. The 1.4 is because when you go diagonally, its approximately sqrt(2) units of distance (as opposed to 1 unit of distance when going up/down/left/right).

    If you continuously need to check if the hero can reach a certain place (or vice versa), there are probably better ways to do this, but it depends on your game. My library will let you know if the hero is unreachable by dispatching an AstarEvent.PATH_NOT_FOUND event. In any case, you should probably only try again when the event has been dispatched (instead of in en ENTER_FRAME).

    There could be better ways to determine if your hero is reachable or not. You should think about which events cause the hero to be unreachable and maybe use that data to determine if he can or can’t be reached at a certain point in the game.

  15. 15 Gimmick

    Hi Dauntless,
    Can I use this with an existing map made up of a 2 dimensional Vector. instead of an Array? “Tile” is a custom class I’ve made which has a walkable property, so is it possible for me to use this with the Vector.<Vector.> instead of Array(Array(int))? Or do I have to scrap my implementation and switch to an Array?

    Thanks in advance

  16. 16 Dauntless

    Hi Gimmmick,

    The Array(Array(int)) is just a quick way to add some data for the example. You can have your Tile class implement the IAstarTile and the IWalkable interface and put them directly into the Map with setTile(). (Instead of creating a BasicTile) The representation inside the Map class will still use Arrays, but it doesn’t matter that you use Vectors in other places.

  17. 17 Gimmick

    Thanks! The game I’m using this in has four to five different “units” each of which can only move on particular tiles (i.e. land, sea) and so I’m wondering how I’d do this. Should I create 2 maps and an analyzer for each unit, or 2 maps and 2 analyzer, or 1 map and analyzer for each unit?

  18. 18 Dauntless

    You should create a single map, add general analyzers to the map (like Walkability) and specific analyzers (land/sea) to the PathRequests.

  19. 19 Gimmick

    Thanks!

  20. 20 Rishi

    Can i merge tilemap with Astar? can you give me a brief idea how to do this?

  21. 21 Dauntless

    Hi Rishi,

    What tilemap are you talking about? Could you give a little bit more information?

Leave a Reply

*