Yonaba / Jumper

Fast, lightweight and easy-to-use pathfinding library for grid-based games
http://yonaba.github.io/Jumper
MIT License
619 stars 125 forks source link

Add search algorithm : Breadth-First Search #29

Open Yonaba opened 10 years ago

Yonaba commented 10 years ago

Following Depth First search and Besr First Search, include Breadth First search, for uniform-cost grids and point graphs.

Pseudo-code:

procedure BFS(G,v) is
  create a queue Q
  create a vector set V
  enqueue v onto Q
  add v to V
  while Q is not empty loop
    t ← Q.dequeue()
    if t is what we are looking for then
      return t
    end if
    for all edges e in G.adjacentEdges(t) loop
      u ← G.adjacentVertex(t,e)
      if u is not in V then
        add u to V
        enqueue u onto Q
      end if
    end loop
  end loop
  return none
end BFS