#+TITLE: Best practices for A* on grids #+OPTIONS: toc:nil author:t creator:nil num:nil #+AUTHOR: D. Chris Rayner #+EMAIL: [email protected] #+LATEX_HEADER: \usepackage[parfill]{parskip} #+LATEX_HEADER: \usepackage{comment} #+LATEX_HEADER: \usepackage{color,hyperref} #+LATEX_HEADER: \definecolor{darkblue}{rgb}{0.2,0.2,0.7} #+LATEX_HEADER: \hypersetup{colorlinks,breaklinks,linkcolor=darkblue,urlcolor=darkblue,anchorcolor=darkblue,citecolor=darkblue} #+LATEX_HEADER: \usepackage{textgreek} #+LATEX_CLASS: article #+LATEX_CLASS_OPTIONS: [koma,utopia,12pt,microtype,paralist]

#+begin_export latex \begin{comment} #+end_export [[https://github.com/riscy/a_star_on_grids/actions][https://github.com/riscy/a_star_on_grids/workflows/test/badge.svg]] [[https://github.com/riscy/a_star_on_grids/raw/master/pdf/a_star_on_grids.pdf][https://img.shields.io/badge/download-pdf-orange.svg]] [[https://img.shields.io/badge/version-20180602-blue.svg]]

[[file:img/grid.png]]

http://www.veryicon.com/icons/system/icons8-metro-style/timeline-list-grid-grid.html

#+begin_export latex \end{comment} #+end_export

• Table of Contents :TOC_3_gh:noexport:

