Im letzten
Beitrag habe ich meiner Implementierung vom Jump Point Search Algorithmus gezeigt. Hier geht es in erster Linie um F# und Wpf.
Da es in Visual Studio bereits eine
Projekt-Vorlage für F# Wpf gibt, habe ich sie auch genommen. Und zwar handelt es sich dabei um eine MVVM-Vorlage. Daher veruschte ich im Rahmen vom MVVM-Pattern zu bleiben.
Typen für das Model und
//JumpSearchModel.fs
//MVVM Model Types.
module JumpMazeModelType =
open Maze.JumpPointSearchType
type SelectedCoin =
| Start of float * float
| Finish of float * float
type MazeEnvironment =
{ maze : JumpPointEnvironment; obstacles : Set<(int * int)>;
wallSize : float; coinX : float; coinY : float; targetX : float; targetY : float}
member this.IsEmpty = Map.isEmpty <| this.maze.grid
let empty = { maze = empty; obstacles = Set.empty;
wallSize = 20.0; coinX = 0.0; coinY = 0.0;targetX = 0.0; targetY = 0.0 }das ViewModel.
//JumpSearchViewModel.fs
//MVVM ViewModel Class Type
type JumpSearchViewModel() as x =
class
inherit ViewModelBase()
let mutable env : MazeEnvironment = JumpMazeModel.empty
let mutable selectedCoin : SelectedCoin = Start (0.0, 0.0)
...
end
DataContext vom View.
<Window.DataContext>
<ViewModel:JumpSearchViewModel></ViewModel:JumpSearchViewModel>
</Window.DataContext>Ich habe nichts besseres gefunden, als das Canvas-Element im
CommandParameter-Binding vom
Button-Element anzugeben, um es später im ViewModel für den Aufruf von
Mouse.GetPosition und für den Zugriff auf die
Children-Auflistung des Canvas-Elementes zu verwenden.
...
<Button Command="{Binding CreateMazeCommand}" CommandParameter="{Binding ElementName=canvas}" >Init Maze</Button>
...//JumpSearchViewModel.fs
type JumpSearchViewModel() as x=
class
...
let mutable canvas : Canvas = null
member x.CreateMazeCommand =
new RelayCommand ((fun canExecute -> x.VerifyX() = null && x.VerifyY() = null), (fun element -> x.CreateMaze(element)))
member x.CreateMaze(element) =
canvas <- element :?> Canvas
...
Die erste Herausforderung war die Start- und Ziel-Spielmarke mit der Tastatur auf dem Labyrinthbrett zu bewegen. Genauer gesagt wird einen von beiden Chips per Mausklick ausgewählt und dann mit einer Pfeiltaste auf die nächste Zelle bewegt, wenn es da gerade kein Hindernis gibt.
...
<!--coins moving with keys-->
<Window.InputBindings>
<KeyBinding Command="{Binding CoinMoveCommand}" Key="Down" >
<KeyBinding.CommandParameter>
<i:Key>Down</i:Key>
</KeyBinding.CommandParameter>
</KeyBinding>
<KeyBinding Command="{Binding CoinMoveCommand}" Key="Up">
<KeyBinding.CommandParameter>
<i:Key>Up</i:Key>
</KeyBinding.CommandParameter>
</KeyBinding>
<KeyBinding Command="{Binding CoinMoveCommand}" Key="Left">
<KeyBinding.CommandParameter>
<i:Key>Left</i:Key>
</KeyBinding.CommandParameter>
</KeyBinding>
<KeyBinding Command="{Binding CoinMoveCommand}" Key="Right">
<KeyBinding.CommandParameter>
<i:Key>Right</i:Key>
</KeyBinding.CommandParameter>
</KeyBinding>
</Window.InputBindings>
...
<!--start and finish coin-->
<Canvas>
...
<Ellipse Name="coin" Fill="Blue"
Canvas.Left="{Binding Path=CoinX }"
Canvas.Top="{Binding Path=CoinY }" />
<Ellipse Name="target" Canvas.Left="{Binding Path=TargetX}"
Canvas.Top="{Binding Path=TargetY}" />
...
</Canvas>
//JumpSearchViewModel.fs
type JumpSearchViewModel() as x =
class
...
member x.CoinX
with get () =
env.coinX
and set value =
env <- JumpMazeModel.setCoinX env value coin
base.RaisePropertyChangedEvent(<@x.CoinX@>)
member x.CoinY
...
member x.TargetX
with get () =
env.targetX
and set value =
env <- JumpMazeModel.setCoinX env value coin
base.RaisePropertyChangedEvent(<@x.TargetX@>)
member x.TargetY
...
member x.CoinMoveCommand =
new RelayCommand ((fun _ -> not env.IsEmpty && not timer.IsEnabled && x.Verify "MazeX" = null && x.Verify "MazeY" = null),
(fun key -> x.CoinMove(key)))
member x.CoinMove(k)=
env <- JumpMazeModel.moveCoin {env with obstacles=obstacles} (k :?> Key) selectedCoin
match selectedCoin with
| Start _ ->
selectedCoin <- Start (env.coinX, env.coinY)
base.RaisePropertyChangedEvent(<@x.CoinX@>)
base.RaisePropertyChangedEvent(<@x.CoinY@>)
| Finish _ ->
selectedCoin <- Finish (env.targetX, env.targetY)
base.RaisePropertyChangedEvent(<@x.TargetX@>)
base.RaisePropertyChangedEvent(<@x.TargetY@>)
...//JumpSearchModel.fs
...
let moveCoin (mazeEnv : MazeEnvironment) key selectedCoin =
let move (coinX, coinY) =
let cx, cy = (int coinX) / int mazeEnv.wallSize , (int coinY) / int mazeEnv.wallSize
match key, mazeEnv.IsEmpty with
| _, true -> coinX, coinY
| Key.Down, false ->
if cy >= mazeEnv.maze.h - 1 || (Set.exists ( fun w -> w = (cx, cy + 1)) mazeEnv.obstacles ) then
coinX, coinY
else
coinX, coinY + mazeEnv.wallSize
| Key.Up, false ->
if cy = 0 || (Set.exists ( fun w -> w = (cx, cy - 1)) mazeEnv.obstacles) then
coinX, coinY
else
coinX, coinY - mazeEnv.wallSize
| Key.Right, false ->
if cx >= mazeEnv.maze.w - 1 || (Set.exists ( fun w -> w = (cx + 1, cy)) mazeEnv.obstacles) then
coinX, coinY
else
coinX + mazeEnv.wallSize, coinY
| Key.Left, false ->
if cx = 0 || (Set.exists ( fun w -> w = (cx - 1, cy)) mazeEnv.obstacles) then
coinX, coinY
else
coinX - mazeEnv.wallSize, coinY
| _, false -> coinX, coinY
match selectedCoin with
| Start (dx, dy) ->
let moveX, moveY = move (dx, dy)
{mazeEnv with coinX = moveX; coinY = moveY}
| Finish (dx, dy) ->
let moveX, moveY = move (dx, dy)
{mazeEnv with targetX = moveX; targetY = moveY}
let setCoinX (mazeEnv : MazeEnvironment) x selectedCoin =
if mazeEnv.IsEmpty |> not && x < float (mazeEnv.maze.w * int mazeEnv.wallSize) then
match selectedCoin with
| Start _ -> {mazeEnv with coinX = x}
| Finish _ -> {mazeEnv with targetX = x}
else
mazeEnv
let setCoinY (mazeEnv : MazeEnvironment) y selectedCoin =
...Die zweite Herausforderung bestand in der Mausklick-Verarbeitung im Zusammenhang mit der Positionsbestimmung des Mauszeigers. Man sollte per Mausklick entweder ein Chip auswählen können oder ein Hindernis an der entsprechenden Position zu zeichnen oder zu löschen.
...
<Canvas.InputBindings>
<MouseBinding MouseAction="LeftClick" Command="{Binding LeftClickCommand}" />
<MouseBinding MouseAction="RightClick" Command="{Binding RightClickCommand}" />
</Canvas.InputBindings>
...
Wie oben schon erwähnt, wird die Position über den Aufruf von
Mouse.GetPosition ermittelt. Die Hindernis-Positionen werden in einer Liste gespeichert und mit der Hilfe von Path-Geometry auf dem
Canvas-Element abgebildet.
//JumpSearchViewModel.fs
type JumpSearchViewModel() as x =
...
let mutable obstacles = set[]
let mutable mazeGeometry = Geometry.Parse("")
...
//maze path geometry.
member x.MazeData
with get () = mazeGeometry
and set value =
mazeGeometry <- value
base.RaisePropertyChangedEvent(<@x.MazeData@>)
member x.LeftClickCommand =
// if the mouse position hit the start or the finish coin position,
// then select a coin. Otherwise add obstacle at mouse position.
new RelayCommand ((fun canExecute -> not env.IsEmpty && not timer.IsEnabled && x.Verify "MazeX" = null && x.Verify "MazeY" = null),
(fun element ->
let pos = Mouse.GetPosition(element :?> UIElement)
let cellPos (posx, posy) = (posx / 20.0 |> int), (posy / 20.0 |> int)
//check if the mouse click hit the start or the finish coin position.
match cellPos (pos.X, pos.Y) = cellPos (env.coinX, env.coinY), cellPos (pos.X, pos.Y) = cellPos (env.targetX, env.targetY) with
| true, _ -> selectedCoin <- Start (env.coinX, env.coinY)
|_, true -> selectedCoin <- Finish (env.targetX, env.targetY)
| _ ->
obstacles <- Set.add (cellPos (pos.X, pos.Y)) obstacles
x.MazeData <- Geometry.Parse(JumpSearchViewModel.CreateMazePath (x.MazeX |> float) (x.MazeY |> float) x.WallSize obstacles)))
member x.RightClickCommand =
//Remove obstacle at mouse position.
new RelayCommand ((fun canExecute -> not env.IsEmpty && not timer.IsEnabled && x.Verify "MazeX" = null && x.Verify "MazeY" = null),
(fun element ->
let pos = Mouse.GetPosition(element :?> UIElement)
let posx, posy = (pos.X/20.0 |> int), (pos.Y / 20.0 |> int)
obstacles <- Set.remove (posx, posy) obstacles
x.MazeData <- Geometry.Parse(JumpSearchViewModel.CreateMazePath (x.MazeX |> float) (x.MazeY |> float) x.WallSize obstacles)))
...
Das Labyrinth und der Ergebnispfad.
<!--Labirynth and solver result path-->
<Path Name="mazePath" Stroke="Black" Data="{Binding Path=MazeData}" StrokeThickness="4" ></Path>
<Path Name="solverPath" Stroke="Purple" Data="{Binding Path=SolverData}" StrokeDashArray="4 2" StrokeThickness="3" ></Path>
...
<Button Command="{Binding CreateMazeCommand}" CommandParameter="{Binding ElementName=canvas}" >Init Maze</Button>
<Button Name="AStar" Command="{Binding CreateAStarCommand}">A* Jump Points Search</Button>Die komplexe Pfade lassen sich leicht mit der Hilfe von der
Markup-Syntax beschreiben.
//JumpSearchViewModel.fs
type JumpSearchViewModel() as x =
...
let mutable mazeGeometry = Geometry.Parse("")
let mutable solverPath = Geometry.Parse("")
...
static member CreateMazePath w h wallSize points =
let builder = StringBuilder()
let folder (acc : StringBuilder) wall =
match wall with
| (x, y) ->
let xf, yf = (float x) * wallSize, (float y) * wallSize
acc.Append(sprintf "M%f,%fV%f" xf yf (yf + wallSize))|>ignore
acc.Append(sprintf " H%fV%fH%f" (xf + wallSize) yf xf)
builder.Append(sprintf "M%f,%f" 0.0 0.0)|>ignore
builder.Append(sprintf "L%f,%f %f,%f" 0.0 0.0 0.0 (h * wallSize)) |> ignore
builder.Append(sprintf " %f,%f %f,%f" 0.0 (h * wallSize) (w * wallSize) (h * wallSize)) |>ignore
builder.Append(sprintf " %f,%f %f,%f" (w * wallSize) (h * wallSize) (w * wallSize) 0.0) |>ignore
builder.Append(sprintf " %f,%f %f,%f" (w * wallSize) 0.0 0.0 0.0)|>ignore
(points |> PSeq.fold folder builder).ToString()
member x.SolverData
with get () = solverPath
and set value =
solverPath <- value
base.RaisePropertyChangedEvent(<@x.SolverData@>)
member x.CreateMazeCommand =
new RelayCommand ((fun canExecute -> x.VerifyX = null && x.VerifyY = null), (fun element -> x.CreateMaze(element)))
member x.CreateMaze(element) =
...
x.MazeData <- Geometry.Parse("")
x.SolverData <- Geometry.Parse("")
env <- JumpMazeModel.createMaze x.MazeX x.MazeY x.WallSize
selectedCoin <- Finish (env.targetX, env.targetY)
x.TargetX <- env.targetX
x.TargetY <- env.targetY
obstacles <- env.obstacles
x.MazeData <- Geometry.Parse(JumpSearchViewModel.CreateMazePath (x.MazeX |> float) (x.MazeY |> float) x.WallSize obstacles)
member x.CreateAStarCommand =
new RelayCommand (
(fun canExecute -> true),
(fun _ ->
if x.VerifyX = null && x.VerifyY = null then x.CreateAStar()))
//create solver path.
member x.CreateAStar() =
...
let jumpPoints = JumpMazeModel.run {env with obstacles = obstacles}
x.SolverData <- Geometry.Parse(jumpPoints |> JumpMazeModel.resultPath |> JumpMazeModel.solverToPath x.WallSize )
Das Schwierigste war für mich die Visualisierung. Es geht bestimmt irgendwie besser und anders. Meine Lösung ist die Verwendung von der
DispatcherTimer-Klasse. Die Positionen von den besuchten Zellen mitsamt Positionen von Vater-Zellen werden in einer Liste -
animatePoints - gespeichert. Bei jedem
Tick-Ereignis wird ein Listenelement aus der Liste genommen und als ein
Ellipse-Element in der
Children-Eigenschaft von Canvas gespeichert. Zusätzlich wird der Weg von der Vater-Zelle zu der aktuellen Zelle gezeichnet.
<Canvas Name="canvas">
...
<Path Stroke="BurlyWood" Data="{Binding Path=AnimateData}" StrokeThickness="2"></Path>
...
</Canvas>
...
<Button Command="{Binding AnimateCommand}" >Animate</Button>
...//JumpSearchViewModel.fs
type JumpSearchViewModel() as x=
class
...
let mutable animateData = String.Empty
let mutable animateResult = String.Empty
let mutable timer = new DispatcherTimer(DispatcherPriority.Normal)
//( (int * int) * ((int * int) * Direction) ) list.
//( jumpPoint * (parent * direction)) list
let mutable animatePoints = []
let mutable undo = []
let mutable canvas : Canvas = null
do
timer.Interval <- new TimeSpan(0, 0, 0, 0, 400)
timer.Tick.Add(fun _ -> x.AnimateOneStep () )
...
member x.AnimateData
with get () = Geometry.Parse(animateData)
and set value =
solverPath <- Geometry.Parse(value)
base.RaisePropertyChangedEvent(<@x.AnimateData@>)
member x.AnimateCommand =
new RelayCommand ((fun _ -> true),
(fun _ ->
match not env.IsEmpty && x.Verify "MazeX" = null && x.Verify "MazeY" = null with
| false -> ()
| true ->
x.SolverData <- Geometry.Parse("")
x.ResetAnimateData()
selectedCoin <- Start (env.coinX, env.coinY)
let animateRun = JumpMazeModel.run {env with obstacles = obstacles}
animateResult <- animateRun |> JumpMazeModel.resultPath |> JumpMazeModel.solverToPath x.WallSize
animatePoints <- animateRun |> JumpMazeModel.animatePoints |> Seq.toList
timer.Start()))
member x.AnimateOneStep () =
match animatePoints with
| [] -> timer.Stop()
| [((currx, curry),(x',y'), d)] ->
let x2, y2, x1, y1 = (currx |> float) * env.wallSize + env.wallSize / 2.0, (curry |> float) * env.wallSize + env.wallSize / 2.0, (x' |> float) * env.wallSize + env.wallSize / 2.0, (y' |> float) * env.wallSize + env.wallSize / 2.0
animateData <- sprintf "%sM%f,%fL%f,%f %f,%f%s" animateData x1 y1 x1 y1 x2 y2 (x.DrawArrow (x2, y2, d))
x.AnimateData <- animateData
x.SolverData <- Geometry.Parse(animateResult)
timer.Stop()
| ((currx, curry),(x',y'), d) :: ts->
let x2, y2, x1, y1 = (currx |> float) * env.wallSize + env.wallSize / 2.0, (curry |> float) * env.wallSize + env.wallSize / 2.0, (x' |> float) * env.wallSize + env.wallSize / 2.0, (y' |> float) * env.wallSize + env.wallSize / 2.0
// add new Point to Path and draw a line with arrows
// from the last point to the new point.
animateData <- sprintf "%sM%f,%fL%f,%f %f,%f%s" animateData x1 y1 x1 y1 x2 y2 (x.DrawArrow (x2, y2, d))
x.AnimateData <- animateData
// move the start coin.
x.CoinX <- x2
x.CoinY <- y2
// add new jump point to canvas children collection.
if canvas <> null then
let e = new Ellipse(Width = 6.0, Height= 6.0, Fill = Brushes.Blue)
canvas.Children.Add(e)|>ignore
Canvas.SetLeft(e, x2 )
Canvas.SetTop(e, y2 )
//add remove function to undo functon list.
undo <- [(fun _ -> canvas.Children.Remove e;)] @ undo
animatePoints <- ts
member x.CreateAStar() =
x.ResetAnimateData()
...
member x.CreateMaze(element) =
x.ResetAnimateData()
...
member private x.ResetAnimateData() =
if timer.IsEnabled then
timer.Stop()
// Remove all added ellipses.
List.map (fun f -> f ()) undo|>ignore
animateData <- String.Empty
x.AnimateData <- animateData
...Der Code.
