{"id":732,"date":"2018-03-30T23:30:37","date_gmt":"2018-03-31T03:30:37","guid":{"rendered":"http:\/\/aristotle2digital.blogwyrm.com\/?p=732"},"modified":"2018-06-29T23:46:31","modified_gmt":"2018-06-30T03:46:31","slug":"an-a-drama","status":"publish","type":"post","link":"https:\/\/aristotle2digital.blogwyrm.com\/?p=732","title":{"rendered":"An A* Drama"},"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

I suppose this blog post started first with some analysis I had decided to do on the A* algorithm and then it just grew from there.\u00a0 I had employed the A* algorithm on a scheduling problem some years back.\u00a0 This application was advocated by one of the developers on my team but I didn\u2019t have the time to properly learn it during development and deployment.\u00a0 I ended up using it as a black box with a silent vow to get around to learning it one of these days.<\/p>\n

Years passed, and my son was learning it as part of a course he was taking and I thought now was the time.\u00a0 So, I purchased AI for Game Developers<\/em>, by David M. Bourg and Glenn Seemann and dug into Chapter 7 entitled A* Pathfinding<\/em>.\u00a0 If you happen to read their book, you\u2019ll find that the approach is highly influenced by and patterned after their material.\u00a0 To my credit, I slogged through a complete example and then animated in a nice little video.\u00a0 If you are interested in that, it can be found at the bottom of this post.<\/p>\n

The premise of the A* algorithm is that the starting point and ending point for some sort of journey are known but that the specific path from A-to-B, as it were, is not.\u00a0 The personal picture I like to entertain is embarking on a car trip from New York to Los Angeles.\u00a0 I know where I am starting and I know where I am to finish, but should I drive through Pennsylvania or Maryland or further south?\u00a0 Does Kentucky figure into my route?\u00a0 What about Idaho?\u00a0 And so on.\u00a0 The hope is to find the shortest path that connects the start with the end with only a general notion of how far apart the two are.<\/p>\n

For simplicity, let\u2019s consider a much simpler problem of a snake trying to find the man who poked him while he dozed on a warm rock in the summer sun.<\/p>\n

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

Our slithering protagonist abstracts the terrain and lays down a grid, with himself starting at the grid point (4,2).\u00a0 He sees that the man is at the grid point (11,4) so he begins to formulate his revenge.\u00a0 However, being impatient to return to his sun-bathed nap our hero wants to dispatch the man as soon as possible.\u00a0 He needs the shortest path.\u00a0 Being mathematically minded and knowledgeable about algorithms, he decides on using the A* algorithm.<\/p>\n

The A* algorithm consists of the following steps:<\/p>\n

    \n
  1. Assume that the starting spot is open<\/li>\n
  2. Take a look around at the nearest neighbor spots<\/li>\n
  3. If they can be occupied, open them by\n
      \n
    1. Putting them on the open list for subsequent visit<\/li>\n
    2. Score them with a perceived cost to move onto them<\/li>\n
    3. Score them with an estimated cost representing how far they are from the destination square<\/li>\n
    4. Total the two scores to give a total cost for the spot<\/li>\n
    5. Assign a pointer from the open spot to the parent spot<\/li>\n<\/ol>\n<\/li>\n
    6. If they can\u2019t be occupied (e.g. the are boundaries or forbidden) ignore them<\/li>\n
    7. Close the starting spot<\/li>\n
    8. Pick the lowest cost open spot on the list (picking arbitrarily if there are ties)<\/li>\n
    9. Open and score any unopened spot<\/li>\n
    10. Close the spot and repeat<\/li>\n<\/ol>\n

      If one of the open spots is the destination spot, don\u2019t bother scoring it (i.e. give it a score of 0) and back-track from it to the start, following all the pointers. \u00a0The resulting path can then be traversed in the forward fashion.<\/p>\n

      For the simple example examined here, the perceived cost will be taken to be 1 for all possible spots, meaning the speed with which any spot can be crossed is the same.\u00a0 In general, spots own a terrain cost that may make it more or less expensive than neighboring spots (the difference between a highway and a surface street each with dramatically different speed limits).<\/p>\n

      The estimated cost is evaluated using a heuristic that counts the spots between the open spot and the final spot with no regard to barriers or terrain.<\/p>\n

      Returning to our intrepid reptile, his spot at (4,2) is now shaded blue, meaning it is in the process of being closed.\u00a0 He scores the spots at (3,2), (3,1), (4,1) and (5,1) and finds that the total costs are 9, 9, 8, and 7 respectively (the heuristic cost for (4,1) is 8 because it takes eight moves, horizontally, vertically, or diagonally to get to (11,4)).<\/p>\n

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

      Of the four spaces he has now opened, he selects (5,1) to next consider as its cost of 7 is the lowest of the bunch.\u00a0\u00a0 Spot (4,2) is now closed (shaded gray) and examining spot (5,1) then opens spots at (6,1) and (6,2).<\/p>\n

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

      Each of these has a score of 6 so he arbitrarily picks (6,1) to examine, opening the additional spots at (7,1) and (7,2).\u00a0 Again, he picks arbitrarily between these two spots, since both own a score of 5 and are the cheapest members of the open list.<\/p>\n

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

      His full adventure can be found in the video below, including a frame-by-frame look at just how he tries to put his revenge in motion.\u00a0 Spoiler:\u00a0 the man gets what\u2019s coming to him in the end.<\/p>\n

      \nhttp:\/\/aristotle2digital.blogwyrm.com\/wp-content\/uploads\/2018\/03\/Astar-Drama.mp4<\/a><\/video><\/div>\n","protected":false},"excerpt":{"rendered":"

      Update 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… Read more ><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-732","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts\/732","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=732"}],"version-history":[{"count":0,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=\/wp\/v2\/posts\/732\/revisions"}],"wp:attachment":[{"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=732"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=732"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/aristotle2digital.blogwyrm.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=732"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}