• [[#description][Description]]
• [[#preliminaries][Preliminaries]]
• [[#move-costs][Move costs]]
  • [[#avoid-floating-point-arithmetic][Avoid floating point arithmetic]]
  • [[#avoid-same-cost-diagonal-and-cardinal-moves][Avoid same-cost diagonal and cardinal moves]]
  • [[#validate-your-move-costs][Validate your move costs]]
  • [[#use-high-performing-move-costs][Use high-performing move costs]]
• [[#heuristics][Heuristics]]
  • [[#use-a-non-overestimating-heuristic][Use a non-overestimating heuristic]]
  • [[#use-manhattan-distance-on-a-4-connected-grid][Use Manhattan distance on a 4-connected grid]]
  • [[#use-octile-distance-on-an-8-connected-grid][Use octile distance on an 8-connected grid]]
  • [[#scale-your-heuristics-up][Scale your heuristics up]]
• [[#algorithmic-details][Algorithmic details]]
  • [[#break-ties-in-favor-of-path-depth][Break ties in favor of path depth]]
  • [[#avoid-recomputing-heuristics][Avoid recomputing heuristics]]
  • [[#know-whether-to-use-a-heap][Know whether to use a heap]]
  • [[#consider-fringe-search][Consider Fringe Search]]
• [[#implementation][Implementation]]
  • [[#maintain-two-pathfinders][Maintain two pathfinders]]
  • [[#choose-the-right-language][Choose the right language]]
  • [[#pack-your-data-structures][Pack your data structures]]
• [[#additional-resources][Additional resources]]
• [[#contributing-and-citing][Contributing and citing]]

• Description This document describes ways to improve an A* implementation, focusing on pathfinding in four- and eight-connected grids. It's pitched at hobbyists and anyone looking for ways to make existing code a bit faster.

  Some accompanying [[https://github.com/riscy/a_star_on_grids/tree/master/src][example code]] is available in C++.

• Preliminaries Forgoing a complete description, recall that A* is essentially a loop that expands a list of /open/ states that reach toward a goal state. Each iteration of the A* loop expands the /open list/ with the neighbors of a state already on the open list. The open state ~i~ that gets chosen is one with the lowest ~f~ value: #+begin_src ruby f_i = g_i + h_i #+end_src which is an estimate of the cost of a path going through ~i~ and continuing to the goal. Here ~g_i~ is the cost of the cheapest path to state ~i~ that A* has generated so far, and ~h_i~ is an efficiently computed /heuristic estimate/ for the cost to get from ~i~ to the goal.

  (For further detail, visit the resources at the end of the document.)

• Move costs On an 8-connected grid, the cost of a single diagonal move (~D~) relative to the cost of a cardinal move (~C~) not only affects the appearance of the paths A* generates, but can also affect its efficiency. ** Avoid floating point arithmetic Prefer integral data types wherever possible. This is not only faster but helps to avoid the numerical imprecision that can confuse debugging attempts. ** Avoid same-cost diagonal and cardinal moves When the entity can move cardinally /or/ diagonally once per time-step, the instinct is to tell A* that cardinal and diagonal moves cost the same (e.g., ~C = D = 1~). While technically true, this increases the number of unique optimal paths across the grid; A* is more efficient when it has fewer options.

  (Note if you're computing many paths at once via a shortest path tree, for instance using Dijkstra's algorithm, then same-cost diagonal and cardinal moves can be beneficial since you can just use a simple [[https://en.wikipedia.org/wiki/Breadth-first_search][BFS]].) ** Validate your move costs ~Ensure C < D < 2C~. If a diagonal move costs /less/ than a cardinal move, A* prefers zigzagging paths. If a diagonal move costs more than /two/ cardinal moves, A* prefers rectilinear paths like you'd see on a 4-connected grid. Paths tend to look best when the costs lie between these two extremes. ** Use high-performing move costs The following cost structures work well in practice. Results can vary depending on the obstacles in the grid, so test before using.

  • ~D = 99~, ~C = 70~ :: If you prefer a diagonal move to cost ~sqrt(2)~ relative to a cardinal move, try ~D = 99~ and ~C = 70~. This close approximation helps to avoid floating point arithmetic.
  • ~D = 3~, ~C = 2~ :: This is still close to a ~D/C~ ratio of ~sqrt(2)~ and remains integral. Moreover, if ~h_i~ is admissible but non-integral for whatever reason, then its [[https://en.wikipedia.org/wiki/Floor_and_ceiling_functions][ceiling]] is admissible and can be used instead. Nathan Sturtevant showed me this when we wrote [[http://www.aaai.org/ocs/index.php/AAAI/AAAI11/paper/viewFile/3594/3821][Euclidean Heuristic Optimization]] (Rayner, Bowling, Sturtevant), and it made a noticeable difference.
  • ~D = 99~, ~C = 50~ :: This gives something close to rectilinear costs but retains a preference for diagonal moves over pairs of cardinal moves. On average this keeps the size of the open list smaller, but it can also increase state expansions. Usually it is noticeably faster.

• Heuristics Here are some tips on selecting a good heuristic. I frequently see these details missed on many first implementations of A*. ** Use a non-overestimating heuristic Heuristics that don't overestimate are called /admissible/. A* recovers an optimal (cheapest) path when its heuristic is admissible. A good, admissible grid heuristic is the "distance" between two states assuming no obstacles. ** Use Manhattan distance on a 4-connected grid The distance between two states on a 4-connected grid, assuming no obstacles, is the Manhattan (or L1-norm or rectilinear) distance: #+begin_src ruby h_i = C * (Δx + Δy) #+end_src where ~Δx~ and ~Δy~ are absolute distances between ~i~ and the goal along the ~x~ and ~y~ axes and ~C~ is the cost to take a cardinal move, which may as well be ~1~. ** Use octile distance on an 8-connected grid When pathfinding on an 8-connected grid, use the octile heuristic: #+begin_src ruby h_i = C * Δx + B * Δy if Δx > Δy C * Δy + B * Δx else #+end_src where ~B = D - C~ with ~C~ being the cost to take a cardinal move and ~D~ being the cost to take a diagonal move.

  Note the octile heuristic can be written without a conditional (albeit with an absolute value), which may help improve instruction level parallelism: #+begin_src ruby h_i = (E * abs(Δx - Δy) + D * (Δx + Δy)) / 2 #+end_src where ~E = 2 * C - D~. You can see how this simplifies further, without floating point arithmetic, if ~D~ (and therefore ~E~) is even.

  A proof for this relies on using a 45-degree rotation matrix to

  turn what is effectively a norm in Linfty into a norm in L1 space.

  • See an [[https://github.com/riscy/a_star_on_grids/blob/master/src/heuristics.cpp#L59][example implementation of the octile heuristic]]
  • See an [[https://github.com/riscy/a_star_on_grids/blob/master/src/heuristics.cpp#L67][example implementation of the non-branching octile heuristic]] ** Scale your heuristics up Once you've selected a good heuristic, try multiplying all of the values it gives you by a constant ~K > 1~ (e.g. ~10~). This simple change yields an algorithm called Weighted A*, which significantly improves run-time at the cost of small suboptimalities in your paths.

  See an [[https://github.com/riscy/a_star_on_grids/blob/master/src/heuristics.cpp#L74][example implementation of a weighted octile heuristic]].

• Algorithmic details Some details that tend not to come up in textbook descriptions of A*. ** Break ties in favor of path depth It is common for more than one state on the open list to have the lowest ~f~ cost. When this is the case it's better to make A* focus on deep solutions rather than a breadth of shallow solutions by tie-breaking on larger ~g~ values. My Ph.D. co-supervisor Nathan Sturtevant created [[http://movingai.com/astar.html][a video demonstration]].

  See [[https://github.com/riscy/a_star_on_grids/blob/master/src/node_heap.h#L9][example tiebreaking code]]. ** Avoid recomputing heuristics To help keep the open list sorted, an implementation of A* might store the ~f_i~ and ~g_i~ values for every open state ~i~. And since ~f_i = g_i + h_i~, the value of ~h_i~ can always be recovered as ~h_i = f_i - g_i~ for any open state ~i~. Using these stored values (a form of [[https://en.wikipedia.org/wiki/Memoization][memoization]]) can be less expensive than recomputing ~h_i~.

  For instance, suppose ~i~ is on the open list with ~f~ and ~g~ values of ~f_current~ and ~g_current~. Then A* iterates to a cheaper path to ~i~ with a cost of ~g_new~. The corresponding value ~f_new~ can be determined /without/ making another call to the heuristic function: #+begin_src ruby f_new = g_new + f_current - g_current #+end_src

  See [[https://github.com/riscy/a_star_on_grids/blob/master/src/algorithms.cpp#L119][an example of using memoized heuristics]]. ** Know whether to use a heap On larger grids with complex obstacles, implementing your open list as a binary heap (preferably on top of an array) can lead to dramatic performance gains. This is why it's generally considered a best practice to do so.

  But heaps can hurt. On smaller grids with few obstacles, a linear scan of the entire open list can be much faster, especially if your implementation is written in a low-level language like C++.

  • See an [[https://github.com/riscy/a_star_on_grids/blob/master/src/algorithms.cpp#L38][A* implementation that uses an array]]
  • See an [[https://github.com/riscy/a_star_on_grids/blob/master/src/algorithms.cpp#L90][A* implementation that uses a heap]]
  • See an [[https://github.com/riscy/a_star_on_grids/blob/master/src/node_heap.h][example heap implementation]] ** Consider Fringe Search [[https://en.wikipedia.org/wiki/Fringe_search][Fringe Search]] is a close cousin of A* that takes a different approach to growing and maintaining the open list. Just about all of the points in this document apply to Fringe Search, such as choosing a good heuristic, the choice of diagonal vs. cardinal move costs, and using memoized heuristic values.

  With compiler optimizations on, I found Fringe Search to be slower than A*, albeit only if the methods in this document are applied. But with compiler optimizations off, Fringe Search can be faster than A*. It's reasonable to /predict/ Fringe Search may be the faster choice in interpreted scripting languages.

  See [[https://github.com/riscy/a_star_on_grids/blob/master/src/algorithms.cpp#L140][an example Fringe Search implementation]].

• Implementation The following are some tips on the actual implementation of your pathfinder. ** Maintain two pathfinders During development you'll be constantly changing and refactoring your code. This can be dangerous -- it is surprisingly easy to write a pathfinder that seems to work but has an invisible bug that isn't obvious until much later.

  To prevent this you should write tested code: write a simple but /correct/ pathinder and use it to test your production pathfinder. For example, if you're finding optimal paths, both your simple pathfinder and your optimized pathfinder should return solutions of the same length, even if they visit different states. ** Choose the right language You'll get huge speed gains by writing your pathfinder in a compiled system-level language like C, or C++, or Rust.

  If you're using a high-level scripting language, you're not necessarily out of luck. If you're using Python, for example, you could look into compiling your pathfinding module with [[http://cython.readthedocs.io/en/latest/src/tutorial/cython_tutorial.html][Cython]] -- it's surprisingly easy to do. ** Pack your data structures If you're coding in a low-level language like C, C++, or Rust, be aware of the effects of structure packing -- /especially/ if you're using an explicit graph to represent a large search space.

  If you're using ~gcc~, for example, try giving your compiler the ~-Wpadded~ argument and see how much it whines about having to pad your data structures with extra bytes. Eric Raymond has a [[http://www.catb.org/esr/structure-packing/][great writeup]] on this topic.

• Additional resources

  • [[https://en.wikipedia.org/wiki/A*_search_algorithm][A* on Wikipedia]] :: Wikipedia gives a thorough description of A*.
  • [[http://movingai.com][Nathan Sturtevant's movingai.com]] :: Benchmark problems, tutorials, and videos covering fundamental and advanced topics.
  • [[http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps][Dijkstra Maps]] :: Dijkstra Maps have also been called "differential heuristics", "ALT heuristics", or "Lipschitz embeddings". We looked at smart ways to set these heuristics up in [[https://webdocs.cs.ualberta.ca/~bowling/papers/13ijcai-hsubset.pdf][Subset Selection of Search Heuristics]] (Rayner, Sturtevant, Bowling) but this article describes some extremely novel ways to use these mappings to control game entities.
  • [[http://theory.stanford.edu/~amitp/GameProgramming/Variations.html][Amit Patel's variants of A*]] :: A listing of some alternatives to A*.

• Contributing and citing If you have any corrections or contributions -- both much appreciated -- feel free to get in touch or simply make a pull request.

  If for any reason you want to cite this document, use the following: #+begin_src bibtex @manual{Rayner2017BestPracticesGrids, author = {D. Chris Rayner}, title = {{Best practices for A* on grids}}, year = 2018 } #+end_src