The path does not reach the end node in my A* algorithm

Question

Following on from How to speed up least-cost path model at large spatial extents, I tried to code an A* algorithm in Netlogo to increase my least-cost path model at large spatial extents. Here is my code:

to findPath [ID-start-node ID-end-node]

 let currentNodesInList [ ]
 let current-node node ID-start-node
 let end-node node ID-end-node
 ask current-node [ set color red]
 ask end-node [ set color red]

 set currentNodesInList lput current-node currentNodesInList

 while [not member? end-node currentNodesInList] [

 ask current-node [ 

 foreach sort nodes-on neighbors [ 

  ask ? [set f-value [link-cost] of link ([who] of current-node) ([who] of ?) + distance end-node] ]  

  let next-current-node min-one-of [nodes-on neighbors] of current-node [f-value]
  ask link ([who] of current-node) ([who] of next-current-node) [set color red]
  set current-node next-current-node

  set currentNodesInList lput current-node currentNodesInList] ]
end

When ID-start-node and ID-end-node are close in the landscape, the code seems to work. However, when the distance between ID-start-node and ID-end-node is higher, the path does not reach the ID-end-node (see figure below; but sometimes, the code works).

In the figure, ID-start-node and ID-end-node are represented by a red start and the path is drawn in red.

Thanks very much for your help.

Answer 1

You might want to take a look at this model in the NetLogo users community:

http://ccl.northwestern.edu/netlogo/models/community/Astardemo1

It implements a simple procedure (find-a-path) that takes in the source and the target patches as parameters and returns a list of patches (which is one of the shortest paths from the source patch to the destination patch) using the A-star shortest path finding algorithm.

Also you might try turning off world wrapping.

Answer 2

A* has to have a way to back up a try old paths if it runs into a deadend, or something that seems inefficient. Your implementation just keeps going on a single path. While your way is definitely the most natural way to implement path finding, and much simpler, that could be why you're running into problems.

Here's an implementation I came up with. It uses patches directly rather than links, which actually seems like it would be better for you. Just give it a patch task that reports the cost of traveling across that patch and the source and target patches. I'm not super happy with it: real A* uses a heap to keep track of how good it think each possible path should be. I had to emulate the heap with a list, so it won't be as fast as true A*. If others see improvements, feel free to edit my answer or make suggestions in the comments! Anyway, here it is:

to-report find-path [ get-cost source destination ]
  let paths (list (list source))
  let estimated-costs (list [distance destination ] of source)
  let path first paths

  let visited patch-set source
  let encountered patch-set source

  while [ source != destination ] [
    let estimated-cost min estimated-costs
    let path-index position estimated-cost estimated-costs
    set path item path-index paths
    set source last path
    let path-cost estimated-cost - [ distance destination ] of source
    let source-cost [ runresult get-cost ] of source

    set paths remove-item path-index paths
    set estimated-costs remove-item path-index estimated-costs

    set visited (patch-set source visited)

    ask [ neighbors with [ not member? self visited ] ] of source [
      let patch-cost runresult get-cost
      let step-cost distance source * (patch-cost + source-cost) / 2
      let est-cost path-cost + step-cost + distance destination

      let add? true

      if member? self encountered [
        let other-path false
        foreach paths [
          if last ? = self [
            set other-path ?
          ]
        ]
        if other-path != false [
          let other-path-index position other-path paths
          let other-path-cost item other-path-index estimated-costs
          ifelse other-path-cost < est-cost [
            set add? false
          ] [
            set paths remove-item other-path-index paths
            set estimated-costs remove-item other-path-index estimated-costs
          ]
        ]
      ]

      if add? [
        set estimated-costs fput est-cost estimated-costs
        set paths fput (lput self path) paths

        set encountered (patch-set self encountered)
      ]
    ]    
  ]
  report path
end

If cost is a patch variable that contains the cost of traveling across that patch, then you'd call it like so: find-path task [ cost ] source-patch target-patch. Hope this helps!