Flutter for OpenHarmony 可视化教学：A* 寻路算法的交互式演示

enum CellType { empty, wall, start, end, path, visited }

class Point {
  final int x, y;
  // 重写 == 和 hashCode，使其可作为 Map 的 key
}

List<Point> openList = [start];
Set<Point> closedList = {};
Map<Point, Point> cameFrom = {}; // 记录父节点
Map<Point, double> gScore = {start: 0};
Map<Point, double> fScore = {start: _heuristic(start, end)};

double _heuristic(Point a, Point b) {
  return (a.x - b.x).abs() + (a.y - b.y).abs();
}

Future<void> _reconstructPath(Map<Point, Point> cameFrom, Point current) async {
  List<Point> totalPath = [];
  while (cameFrom.containsKey(current)) {
    current = cameFrom[current]!;
    totalPath.add(current);
  }
  // 从起点到终点反向遍历，再反转
  totalPath = totalPath.reversed.toList();
  // 逐个高亮为黄色
}

import 'dart:ui' as ui;
import 'package:flutter/material.dart';

void main() {
  runApp(const PathFindingApp());
}

class PathFindingApp extends StatelessWidget {
  const PathFindingApp({super.key});

  @override
  Widget build(BuildContext context) {
    return MaterialApp(
      title: 'A* 寻路算法',
      theme: ThemeData.dark(),
      home: const AStarVisualizer(),
      debugShowCheckedModeBanner: false,
    );
  }
}

// 网格状态枚举
enum CellType { empty, wall, start, end, path, visited }

// 二维坐标点
class Point {
  final int x, y;
  Point(this.x, this.y);

  @override
  bool operator ==(Object other) {
    return other is Point && x == other.x && y == other.y;
  }

  @override
  int get hashCode => Object.hash(x, y);
}

class AStarVisualizer extends StatefulWidget {
  const AStarVisualizer({super.key});

  @override
  State<AStarVisualizer> createState() => _AStarVisualizerState();
}

class _AStarVisualizerState extends State<AStarVisualizer> {
  static const int rows = 15;
  static const int cols = 20;
  late List<List<CellType>> grid;
  Point? start;
  Point? end;
  bool isRunning = false;

  @override
  void initState() {
    super.initState();
    _resetGrid();
  }

  void _resetGrid() {
    grid = List.generate(rows, (i) {
      return List.generate(cols, (j) {
        return CellType.empty;
      });
    });
    start = Point(1, 1);
    end = Point(rows - 2, cols - 2);
    grid[start!.x][start!.y] = CellType.start;
    grid[end!.x][end!.y] = CellType.end;
  }

