The three rules of Ruby Q.:
Please do not post any solutions or spoiler discussion for this quiz
48 hours have passed from the time on this message.
Support Ruby Q. by submitting ideas as often as you can:
Suggestion: A [QUIZ] in the subject of emails about the problem helps
on Ruby T. follow the discussion. Please reply to the original quiz
if you can.
by Steven D.
The A* (A-Star) search algorithm is a path-finding algorithm with many
including Artificial Intelligence for games. The search builds the route
tile to tile until it reaches the goal. To help choose the best possible
the algorithm will use an equation that takes into account the distance
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 (*)
Step 2: Go through that list finding the cost of movement for each of
choice tiles. The cost of movement is the path cost so far, plus the
move to the tile being considered.
Our cost so far is 0, since we just started. The cost of a forest is 2
total cost of this move is 2 (0 + 2).
Step 3: Determine the distance from the choice tiles to the goal and
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
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: