15 puzzle solver: Difference between revisions
Content added Content deleted
Hendursaga (talk | contribs) m (Fixed spelling error, bumped tested version.) |
(Add solution on C#) |
||
Line 2,655: | Line 2,655: | ||
The program takes about 12 seconds to solve the puzzle on my machine. I sacrificed efficiency for readability and extensibility. |
The program takes about 12 seconds to solve the puzzle on my machine. I sacrificed efficiency for readability and extensibility. |
||
=={{header|C sharp|C#}}== |
|||
{{libheader|System.Windows.Forms}} |
|||
{{libheader|System.Drawing}} |
|||
{{works with|C sharp|3+}} |
|||
Note 1: The program does not output a text solution. It's solvig step by step in grafical interface.<br> |
|||
Note 2: Rosetta task avaiable from UI. Click "Task" button and run slover. The solution is obtained for 164 moves. |
|||
<syntaxhighlight lang="csharp">using System; |
|||
using System.Collections.Generic; |
|||
using System.Drawing; |
|||
using System.Windows.Forms; |
|||
public static class Program |
|||
{ |
|||
public static void Main(string[] args) |
|||
{ |
|||
FifteenPuzzle Game = new FifteenPuzzle(); |
|||
Application.Run(Game.Form); |
|||
} |
|||
} |
|||
public class Puzzle |
|||
{ |
|||
private int mOrderedNumer; |
|||
public int OrderedNumer |
|||
{ |
|||
get { return mOrderedNumer; } |
|||
} |
|||
public int CurrentNumber; |
|||
public bool IsPined = false; |
|||
public int X; |
|||
public int Y; |
|||
public int InvX |
|||
{ |
|||
get { return (FifteenPuzzle.GridSize - 1) - X; } |
|||
} |
|||
public int InvY |
|||
{ |
|||
get { return (FifteenPuzzle.GridSize - 1) - Y; } |
|||
} |
|||
public Puzzle(int OrderedNumer) |
|||
{ |
|||
mOrderedNumer = OrderedNumer; |
|||
CurrentNumber = OrderedNumer; |
|||
X = OrderedNumer % FifteenPuzzle.GridSize; |
|||
Y = OrderedNumer / FifteenPuzzle.GridSize; |
|||
} |
|||
public bool IsEmptyPuzzle |
|||
{ |
|||
get { return CurrentNumber >= (FifteenPuzzle.BlockCount - 1); } |
|||
} |
|||
public bool IsTruePlace |
|||
{ |
|||
get { return (CurrentNumber == mOrderedNumer); } |
|||
} |
|||
public bool NearestWith(Puzzle OtherPz) |
|||
{ |
|||
int dx = (X - OtherPz.X); |
|||
int dy = (Y - OtherPz.Y); |
|||
if ((dx == 0) && (dy <= 1) && (dy >= -1)) return true; |
|||
if ((dy == 0) && (dx <= 1) && (dx >= -1)) return true; |
|||
return false; |
|||
} |
|||
public int MHDistance(Puzzle OtherPz) |
|||
{ |
|||
int dx = (X - OtherPz.X); |
|||
int dy = (Y - OtherPz.Y); |
|||
if (dx < 0) dx = -dx; |
|||
if (dy < 0) dy = -dy; |
|||
return dx + dy; |
|||
} |
|||
public override string ToString() |
|||
{ |
|||
return (CurrentNumber + 1).ToString(); |
|||
} |
|||
public void UpdateView(Button V) |
|||
{ |
|||
V.Visible = true; |
|||
V.Text = ToString(); |
|||
if (IsEmptyPuzzle) V.Visible = false; |
|||
} |
|||
} |
|||
public class FifteenPuzzle |
|||
{ |
|||
public const int GridSize = 4; //Standard 15 puzzle is 4x4 |
|||
public const int BlockCount = 16; |
|||
static readonly Random R = new Random(); |
|||
private Form mForm; |
|||
public Form Form |
|||
{ |
|||
get { return mForm; } |
|||
} |
|||
private List<Button> Puzzles = new List<Button>(); |
|||
private int Moves = 0; |
|||
private DateTime Start; |
|||
private SolverPuzzle Solver; |
|||
private Button SolverButton; |
|||
private Timer SolverClock; |
|||
public FifteenPuzzle() |
|||
{ |
|||
this.mForm = CreateForm(); |
|||
this.Solver = new SolverPuzzle(Puzzles.ConvertAll<Puzzle>(Bt => (Puzzle)Bt.Tag)); |
|||
} |
|||
private Form CreateForm() |
|||
{ |
|||
int ButtonSize = 50; |
|||
int ButtonMargin = 3; |
|||
int FormEdge = 9; |
|||
Font ButtonFont = new Font("Arial", 15.75F, FontStyle.Regular); |
|||
Button StartButton = CreateButton("New Game", NewGameWithRandomBoard); |
|||
StartButton.Location = new Point(FormEdge, (GridSize * (ButtonMargin + ButtonSize)) + FormEdge); |
|||
int FormWidth = (GridSize * ButtonSize) + ((GridSize - 1) * ButtonMargin) + (FormEdge * 2); |
|||
int FormHeigth = FormWidth + StartButton.Height; |
|||
Form Form = new Form(); |
|||
Form.Text = "Fifteen"; |
|||
Form.ClientSize = new Size(FormWidth, FormHeigth); |
|||
Form.FormBorderStyle = FormBorderStyle.FixedSingle; |
|||
Form.MaximizeBox = false; |
|||
Form.SuspendLayout(); |
|||
for (int i = 0; i < BlockCount; i++) |
|||
{ |
|||
Button Bt = new Button(); |
|||
Puzzle Pz = new Puzzle(i); |
|||
int PosX = FormEdge + (Pz.X) * (ButtonSize + ButtonMargin); |
|||
int PosY = FormEdge + (Pz.Y) * (ButtonSize + ButtonMargin); |
|||
Bt.Location = new Point(PosX, PosY); |
|||
Bt.Size = new Size(ButtonSize, ButtonSize); |
|||
Bt.Font = ButtonFont; |
|||
Bt.Tag = Pz; |
|||
Bt.UseVisualStyleBackColor = true; |
|||
Bt.TabStop = false; |
|||
Bt.Enabled = false; |
|||
Pz.UpdateView(Bt); |
|||
Bt.Click += new EventHandler(MovePuzzle); |
|||
Puzzles.Add(Bt); |
|||
Form.Controls.Add(Bt); |
|||
} |
|||
// solver controls |
|||
SolverClock = new Timer(); |
|||
SolverClock.Interval = 300; |
|||
SolverClock.Tick += new EventHandler(SolverStep); |
|||
SolverButton = CreateButton("Run Solver", RunOrStopSolver); |
|||
SolverButton.Location = new Point(FormWidth - FormEdge - SolverButton.Width, StartButton.Location.Y); |
|||
SolverButton.Enabled = false; |
|||
Button TaskButton = CreateButton("Task", NewGameWithTask); |
|||
TaskButton.Location = new Point(StartButton.Location.X + StartButton.Width + ButtonMargin, StartButton.Location.Y); |
|||
TaskButton.Size = new Size((SolverButton.Location.X - ButtonMargin) - TaskButton.Location.X, 23); |
|||
Form.Controls.Add(StartButton); |
|||
Form.Controls.Add(TaskButton); |
|||
Form.Controls.Add(SolverButton); |
|||
Form.ResumeLayout(); |
|||
return Form; |
|||
} |
|||
private Button CreateButton(string Text, EventHandler ClickHandler) |
|||
{ |
|||
Button Bt = new Button(); |
|||
Bt.Size = new Size(80, 23); |
|||
Bt.Text = Text; |
|||
Bt.Font = new Font("Arial", 9.75F, FontStyle.Regular); |
|||
Bt.UseVisualStyleBackColor = true; |
|||
Bt.TabStop = false; |
|||
Bt.Click += ClickHandler; |
|||
return Bt; |
|||
} |
|||
private void NewGameWithRandomBoard(object Sender, EventArgs E) |
|||
{ |
|||
do |
|||
{ |
|||
for (int i = 0; i < Puzzles.Count; i++) |
|||
{ |
|||
Button Bt1 = Puzzles[R.Next(i, Puzzles.Count)]; |
|||
Button Bt2 = Puzzles[i]; |
|||
Swap(Bt1, Bt2); |
|||
} |
|||
} |
|||
while (!IsSolvable()); |
|||
NewGameBase(); |
|||
} |
|||
private void NewGameWithTask(object Sender, EventArgs E) |
|||
{ |
|||
int[] RosettaTask = new int[] |
|||
{ |
|||
15, 14, 1, 6, |
|||
9, 11, 4, 12, |
|||
0, 10, 7, 3, |
|||
13, 8, 5, 2, |
|||
}; |
|||
for (int i = 0; i < Puzzles.Count; i++) |
|||
{ |
|||
Button Bt = Puzzles[i]; |
|||
Puzzle Pz = (Puzzle)Bt.Tag; |
|||
Pz.CurrentNumber = RosettaTask[i] - 1; |
|||
if (Pz.CurrentNumber < 0) Pz.CurrentNumber = BlockCount - 1; |
|||
Pz.UpdateView(Bt); |
|||
} |
|||
NewGameBase(); |
|||
} |
|||
private void NewGameBase() |
|||
{ |
|||
Solver.Clear(); |
|||
for (int i = 0; i < Puzzles.Count; i++) |
|||
{ |
|||
Puzzles[i].Enabled = true; |
|||
} |
|||
SolverButton.Enabled = true; |
|||
Moves = 0; |
|||
Start = DateTime.Now; |
|||
} |
|||
private void MovePuzzle(object Sender, EventArgs E) |
|||
{ |
|||
Button Bt1 = (Button)Sender; |
|||
Puzzle Pz1 = (Puzzle)Bt1.Tag; |
|||
Button Bt2 = Puzzles.Find(Bt => ((Puzzle)Bt.Tag).IsEmptyPuzzle); |
|||
Puzzle Pz2 = (Puzzle)Bt2.Tag; |
|||
if (Pz1.NearestWith(Pz2)) |
|||
{ |
|||
Swap(Bt1, Bt2); |
|||
Moves++; |
|||
} |
|||
CheckWin(); |
|||
} |
|||
private void CheckWin() |
|||
{ |
|||
Button WrongPuzzle = Puzzles.Find(Bt => !((Puzzle)Bt.Tag).IsTruePlace); |
|||
bool UWin = (WrongPuzzle == null); |
|||
if (UWin) |
|||
{ |
|||
for (int i = 0; i < Puzzles.Count; i++) |
|||
{ |
|||
Puzzles[i].Enabled = false; |
|||
} |
|||
SolverClock.Enabled = false; |
|||
SolverButton.Enabled = false; |
|||
SolverButton.Text = "Run Solver"; |
|||
TimeSpan Elapsed = DateTime.Now - Start; |
|||
Elapsed = TimeSpan.FromSeconds(Math.Round(Elapsed.TotalSeconds, 0)); |
|||
MessageBox.Show(String.Format("Solved in {0} moves. Time: {1}", Moves, Elapsed)); |
|||
} |
|||
} |
|||
private void Swap(Button Bt1, Button Bt2) |
|||
{ |
|||
if (Bt1 == Bt2) return; |
|||
Puzzle Pz1 = (Puzzle)Bt1.Tag; |
|||
Puzzle Pz2 = (Puzzle)Bt2.Tag; |
|||
int g = Pz1.CurrentNumber; |
|||
Pz1.CurrentNumber = Pz2.CurrentNumber; |
|||
Pz2.CurrentNumber = g; |
|||
Pz1.UpdateView(Bt1); |
|||
Pz2.UpdateView(Bt2); |
|||
} |
|||
private bool IsSolvable() |
|||
{ |
|||
// WARNING: size of puzzle board MUST be even(like 4)! |
|||
// For explain see: https://www.geeksforgeeks.org/check-instance-15-puzzle-solvable/ |
|||
int InvCount = 0; |
|||
for (int i = 0; i < Puzzles.Count - 1; i++) |
|||
{ |
|||
for (int j = i + 1; j < Puzzles.Count; j++) |
|||
{ |
|||
Puzzle Pz1 = (Puzzle)Puzzles[i].Tag; |
|||
if (Pz1.IsEmptyPuzzle) continue; |
|||
Puzzle Pz2 = (Puzzle)Puzzles[j].Tag; |
|||
if (Pz2.IsEmptyPuzzle) continue; |
|||
if (Pz1.CurrentNumber > Pz2.CurrentNumber) InvCount++; |
|||
} |
|||
} |
|||
Button EmptyBt = Puzzles.Find(Bt => ((Puzzle)Bt.Tag).IsEmptyPuzzle); |
|||
Puzzle EmptyPz = (Puzzle)EmptyBt.Tag; |
|||
bool Result = false; |
|||
// even + odd |
|||
if (((EmptyPz.InvY + 1) % 2 == 0) && (InvCount % 2 != 0)) Result = true; |
|||
// odd + even |
|||
if (((EmptyPz.InvY + 1) % 2 != 0) && (InvCount % 2 == 0)) Result = true; |
|||
return Result; |
|||
} |
|||
private void RunOrStopSolver(object Sender, EventArgs E) |
|||
{ |
|||
SolverClock.Enabled = !SolverClock.Enabled; |
|||
if (SolverClock.Enabled) |
|||
{ |
|||
SolverButton.Text = "Stop Solver"; |
|||
} |
|||
else |
|||
{ |
|||
SolverButton.Text = "Run Solver"; |
|||
Solver.Clear(); |
|||
} |
|||
} |
|||
private void SolverStep(object Sender, EventArgs E) |
|||
{ |
|||
Point NextMove = Solver.AnalysisPosition(); |
|||
Button NextBt = Puzzles.Find(Bt => (((Puzzle)Bt.Tag).X == NextMove.X && ((Puzzle)Bt.Tag).Y == NextMove.Y)); |
|||
if (NextBt != null) MovePuzzle(NextBt, EventArgs.Empty); |
|||
} |
|||
} |
|||
public class SolverPuzzle |
|||
{ |
|||
static readonly int[] SolvingSecuence = new int[] { 0, 1, 2, 3, 4, 8, 12, 5, 6, 7, 9, 13, 10, 11, 14 }; |
|||
static readonly Point[] GameSteps = new Point[] { new Point(0, 1), new Point(1, 0), new Point(-1, 0), new Point(0, -1) }; |
|||
private List<Puzzle> Puzzles; |
|||
private PathSearch Navigator; |
|||
private Queue<Point> PlanedMoves = new Queue<Point>(); |
|||
private class DeadLock |
|||
{ |
|||
public int[] BoardMask; |
|||
public int EntryOrderedNumber; |
|||
public Point[] StepToSolve; |
|||
public bool InBoard(List<Puzzle> Puzzles) |
|||
{ |
|||
bool HasDeadLock = true; |
|||
for (int i = 0; i < BoardMask.Length; i++) |
|||
{ |
|||
if (BoardMask[i] < 0) continue; |
|||
if (BoardMask[i] != Puzzles[i].CurrentNumber) |
|||
{ |
|||
HasDeadLock = false; |
|||
break; |
|||
} |
|||
} |
|||
return HasDeadLock; |
|||
} |
|||
} |
|||
private static List<DeadLock> DeadLocks = new List<DeadLock>(); |
|||
static SolverPuzzle() |
|||
{ |
|||
// create deadlocks |
|||
DeadLock D; |
|||
// top line |
|||
D = new DeadLock(); |
|||
D.EntryOrderedNumber = 0; |
|||
D.BoardMask = new int[] { 0, 1, 2, -1, -1, -1, -1, 3, -1, -1, -1, -1, -1, -1, -1, -1, }; |
|||
D.StepToSolve = new Point[] |
|||
{ |
|||
new Point(1, 0), new Point(2, 0), new Point(3, 0), new Point(3, 1), new Point(2, 1), |
|||
new Point(2, 0), new Point(1, 0), new Point(0, 0), new Point(0, 1), |
|||
}; |
|||
DeadLocks.Add(D); |
|||
// left line |
|||
D = new DeadLock(); |
|||
D.EntryOrderedNumber = 1; |
|||
D.BoardMask = new int[] { 0, -1, -1, -1, 4, -1, -1, -1, 8, -1, -1, -1, -1, 12, -1, -1, }; |
|||
D.StepToSolve = new Point[] |
|||
{ |
|||
new Point(0, 0), new Point(0, 1), new Point(0, 2), new Point(0, 3), new Point(1, 3), |
|||
new Point(1, 2), new Point(0, 2), new Point(0, 1), new Point(0, 0), new Point(1, 0), |
|||
new Point(1, 1), |
|||
}; |
|||
DeadLocks.Add(D); |
|||
// second from top line |
|||
D = new DeadLock(); |
|||
D.EntryOrderedNumber = 5; |
|||
D.BoardMask = new int[] { -1, -1, -1, -1, -1, 5, 6, -1, -1, -1, -1, 7, -1, -1, -1, -1, }; |
|||
D.StepToSolve = new Point[] |
|||
{ |
|||
new Point(2, 1), new Point(3, 1), new Point(3, 2), new Point(2, 2), new Point(2, 1), |
|||
new Point(1, 1), new Point(1, 2), |
|||
}; |
|||
DeadLocks.Add(D); |
|||
// second from left line |
|||
D = new DeadLock(); |
|||
D.EntryOrderedNumber = 7; |
|||
D.BoardMask = new int[] { -1, -1, -1, -1, -1, 5, -1, -1, -1, 9, -1, -1, -1, -1, 13, -1, }; |
|||
D.StepToSolve = new Point[] |
|||
{ |
|||
new Point(2, 1), new Point(1, 1), new Point(1, 2), new Point(1, 3), new Point(2, 3), |
|||
new Point(2, 2), new Point(1, 2), new Point(1, 1), new Point(2, 1), new Point(3, 1), |
|||
new Point(3, 2), |
|||
}; |
|||
DeadLocks.Add(D); |
|||
} |
|||
public SolverPuzzle(List<Puzzle> Puzzles) |
|||
{ |
|||
this.Puzzles = Puzzles; |
|||
Navigator = new PathSearch(Puzzles, GameSteps); |
|||
} |
|||
public Point AnalysisPosition() |
|||
{ |
|||
// just do exist plan |
|||
if (PlanedMoves.Count > 0) return PlanedMoves.Dequeue(); |
|||
bool AllPined = PinTruePuzzles(); |
|||
// already solved |
|||
if (AllPined) return new Point(-1, -1); |
|||
Puzzle EmptyPz = Puzzles.Find(Pz => Pz.IsEmptyPuzzle); |
|||
Puzzle WrongPz = FindWrongPuzzle(); |
|||
// get path (empty puzzle => wrong puzle) if a far! |
|||
if (EmptyPz.MHDistance(WrongPz) > 1) |
|||
{ |
|||
PlanedPath(EmptyPz, WrongPz); |
|||
// do path! |
|||
if (PlanedMoves.Count > 0) return PlanedMoves.Dequeue(); |
|||
} |
|||
else // empty puzzle near |
|||
{ |
|||
// move empty puzzle around! |
|||
WrongPz.IsPined = true; |
|||
Puzzle BestPz = FindBestPuzzleToSwap(WrongPz); |
|||
// if already in place - click on target |
|||
if (BestPz == EmptyPz) return new Point(WrongPz.X, WrongPz.Y); |
|||
PlanedPath(EmptyPz, BestPz); |
|||
// do path! |
|||
if (PlanedMoves.Count > 0) return PlanedMoves.Dequeue(); |
|||
} |
|||
// if we are here SPEC CASE AHEAD |
|||
for (int i = 0; i < DeadLocks.Count; i++) |
|||
{ |
|||
DeadLock Lock = DeadLocks[i]; |
|||
if (Lock.InBoard(Puzzles)) |
|||
{ |
|||
// unpin dest |
|||
Puzzle DestPz = Puzzles.Find(Pz => Pz.OrderedNumer == Lock.EntryOrderedNumber); |
|||
DestPz.IsPined = false; |
|||
PlanedPath(EmptyPz, DestPz); |
|||
PlanedPath(Lock.StepToSolve); |
|||
// do path! |
|||
if (PlanedMoves.Count > 0) return PlanedMoves.Dequeue(); |
|||
} |
|||
} |
|||
// never throw on normal state |
|||
throw new Exception("Wtf?"); |
|||
} |
|||
private void PlanedPath(Point[] Steps) |
|||
{ |
|||
// add to plan |
|||
for (int i = 0; i < Steps.Length; i++) |
|||
{ |
|||
PlanedMoves.Enqueue(Steps[i]); |
|||
} |
|||
} |
|||
private void PlanedPath(Puzzle StartPz, Puzzle TargetPz) |
|||
{ |
|||
List<Point> Path = Navigator.FindPath(StartPz, TargetPz); |
|||
// add to plan |
|||
for (int i = 0; i < Path.Count; i++) |
|||
{ |
|||
PlanedMoves.Enqueue(Path[i]); |
|||
} |
|||
} |
|||
private Puzzle FindBestPuzzleToSwap(Puzzle CentrPz) |
|||
{ |
|||
Puzzle TruePlacePz = Puzzles.Find(Pz => Pz.OrderedNumer == CentrPz.CurrentNumber); |
|||
Puzzle BestPz = null; |
|||
int BestDistance = 0; |
|||
for (int i = 0; i < GameSteps.Length; i++) |
|||
{ |
|||
Puzzle NierPz = Puzzles.Find(Pz => ((Pz.X == CentrPz.X + GameSteps[i].X) && (Pz.Y == CentrPz.Y + GameSteps[i].Y))); |
|||
if (NierPz == null) continue; |
|||
if (NierPz.IsPined) continue; |
|||
int Distance = TruePlacePz.MHDistance(NierPz); |
|||
if (BestPz == null) |
|||
{ |
|||
BestDistance = Distance; |
|||
BestPz = NierPz; |
|||
continue; |
|||
} |
|||
if (Distance < BestDistance) |
|||
{ |
|||
BestDistance = Distance; |
|||
BestPz = NierPz; |
|||
} |
|||
} |
|||
return BestPz; |
|||
} |
|||
private Puzzle FindWrongPuzzle() |
|||
{ |
|||
for (int i = 0; i < SolvingSecuence.Length; i++) |
|||
{ |
|||
Puzzle SecPz = Puzzles.Find(Pz => Pz.CurrentNumber == SolvingSecuence[i]); |
|||
// first unpined in solving sec |
|||
if (!SecPz.IsPined) return SecPz; |
|||
} |
|||
return null; |
|||
} |
|||
private bool PinTruePuzzles() |
|||
{ |
|||
// unpin all |
|||
for (int i = 0; i < Puzzles.Count; i++) |
|||
{ |
|||
Puzzles[i].IsPined = false; |
|||
} |
|||
// pin |
|||
bool AllPined = true; |
|||
for (int i = 0; i < SolvingSecuence.Length; i++) |
|||
{ |
|||
Puzzle SecPz = Puzzles.Find(Pz => Pz.OrderedNumer == SolvingSecuence[i]); |
|||
// stop pining on first wrong puzzle |
|||
if (!SecPz.IsTruePlace) |
|||
{ |
|||
AllPined = false; |
|||
break; |
|||
} |
|||
SecPz.IsPined = true; |
|||
} |
|||
return AllPined; |
|||
} |
|||
public void Clear() |
|||
{ |
|||
PlanedMoves.Clear(); |
|||
} |
|||
} |
|||
public class PathSearch |
|||
{ |
|||
// AStar path search. Extremely naive realization for one task. |
|||
private Stack<NodeSearch> OpenedNodes = new Stack<NodeSearch>(); |
|||
private List<NodeSearch> Nodes = new List<NodeSearch>(); |
|||
private Point[] Steps; |
|||
private const float StepCost = 1f; |
|||
private enum NodeState { Unknown, Open, Closed } |
|||
private class NodeSearch |
|||
{ |
|||
public Puzzle Puzzle; |
|||
public Point Location |
|||
{ |
|||
get { return new Point(Puzzle.X, Puzzle.Y); } |
|||
} |
|||
public int X |
|||
{ |
|||
get { return Puzzle.X; } |
|||
} |
|||
public int Y |
|||
{ |
|||
get { return Puzzle.Y; } |
|||
} |
|||
public bool IsWalkable |
|||
{ |
|||
get { return !Puzzle.IsPined; } |
|||
} |
|||
public float G = 0f; |
|||
public NodeState State = NodeState.Unknown; |
|||
public NodeSearch ParentNode; |
|||
public NodeSearch(Puzzle Puzzle) |
|||
{ |
|||
this.Puzzle = Puzzle; |
|||
} |
|||
public void Clear() |
|||
{ |
|||
G = 0f; |
|||
State = NodeState.Unknown; |
|||
ParentNode = null; |
|||
} |
|||
} |
|||
public PathSearch(List<Puzzle> Puzzles, Point[] GameSteps) |
|||
{ |
|||
this.Steps = GameSteps; |
|||
// bind puzzles to search nodes |
|||
for (int i = 0; i < Puzzles.Count; i++) |
|||
{ |
|||
Nodes.Add(new NodeSearch(Puzzles[i])); |
|||
} |
|||
} |
|||
public List<Point> FindPath(Puzzle StartPz, Puzzle TargetPz) |
|||
{ |
|||
List<Point> Path = new List<Point>(); |
|||
NodeSearch Start = Nodes.Find(Ns => (Ns.Puzzle == StartPz)); |
|||
if (Start == null) return Path; |
|||
NodeSearch Target = Nodes.Find(Ns => (Ns.Puzzle == TargetPz)); |
|||
if (Target == null) return Path; |
|||
Start.State = NodeState.Open; |
|||
OpenedNodes.Push(Start); |
|||
bool PathFound = false; |
|||
while (OpenedNodes.Count > 0) |
|||
{ |
|||
NodeSearch CurrentNode = OpenedNodes.Pop(); |
|||
if (CurrentNode == Target) |
|||
{ |
|||
PathFound = true; |
|||
break; |
|||
} |
|||
for (int i = 0; i < Steps.Length; i++) |
|||
{ |
|||
NodeSearch NextNode = Nodes.Find(Ns => ((Ns.X == CurrentNode.X + Steps[i].X) && (Ns.Y == CurrentNode.Y + Steps[i].Y))); |
|||
if (NextNode == null) continue; |
|||
if (!NextNode.IsWalkable) continue; |
|||
if (NextNode.State == NodeState.Closed) continue; |
|||
if (NextNode.State == NodeState.Open) |
|||
{ |
|||
float NewG = CurrentNode.G + StepCost; |
|||
if (NewG < NextNode.G) |
|||
{ |
|||
NextNode.ParentNode = CurrentNode; |
|||
NextNode.G = NewG; |
|||
OpenedNodes.Push(NextNode); |
|||
} |
|||
} |
|||
else |
|||
{ |
|||
// unknow node |
|||
NextNode.State = NodeState.Open; |
|||
NextNode.ParentNode = CurrentNode; |
|||
NextNode.G = CurrentNode.G + StepCost; |
|||
OpenedNodes.Push(NextNode); |
|||
} |
|||
} |
|||
CurrentNode.State = NodeState.Closed; |
|||
} |
|||
// restore path |
|||
if (PathFound) |
|||
{ |
|||
NodeSearch CurentNode = Target; |
|||
while (CurentNode != Start) |
|||
{ |
|||
Path.Add(CurentNode.Location); |
|||
CurentNode = CurentNode.ParentNode; |
|||
} |
|||
Path.Reverse(); |
|||
} |
|||
// clear state |
|||
OpenedNodes.Clear(); |
|||
for (int i = 0; i < Nodes.Count; i++) |
|||
{ |
|||
Nodes[i].Clear(); |
|||
} |
|||
return Path; |
|||
} |
|||
}</syntaxhighlight> |
|||
=={{header|C++}}== |
=={{header|C++}}== |