{"id":747,"date":"2018-04-27T23:30:22","date_gmt":"2018-04-28T03:30:22","guid":{"rendered":"http:\/\/aristotle2digital.blogwyrm.com\/?p=747"},"modified":"2018-06-29T23:47:23","modified_gmt":"2018-06-30T03:47:23","slug":"a-cross-country-a","status":"publish","type":"post","link":"https:\/\/aristotle2digital.blogwyrm.com\/?p=747","title":{"rendered":"A Cross-Country A*"},"content":{"rendered":"
\nUpdate 6\/29\/18: Please note that there is an error in this post.\u00a0 There should be included in the reckoning of the cost of a space the total movement cost from the starting space to the space in question.\u00a0 Please consult the Tweaks and Kinks in the A*<\/a><\/em> post for details. <\/div>\n

Last month\u2019s column introduced and explored the basic A* algorithm within the cheeky context of a snake, a man, and a path to revenge.\u00a0 In this month\u2019s post, the algorithm is extended to include terrain costs that take into account that different types of spots may be more expensive to traverse based on their nature (e.g., mountain, river, forest, desert, etc.).\u00a0 As in the simpler case already studied, the A* seeks to find the shortest path between a starting point and the goal when the latter is known but the best way to travel is not.<\/p>\n

It is important to remember that at the core of the A* algorithm is the idea of an open spot.\u00a0 An open spot is a location adjacent to the current spot that the algorithm is visiting.\u00a0 From the vantage of the current spot, the neighboring spots can be examined and scored based on two criteria:\u00a0 the cost to move into that spot and a heuristic guess as to how far the spot is from the goal.\u00a0 These actions open the spot, which is placed on a list for future exploration.\u00a0 Once the A* has finished examining the neighborhood of the current spot, it closes that spot and selects the next spot to visit from among the lowest scoring spots on the list of open spots.\u00a0 By keeping pointers from open spots to the parent spots that opened them, the A* is able to back-track from the goal (once it has found it) to the beginning spot, thus determining the shortest path.\u00a0 The reader is encouraged to read the earlier post (An A* Drama<\/a><\/em>) for more details.<\/p>\n

As in the previous post, the material here is strongly influenced by Chapter 7 of AI for Game Developers<\/em>, by David M. Bourg and Glenn Seemann.<\/p>\n

This month\u2019s story begins with a wayfarer, who is journeying in the wilderness, looking for the shortest path home to his city.<\/p>\n

\"\"<\/a><\/p>\n

He weighs his options for path based not just on distance but on how well he can travel across each type of terrain. \u00a0\u00a0Normalizing his speed to the plain (blank of unfilled space), the wayfarer estimates that he can move 2 faster across the plain than through the forest, 5 times faster than crossing the water, 7 time faster than moving across the desert, and 10 times faster than climbing over the mountains.\u00a0 To evaluate his options he records his travel-time estimates and then lays a grid over his map to assist with his planning.<\/p>\n

\"\"<\/a><\/p>\n

The mountain range to his north-east lies in a direct, as-the-crow-flies path from his current location at grid point (4,2) to the city at (9,6), but taking this route may not be the most time-optimal approach.\u00a0 He starts looking for ways to go around rather than over the mountain range.<\/p>\n

By going through the desert to the east and south-east, he can head in roughly the \u2018right\u2019 direction and skirt the mountains completely, but the desert is not much cheaper than the mountains.\u00a0 He also considers going due north along the river course and then turning east in the forest, but a river trip is 5 times slower than in the plain.\u00a0 Finally he considers the possibility of going in the completely \u2018wrong\u2019 direction by heading to the south-west, where a ford allows him to cross the river on foot.\u00a0 Once on the other side, he can follow the flow upstream (to the north-east) until he enters the forest and can approach the city from the east.\u00a0 He scores these different possibilities and find that the last route is the cheapest.<\/p>\n

\"\"<\/a><\/p>\n

Given the same information, will the A* also find this over-the-river-and-through-the-woods path?<\/p>\n

The first step to answering this question is to add the terrain cost to the A* algorithm.\u00a0 This is done by simply using the time-scaling the wayfarer had already noted to the local score when a spot is opened.\u00a0 \u00a0\u00a0For example, when the search begins, the A* starts at (4,2) and opens the 8 locations surrounding that spot.\u00a0 Grid locations (4,3), (3,3), and (3,2) are assigned a local cost of 5 since they are river spots.\u00a0 The remaining five spots ((3,1), (4,1), (5,1), (5,2), and (5,3)) are assigned a local cost of 1 since they are plain spots.<\/p>\n

The heuristic scoring for the remaining cost is calculated as it was in the previous case as simply the as-the-crow-flies distance; that is to say that no regard is paid to terrain cost or even if the spot is available for traversal.\u00a0 It turns out that as long as all spots are scored on even footing with a common heuristic, the details of the scoring don\u2019t matter.<\/p>\n

\"\"<\/a><\/p>\n

Initially, the A* flirts with moving to the north-east since the local costs are low (being plains) and the total cost is low since the path is moving in the correct direction.\u00a0 But quickly, the A* loses interest in these paths since their score, once opened, places them near the bottom of the open list.<\/p>\n

After some exploration, the A* settles in on the path across the river, up along the western shore, through the forest to the north, and straight on to the east, thus bypassing the mountains and desert completely.<\/p>\n

\"\"<\/a><\/p>\n

At this point, the A*, can pick either (7,5) or (7,6) as the next spot with no penalty, since both take the same amount of time in this geometry.\u00a0 The selection for equally-scored spots is random so A* can meander a bit picking between any of the following paths:<\/p>\n