[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

[QUIZ] A* (#98

James Gray

10/13/2006 12:39:00 PM

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rub...

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Steven Davidovitz

The A* (A-Star) search algorithm is a path-finding algorithm with many uses,
including Artificial Intelligence for games. The search builds the route from
tile to tile until it reaches the goal. To help choose the best possible tile
the algorithm will use an equation that takes into account the distance from the
tile to the goal and the cost of moving to that tile.

Let's work through an example, so you can see how this comes together.

Movement Cost for Terrain:
Non-walkable:
N/A = Water (~)
Walkable:
1 = Flatlands (. or @ or X)
2 = Forest (*)
3 = Mountain (^)

Test Map:
@*^^^ @ = User start
~~*~. X = The goal tile
**...
^..*~
~~*~X

Step 1: Search the surrounding tiles for walkable choices.

The only possible tile for the fist step is to the right: a forest (*) tile.

Step 2: Go through that list finding the cost of movement for each of those
choice tiles. The cost of movement is the path cost so far, plus the cost to
move to the tile being considered.

Our cost so far is 0, since we just started. The cost of a forest is 2 so the
total cost of this move is 2 (0 + 2).

Step 3: Determine the distance from the choice tiles to the goal and add that
to the cost from Step 2 to find the score for each tile.

You can calculate the distance from the tile to the goal using Manhattan
distance formula |x1 - x2| + |y1 - y2|. For our example that is:

|1 - 4| + |0 - 4| = |-3| + |-4| = 7

Knowing that we can produce the final score for this move:

score = cost (2) + distance to goal (7) = 9

Step 4: Choose the best tile to move to by comparing the score of the
surrounding tiles and choosing the lowest.

Step 6: Repeat Steps 1-4 until you reach the goal tile. Be careful to prevent
checking tiles twice and/or circling back.

Test Map Solution:
##^^^ # = Best path
~~#~.
**.#.
^..#~
~~*~#

When you have a working solution, try it out on this move involved map:

http://www.rub...large_map.txt
19 Answers

James Gray

10/13/2006 1:05:00 PM

0

Just FYI, the summary for this quiz will be a little early. I will
post it sometime Wednesday.

James Edward Gray II

jason r tibbetts

10/13/2006 2:31:00 PM

0

Step #5 is missing. Should it be '???' or 'Profit!'?

:)

...

> Step 4: Choose the best tile to move to by comparing the score of the
> surrounding tiles and choosing the lowest.
>
> Step 6: Repeat Steps 1-4 until you reach the goal tile. Be careful to prevent
> checking tiles twice and/or circling back.

...

Martin Coxall

10/13/2006 2:37:00 PM

0

> Step 1:

>*snip*

> Step 3:

Slight concern- aren't you actually here giving us a solution to a
problem, and then just asking to implement the algorithm you've
already explained? Where's the fun in that.

Part of the joy should be in doing some research and applying some
thought to find the best algorithm. It slightly ruins it if you give
us an answer in the problem.

Martin

James Gray

10/13/2006 2:42:00 PM

0

On Oct 13, 2006, at 9:30 AM, jason r tibbetts wrote:

> Step #5 is missing. Should it be '???' or 'Profit!'?
>
> :)

Oops. That's my fault. I consolidated two of the steps in the
original quiz and obviously forgot to renumber. I'll fix it on the
web site.

James Edward Gray II

Jacob Fugal

10/13/2006 2:47:00 PM

0

On 10/13/06, Martin Coxall <pseudo.meta@gmail.com> wrote:
> Slight concern- aren't you actually here giving us a solution to a
> problem, and then just asking to implement the algorithm you've
> already explained? Where's the fun in that.

Actually, the basic algorithm he explained isn't quite A-star (I'm
guessing on purpose). There's lots of room for improvement in both
algorithm and heuristic. I'm guessing that's where the fun and variety
of this quiz will be. :)

Jacob Fugal

Sander Land

10/13/2006 3:09:00 PM

0

On 10/13/06, Jacob Fugal <lukfugl@gmail.com> wrote:
> Actually, the basic algorithm he explained isn't quite A-star (I'm
> guessing on purpose). There's lots of room for improvement in both
> algorithm and heuristic. I'm guessing that's where the fun and variety
> of this quiz will be. :)
>
> Jacob Fugal

Isn't he just explaining a greedy search without backtracking?
Also, this algorithm seems to go wrong even on the small map:

##^^^
~~#~.
**.#.
^..*~
~~*~X

