The A-Star Algorithm

[Owen Densmore]

Has anyone had much experience with the A* algorithm?
  http://en.wikipedia.org/wiki/A-star_search_algorithm
.. this looks *really* interesting.

I know one of us does .. James Steiner posted this to the netlogo list:
  http://turtlezero.com/models/model-viewer-3.php?model=a-star-new_14
.. just hit "go" to see it run, or "setup" then "go" for a new run.

     -- Owen

Owen Densmore
http://backspaces.net - http://redfish.com - http://friam.org

[Martin C. Martin-2]

Owen Densmore wrote:
> Has anyone had much experience with the A* algorithm?
>   http://en.wikipedia.org/wiki/A-star_search_algorithm
> .. this looks *really* interesting.

I think it's the gold standard for path planning in video games these days.

- Martin

[Stephen Guerin]

Owen writes:
> Has anyone had much experience with the A* algorithm?
>   http://en.wikipedia.org/wiki/A-star_search_algorithm
> .. this looks *really* interesting.

Yep, it's arguably the most common form of path-finding in games. One nice
feature is that it can easily handle moving over areas with different costs.

> I know one of us does .. James Steiner posted this to the
> netlogo list:
>   http://turtlezero.com/models/model-viewer-3.php?model=a-star-new_14
> .. just hit "go" to see it run, or "setup" then "go" for a new run.

Nice demo, James!

-Steve

[James Steiner]

> > I know one of us does .. James Steiner posted this to the
> > netlogo list:
> > http://turtlezero.com/models/model-viewer-3.php?model=a-star-new_14
> > .. just hit "go" to see it run, or "setup" then "go" for a new run.
> Nice demo, James!
>
> -Steve

Thanks, Steve!

And thank you, Owen, for sharing my model with this list!

One interesting feature of all these grid search methods, is that they
have not only the current best path to the goal, but also have *a*
path, if not the *best* path, from every point searched, back to the
origin. So, for example, rather than several enemies finding their own
path to the player, the program can instead find the path from the
player to the most distant enemy, also noting which *other* enemies
are on the paths searched. Any enemies not found can be searched for,
also recording incidental enemies found. This puts to use what would
otherwise be wasted search time and data. The result being that a
route will have been found from every enemy back to the player.

This seems like it might be useful. For example, creating a search
path matrix over terrain, using the levelness and down-hillness of the
terrain as the heuristic, and searching from the lowest point to the
highest point, might create a map of the down-hill flow over the
terrain toward the lowest point. Or something.

~~James

[Giles Bowkett]

That's a really cool demo.

I was curious about game AI for a while and a friend in the industry
told me the best place to start is to do an implemention of A*.
Definitely the industry standard from what I can tell.

I was very curious about one idea, actually, which is that if you had
a reasonably logical way to map musical notes to "spaces" on a grid,
you might be able to use A* to generate melodies. Unsure how feasible
that really is, though.


--
Giles Bowkett
www.gilesgoatboy.org

On 4/6/06, James Steiner <gregortroll at gmail.com> wrote:

> > > I know one of us does .. James Steiner posted this to the
> > > netlogo list:
> > > http://turtlezero.com/models/model-viewer-3.php?model=a-star-new_14
> > > .. just hit "go" to see it run, or "setup" then "go" for a new run.
> > Nice demo, James!
> >
> > -Steve
>
> Thanks, Steve!
>
> And thank you, Owen, for sharing my model with this list!
>
> One interesting feature of all these grid search methods, is that they
> have not only the current best path to the goal, but also have *a*
> path, if not the *best* path, from every point searched, back to the
> origin. So, for example, rather than several enemies finding their own
> path to the player, the program can instead find the path from the
> player to the most distant enemy, also noting which *other* enemies
> are on the paths searched. Any enemies not found can be searched for,
> also recording incidental enemies found. This puts to use what would
> otherwise be wasted search time and data. The result being that a
> route will have been found from every enemy back to the player.
>
> This seems like it might be useful. For example, creating a search
> path matrix over terrain, using the levelness and down-hillness of the
> terrain as the heuristic, and searching from the lowest point to the
> highest point, might create a map of the down-hill flow over the
> terrain toward the lowest point. Or something.
>
> ~~James
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9a-11:30 at cafe at St. John's College
> lectures, archives, unsubscribe, maps at http://www.friam.org
>

[Frank Wimberly]

By the way, the A* algorithm is not at all new.  I remember teaching it
in, say, 1984.  According to the text (Rich) that we used at that time
it was first described by Hart, Nilsson and Raphael in an IEEE
publication in 1968.

---
Frank C. Wimberly
140 Calle Ojo Feliz              [phone] or [phone] (cell)
Santa Fe, NM 87505           wimberly3 at earthlink.net

-----Original Message-----
From: [hidden email] [mailto:[hidden email]] On
Behalf Of Giles Bowkett
Sent: Thursday, April 06, 2006 10:53 AM
To: The Friday Morning Applied Complexity Coffee Group
Subject: Re: [FRIAM] The A-Star Algorithm

