ダイクストラ法という最短経路を求めるアルゴリズムをSwiftで試してみました。
参考にさせて頂いたのはこちらの記事です。
ダイクストラ法とは
ダイクストラ法(だいくすとらほう、英: Dijkstra’s algorithm)はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。
Wikipediaによると上記のようなものになります。
今回はこれをSwiftで実装してみます。
実装
まずは画面上に点を設置します。
import UIKit class ViewController: UIViewController { override func viewDidLoad() { super.viewDidLoad() (0...5).forEach { _ in let dot = UIView(frame: CGRect( x: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.width)))), y: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.height)))), width: 20, height: 20)) dot.backgroundColor = UIColor.darkGray dot.layer.cornerRadius = dot.frame.width / 2 view.addSubview(dot) } } }
次にStartとGoalを決めます。
class ViewController: UIViewController { override func viewDidLoad() { super.viewDidLoad() var dots: [UIView] = [] (0...5).forEach { _ in let dot = UIView(frame: CGRect( x: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.width)))), y: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.height)))), width: 20, height: 20)) dot.backgroundColor = UIColor.darkGray dot.layer.cornerRadius = dot.frame.width / 2 dots.append(dot) view.addSubview(dot) } let startLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20)) startLabel.text = "S" startLabel.textColor = UIColor.white startLabel.textAlignment = .center dots.first?.addSubview(startLabel) let goalLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20)) goalLabel.text = "G" goalLabel.textColor = UIColor.white goalLabel.textAlignment = .center dots.last?.addSubview(goalLabel) } }
続けて線同士を繋げて経路を作ろうと思います。
各点に他経路への参照を持たせるためにDotViewというクラスを作って各点をUIViewからDotViewにします。
下だと場合によっては循環参照が起こったり場合によってゴールまで着けない事もあるのですが、今回は「ダイクストラ法」の勉強という事で無視します。
import UIKit class ViewController: UIViewController { override func viewDidLoad() { super.viewDidLoad() var dots: [DotView] = [] // UIViewをDotViewに変更 (0...5).forEach { _ in let dot = DotView(frame: CGRect( // UIViewをDotViewに変更 x: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.width)))), y: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.height)))), width: 20, height: 20)) dot.backgroundColor = UIColor.darkGray dot.layer.cornerRadius = dot.frame.width / 2 dots.append(dot) view.addSubview(dot) } let startLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20)) startLabel.text = "S" startLabel.textColor = UIColor.white startLabel.textAlignment = .center dots.first?.addSubview(startLabel) let goalLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20)) goalLabel.text = "G" goalLabel.textColor = UIColor.white goalLabel.textAlignment = .center dots.last?.addSubview(goalLabel) // 以下今回追加 dots.forEach { dot in var otherDots = dots.filter { $0 != dot } dot.otherDots.append(otherDots.remove(at: Int(arc4random_uniform(UInt32(otherDots.count))))) dot.otherDots.append(otherDots.remove(at: Int(arc4random_uniform(UInt32(otherDots.count))))) } } } // 以下が今回追加分 class DotView: UIView { var otherDots: [UIView] = [] }
上で参照を持たせたので、次は線を引きます。
import UIKit class ViewController: UIViewController { override func viewDidLoad() { super.viewDidLoad() var dots: [DotView] = [] (0...5).forEach { _ in let dot = DotView(frame: CGRect( x: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.width)))), y: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.height)))), width: 20, height: 20)) dot.backgroundColor = UIColor.darkGray dot.layer.cornerRadius = dot.frame.width / 2 dots.append(dot) view.addSubview(dot) } let startLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20)) startLabel.text = "S" startLabel.textColor = UIColor.white startLabel.textAlignment = .center dots.first?.addSubview(startLabel) let goalLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20)) goalLabel.text = "G" goalLabel.textColor = UIColor.white goalLabel.textAlignment = .center dots.last?.addSubview(goalLabel) dots.forEach { dot in var otherDots = dots.filter { $0 != dot } dot.otherDots.append(otherDots.remove(at: Int(arc4random_uniform(UInt32(otherDots.count))))) dot.otherDots.append(otherDots.remove(at: Int(arc4random_uniform(UInt32(otherDots.count))))) } // 以下は今回追加 dots.forEach { dot in dot.otherDots.forEach { otherDot in let lineView = LineView(start: dot.frame.origin, end: otherDot.frame.origin) view.addSubview(lineView) view.sendSubview(toBack: lineView) } } } } class DotView: UIView { var otherDots: [DotView] = [] } // 以下は今回追加 class LineView: UIView { let start: CGPoint let end: CGPoint init(start: CGPoint, end: CGPoint) { self.start = start self.end = end super.init(frame: CGRect( x: ([start.x, end.x].min() ?? 0) + 10, y: ([start.y, end.y].min() ?? 0) + 10, width: abs(start.x - end.x), height: abs(start.y - end.y))) backgroundColor = UIColor.clear } required init?(coder aDecoder: NSCoder) { fatalError("init(coder:) has not been implemented") } override func draw(_ rect: CGRect) { let path = UIBezierPath() path.move(to: CGPoint(x: start.x - frame.origin.x + 10, y: start.y - frame.origin.y + 10)) path.addLine(to: CGPoint(x: end.x - frame.origin.x + 10, y: end.y - frame.origin.y + 10)) path.lineWidth = 4.0 UIColor.darkGray.setStroke() path.stroke() } }
これで経路を作る事ができました。
ここからダイクストラ法を実装していきます。
まずはDotViewにtypeとscore(スタートからの距離)を追加して、viewDidLoadの中でtypeを設定します。
import UIKit class ViewController: UIViewController { override func viewDidLoad() { super.viewDidLoad() var dots: [DotView] = [] (0...5).forEach { _ in let dot = DotView(frame: CGRect( x: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.width)))), y: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.height)))), width: 20, height: 20)) dot.backgroundColor = UIColor.darkGray dot.layer.cornerRadius = dot.frame.width / 2 dots.append(dot) view.addSubview(dot) } let startLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20)) startLabel.text = "S" startLabel.textColor = UIColor.white startLabel.textAlignment = .center dots.first?.addSubview(startLabel) dots.first?.type = .start // 追加 let goalLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20)) goalLabel.text = "G" goalLabel.textColor = UIColor.white goalLabel.textAlignment = .center dots.last?.addSubview(goalLabel) dots.last?.type = .goal // 追加 dots.forEach { dot in var otherDots = dots.filter { $0 != dot } dot.otherDots.append(otherDots.remove(at: Int(arc4random_uniform(UInt32(otherDots.count))))) dot.otherDots.append(otherDots.remove(at: Int(arc4random_uniform(UInt32(otherDots.count))))) } dots.forEach { dot in dot.otherDots.forEach { otherDot in let lineView = LineView(start: dot.frame.origin, end: otherDot.frame.origin) view.addSubview(lineView) view.sendSubview(toBack: lineView) } } } } // 今回修正 class DotView: UIView { enum DotType { case start case goal case normal } var otherDots: [DotView] = [] var score: CGFloat = 0 var type: DotType = .normal var routeDots: [DotView] = [] } // 省略
経路を作ったので、どれが最短経路かを計算します。
ViewControllerを以下のように修正します。
import UIKit class ViewController: UIViewController { override func viewDidLoad() { super.viewDidLoad() var dots: [DotView] = [] (0...5).forEach { _ in let dot = DotView(frame: CGRect( x: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.width)))), y: CGFloat(arc4random_uniform(UInt32(Int32(view.frame.height)))), width: 20, height: 20)) dot.backgroundColor = UIColor.darkGray dot.layer.cornerRadius = dot.frame.width / 2 dots.append(dot) view.addSubview(dot) } let startLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20)) startLabel.text = "S" startLabel.textColor = UIColor.white startLabel.textAlignment = .center dots.first?.addSubview(startLabel) dots.first?.type = .start let goalLabel = UILabel(frame: CGRect(x: 0, y: 0, width: 20, height: 20)) goalLabel.text = "G" goalLabel.textColor = UIColor.white goalLabel.textAlignment = .center dots.last?.addSubview(goalLabel) dots.last?.type = .goal dots.forEach { dot in var otherDots = dots.filter { $0 != dot } dot.otherDots.append(otherDots.remove(at: Int(arc4random_uniform(UInt32(otherDots.count))))) dot.otherDots.append(otherDots.remove(at: Int(arc4random_uniform(UInt32(otherDots.count))))) } dots.forEach { dot in dot.otherDots.forEach { otherDot in let lineView = LineView(start: dot.frame.origin, end: otherDot.frame.origin) view.addSubview(lineView) view.sendSubview(toBack: lineView) } } if let start = dots.first { var targetDots = [start] while targetDots.count != 0 { let targetDot = targetDots.remove(at: 0) targetDot.otherDots.forEach { let dx = targetDot.frame.origin.x - $0.frame.origin.x let dy = targetDot.frame.origin.y - $0.frame.origin.y if $0.score == 0 || targetDot.score + sqrt(dx*dx + dy*dy) < $0.score { $0.score = targetDot.score + sqrt(dx*dx + dy*dy) targetDots.append($0) $0.routeDots = targetDot.routeDots + [targetDot] } } } } if let last = dots.last, last.routeDots.count != 0 { last.routeDots.append(last) (0...(last.routeDots.count - 2)).forEach { let lineView = LineView( start: last.routeDots[$0].frame.origin, end: last.routeDots[$0 + 1].frame.origin, color: UIColor.red, lineWidth: 2) view.addSubview(lineView) } } } } class DotView: UIView { enum DotType { case start case goal case normal } var otherDots: [DotView] = [] var score: CGFloat = 0 var type: DotType = .normal var routeDots: [DotView] = [] } class LineView: UIView { let start: CGPoint let end: CGPoint let color: UIColor let lineWidth: CGFloat init(start: CGPoint, end: CGPoint, color: UIColor = UIColor.darkGray, lineWidth: CGFloat = 4) { self.start = start self.end = end self.color = color self.lineWidth = lineWidth super.init(frame: CGRect( x: ([start.x, end.x].min() ?? 0) + 10, y: ([start.y, end.y].min() ?? 0) + 10, width: abs(start.x - end.x), height: abs(start.y - end.y))) backgroundColor = UIColor.clear } required init?(coder aDecoder: NSCoder) { fatalError("init(coder:) has not been implemented") } override func draw(_ rect: CGRect) { let path = UIBezierPath() path.lineWidth = lineWidth color.set() path.move(to: CGPoint(x: start.x - frame.origin.x + 10, y: start.y - frame.origin.y + 10)) path.addLine(to: CGPoint(x: end.x - frame.origin.x + 10, y: end.y - frame.origin.y + 10)) path.stroke() } }
実際の計算は下の部分です。
スタートから順番に点を辿り、その順路が最短なら更に探索、最短でなければそのルートは探索終了しています。
if let start = dots.first { var targetDots = [start] while targetDots.count != 0 { let targetDot = targetDots.remove(at: 0) targetDot.otherDots.forEach { let dx = targetDot.frame.origin.x - $0.frame.origin.x let dy = targetDot.frame.origin.y - $0.frame.origin.y if $0.score == 0 || targetDot.score + sqrt(dx*dx + dy*dy) < $0.score { $0.score = targetDot.score + sqrt(dx*dx + dy*dy) targetDots.append($0) $0.routeDots = targetDot.routeDots + [targetDot] } } } }
これを実行すると、以下のように最短経路を表示できた事が分かります。