{"id":111,"date":"2022-01-23T22:04:44","date_gmt":"2022-01-23T22:04:44","guid":{"rendered":"https:\/\/timallanwheeler.com\/blog\/?p=111"},"modified":"2022-01-23T22:04:44","modified_gmt":"2022-01-23T22:04:44","slug":"sokoban-reach-and-code-performance","status":"publish","type":"post","link":"https:\/\/timallanwheeler.com\/blog\/2022\/01\/23\/sokoban-reach-and-code-performance\/","title":{"rendered":"Sokoban Reach and Code Performance"},"content":{"rendered":"\n<p>In my previous post, I covered some basic Sokoban search algorithms and some learnings from my digging into <a href=\"http:\/\/sokobano.de\/wiki\/index.php?title=Sokoban_solver_%22scribbles%22_by_Brian_Damgaard_about_the_YASS_solver\">YASS (Yet Another Sokoban Solver)<\/a>. I covered the problem representation but glossed over how we determine the pushes available to us in a given board state. In this post, I cover how we calculate that and then conduct into a bunch of little efficiency investigations.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"250\" height=\"200\" src=\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2022\/01\/moves.gif\" alt=\"\" class=\"wp-image-117\"\/><figcaption>A push-optimal solution to a Sokoban puzzle<\/figcaption><\/figure><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Set of Actions<\/h2>\n\n\n\n<p>We are trying to find push-optimal solutions to Sokoban problems. That is, we are trying to get every box on a box in the fewest number of pushes possible. As such, the actions available to us each round are the set of pushes that our player can conduct from their present position:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"250\" height=\"200\" src=\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2022\/01\/spiffy_moves.png\" alt=\"\" class=\"wp-image-112\"\/><figcaption>The set of pushes the player (red star) can conduct from their present position<\/figcaption><\/figure><\/div>\n\n\n\n<p>Our Sokoban solver will need to calculate the set of available pushes in every state. As such, we end up calculating the pushes a lot, and the more efficient we are at it, the faster we can conduct our search.<\/p>\n\n\n\n<p>A push is valid if:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>our player can reach a tile adjacent to the block from their current position<\/li><li>the tile opposite the player, on the other side of the block, is free<\/li><\/ul>\n\n\n\n<p>As such, player reachability is crucial to the push calculation.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"250\" height=\"200\" src=\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2022\/01\/spiffy_reachability.png\" alt=\"\" class=\"wp-image-113\"\/><figcaption>Reachablity for the same game state as the previous image. Red tiles are player-reachable, and green tiles are reachable boxes.<\/figcaption><\/figure><\/div>\n\n\n\n<p>Above we see the tiles reachable from the player&#8217;s position (red) and the boxes adjacent to player-reachable tiles. This view is effectively the output of our reachability calculation.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Efficient Reach Calculations<\/h2>\n\n\n\n<p>The set of reachable tiles can be found with a simple flood-fill starting from the player&#8217;s starting location. We don&#8217;t care about the shortest distance, just reachability, so this can be achieved with either a breadth-first or a depth-first traversal:<\/p>\n\n\n\n<figure class=\"wp-block-gallery aligncenter columns-2 is-cropped wp-block-gallery-1 is-layout-flex wp-block-gallery-is-layout-flex\"><ul class=\"blocks-gallery-grid\"><li class=\"blocks-gallery-item\"><figure><img loading=\"lazy\" decoding=\"async\" width=\"250\" height=\"200\" src=\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2022\/01\/reaches_bfs-1.gif\" alt=\"\" data-id=\"121\" data-link=\"https:\/\/timallanwheeler.com\/blog\/?attachment_id=121#main\" class=\"wp-image-121\"\/><\/figure><\/li><li class=\"blocks-gallery-item\"><figure><img loading=\"lazy\" decoding=\"async\" width=\"250\" height=\"200\" src=\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2022\/01\/reaches_dfs-1.gif\" alt=\"\" data-id=\"122\" data-full-url=\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2022\/01\/reaches_dfs-1.gif\" data-link=\"https:\/\/timallanwheeler.com\/blog\/?attachment_id=122#main\" class=\"wp-image-122\"\/><\/figure><\/li><\/ul><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\">Naive Reach Calculation<\/h3>\n\n\n\n<p>Let&#8217;s look at a naive Julia implementation using depth-first traversal:<\/p>\n\n\n\n<pre lang=\"julia\">function calc_reachable_tiles(game::Game, board::Board, \u25a1_start::TileIndex)\n   min_reachable_tile = \u25a1_start\n   reachable_tiles = Set{TileIndex}()\n   reachable_boxes = Set{TileIndex}()\n   to_visit = TileIndex[]\n\n   push!(reachable_tiles, \u25a1_start)\n   push!(to_visit, \u25a1_start)\n\n   while !isempty(to_visit)\n      # pop stack\n      \u25a1 = pop!(to_visit)\n\n      # Examine tile neighbors\n      for dir in DIRECTIONS\n         \u25a9 = \u25a1 + game.step_fore[dir]\n         if ((board[\u25a9] & WALL) == 0) && (\u25a9 \u2209 reachable_tiles)\n            if ((board[\u25a9] & BOX) == 0)\n                push!(to_visit, \u25a9)\n                push!(reachable_tiles, \u25a9)\n                min_reachable_tile = min(min_reachable_tile, \u25a1_start)\n            else\n                push!(reachable_boxes, \u25a9)\n            end\n         end\n      end\n   end\n\n   return (reachable_tiles, reachable_boxes, min_reachable_tile)\nend<\/pre>\n\n\n\n<p>This code is somewhat inefficient, most notably in that it allocates sets for both <code>reachable_tiles<\/code> and <code>reachable_boxes<\/code>, which change in size during its execution. (We also compute the minimum reachable tile, for use in state hashing, as explained in <a href=\"https:\/\/timallanwheeler.com\/blog\/2022\/01\/19\/basic-search-algorithms-on-sokoban\/\">the previous post<\/a>.) Let&#8217;s evaluate its runtime on this large puzzle:<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2022\/01\/image.png\" alt=\"\" class=\"wp-image-124\" width=\"297\" height=\"264\" srcset=\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2022\/01\/image.png 675w, https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2022\/01\/image-300x267.png 300w\" sizes=\"auto, (max-width: 297px) 100vw, 297px\" \/><figcaption>A large test puzzle based on Sasquatch 49. All tiles are initially reachable<\/figcaption><\/figure><\/div>\n\n\n\n<p>Using <code>@btime<\/code> from <a href=\"https:\/\/juliaci.github.io\/BenchmarkTools.jl\/stable\/\">BenchmarkTools.jl<\/a>, we get <code>15.101 \u03bcs (28 allocations: 9.72 KiB)<\/code>. Honestly, 15 microseconds is actually quite good &#8211; much better than I expected from a naive implementation. That being said, let&#8217;s see if we can do better.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">YASS Reach Calculation with Preallocated Memory<\/h3>\n\n\n\n<p>I spent a fair amount of time investigating YASS, which was written in Pascal. The Pascal code was structured differently than most of the code bases I&#8217;ve worked with. The working memory is declared and allocated at the top of the file in a global space, and is then used throughout. This preallocation makes it incredibly efficient. (As an aside, it was quite difficult to tell where variables were defined, since the naming conventions didn&#8217;t make it clear what was declared locally and what was global, and Pascal scoping really threw me into a loop). I feel that a lot of modern programming gets away with assuming we have a lot of memory, and is totally fine with paying the performance cost. However, in tight inner loops like this reach calculation, which might run many hundreds of thousands of times, we care enough about performance to pay special attention.<\/p>\n\n\n\n<p>The <a href=\"https:\/\/docs.julialang.org\/en\/v1\/manual\/performance-tips\/\">Julia performance tips<\/a> specifically call out paying attention to memory allocations. The previous code allocated 9.72 KiB. Let&#8217;s try to knock that down.<\/p>\n\n\n\n<p>We&#8217;ll start by defining a struct that holds our preallocated memory. Rather than keeping lists or sets of player-reachable tiles and boxes, we&#8217;ll instead store a single flat array of tiles the same length as the board. This representation lets us just flag a given tile as a player-reachable tile or a player-reachable box:<\/p>\n\n\n\n<pre lang=\"julia\">mutable struct ReachableTiles\n    # The minimum (top-left) reachable tile. Used as a normalized player position\n    min_reachable_tile::TileIndex \n    # Incremented by 2 in each reach calculation\n    # The player-reachable tiles have the value 'calc_counter'\n    # Tiles with neighboring boxes have the value 'calc_counter' + 1\n    # Non-floor tiles are set to typemax(UInt32)\n    calc_counter::UInt32\n    tiles::Vector{UInt32}\nend<\/pre>\n\n\n\n<p>This data structure lets us store everything we care about, and does not require clearing between calls (only once we get to wraparound). We just increment a counter and overwrite our memory with every call.<\/p>\n\n\n\n<pre lang=\"julia\">is_reachable(\u25a1::Integer, reach::ReachableTiles) = reach.tiles[\u25a1] == reach.calc_counter\nis_reachable_box(\u25a1::Integer, reach::ReachableTiles) = reach.tiles[\u25a1] == reach.calc_counter + 1<\/pre>\n\n\n\n<p>The reachability calculation from before can now be modified to update our <code>ReachableTiles<\/code> struct:<\/p>\n\n\n\n<pre lang=\"julia\">function calc_reachable_tiles!(\n    reach::ReachableTiles,\n    game::Game,\n    board::Board,\n    \u25a1_start::TileIndex,\n    stack::Vector{TileIndex}\n  )::Int\n    \n    # The calc counter wraps around when the upper bound is reached\n    if reach.calc_counter \u2265 typemax(UInt32) - 2\n        clear!(reach, board)\n    end\n\n    reach.calc_counter += 2\n    reach.min_reachable_tile = \u25a1_start\n    reach.tiles[\u25a1_start] = reach.calc_counter\n    n_reachable_tiles = 1\n\n    # depth-first search uses a stack\n    stack[1] = \u25a1_start\n    stack_hi = 1 # index of most recently pushed item\n\n    # stack contains items as long as stack_hi > 0\n    while stack_hi > 0\n        # pop stack\n        \u25a1 = stack[stack_hi]\n        stack_hi -= 1\n\n        # Examine tile neighbors\n        for dir in DIRECTIONS\n            \u25a9 = \u25a1 + game.step_fore[dir]\n            if reach.tiles[\u25a9] < reach.calc_counter\n                # An unvisited floor tile, possibly with a box\n                # (non-floors are typemax ReachabilityCount)\n                if (board[\u25a9] &#038; BOX) == 0 # not a box\n                    n_reachable_tiles += 1\n                    # push the square to the stack\n                    stack_hi += 1\n                    stack[stack_hi] = \u25a9\n                    reach.tiles[\u25a9] = reach.calc_counter\n                    reach.min_reachable_tile = min(\u25a9, reach.min_reachable_tile)\n                else\n                    # a box\n                    reach.tiles[\u25a9] = reach.calc_counter + 1\n                end\n            end\n        end\n    end\n\n    reach.calculated = true\n    return n_reachable_tiles\nend<\/pre>\n\n\n\n<p>This time, <code>@btime<\/code> gives us <code>2.490 \u03bcs (2 allocations: 224 bytes)<\/code>, which is about 6x faster and a massive reduction in allocations.<\/p>\n\n\n\n<p>I was particularly pleased by the use of the <code>stack<\/code> memory passed into this method. Our depth-first traversal has to keep track of tiles that need to be expanded. The code uses a simple vector to store the stack, with just a single index variable <code>stack_hi<\/code> that points to the most recently pushed tile. We know that we will never have more items in the stack than tiles on our board, so <code>stack<\/code> can simply be the same length as our board. When we push, we increment <code>stack_hi<\/code> and place our item there. When we pop, we  grab our item from <code>stack[stack_hi]<\/code> and then decrement. I loved the elegance of this when I discovered it. Nothing magic or anything, just satisfyingly clean and simple.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Avoiding Base.iterate<\/h3>\n\n\n\n<p>After memory allocations, the other thing common culprit of inefficient Julia code is a variable with an uncertain \/ wavering type. At the end of the day, everything ends up as assembly code that has to crunch real bytes in the CPU, so any variable that can be multiple things necessarily has to be treated in multiple ways, resulting in less efficient code.<\/p>\n\n\n\n<p>Julia provides a <a href=\"https:\/\/docs.julialang.org\/en\/v1\/stdlib\/InteractiveUtils\/#InteractiveUtils.@code_warntype\"><code>@code_warntype<\/code><\/a> macro that lets one look at a method to see if anything has a changing type. I ran it on the implementation above and was surprised to see an internal variable with a union type, <code>@_9::Union{Nothing, Tuple{UInt8, UInt8}}<\/code>. <\/p>\n\n\n\n<p>It turns out that <code>for dir in DIRECTIONS<\/code> is calling <code><a href=\"https:\/\/docs.julialang.org\/en\/v1\/manual\/interfaces\/\">Base.iterate<\/a><\/code>, which returns either a tuple of the first item and initial state or nothing if empty. I was naively thinking that because <code>DIRECTIONS<\/code> was just <code>0x00:0x03<\/code> that this would be handled more efficiently. Anyways, I was able to avoid this call by using a while loop:<\/p>\n\n\n\n<pre lang=\"julia\">dir = DIR_UP\nwhile dir <= DIR_RIGHT\n    ...\n    dir += 0x01\nend<\/pre>\n\n\n\n<p>That change drops us down to <code>1.989 \u03bcs (2 allocations: 224 bytes)<\/code>, which is now about 7.5x faster than the original code. Not bad!<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Graph-Based Board Representation<\/h3>\n\n\n\n<p>Finally, I wanted to try out a different board representation. The code about stores the board, a 2d grid, as a flat array. To move left we decrement our index, to move right we increment our index, and to move up or down we change by our row length.<\/p>\n\n\n\n<p>I looked into changing the board to only store the non-wall tiles and represent it as a graph. That is, have a flat list of floor tiles and for every tile and every direction, store the index of its neighbor in that direction, or zero otherwise:<\/p>\n\n\n\n<pre lang=\"julia\">struct BoardGraph\n    # List of tile values, one for each node\n    tiles::Tiles\n\n    # Index of the tile neighbor for each tile.\n    # A value of 0 means that edge is invalid.\n    neighbors::Matrix{TileIndex} # tile index \u00d7 direction\nend<\/pre>\n\n\n\n<p>This form has the advantage of a smaller memory footprint. By dropping the wall tiles we can use about half the space. Traversal between tiles should be about as expensive as before.<\/p>\n\n\n\n<p>The reach calculation looks more or less identical.  As we'd expect, the performance is close to the same too: <code>2.314 \u03bcs (4 allocations: 256 bytes)<\/code>. There is some slight inefficiency, perhaps because memory lookup is not as predictable, but I don't really know for sure. Evenly structured grid data is a nice thing!<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Pushes<\/h2>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"250\" height=\"200\" src=\"https:\/\/timallanwheeler.com\/blog\/wp-content\/uploads\/2022\/01\/spiffy_moves.png\" alt=\"\" class=\"wp-image-112\"\/><\/figure><\/div>\n\n\n\n<p>Once we've done our reachable tiles calculation, we need to use it to compute our pushes. The naive way is to just iterate over our boxes and append to a vector of pushes:<\/p>\n\n\n\n<pre lang=\"julia\">function get_pushes(game::Game, s::State, reach::ReachableTiles)\n    pushes = Push[]\n    for (box_number, \u25a1) in enumerate(s.boxes)\n        if is_reachable_box(\u25a1, reach)\n            # Get a move for each direction we can get at it from,\n            # provided that the opposing side is clear.\n            for dir in DIRECTIONS\n                \u25a1_dest = \u25a1 + game.step_fore[dir] # Destination tile\n                \u25a1_player = \u25a1 - game.step_fore[dir] # Side of the player\n                # If we can reach the player's pos and the destination is clear.\n                if is_reachable(\u25a1_player, reach) && ((s.board[\u25a1_dest] & (FLOOR+BOX)) == FLOOR)\n                    push!(pushes, Push(box_number, dir))\n                end\n            end\n        end\n    end\n    return pushes\nend<\/pre>\n\n\n\n<p>We can of course modify this to use preallocated memory. In this case, we pass in a vector pushes. The most pushes we could have is four times the number of boxes. We allocate that much and have the method return the actual number of boxes:<\/p>\n\n\n\n<pre lang=\"julia\">function get_pushes!(pushes::Vector{Push}, game::Game, s::State, reach::ReachableTiles)::Int\n    n_pushes = 0\n    for (box_number, \u25a1) in enumerate(s.boxes)\n        if is_reachable_box(\u25a1, reach)\n            # Get a move for each direction we can get at it from,\n            # provided that the opposing side is clear.\n            for dir in DIRECTIONS\n                \u25a1_dest = \u25a1 + game.step_fore[dir] # Destination tile\n                \u25a1_player = \u25a1 - game.step_fore[dir] # Side of the player\n                # If we can reach the player's pos and the destination is clear.\n                if is_reachable(\u25a1_player, reach) && ((s.board[\u25a1_dest] & (FLOOR+BOX)) == FLOOR)\n                    n_pushes += 1\n                    pushes[n_pushes] = Push(box_number, dir)\n                end\n            end\n        end\n    end\n    return n_pushes\nend<\/pre>\n\n\n\n<p>Easy! This lets us write solver code that looks like this:<\/p>\n\n\n\n<pre lang=\"julia\">n_pushes = get_pushes!(pushes, game, s, reach)\nfor push_index in 1:n_pushes\n    push = pushes[push_index]\n    ...\nend<\/pre>\n\n\n\n<p>An alternative is to do something similar to <code>Base.iterate<\/code> and generate the next push given the previous push:<\/p>\n\n\n\n<pre lang=\"julia\">\"\"\"\nGiven a push, produces the next valid push, with pushes ordered\nby box_index and then by direction.\nThe first valid push can be obtained by passing in a box index of 1 and direction 0x00.\nIf there no valid next push, a push with box index 0 is returned.\n\"\"\"\nfunction get_next_push!(\n    game::Game,\n    s::State,\n    reach::ReachableTiles,\n    push::Push = Push(1, 0)\n  )\n    box_index = push.box_index\n    dir = push.dir\n    while box_index \u2264 length(s.boxes)\n        \u25a1 = s.boxes[box_index]\n        if is_reachable_box(\u25a1, reach)\n            # Get a move for each direction we can get at it from,\n            # provided that the opposing side is clear.\n            while dir < N_DIRS\n                dir += one(Direction)\n                \u25a1_dest = game.board_start.neighbors[\u25a1, dir]\n                \u25a1_player = game.board_start.neighbors[\u25a1, OPPOSITE_DIRECTION[dir]]\n                # If we can reach the player's pos and the destination is clear.\n                if \u25a1_dest > 0 && \n                   \u25a1_player > 0 &&\n                   is_reachable(\u25a1_player, reach) &&\n                   not_set(s.tiles[\u25a1_dest], BOX)\n                    return Push(box_index, dir)\n                end\n            end\n        end\n\n        # Reset\n        dir = 0x00\n        box_index += one(BoxIndex)\n    end\n\n    # No next push\n    return Push(0, 0)\nend<\/pre>\n\n\n\n<p>We can then use it as follows, without the need to preallocate a list of pushes:<\/p>\n\n\n\n<pre lang=\"julia\">push = get_next_push!(game, s, reach)\nwhile push.box_index > 0\n    ...\n    push = get_next_push!(game, s, reach, push)\nend<\/pre>\n\n\n\n<p>Both this code and the preallocated <code>pushes<\/code> approach are a little annoying, in a similar what that changing <code>for dir in DIRECTIONS<\/code> to a while loop is annoying. They uses up more lines than necessary and thus makes the code harder to read. That being said, these approaches are more efficient. Here are solve times using A* with all three methods on Sasquatch 02:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>naive: 17.200 \u03bcs<\/li><li>Preallocated pushes: 16.480 \u03bcs<\/li><li>iterator: 15.049 \u03bcs<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Conclusion<\/h2>\n\n\n\n<p>This post thoroughly covered how to compute the player-reachable tiles and player-reachable boxes for a given Sokoban board. Furthermore, we used this reachability to compute the valid pushes. We need the pushes in every state, so we end up computing both many times during a solver run.<\/p>\n\n\n\n<p>I am surprised to say that my biggest takeaway is actually that premature optimization is the root of all evil. I had started this Sokoban project keen on figuring out how YASS could solve large Sokoban problems as effectively as possible. I spent a lot of time learning about its memory representations and using efficient preallocated memory implementations for the Julia solver. <\/p>\n\n\n\n<p>I would never have guessed that the difference between a naive implementation and an optimized implementation for the reach calculation would merely yield a 7.5x improvement. Furthermore, I would never have thought that the naive implementation for getting the pushes would be basically the same as using a preallocated vector. There are improvements, yes, but it really goes to show that these improvements are really only worth it if you really measure your code and really need that speed boost. The sunk development time and the added code complexity is simply not worth it for a lot of everyday uses.<\/p>\n\n\n\n<p>So far, the search algorithm used has had a far bigger impact on solver performance than memory allocation \/ code efficiencies. In some ways that makes me happy, as algorithms represent \"how we go about something\" and the memory allocation \/ efficiencies are more along the lines of implementation details.<\/p>\n\n\n\n<p>As always, programmers need to use good judgement, and should look at objective data.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In my previous post, I covered some basic Sokoban search algorithms and some learnings from my digging into YASS (Yet Another Sokoban Solver). I covered the problem representation but glossed over how we determine the pushes available to us in a given board state. In this post, I cover how we calculate that and then [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[3],"class_list":["post-111","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-sokoban"],"_links":{"self":[{"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/posts\/111","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/comments?post=111"}],"version-history":[{"count":17,"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/posts\/111\/revisions"}],"predecessor-version":[{"id":137,"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/posts\/111\/revisions\/137"}],"wp:attachment":[{"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/media?parent=111"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/categories?post=111"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/timallanwheeler.com\/blog\/wp-json\/wp\/v2\/tags?post=111"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}