Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- List<Point> ComputeBestPath(Point startPt, Point endPt) {
- pbField.Refresh();
- field[startPt.X, startPt.Y].DistanceFromStart = 0;
- int x, y;
- List<Point> scanPoints = new List<Point>();
- List<Point> retPath = new List<Point>();
- scanPoints.Add(startPt);
- if (!field[startPt.X, startPt.Y].Cell.Traversable || !field[endPt.X, endPt.Y].Cell.Traversable) {
- bestPath.Clear();
- lblPathDifficulty.Text = "n/a";
- lblDistance.Text = "n/a";
- return new List<Point>();
- }
- int iterations = 0;
- bool searching = true;
- Point newPt = new Point();
- Point pt = endPt;
- double dist = initialDist;
- g.Clear(Color.Transparent);
- while (scanPoints.Count > 0 && searching) {
- x = scanPoints[0].X;
- y = scanPoints[0].Y;
- foreach (MoveDir p in ValidMoves(x, y)) {
- double d = field[x, y].DistanceFromStart + (field[p.X, p.Y].Cell.Difficulty * p.Distance);
- if (d < field[p.X, p.Y].DistanceFromStart) {
- if (cbShowScan.Checked)
- g.DrawRectangle(new Pen(Color.FromArgb(63, Color.White), 2f), p.X * cellSize + 1.5f, p.Y * cellSize + 1.5f, cellSize - 3, cellSize - 3);
- if (cbAnimateScan.Checked && ++iterations == numAnimationSpeed.Value) {
- pbField.Refresh();
- iterations = 0;
- }
- field[p.X, p.Y].DistanceFromStart = d;
- if (p.X == endPt.X && p.Y == endPt.Y) {
- searching = false;
- break;
- }
- scanPoints.Add(new Point(p.X, p.Y));
- }
- }
- scanPoints.RemoveAt(0);
- scanPoints = (from Point p in scanPoints
- orderby (field[p.X, p.Y].DistanceFromStart * diffWeight) + (CalculateDistance(p, endPt) * distWeight)
- select p).ToList();
- }
- double totalDiff = 0.0;
- if (field[endPt.X, endPt.Y].DistanceFromStart == initialDist)
- retPath.Clear();
- else {
- pt = endPt;
- int moveTurns = 0;
- searching = true;
- while (searching) {
- retPath.Insert(0, pt);
- totalDiff += field[pt.X, pt.Y].Cell.Difficulty;
- dist = initialDist;
- moveTurns++;
- foreach (MoveDir p in ValidMoves(pt.X, pt.Y)) {
- if (field[p.X, p.Y].DistanceFromStart < dist) {
- newPt = new Point(p.X, p.Y);
- dist = field[p.X, p.Y].DistanceFromStart;
- }
- }
- pt = newPt;
- if (newPt == startPt)
- searching = false;
- }
- }
- lblDistance.Text = (retPath.Count == 0 ? "no path" : retPath.Count.ToString());
- lblPathDifficulty.Text = totalDiff.ToString();
- return retPath;
- }
- IEnumerable<MoveDir> ValidMoves(int x, int y) {
- foreach (MoveDir pt in movePoints) {
- MoveDir p = new MoveDir(x + pt.X, y + pt.Y, pt.Distance);
- if (p.X >= 0 && p.X < maxX && p.Y >= 0 && p.Y < maxY) {
- if (field[p.X, p.Y].Cell.Traversable) {
- if (x != p.X && y != p.Y) {
- if (field[x, p.Y].Cell.Traversable && field[p.X, y].Cell.Traversable)
- yield return p;
- }
- else
- yield return p;
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement