猴子与香蕉 AI 游戏
-
一款解决从源头到目的地寻找正确路径问题的 AI 游戏。
-
使用广度优先算法。
游戏 APK 下载安装链接
YouTube 上的游戏视频
解释游戏玩法
- 猴子找到四条通往香蕉的路。
- 它会走每一条路，检查香蕉是否在那里，或者什么。
- 如果在那里，它就赢了，否则它就走下一条路……
- 香蕉的目标或位置是随机的。
项目实现 (一些重要代码) :-
我们使用 Flutter 进行开发。
-
首先：我们使用图来设计 UI，并将游戏视为一组节点和边，然后使用广度优先算法，使用 Dart 中的迭代器来搜索随机目标 (香蕉)。
-
_BreadthFirstTree 创建 BreadthFirstIterator。此外，这两个集合都存储 Graph 对象以保存树数据结构本身。
ITreeIterator 为所有特定的树集合迭代器定义了一个通用接口
- hasNext() – 如果迭代器尚未到达集合末尾，则返回 true，否则返回 false；
- getNext() – 返回集合的下一个值；
- reset() – 重置迭代器并将当前位置设置为开头。
广度优先算法使用 **队列** 数据结构
来存储需要接下来访问的节点（顶点）。
Dart 中的图代码
一个存储图的邻接列表的类。它存储为映射数据结构，其中键代表节点的（顶点的）ID，值是与该 ID (键) 的顶点相邻的顶点的列表（其他节点 ID）。此外，该类定义了 addEdge() 方法来向邻接列表添加边。
class Graph {
final Map<int, Set<int>> adjacencyList = Map<int, Set<int>>();
void addEdge(int source, int target) {
if (adjacencyList.containsKey(source)) {
adjacencyList[source].add(target);
} else {
adjacencyList[source] = {target};
}
}
}
树集合
- BreadthFirstTreeCollection – 一个树集合类，它存储图对象并实现 createIterator() 方法来创建一个使用广度优先算法遍历图的迭代器。
class BreadthFirstTreeCollection implements ITreeCollection {
final Graph graph;
const BreadthFirstTreeCollection(this.graph);
@override
ITreeIterator createIterator() {
return BreadthFirstIterator(this);
}
@override
String getTitle() {
return 'Breadth-first';
}
}
广度优先算法代码 :-
- BreadthFirstIterator – 树迭代器的特定实现，它使用广度优先算法遍历树集合。该算法使用 **队列** 数据结构来存储需要通过 getNext() 方法访问的顶点（节点）。
class BreadthFirstIterator implements ITreeIterator {
final BreadthFirstTreeCollection treeCollection;
final Set<int> visitedNodes = <int>{};
final ListQueue<int> nodeQueue = ListQueue<int>();
final int _initialNode = 1;
int _currentNode;
BreadthFirstIterator(this.treeCollection) {
_currentNode = _initialNode;
nodeQueue.add(_initialNode);
}
Map<int, Set<int>> get adjacencyList => treeCollection.graph.adjacencyList;
@override
bool hasNext() {
return nodeQueue.isNotEmpty;
}
@override
int getNext() {
if (!hasNext()) {
return null;
}
_currentNode = nodeQueue.removeFirst();
visitedNodes.add(_currentNode);
if (adjacencyList.containsKey(_currentNode)) {
for (var node in adjacencyList[_currentNode]
.where((n) => !visitedNodes.contains(n))) {
nodeQueue.addLast(node);
}
}
return _currentNode;
}
@override
void reset() {
_currentNode = _initialNode;
visitedNodes.clear();
nodeQueue.clear();
nodeQueue.add(_initialNode);
}
}
图 (节点 & 边) 定义
Graph _buildGraph() {
var graph = Graph();
graph.addEdge(1, 21);
graph.addEdge(1, 22);
graph.addEdge(1, 23);
graph.addEdge(1, 24);
graph.addEdge(21, 31);
graph.addEdge(21, 25);
graph.addEdge(21, 20);
graph.addEdge(21, 14);
graph.addEdge(21, 13);
graph.addEdge(21, 7);
graph.addEdge(21, 11);
graph.addEdge(21, 28);
....
....
....
....
return graph;
}