That's a really cool demo.

I was curious about game AI for a while and a friend in the industry
told me the best place to start is to do an implemention of A*.
Definitely the industry standard from what I can tell.

I was very curious about one idea, actually, which is that if you had
a reasonably logical way to map musical notes to "spaces" on a grid,
you might be able to use A* to generate melodies. Unsure how feasible
that really is, though.


--
Giles Bowkett
www.gilesgoatboy.org

On 4/6/06, James Steiner <gregortroll at gmail.com> wrote:
> > > I know one of us does .. James Steiner posted this to the
> > > netlogo list:
> > >
http://turtlezero.com/models/model-viewer-3.php?model=a-star-new_14
> > > .. just hit "go" to see it run, or "setup" then "go" for a new
run.

> > Nice demo, James!
> >
> > -Steve
>
> Thanks, Steve!
>
> And thank you, Owen, for sharing my model with this list!
>
> One interesting feature of all these grid search methods, is that they
> have not only the current best path to the goal, but also have *a*
> path, if not the *best* path, from every point searched, back to the
> origin. So, for example, rather than several enemies finding their own
> path to the player, the program can instead find the path from the
> player to the most distant enemy, also noting which *other* enemies
> are on the paths searched. Any enemies not found can be searched for,
> also recording incidental enemies found. This puts to use what would
> otherwise be wasted search time and data. The result being that a
> route will have been found from every enemy back to the player.
>
> This seems like it might be useful. For example, creating a search
> path matrix over terrain, using the levelness and down-hillness of the
> terrain as the heuristic, and searching from the lowest point to the
> highest point, might create a map of the down-hill flow over the
> terrain toward the lowest point. Or something.
>
> ~~James
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9a-11:30 at cafe at St. John's College
> lectures, archives, unsubscribe, maps at http://www.friam.org
>

============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org

[Parks, Raymond]

James Steiner wrote:
> This seems like it might be useful. For example, creating a search
> path matrix over terrain, using the levelness and down-hillness of the
> terrain as the heuristic, and searching from the lowest point to the
> highest point, might create a map of the down-hill flow over the
> terrain toward the lowest point. Or something.

   Be careful what you try with this algorithm.  We used Djikstra's
algorithm (a specialized case of the A*) in a graph searching
application only to discover that it does not work well for multiple
path optimization criteria.  Our application was attack graphs with the
paths between nodes being assigned variables such as difficulty,
detection probability, and cost.  We could optimize for one variable but
we could only have constraints on the others, i.e. search for the least
detectable attack that costs less than 10000 units and has at least a
70% chance of success.

   This worked for our application but not very well.  Later, we tried
using routing algorithms, but either our implementation was buggy or the
algorithm really didn't work for multi-factor optimization.

   The most recent version dropped back to a simple brute-force run of
all paths to calculate the variable factors of each path.

--
Ray Parks                   rcparks at sandia.gov
IDART Project Lead          Voice:505-844-4024
IORTA Department            Mobile:[phone]
http://www.sandia.gov/scada Fax:[phone]
http://www.sandia.gov/idart Pager:800-690-5288

[Giles Bowkett]

There are lots of optimizations and hacks for A* in a book called "AI
Game Programming Wisdom," but obviously with games you can load the
dice and the players won't mind as long as they're having fun.

--
Giles Bowkett
www.gilesgoatboy.org

On 4/7/06, Raymond Parks <rcparks at sandia.gov> wrote:

> James Steiner wrote:
> > This seems like it might be useful. For example, creating a search
> > path matrix over terrain, using the levelness and down-hillness of the
> > terrain as the heuristic, and searching from the lowest point to the
> > highest point, might create a map of the down-hill flow over the
> > terrain toward the lowest point. Or something.
>
>    Be careful what you try with this algorithm.  We used Djikstra's
> algorithm (a specialized case of the A*) in a graph searching
> application only to discover that it does not work well for multiple
> path optimization criteria.  Our application was attack graphs with the
> paths between nodes being assigned variables such as difficulty,
> detection probability, and cost.  We could optimize for one variable but
> we could only have constraints on the others, i.e. search for the least
> detectable attack that costs less than 10000 units and has at least a
> 70% chance of success.
>
>    This worked for our application but not very well.  Later, we tried
> using routing algorithms, but either our implementation was buggy or the
> algorithm really didn't work for multi-factor optimization.
>
>    The most recent version dropped back to a simple brute-force run of
> all paths to calculate the variable factors of each path.
>
> --
> Ray Parks                   rcparks at sandia.gov
> IDART Project Lead          Voice:505-844-4024
> IORTA Department            Mobile:[phone]
> http://www.sandia.gov/scada Fax:[phone]
> http://www.sandia.gov/idart Pager:800-690-5288
>
>
> ============================================================
> FRIAM Applied Complexity Group listserv
> Meets Fridays 9a-11:30 at cafe at St. John's College
> lectures, archives, unsubscribe, maps at http://www.friam.org
>