About

According to WikiPedia, A* (pronounced A Star) is

a best-first, graph search algorithm that finds the least-cost path from a given initial node to one goal node (out of one or more possible goals).

In other words, A* finds the best path from point A to point B. This can be the shortest path but it doesn’t have to be. It could for example be better to pass around a mountain (which would be a longer path) than to go over it.

What you can find here, is an ActionScript 3 (AS3) implementation of A*. It’s primary goal is stability. It should be able to find the path on a 10×10 map as well as on a 1000×1000 map. I will probably create a Lite edition which will focus entirely on speed and ignore stability and be less dynamic/extensible.

Demo

Enough with the chit-chat! Since a picture (or movie) says more than a thousand words, I’ve created this little test application / demo. It still uses v1.1, but it gives a good first look at what is possible.

Demo

Why use this implementation?

I have tried my best to add a lot of extensibility and flexibility to this implementation:

  • Any type of map (square tiles, hexagonal tiles, octagonal, …)
  • Add restrictions to tiles (fe. max numbers of chars on 1 tile, maximum height of a tile, …)
  • Add restrictions to movement (fe. maximum height difference between two tiles)
  • Specify the intensity of the algorithm (the number of iterations per interval & the time between intervals)
  • Asynchronous with search queue (You can add search requests to the Astar instance without worrying about other requests. They will be handled as First Come First Serve)
  • Supports 3D


Download

Latest version
Version 1.3.1

Beta
Version 1.4

Older versions
Version 1.3
Version 1.2
Version 1.1
Version 1.0

Documentation

I’ve created a few pages with some examples and of course there’s also ASDoc documentation. If you think something is unclear or if you want some more examples, just send me an email (or comment) and I’ll update these pages.

The ASDoc documentation is available both online and as a download:
Online
Download

Changelog

V1.1

  • Added AstarPath.toArray();

V1.2

  • Fixed some memory leaks thanks to Mario Benedek

V1.3
I forgot to write down every single change, so I’ll list the biggest changes. Please see the documentation for more information.

  • Analyzers can now be added to a PathRequest
  • Moved heuristic to IMap
  • Moved goal condition to PathRequest
  • Added Astar.safety, Astar.NORMAL_CHECK, Astar.NO_CHECK
  • Moved classes and packages around
  • Removed Analyzer.implementsInterface()
  • Added a static map option. See the Astar constructor for more information

V.1.3.1

  • Fixed a bug in the basic2d.Map class.

Planned

  • Add cooperative searching (multiple agents that are aware of each other)

Bugs

No bugs so far, but if you do find one, please let me know! Feature requests are also appreciated.


License

AS3 A* is free of charge and available under the MIT License. How I understand this license, is that you can use this library in any project you want (including commercial), as long as you keep the copyright notice in the files intact. You also can’t sue me if anything goes wrong ;) .

AS2 A*

A while back, I created an AS2 version of A*. It’s still online, though not under active development.
Documentation: Offline or Online
Source Files: AS2 Astar
SWC Component: SWC AS2 A*
Demo .fla: AS2 A* Example FLA