  void _clearWalls() {
    for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) {
        if (grid[i][j] == CellType.wall) {
          grid[i][j] = CellType.empty;
        }
      }
    }
  }

  // A* 算法核心
  Future<void> _runAStar() async {
    if (start == null || end == null) return;

    setState(() {
      isRunning = true;
    });

    // 开启列表：待检查的节点
    List<Point> openList = [Point(start!.x, start!.y)];
    // 关闭列表：已检查的节点
    Set<Point> closedList = {};

    // 记录路径 (父节点映射)
    Map<Point, Point> cameFrom = {};

    // gScore: 从起点到该节点的实际代价
    Map<Point, double> gScore = {};
    gScore[start!] = 0;

    // fScore: 从起点经由该节点到终点的预估总代价
    Map<Point, double> fScore = {};
    fScore[start!] = _heuristic(start!, end!);

    while (openList.isNotEmpty) {
      // 1. 找到fScore最小的节点
      Point current = openList.reduce((a, b) {
        return (fScore[a] ?? double.infinity) < (fScore[b] ?? double.infinity)
            ? a
            : b;
      });

      // 2. 如果到达终点，重构路径
      if (current == end) {
        await _reconstructPath(cameFrom, current);
        setState(() {
          isRunning = false;
        });
        return;
      }

      // 3. 将当前节点移出开启列表，加入关闭列表
      openList.remove(current);
      closedList.add(current);

      // 可视化：标记为已访问
      if (grid[current.x][current.y] != CellType.start &&
          grid[current.x][current.y] != CellType.end) {
        grid[current.x][current.y] = CellType.visited;
        setState(() {});
        await Future.delayed(const Duration(milliseconds: 50));
      }

      // 4. 检查邻居 (上下左右)
      List<Point> neighbors = [
        Point(current.x - 1, current.y),
        Point(current.x + 1, current.y),
        Point(current.x, current.y - 1),
        Point(current.x, current.y + 1),
      ];

      for (Point neighbor in neighbors) {
        int x = neighbor.x;
        int y = neighbor.y;

        // 检查是否越界或为墙壁
        if (x < 0 ||
            x >= rows ||
            y < 0 ||
            y >= cols ||
            grid[x][y] == CellType.wall) {
          continue;
        }

        // 如果已经在关闭列表，跳过
        if (closedList.contains(neighbor)) {
          continue;
        }

        // 计算临时的gScore (从起点到邻居的代价)
        double tentativeGScore = (gScore[current] ?? double.infinity) + 1;

        // 如果该邻居不在开启列表中，或者找到了更短的路径
        if (!openList.contains(neighbor) ||
            tentativeGScore < (gScore[neighbor] ?? double.infinity)) {
          // 记录路径
          cameFrom[neighbor] = current;
          gScore[neighbor] = tentativeGScore;
          fScore[neighbor] = tentativeGScore + _heuristic(neighbor, end!);

          if (!openList.contains(neighbor)) {
            openList.add(neighbor);
          }
        }
      }
    }

    // 没有找到路径
    ScaffoldMessenger.of(context).showSnackBar(
      const SnackBar(content: Text('未找到可达路径！')),
    );
    setState(() {
      isRunning = false;
    });
  }

  // 启发式函数 (曼哈顿距离)
  double _heuristic(Point a, Point b) {
    return ((a.x - b.x).abs() + (a.y - b.y).abs()).toDouble();
  }

  // 重构路径
  Future<void> _reconstructPath(
      Map<Point, Point> cameFrom, Point current) async {
    List<Point> totalPath = [current];
    while (cameFrom.containsKey(current)) {
      current = cameFrom[current]!;
      totalPath.add(current);
    }
    totalPath = totalPath.reversed.toList();

    // 高亮显示路径
    for (Point p in totalPath) {
      if (p != start && p != end) {
        grid[p.x][p.y] = CellType.path;
        setState(() {});
        await Future.delayed(const Duration(milliseconds: 100));
      }
    }
  }

  @override
  Widget build(BuildContext context) {
    return Scaffold(
      appBar: AppBar(
        title: const Text('A* 寻路算法可视化'),
      ),
      body: Column(
        children: [
          const Text('绿色=起点, Red=终点, Gray=障碍物, Blue=探索中, Yellow=路径'),
          Expanded(
            child: GridView.builder(
              padding: const EdgeInsets.all(8),
              gridDelegate: SliverGridDelegateWithFixedCrossAxisCount(
                crossAxisCount: cols,
                mainAxisSpacing: 1,
                crossAxisSpacing: 1,
              ),
              itemCount: rows * cols,
              itemBuilder: (context, index) {
                int row = index ~/ cols;
                int col = index % cols;
                bool isStart = Point(row, col) == start;
                bool isEnd = Point(row, col) == end;

                Color color = Colors.transparent;
                if (grid[row][col] == CellType.wall) {
                  color = Colors.grey;
                } else if (grid[row][col] == CellType.visited) {
                  color = Colors.blue.withOpacity(0.5);
                } else if (grid[row][col] == CellType.path) {
                  color = Colors.yellow;
                } else if (isStart) {
                  color = Colors.green;
                } else if (isEnd) {
                  color = Colors.red;
                }

                return GestureDetector(
                  onTap: () {
                    if (isRunning) return;
                    setState(() {
                      if (grid[row][col] == CellType.empty) {
                        grid[row][col] = CellType.wall;
                      } else if (grid[row][col] == CellType.wall) {
                        grid[row][col] = CellType.empty;
                      }
                    });
                  },
                  child: Container(
                    decoration: BoxDecoration(color: color),
                    child: const SizedBox(),
                  ),
                );
              },
            ),
          ),
          Row(
            mainAxisAlignment: MainAxisAlignment.spaceEvenly,
            children: [
              ElevatedButton.icon(
                onPressed: () {
                  if (!isRunning) {
                    _resetGrid();
                    setState(() {});
                  }
                },
                icon: const Icon(Icons.refresh),
                label: const Text('重置'),
              ),
              ElevatedButton.icon(
                onPressed: () {
                  if (!isRunning) {
                    _clearWalls();
                    setState(() {});
                  }
                },
                icon: const Icon(Icons.delete),
                label: const Text('清空障碍'),
              ),
              ElevatedButton.icon(
                onPressed: _runAStar,
                icon: const Icon(Icons.route),
                label: Text(isRunning ? '运行中...' : '开始寻路'),
              ),
            ],
          ),
        ],
      ),
    );
  }
}