AS2 - A star algorithm

[dragonjet]

I'm trying to make a Tower defense game like Desktop TD or Xeno Tactics.
My problem is the pathfiniding of shortest path from start to finish.
I have done TDs before but only those with pre-defined paths.
One of my games though is similar to what I'm asking,
but has speed problems:

• 
  Winter Wars by dragonjet

  Click to view.

  Type

  Game

  Rated

  Everyone

I've searched at Google and the net and I found A-star algorithm.
I searched for A-star tutorials and I got mostly AS3 codes.
They gave the step-by-step instructions but incomplete,
like how to get exact heuristics and how to deal with juggling.

Can somebody help me with AS2 A-star algorithm?
Codes? Detailed instructions on how to get heuristics?
Or how to deal with juggling and stuff, thanks.

[ssjskipp]

Most of the time, A* is implemented as a function that takes a 2D array, a start row and column, and end row and column. It then returns an array of row and column pairs in some order (from start to end or end to start) of the "best" path.

The 2D Array is a numeric grid of positive values where 0 is impassable (walls, water, etc), and the higher the number the higher the 'cost' (1 is like grass, 90 is fucking lava, you get it).

That's pretty much all you need to know about it... Sometimes they have options for diagonals or not. Just search AS2 A Star and I'm sure you'll find them.

[henke37]

There is a reason for this, path finding is slow, it really benefits from the performance boost that as 3 provides.

[dELtaluca]

At 1/14/10 03:49 AM, dragonjet wrote: like how to get exact heuristics and how to deal with juggling.

there's no such thing as an exact heuristic, that's why it's called a heuristic, and their is no 'best' heuristic to use, it depends on the application, but usually the distance between the node and the target is good enough for most applications.

and juggling? wtf are you on about, there is no such thing as 'juggling' in a-star :P

[dragonjet]

At 1/14/10 07:21 AM, dELtaluca wrote: and juggling? wtf are you on about, there is no such thing as 'juggling' in a-star :P

there is a term 'juggling' in Tower defense games,
where in the best path is cut and another path is made,
creeps must detect this and must go back to take the new route.

At 1/14/10 05:30 AM, ssjskipp wrote: Most of the time, A* is implemented as a function that takes a 2D array, a start row and column, and end row and column. It then returns an array of row and column pairs in some order (from start to end or end to start) of the "best" path.
The 2D Array is a numeric grid of positive values where 0 is impassable (walls, water, etc), and the higher the number the higher the 'cost' (1 is like grass, 90 is fucking lava, you get it).

Thanks, but I already understand the basics of A-star.
I'll re-state my question below my post.

That's pretty much all you need to know about it... Sometimes they have options for diagonals or not. Just search AS2 A Star and I'm sure you'll find them.

I've also tried the diagonal heuristics computation,
it worked at first, but not in all instances.

Now I will refine my question, what I don't understand about A-star is that,
Heuristics are our main way of getting the path right?
but they are estimates only right? But what if those estimates are wrong?
Like the one with lowest heuristic distance leads to a dead end?

[hesselbom]

You can read this very easy to understand tutorial and then implement your own.

At 1/15/10 01:00 AM, dragonjet wrote: but they are estimates only right? But what if those estimates are wrong?
Like the one with lowest heuristic distance leads to a dead end?

If the estimate are wrong, in A*, it simply means it will take longer time to calculate the path. Nothing more.

[LeechmasterB]

Hey, first of a heuristic could be the manhattan distance from one point to another. It can be anything that indicates in which direction it is most probable to find the next path node.

Second, unless you have a dynamic/changing terrain (generated obstacles at runtime in the game) or want to use the A-Star also to maneuvre around troops, then you should not use A-Star!

Instead you can use Dijkstra (on which A-Star is based essentially) and create a static routing table for your terrain. Once you created the routing table at startup of your game you only will have to do lookups to find a path (O(1) instead of O(n log n) or O(n^2) ). As you see this is also essential if you have lots of troops running around trying to find paths all the time. Path finding can slow down your game a lot!

cheers

[dragonjet]

At 1/15/10 03:21 AM, hesselbom wrote: You can read this very easy to understand tutorial and then implement your own.

actually, that is the tutorial I've been studying.
It helped a lot but is incomplete as I said ^^

At 1/15/10 03:57 AM, LeechmasterB wrote: Hey, first of a heuristic could be the manhattan distance from one point to another. It can be anything that indicates in which direction it is most probable to find the next path node.

I actually need even the diagonal so, no to manhattan method

Second, unless you have a dynamic/changing terrain (generated obstacles at runtime in the game) or want to use the A-Star also to maneuvre around troops, then you should not use A-Star!
Instead you can use Dijkstra (on which A-Star is based essentially) and create a static routing table for your terrain. Once you created the routing table at startup of your game you only will have to do lookups to find a path (O(1) instead of O(n log n) or O(n^2) ). As you see this is also essential if you have lots of troops running around trying to find paths all the time. Path finding can slow down your game a lot!

I do have a dynamic and changing terrain.
It's because a tower defense like Desktop TD and Xeno Tactics
where the path depends on how the user built the towers.
I execute the path finding whenever the user builds or sells a tower.
In this case, what should I use? A-star or Dijkstra?

[LeechmasterB]

At 1/15/10 07:11 AM, dragonjet wrote: I actually need even the diagonal so, no to manhattan method

It is a heuristic so even if you need the diagonal it does not matter! HEURISTIC... I even tried explaining it above :P. Anyways you can also just use the real distance or squared distance.