108 Responses to “A* (Astar)”


  1. 1 Karim

    great stuff you made man!!!

    so if I understand the MIT licence correctly I can use it?
    i’ll be sure to credit you :)

  2. 2 admin

    How I understand the MIT license, is that you can use/sell/modify/copy any part of it, as long as you keep the original comments at the start of the classes intact.

  3. 3 Jesse

    Wow, great job man!
    At school, we are building a little game in Java, and we are also implementing the A* algorithm.
    This can be a great resource, for finding out the inner workings of the algorithm.

    I will keep track of your site, hopeful to see more nice things. Keep up the good work!

  4. 4 Aaron

    Thank you for such an extensible implementation! I’ve never seen one quite so useful before. I appreciate it!

  5. 5 admin

    Thanks Aaron :) . “Be sure to tell your friends” ;)

  6. 6 Stephen

    Hi

    This is a very useful extensible implementation. It plugs very nicely into something I am building at the moment. It’s a shame that this page doesn’t rank high on a Google search – I found this site because I had your AS2 implementation from years back.

    I have a feature request. I would find it useful to be able to have access to an ‘AstarSearchedPath’, as well as the AstarPath. Essentially a collection of all the searched DataTile’s that could then be used to visualise the algorithms search strategy.

    Anyways, once again excellent work. I will spread the word about this :D

  7. 7 admin

    Hi Stephen,

    Thanks for your comment! I’m doing my best to get it high on the google rankings, but I don’t really feel like spamming all the AS fora just to promote myself. Just be sure to blog about me and I’ll rise to the top :) .

    I could get an AstarSearchedPath for you, but it should only be used @ development time as it would obviously slow down the algorithm. Why do you want it exactly? Is it because you want to know why your character takes a certain path when you expected another?

    But your suggestion actually makes sense, even it if would only come in handy for myself while debugging it. (It would be a lot clearer than the Flex debugger)

    I’ve also had some other suggestions (like a toArray() method for the AstarPath and the ability to bind analyzers to a request so that different types of players can share the same instance) and I will be adding yours, probably as a separate release.

    Greets!

  8. 8 Stephen

    Hi

    Thanks for the response :)

    The project I am working on is a set of modules that simulate various aspects of computer games. For pathfinding/AI we are attempting to visualise the computation that goes on behind the scenes when a computer searches for a path using A Star. So, I am not particularly interested in speed, but instead want to be able to access information about searched tiles. I needed to get something spiked quickly and so have hacked a quick solution – apologies :D . I have set Astar Iterations to 1 and modified inspectNeighbours in Astar to dispatch an AstarSearchedEvent as each open neighbour tile is analysed:

    this.dispatchEvent(new AstarSearchedEvent(AstarSearchedEvent.TILE_SEARCHED, cN.getPosition(), cN.getParent().getPosition()));

    I’ve created a SearchCountTile class and associated ISearchCountTile interface with an incrementSearchCount method. The method that catches the AstarSearchedEvent uses position to retrieve and increment the associated SearchCountTile from the map. With this I can visually show how many times a tile has been searched, and I can also visualise in some way the route from parent tile to tile. This allows me to animate in various ways the search as it happens and seems to be working fine. Tiles with different costs appear to be correctly analysed, and final found paths seem correct. However, I’m still thinking about ways to visualise this so it’s got a long way to go yet!!!

    Anyways – that will give you an idea of where I am going with this. You are right though – something could be integrated into your code to help with debugging. Cheers

    Stephen

  9. 9 Michel

    I love this! it works really great! so thanks :)

    Only “bug”, “thing” i found was when i uses the smartClippingAnalyzer it has some duplicate veriable definition errors on line 46, 47, 55, 56, 61 and 62 nothing big.

    Again, thank you!

  10. 10 DooM McQ

    Wow, indeed a very extensible library, i’m just downloading and getting ready to test it, but i did noticed these in your analyzer example

    I think here is where you r going to avoid jumping on the avoidable tile, but not sure xD

    override protected function analyze(mainTile : *, allNeighbours:Array, neighboursLeft : Array, map : IMap) : Array
    {
    var newLeft:Array = new Array();
    for(var i:Number = 0; i distance)<<<<<<<<
    newLeft.push(neighboursLeft[i]);
    } <<<<<<<<
    return newLeft;
    }

    Again congratulations, a fine implementation =)

  11. 11 admin

    Hi DooM McQ,

    You’re right, something went wrong there … I’ve edited the code and it should work now.

    Thanks for reporting!

  12. 12 OnurG.

    great job,

  13. 13 pento

    hi.
    how can i use Hex map?
    is any body know?

  14. 14 Tim

    Hi and thanks for this amazing pathfinding engine!
    I only have one problem, i can not access the AstarPath like an array and “event.getPath() as Array” doesen’t worked for me. I only recieved a string with the path info. Is there a way to get the path as an array?
    Thanks

  15. 15 admin

    The AstarPath class implements the IIterator class, so you can loop through it like this:

    while(path.hasNext()) path.getNext();

    But since a lot of people have asked for a simple array, I’ve updated the AstarPath class to include a toArray() method.

  16. 16 Tim

    Many thanks!

  17. 17 B.Riché

    Hey,
    that’s a very good job, this is the first as3 A* implementation I see that includes the heights and max occupation of the tiles !!

    This is a very good implementation, great work !

  18. 18 Chris

    The example gives some errors trying to compile?

    http://yfrog.com/3oerrorxpdj

  19. 19 Chris

    Ah nevermind I see already.. the code blocks are not working.. it converts html entities

  20. 20 crazedwood

    hi,

    I see the demo,so good.can I get the demo source? I think its help for me. my English is so bad, :P ,My mail:c.sx@hotmail.com. many tks.

    crazedwood

  21. 21 MartinT

    Really nice implementation.

    Maybe you can guide me.

    I’m trying to add an analyser that would prefer straight line even if it’s cost a little more. I already changed the diagonal const to avoid diagonal move.

    I was thinking maybe changing the cost in the map, but it didn’t seem right like the full proof approach.

    ex:
    map
    1111E
    11111
    11111
    S1111

    should do
    1111E
    11110
    11110
    S0000

    instead of
    1110E
    11001
    10011
    S0111

    Thx in advance

    Martin

  22. 22 B.Riché

    Hi !

    I’m looking for an algorithm that could allow to search for the closest tile when no path has been found. Does someone knows how this could be managed ?

  23. 23 Radek

    Hello,

    I have used your code and it was great help. I only thought it would be great if it can work with negative coordinates like x:-5,y-1.

    Is there some easy way how to make it work with negative numbers?

  24. 24 Dauntless

    Hi,

    That would require some tweaking. Why do you need that exactly? It would probably be easier to create a mapping function that (fe) adds 1000 to every coordinate, hence making them positive.

  25. 25 Radek

    Thanks for your reply!

    I am trying to make MMO with huge maps. I am using negative values because I want to make sure I can expand maps in the future. So I am not limited to starting point 0,0 and can expand in both ways.

    I am using negative values in all system, so I didnt thought about your solution (add +1000). But as map will be separated into smaller parts anyway, your solution will work I beleive ;)
    Shame I didnt thought about that, because in my solution I still added +13, but I had to recreate separate pathfinding map on every avatar move :(

    So thank you for your tip, but you can still take it as suggestion for future release :D ! Also thank you for your AStar implementation, it saved me a lot of time!

  26. 26 Rodrigo

    Thanks a lot for the AStar. But I’m having troubles runing the example. I get this error:
    C:\… .as:130: 1046: No se encontró el tipo o no es una constante en tiempo de compilación: AstarEvent.

    Mmmh. Is really strange, because I imported the AstarEvent. Do you know what can be the problem?

    Rod

  27. 27 Dauntless

    I just tried it here and it worked.

    Try recreating your project and maybe clear out your ASO cache.

  28. 28 Strapro

    You sir are a coding god.
    Your implementation was the second I tried and it was far far better.
    My map is approximately 1500 tiles and I am requesting 10 paths pretty much simultaneously.
    No sweat at all! Thank you

  29. 29 Dauntless

    Thanks for the compliments

  30. 30 Anduin Arilan

    Thank you so much! I tried implementing psuedocode from Wikipedia and several other tutorials to no avail. You really should have a donate button!

  31. 31 Dauntless

    You’re welcome :) . If you can’t help yourself, you can always donate on http://www.airdoc.be , one of my application sites.

  32. 32 Tilman

    Thank you :)
    very very good as3 astar implementation.

    but 2 things:
    can you add:
    [Event(name="pathFound", type="be.dauntless.astar.AstarEvent")]
    [Event(name = "pathNotFound", type = "be.dauntless.astar.AstarEvent")]
    over: public class Astar extends EventDispatcher
    // its better for code completion

    and dispatch an progress event while getting path? (runCore)
    if possible ^^

    Thanks

  33. 33 Dauntless

    Thanks for your feedback!

    I’ll add the metadata in the next update.

    Dispatching a progress event isn’t that easy, since you never know if you’re close to finding the actual path… I could maybe dispatch an event that contains the current path, but that would be a lot of overhead (since parent.parent.parent… would have to be calculated every iteration). Your thoughts?

  34. 34 MattM

    I am relatively new to AS3, but I would like to implement this pathfinding in a game I’m trying to make. I get errors when I try to use the basic example. Could you possibly let me know what I need to do to fix it?

    PathFinder.as, Line 23 1084: Syntax error: expecting rightparen before semicolon.
    PathFinder.as, Line 23 1084: Syntax error: expecting semicolon before rightparen.
    PathFinder.as, Line 25 1084: Syntax error: expecting rightparen before semicolon.
    PathFinder.as, Line 25 1084: Syntax error: expecting semicolon before rightparen.

    It looks like it doesn’t like these commands: y&lt, x&lt. But I don’t know how to fix it.

    Thanks.

  35. 35 Dauntless

    < is html for ‘<‘; my Blog was messing up the code. It’s fixed now.

  36. 36 MattM

    Thanks for the quick response. Algorithm looks awesome too. Thanks!

  37. 37 Baby Speer

    Good evening Doctor,

    I’m using small maps to implement your class, but I’m looking for absolute optimization… I barely need things like Height or Cost –only 1 or 0–, and don’t need to use clippings (only Manhattan). How can I turn these off in order to spend the least CPU? Or does it work by default with none of those features and you need to reference them?

    BTW, Thanks for an excellent class…

  38. 38 Baby Speer

    By Manhattan I mean ONLY straight lines and not diagonals. I’m also worried about computing time with Occupation…

  39. 39 Chris

    I can’t believe this was out there all along!

  40. 40 Breakdance McFunkypants

    Hi Dauntless,

    I just wanted to say THANK YOU. I have downloaded and tested pretty much every single a-star implementation on the web. Literally dozens.

    Yours is the most feature-rich AND easiest to implement. I just successfully compiled it using FlashDevelop in a pure as3 project and it worked perfectly. I am using it for a turn-based-strategy RPG game.

    I am most grateful. You are a master programmer and I deeply respect your skill and talent. Keep up the wonderful work.

    - ChrisK aka Breakdance McFunkypants

  41. 41 Dauntless

    If you just want a really lightweight implementation for small maps, you should use another A* implementation. Here are a few: http://www.gotoandplay.it/_articles/index.php

  42. 42 Breakdance McFunkypants

    I prefer your implementation here rather than the messy and poorly programmed smaller ones available on gotoandplay. Most of those examples are either incomplete or have dependencies such as drawing to the screen which means that you can’t simply use the code provided, you need to hack it to interface it with your current game. On the other hand, your a-star as presented here is perfectly encapsulated and self-contained and can simply be dropped into an existing game without problems. Simply put: your code is best because it is more useable and easier to work with.

    One question: would you please be kind enough to show me an example of using this with a HEXAGON grid, as mentioned above?

    Thank you! =)

  43. 43 Dauntless

    I was referring to Baby Speer’s post about the small implementation.

    I haven’t used it on a hex-map yet, but it would probably be something like this:

    public function getNeighbours(position : Point) : Array
    		{
    			var x:Number = position.x;
    			var y:Number = position.y;
     
    			var neighbours:Array = new Array();
     
    			if(this.isValidPosition(new Point(x-1, y))) neighbours.push(this.getTileAt(new Point(x-1, y)));
    			if(this.isValidPosition(new Point(x+1, y))) neighbours.push(this.getTileAt(new Point(x+1, y)));
     
    			if(this.isValidPosition(new Point(x, y-1))) neighbours.push(this.getTileAt(new Point(x, y-1)));
    			if(this.isValidPosition(new Point(x, y-1))) neighbours.push(this.getTileAt(new Point(x, y-1)));
     
    			if(this.isValidPosition(new Point(x, y+1))) neighbours.push(this.getTileAt(new Point(x, y+1)));
     
    			if(y % 2 == 0)
    			{
    				if(this.isValidPosition(new Point(x-1, y-1))) neighbours.push(this.getTileAt(new Point(x-1, y-1)));
    				if(this.isValidPosition(new Point(x-1, y+1))) neighbours.push(this.getTileAt(new Point(x-1, y+1)));
    			}
    			else
    			{					
    				if(this.isValidPosition(new Point(x+1, y-1))) neighbours.push(this.getTileAt(new Point(x+1, y-1)));				
    				if(this.isValidPosition(new Point(x+1, y+1))) neighbours.push(this.getTileAt(new Point(x+1, y+1)));
    			}
     
    			return neighbours;
    		}
     
    		public function isDiagonal(from : Point, to : Point) : Boolean
    		{
    			return false;
    		}

    Just take a hexmap and map out the coordinates. (And don’t use a clipping analyzer)

  44. 44 Breakdance McFunkypants

    I really appreciate the example. Looks like there is one duplicate line of code in your code which I’ll assume is just by accident and should be deleted. Otherwise, I think I may be able to figure this out. The example is very helpful to at least points me in the right direction – as any good pathfinding algorithm should! =P

    Thanks again!

  45. 45 Bryce

    Cool stuff. Thanks!

  46. 46 Michael

    i was wondering if it’s possible to implement this code on google maps. you see, i’m making this project which uses the google maps api created using flash as3. and my goal is for it to have a pathfinder using A star algorihtm. can you help me with that? i’d really appreciate it!!

    thanks for this great example man!! it’s easier to understand for noobs like me…thanks!!

  47. 47 Dauntless

    Hi Michael,

    That’s not really how it works. As far as I know Google doesn’t supply any information about available points & distances.

    The Google Maps API does provide a Directions class that gets the directions for you, so if you’re using a normal map you can use that.

    If you’ve created a custom map (fe a building or something) you could try creating all the points yourself and setting up distances, but since that’s not a tilebased environment, these classes would have to be modified pretty heavily and you’d be better off just creating your own A* implementation.

  48. 48 Michael

    hey dauntless,

    well, you see, i couldn’t use google’s own directions class, cause the whole point of our thesis was to create a A* pathfinder implementation using the google maps api. but since you said, there’s no way to do it in google maps api, how do i create my own map exactly and implement a* there?

    also can i use the map image of google maps itself as my base map for the pathfinder?

    sorry, i’m really new with this stuff..i appreciate your help man!!

  49. 49 James

    sir.. does dat mean implementing A* algorithm on google maps is impossible? thank you so much..

  50. 50 Dauntless

    If you want to implement path-finding, you have to have points on your map that you can use to navigate. In my A* example/implementation every tile in a 2D grid is a point. In navigation software, every ramp, crossroads, freeway exit, etc is a point.

    Then you need information about those points. Fe: What is the cost of going from point A to point B?

    If you’ve got that, you could actually use my classes. (Although I don’t think your professor would like that?) You would have to override the Map class to be able to get the correct neighbors and you would have to hack DataTile.as to get a proper H. (I should really improve my implementation…)

    By the way, if you really want to implement some sort of navigation throughout fe a country, you would use 2 pathfinding algorithms: One to do high level pathfinding (going from city to city) and one to do low level pathfinding (navigating in the cities itself)

  51. 51 James

    ahh ok sir.. we cud use low level path finding then.. does google maps include the costs of every point in a map? thank u so much

  52. 52 Dauntless

    I doubt it. But if your professor says you can do it, there will probably be a way.

  53. 53 Konrad

    Can you tell how your algoritm behave withing a grid graph of size 500×500? It takes about 5 seconds from the very first node to last. I would like to compare it. Can you please extend your demo application with setting grid graph feature?

  54. 54 Konrad

    Can you please extend your demo to change total grid size?

  55. 55 James

    ok sir.. thank u so mch.. god bless..

  56. 56 suraj

    how can i define a unwalkabale tile??

  57. 57 Dauntless

    The BasicTile class has a third argument in its constructor that does exactly that. See the example above for an… example ;)

  58. 58 wyemun

    i noticed that when :
    AstarPath.toArray(), it is not an numeric indexed array, rather a string+associative array like such:

    astarpath["1"] = …
    astarpath["2"] = …
    astarpath["3"] = …

    rather than
    astarpath[1] = …
    astarpath[2] = …
    astarpath[3] = …

    other than that, good job!

  59. 59 Josh

    You should also implement space-time A*. I’m new to this aspect of game design or else I’d do it myself. I think a lot of people would use it, I know I would. This would be ideal for RTS games, or maps with a lot of units moving about. I’d even donate to see this done ;)

  60. 60 Dauntless

    Hi Josh,

    Thanks for the suggestion and the information you sent me.

    I’m pretty busy right now, but I’ll take a look at it when some time frees up.

    Jeroen

  61. 61 Ivan Andonov

    I needed hex grid and your sample helped me alot.
    Here how i do it.
    (there is a minor performance change when adding the neighbours)

    [code]
    package com.dauntless.astar {

    import flash.geom.Point;

    import com.dauntless.astar.*;

    public class MapHex extends Map {

    public function MapHex(width:Number, height:Number) {
    super(width, height);
    };

    override public function getNeighbours(position:Point):Array {
    var x:Number = position.x;
    var y:Number = position.y;

    var neighbours:Array = new Array();

    addNeighbour(new Point(x-1, y), neighbours);
    addNeighbour(new Point(x+1, y), neighbours);

    addNeighbour(new Point(x, y-1), neighbours);
    addNeighbour(new Point(x, y+1), neighbours);

    if(y % 2 == 0) {
    addNeighbour(new Point(x-1, y-1), neighbours);
    addNeighbour(new Point(x-1, y+1), neighbours);
    } else {
    addNeighbour(new Point(x+1, y-1), neighbours);
    addNeighbour(new Point(x+1, y+1), neighbours);
    }

    return neighbours;
    };

    override public function isDiagonal(from:Point, to:Point):Boolean {
    return from.y != to.y;
    };

    private function addNeighbour(neighbour:Point, neighbours:Array):void {
    var tile:IPositionTile = getTileAt(neighbour);
    if (tile != null) {
    neighbours.push(tile);
    }
    };

    };

    };

    // there is a small change in Astar.as as well
    // replacing
    _map = new Map(this._currentRequest.getMap().getWidth(), this._currentRequest.getMap().getHeight());
    // with
    var MapClass:Object = getDefinitionByName(getQualifiedClassName(this._currentRequest.getMap()));
    _map = new MapClass(this._currentRequest.getMap().getWidth(), this._currentRequest.getMap().getHeight());
    [/code]

  62. 62 Dauntless

    Thanks Ivan! I’ll take a look at it when I have some spare time.

    I also think I changed that last part (getDefByName) in the latest internal.

    For those who are interested: I’m working on making it 3D compatible which turns out to be a little more tricky than I thought.

  63. 63 Ivan Andonov

    I did complete it and here you can see the working demo:
    http://iconcept.bg/HexGrid.htm

  64. 64 iMain

    Hey,
    Thanks for great implementation,

    How to find a way in map with the obstacles as with WalkableAnalyzer but without the diagonals in the ways?

  65. 65 iMain

    need to add new analyzer.
    thanks!

  66. 66 Alexis

    Very nice work Dauntless, I found the post on Kirpua forums for 2005. It’s great to find it here in AS3. I’ve been looking at Tonypa’s AS1 A* code and converting it :)

  67. 67 Jclaine

    Love the work, but I did notice that with the cost analyzer that even if all the values are the same, if it is over 1 it requires a significant amount calculation. I haven’t dug to the code yet to see if this is fixable yet. You can recreate in your example by setting all the tiles to 100 and watch the MS go up.

  68. 68 keulu

    Hi ! i’m very impressive by your works. really nice ;)

    But i try to use waypoints on my project with this pathfinding and i don’t succeed.

    does anybody can help me ?

    i try to go A to C via B.

    thanks a lot.

    a good job again ;)

    (sorry for my English, I’m french ^^)

  69. 69 Dauntless

    Bonsoir Keulu!

    The easiest way to do that is to just calculate a path from A to B and then from B to C. Is there a reason why you can’t do it like that?

  70. 70 keulu

    waaahhhhh. speedy answer ^^

    not at all, it was just to see if it was possible to do so.
    I suspected it was going to end up like that.

    thanks and good job again ;)

  71. 71 Dauntless

    You’re welcome :)

    By the way, I’ve got v1.3 ready to release. I’m finishing up the documentation & creating some demo’s, so be sure to check back here soon!

  72. 72 Jclaine

    Looking forward to implementing v1.3, might I suggest that you swap out the math.abs() for a bitwise operation? IE i = (x ^ (x >> 31)) – (x >> 31); (code from http://lab.polygonal.de/2007/05/10/bitwise-gems-fast-integer-math/)

  73. 73 Alexander

    Hi, I can’t get how to make tiles unwalkable. Maybe I’m doing something wrong? =)

    So, here’s how I’m using your system:

    1. creating new Astar instance
    2. making new Map
    3. filling map with BasicTile –
    y x loops here {
    var des:Boolean (random true or false here for a test)
    var bt:BasicTile = new BasicTile(1,new Point(x, y),des);
    myMap.setTile(bt);
    }
    4. creating new PathRequest
    5. adding AstarEvent listener to Astar instance
    6. using getPath on Astar instance
    7. catching a path

    everything works fine, but path is ignoring unwalkable tiles =(

  74. 74 Dauntless

    Hi Alexander,

    I was updating the documentation for v1.3 and I accidentally removed the documentation for v1.2 and I don’t have a backup. This page was way longer with an example of how you should use the analyzers.

    Answer: you have to add the WalkableAnalyzer: astar.addAnalyzer(new WalkableAnalyzer());

  75. 75 Alexander

    Thanks, now I think I’ve got how it all works together :)
    (You are responding so fast %)

  76. 76 Joeri

    Looking good, will try it out.
    The thing is that I have a 3d terrain, with uphill and downhill.
    Does your A* handle that as well?
    Not sure how to define a height map for it.

    I guess I better read the docs first.
    Thanks.

  77. 77 Dauntless

    Hi Joeri,

    I didn’t notice your post, sorry for that. In case you’re still wondering (or anyone else), it should support full 3D. You can have bridges, gravity, inclines, etc. If your map doesn’t have bridges or overhangs (ie, any place where there are multiple possible positions on one (x,y) location), you can use a regular 2D approach with a HeightAnalyzer (or similar).

  78. 78 drag0n

    great work!
    wondering if u have considered multi-points like point 1 to 2, 2 to 3, 3 ta 4, ect

  79. 79 Dauntless

    I dont really understand what you mean. Could you please ellaborate and/or give an example?

  80. 80 drag0n

    as in a tower defense having multipull points to go to. have staring point then 2 other points to get to and then go to the finish point, im guessing basically just running it to find best path between each point.

  81. 81 Dauntless

    If you want to hit them in a specific order, you can easily do this yourself. Every time you end up at a specific point, you just look up the path for the following point. This way your path will also be more up-to-date than if you calculate it at the start (and the user changes map while your enemies are walking)

    If you don’t care about the order and want them to just find the shortest path between all of the possibilities, you will have to calculate a path for each possible combination and compare the path lengths yourself. This is actually the same problem as the traveling salesman problem (http://en.wikipedia.org/wiki/Traveling_salesman_problem) and it’s considered a very hard (=time consuming) problem to solve. I would suggest you avoid it :)

    A lot of tower defense games also use a fixed path (or a number of fixed paths and choose one at random), but that only works for TD games where you can only place your towers at fixed locations along the path.

    If you want any more advice, please tell me what kind of TD game you are building :)

  82. 82 Electrolyte

    Hi,

    This is great! Thank you so much for sharing this.

    I have a question about the default walkable tiles, I would like to flip the data so that tiles in the mapdata of ’0′ are considered walls and then number 1 upwards are walkable. Is this possible?

    I’m quite new to using classes and I’ve read though the documents but cant seem to find it, apologies if I’ve missed it. Any help would be great.

    Thank you again for some great code :D

  83. 83 Dauntless

    The third argument of the BasicTile constructor is a boolean that tells the tile if it’s walkable or not. So in stead of doing this:

    map.setTile(new BasicTile(1, new Point(x, y), (dataMap[y][x]==0)));

    You could do this:

    map.setTile(new BasicTile(1, new Point(x, y), (dataMap[y][x]>0)));

  84. 84 Electrolyte

    Thank you! Sorry yes I worked that out in the end. Its a great function and have got it integrated into the game, works a treat. Will be putting you in credits :D

  85. 85 Renofox

    This is exactly what I need for my game! I have managed to create a map and place walkable and nonwalkable tiles on it, but I’m stuck trying to create a PathRequest. Is it possible to get the code for the demo to see how it works?

  86. 86 Dauntless

    Hi Renofox,

    There’s a small example on the overview page (http://www.dauntless.be/astar/overview/). I could give you the source for the demo, but it’s written with v1.0 and the library has changed a lot since then. It’s also pretty much hacked together so it would just get really confusing.

    I also intended to add a few demo’s to the .rar, but apparently I forgot/misplaced them.

  87. 87 eKimiya

    Hi !
    I think there is a problem with your Map class. The function calcIndex doesn’t seems to work if you use it with a map witch is
    longer than wide…

    Anyway, it’s a great job !!

    See ya

  88. 88 bruceb

    hey first thanks for your time and effort on this!

    I’m getting stack overflow errors… no idea what’s really going on but here’s what I”m doing:

    I have a maze, and I need to find (any) two tiles that have a path length that’s between two values

    so I choose two tiles at random, loop on astar.getPath() till a path is found that has right number of steps, then I break

    sometimes this happens in maybe 5 iterations, sometimes more. when it takes more than maybe 10 iterations it blows up w/ a stack overflow error

    here by iterations I mean iterations of my loop, not the iterations internal to your A* classes

    thoughts? suggestions? thanks

  89. 89 Dauntless

    Hi Bruce,

    I think that’s a really inefficient way of finding the right tiles!

    A better way would be to maybe choose one random tile and have A* search until a path with the correct length is available. If you implement the IMap.getHeuristic function so that it always returns 0, you have a Breadth-first search that expands in all directions equally fast.

    You can’t use the PathRequest.isTarget method since you don’t have any information about the path there, only the tile.

    If you give me some more information, I can probably help you hack it together (= making a few private methods/properties public). What does your map look like? Is it just a binary map (walkable/non-walkable) or are there also costs involved?

    And what’s the overall idea behind your problem? It seems like this is a sub problem of a bigger problem that could maybe be handled differently?

    If you want to keep some information private, you can always email me using the contact form :)

  90. 90 Niclas

    Hey!

    Awesome work! Works really well!

    Thanks a lot!

  91. 91 kevin

    Hi Bruce,
    There were some problem in my program.I wrote the code like the example which you wrote.But even that the data of map were all allow through,When i want get the path for any two point.That were warning me “path was no found”,I can’t find the reason.

  92. 92 Dauntless

    Hi Kevin,

    Are you addressing me, or Bruce?

    If you can’t make it work, feel free to e-mail me your test project.

    Jeroen

  93. 93 Martin

    I encounter a problem; don’t know where it comes from exactly (it may be misconfiguration on my side, or some kind of problem in the framework)

    it happens in the following scenario:

    I have a initialized map 160×160 grid units;
    I click on a grid unit that is walkable; but it is all surrounded by unwalkable grid units;

    it then generates huge amount of iterations because I receive lag and path not found after 5-6 seconds.

    I think this happens because the algorithm can’t figure out the tile is all blocked and it tries to iterate over the whole map to find a way to it.

    Please give feedback :)

    Thank you

  94. 94 Dauntless

    Hi Martin,

    You’re right that the current library can’t recognize this situation. A solution to this would be to have two A* instances running side by side (one going from start to end and one going from end to start) where you would stop the other instance if one instance can’t find a path. I don’t think the current implementation supports stopping calculations halfway, so I’d have to look into that. When I find some time, I’ll see if I can fix something up to help in your situation :) .

  95. 95 Martin

    Thank you :)

    It is actually not a huge problem for me, because it occurs very rarely. However it may be good addition to your framework :)

  96. 96 Martin

    Regarding the situation I mentioned in the previous post – I now believe it is some kind of failure in either the algorithm, or the implementation.

    Imagine a map, of some size, where there is some tile that is walkable, and it is all surrounded by occupied tiles. Something like this:

    1 1 1 1 1 1 1
    1 • • • 1 1 1
    1 • 1 • 1 1 1
    1 • • • 1 1 1
    1 1 1 1 1 1 1
    etc..

    where dots are occupied tiles and ones are walkable (free) tiles.
    Guess a scenario where you click on the free tile that is all surrounded by occupied tiles. In a normal scenario, the algorithm would reach the dots, surround all of them and conclude that it cannot shorten the distance to the destination any more. In that case it should fire path not found. Instead, I suspect the framework to continue the search algorithm and expand throughout all the map which causes big amount of unnecessary iterations until all the edges of the map are reached. I don’t know if this problem is by design of the algorithm, or a problem in the implementation. Please take a look…

    Best regards,
    Martin

  97. 97 Dauntless

    Hi Martin,

    A* will indeed continue searching the entire map. There is no mechanism that detects if a certain tile is unreachable. In this current implementation, you can dismiss the heuristic (so A* becomes breadth-first) and add ‘teleport tiles’ to your map. That way, it would be pretty hard to decide if a certain tile is unreachable.

    It would of course be possible to add a check to see if the immediate neighbors of the target tile have all been visited, but if the tile is on a little island, it’s still unreachable, and its immediate neighbors will never be visited.

    Like I said, the only “good” way to fix is is to start two astar intances and have them go toward each other. However, a bidirectional search often has the problem that the two search paths miss each other all together and you end up calculating the path twice (and end up with two equally valid paths)

    Depending on your game, you can maybe find a few optimizations yourself. If the islands are fixed, you could perform a flood-fill on a few tiles so that you know which tiles can be generally reached, and which can not. If your map only changes sporadically, you could still use this technique (maybe even using bitmap operations for a faster flood-fill). If you are certain that you will never have a situation where you would have to first move further away from the target in order to get closer, you could probably add a check for that and stop the algorithm if this happens. A possible situation where you have to move further away before getting closer is of course when you have to move around a wall or something.

  98. 98 Martin

    Understood. As I said it’s not a big issue. I notice another strange thing however. Sometimes, when pathfinding is initiated, even for very simple routes (that would result in 4-5 tiles path found) I get the very same thing – lag and 5-6 seconds of delay. Very strange, since the destination is very near and it is supposed to be resolved very quickly. If you don’t mind I could send you a link to the demo of the game so that you can see yourself what the issue is…

  99. 99 Dauntless

    Sure, you can send me a link to the demo. And preferably a situation where you get the delay (if you can reproduce it?)

  100. 100 Martin

    I sent you a personal message. Thank you

  101. 101 clement

    Where can I find an example with height tiles? ( hills & valleys )
    I’ve been through the doc but can’t understand how to implement that…

  102. 102 Dauntless

    What exactly are you looking for? There’s a HeightAnalyzer in be.dauntless.astar.basic2d.analyzers. That analyzer can make sure your path wont go above a certain height or below a certain height. It can also make sure that there’s a max (or min) difference between the current tile and the next tile. (Fe: Your hero can only jump 3 high, so maxDiff should be 3).

    For this to work, your tiles need to implement the IHeightTile, which just makes sure that each tile has a certain height.

  1. 1 A* (Astar) « AS3 Game Gears
  2. 2 newb.to.pro(grammer) » A*Star Pathfinding
  3. 3 PathFinder A* | howdoflash
  4. 4 Polygonal map generation and pathfinding | Wired Vagrant
  5. 5 Find a path from point A to B in X steps. (A* ish) | Software development support, software risk,bugs for bugs, risk analysis,
  6. 6 Optimization – Choosing the right algorithm - selene tan

Leave a Reply

*