##^^^
~~#~.
**.##
^..*~
~~*~X

James Gray

10/13/2006 3:23:00 PM

0

On Oct 13, 2006, at 9:36 AM, Martin Coxall wrote:

>> Step 1:
>
>> *snip*
>
>> Step 3:
>
> Slight concern- aren't you actually here giving us a solution to a
> problem, and then just asking to implement the algorithm you've
> already explained? Where's the fun in that.

I do encourage quiz creators to do this, yes. It's being done here
and this isn't the first quiz to do it.

I feel it lowers the bar for people to play with the quiz. No one is
forced to use the described algorithm and it helps some people decide
where to start.

I feel there are still plenty of interesting things to see in just
how people actually code it up.

James Edward Gray II

Jacob Fugal

10/13/2006 4:16:00 PM

0

On 10/13/06, Sander Land <sander.land@gmail.com> wrote:
> On 10/13/06, Jacob Fugal <lukfugl@gmail.com> wrote:
> > Actually, the basic algorithm he explained isn't quite A-star (I'm
> > guessing on purpose). There's lots of room for improvement in both
> > algorithm and heuristic. I'm guessing that's where the fun and variety
> > of this quiz will be. :)
> >
> > Jacob Fugal
>
> Isn't he just explaining a greedy search without backtracking?
> Also, this algorithm seems to go wrong even on the small map:

Pretty much, yes. Hoping it's not a spoiler, here's how you really do A*:

1) use a priority queue (prioritized by estimated cost)
2) initialize the queue with the start state(s)
3) while the queue is not empty
a) shift the head off the queue (cheapest state found so far)
b) return the path to the current state if the state is a goal state
b) expand that state by finding neighbors and calculating their costs
c) push each neighbor onto the queue
4) if the queue emptied without finding a solution, there is no solution

For the sake of both brevity and challenge, I've left some details out, such as:

* How do you prevent cycles and backtracking?
* How do you calculate costs for a new state?
* How do you manage your priority queue?
* How do you keep track of the path so you can return it when you hit a goal?

Happy hacking!

James Gray

10/13/2006 4:28:00 PM

0

On Oct 13, 2006, at 11:15 AM, Jacob Fugal wrote:

> Hoping it's not a spoiler, here's how you really do A*:
>
> 1) use a priority queue (prioritized by estimated cost)
> 2) initialize the queue with the start state(s)
> 3) while the queue is not empty
> a) shift the head off the queue (cheapest state found so far)
> b) return the path to the current state if the state is a goal state
> b) expand that state by finding neighbors and calculating their
> costs
> c) push each neighbor onto the queue
> 4) if the queue emptied without finding a solution, there is no
> solution

The priority queue is the major aspect not really touched on by the
quiz, yes. If you need help with this, a past Ruby Quiz about heaps
had code you could borrow:

http://www.rubyquiz.com/q...

Just be sure to read the summary where I fix a couple of bugs in the
code.

James Edward Gray II

Timothy Goddard

10/14/2006 12:30:00 AM

0

James Edward Gray II wrote:
> On Oct 13, 2006, at 11:15 AM, Jacob Fugal wrote:
>
> > Hoping it's not a spoiler, here's how you really do A*:
> >
> > 1) use a priority queue (prioritized by estimated cost)
> > 2) initialize the queue with the start state(s)
> > 3) while the queue is not empty
> > a) shift the head off the queue (cheapest state found so far)
> > b) return the path to the current state if the state is a goal state
> > b) expand that state by finding neighbors and calculating their
> > costs
> > c) push each neighbor onto the queue
> > 4) if the queue emptied without finding a solution, there is no
> > solution
>
> The priority queue is the major aspect not really touched on by the
> quiz, yes. If you need help with this, a past Ruby Quiz about heaps
> had code you could borrow:
>
> http://www.rubyquiz.com/q...
>
> Just be sure to read the summary where I fix a couple of bugs in the
> code.
>
> James Edward Gray II

My solution for last week's quiz used an A* search with a priority
queue if anybody wants to see some live code. The queue was, however,
designed for adding large numbers of new states in batches and would
need to be adapted.

By complete coincidence I've actually attempted something almost
identical to this before, attempting top move from any cell on the left
side to any cell on the right. I found that for larger grids an A*
search cell-by-cell becomes unacceptably slow.

I think the real challenge in this quiz will be forming intelligent
methods of reducing the number of states that must be searched. I never
actually did this for the left-to-right problem but have several ideas
for this quiz. Don't worry, they haven't given us the answers to the
real problems :)