I do have a dynamic and changing terrain.
It's because a tower defense like Desktop TD and Xeno Tactics
where the path depends on how the user built the towers.
I execute the path finding whenever the user builds or sells a tower.
In this case, what should I use? A-star or Dijkstra?

In that case you have to figure out what the optimum is. Dijkstra should not take all that long if the map is "small" (small is of course a relative term), and you could distribute the calculation over a couple of frames instead of doing it within the same cycle.
If you find out the terrain is too big to run a dijkstra during runtime, go with astar. But like said depending on how many objects you have moving around astar might kill the performance.

Now there is a way to improve the astar by "caching/storing" the paths you found until a new tower is built. So your troops can look up if an up to date path exists and only search new paths if the terrain changed or it doesn't exist.

As to implementation, its an algorithm. So if you know how to program you should be able to implement any algorithm, given enough time and thought to it. The key is understanding the abstract concept behind an algortithm, without that you are just "copy pasting" stuff even if you write it down line for line.

Hopefully this helps a bit.

[hesselbom]

At 1/15/10 07:11 AM, dragonjet wrote:

At 1/15/10 03:21 AM, hesselbom wrote: You can read this very easy to understand tutorial and then implement your own.

actually, that is the tutorial I've been studying.
It helped a lot but is incomplete as I said ^^

What is it that you feel is missing?

I used it for a prototype tower defense and it went well with no performance issues. Obviously you can't recalculate the path for each unit but you don't have to! Calculate it once and use the same path for each unit to traverse. Your implementation of the algorithm should return an array of all the tiles to traverse, in order, and you can just have the units reference this list and check where the next tile is depending on what tile they are currently standing on.

And if the user would place a new tower, or some kind of blockage, just recalculate the path once and have the units reference that array instead.

For all this, that tutorial will suffice. It did for me.

[GustTheASGuy]

You don't need A* for TD pathfinding. Simply build a distance map *starting* from each distinct goal.

function fill (dist)
{
  this.stamp = stamp; this.dist = dist+1;
  for (n in neighbors)
    if (n.open && (n.stamp != stamp || n.dist > dist))
      n.fill (dist);
}

[henke37]

A* is not guaranteed to find the shortest path if the estimate is bigger than the real value. Stick a teleporter behind the starting point that leads directly to the goal. If the estimate says that the road forward is better than the teleport, A* will take it.

A good trick is to do path finding in levels, build an overall map of the world and find the path there, then find the detailed path as needed. You don't do pathfinding for every meter when calculating the best path between two locations in different cities.

[dragonjet]

At 1/15/10 08:52 AM, hesselbom wrote:

At 1/15/10 07:11 AM, dragonjet wrote:

At 1/15/10 03:21 AM, hesselbom wrote: You can read this very easy to understand tutorial and then implement your own.

actually, that is the tutorial I've been studying.
It helped a lot but is incomplete as I said ^^

What is it that you feel is missing?

The part of the algorithm where they say that:
a path with lower heuristic that leads to a dead end should not be taken,
but a path with larger heuristic should be taken because it's the only way.
that is the missing part for me.

I used it for a prototype tower defense and it went well with no performance issues. Obviously you can't recalculate the path for each unit but you don't have to! Calculate it once and use the same path for each unit to traverse. Your implementation of the algorithm should return an array of all the tiles to traverse, in order, and you can just have the units reference this list and check where the next tile is depending on what tile they are currently standing on.
And if the user would place a new tower, or some kind of blockage, just recalculate the path once and have the units reference that array instead.

I was always doing that in all of my tower defense games.
Calculate only when you build a new tower,
and the creeps only reference that path.

At 1/15/10 07:20 AM, LeechmasterB wrote: In that case you have to figure out what the optimum is. Dijkstra should not take all that long if the map is "small" (small is of course a relative term), and you could distribute the calculation over a couple of frames instead of doing it within the same cycle.

this might be the one to save me.
It's a 676-tile map (26 x 26 tiles).
Basically if I run pathfiniding in 1 frame, it would kill the game.
But if I run it in lets say 10 frames, about 68 tiles per frame,
that wouldn't be very hard for the system,
it's just that the creeps will have a 10-frame delay
in responding to change in paths due to building towers.
(1/3 of a second for my game @ 30 fps)

As to implementation, its an algorithm. So if you know how to program you should be able to implement any algorithm, given enough time and thought to it. The key is understanding the abstract concept behind an algortithm, without that you are just "copy pasting" stuff even if you write it down line for line.

Yes, I understand that very well. I'm not a copy-paster guy.
That's why I was asking for help in algorithm, and optional codes.
As you see my questions were logical, not a beg for codes ^^

Thanks guys for your help, I'll test them out and see if it works.

[Johnny]

Not sure if this is valid or not, but how does threading work in flash with Timers vs. EnterFrame events?

If multiple timers can run at the same time at different speeds (in tandem with other events), you could calculate your Pathfinding inside a timer (possibly over the course of a few ticks) and keep the rendering in the enterFrame completely.

[GustTheASGuy]

At 1/16/10 09:58 PM, dragonjet wrote: The part of the algorithm where they say that:
a path with lower heuristic that leads to a dead end should not be taken,
but a path with larger heuristic should be taken because it's the only way.
that is the missing part for me.

Where does it say anything like that?
It uses the heuristic to choose which nodes to check first. If there's a dead end, it goes back and checks the next highest heuristic. It does the same even when the goal is found, to find the most optimal path. This is why the exact algorithm is not suitable for game AI.
Anyway, the algorithm is fine and the page explains everything. You can easily find demo implementations.

I was always doing that in all of my tower defense games.
Calculate only when you build a new tower,
and the creeps only reference that path.

Great. See my post on doing it properly. It's simpler.