Welcome to my blog. You can post whatever you like!

The blog post is using markdown, and here is a simple guide. Markdown Guide

LOGIN TO POST A BLOG

steam游戏LYNE及AI

Satori

Author: Satori

Posted: 2017-06-29 18:11:16

Category: AI LYNE 技术 游戏

Views: 524 Comments: 0

最近steam夏季打折,不得不剁手233,在推荐里面看到了一款叫LYNE的小游戏,很符合我的风格233 [LYNE 游戏steam地址][1] ![LYNE][2] 这个游戏规则很简单,就是类似一笔画把所有的相同图案一笔画画完。 比如上图就有3个不同的图案,三角形、菱形和正方形。其中每个图形有两个特别的图案,分别对应这个图案的起点和终点。对于每种图形而言,从起点出发,画出一条路径把这种图形全部串进来,最后走向终点。一共有8个方向可以走(**不越界**的情况下),然后所有画出的路径不能交叉。当从一个起点出发的时候一路上只能走相同的图形,不能去其他的图形。 其中这游戏难点在于除了基本图案之外还有一个正八边形的特殊图形,它可以起到一个桥梁的作用,任何图形都能走到它那里,不过从这个图形出来的图形必须是另一个正八边形或者和起点相同的图案,它中间有孔,孔的个数代表需要从其它图形走到它那里几次(也就是**入度**),走多走少都不行。 但是这个游戏不好的一点是关卡太多,一共26个大关,每一个大关有25个小关,一共650关,打起来相当费劲,到后期难度非常大,非常耗时,很多时候需要试,打玩3个大关的时候,我就已经不行了QAQ 其实这个游戏最难的地方还是在于正八边形,它最灵活,任意图形都能到它,导致出现很多种可能性。游戏后期大量出现孔很多的正八边形,给游戏带来许多困难。 ### **所以我机智地写了一个AI去解决这个问题** 整体的思路是基于递归回溯,步骤如下。 - 先选一个没有走过的起点 - 从起点出发,寻找正八边形或者同形状的图形 - 判断某个方向走是否会发生边的碰撞 - 新到的点是否为终点,如果是换一个起点 - 如果所有起点走完了,就看看所有的图形和正八边形是否走完或者走全了,是就返回结果,不是就回溯。 ### 具体到代码,主要用以下几个数据结构: - map: 用于存原始棋盘的信息,用数字代表图形的种类,特别的,0代表正八边形 - end_point: 用于存储不同种类图形的起点和终点 - need_visit: 用于存某个点需要走过的个数(普通图形为1,正八边形为孔的个数,当所有点数值为0时认为遍历成功) - link: 用于存储哪些点相连,用于边的碰撞检测 - res: 用于存走过点的顺序集合,也就是最终的结果 ### 具体的代码如下: ``` #include <vector> #include <string> #include <fstream> using namespace std; typedef pair<int, int> Point; // The max size of the map int const MAX = 10; int row, col; // map: the map of original map, number start from 1 represents different type, 0 represent general point int map[MAX][MAX]; // end_point: the map of end point, number start from 1 represents the end point, 0 represent non endpoint int end_point[MAX][MAX]; // need_visit: the count of times that the point should be visited int need_visit[MAX][MAX]; // link: the collection of connected points vector<pair<Point, Point>> link; // res: the result of the route vector<Point> res; // final_res: the partitioned result vector<vector<Point>> final_res; void init() { // initial array for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { map[i][j] = -1; end_point[i][j] = 0; need_visit[i][j] = 0; } } ifstream in("in.txt"); in >> row; in >> col; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { char ch; in >> ch; // normal point if (ch >= 'a' && ch <= 'z') { map[i][j] = ch - 'a' + 1; need_visit[i][j] = 1; } // general point else if (ch >= '0' && ch <= '9') { map[i][j] = 0; need_visit[i][j] = ch - '0'; } // end point else if (ch >= 'A' && ch <= 'Z') { map[i][j] = ch - 'A' + 1; end_point[i][j] = ch - 'A' + 1; need_visit[i][j] = 1; } } } in.close(); } Point findEndPoint() { for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { // if it is a end point that is not visited if (end_point[i][j] != 0 && need_visit[i][j] > 0) { return Point(i, j); } } } return Point(-1, -1); } bool judgeAllVisited() { // judge if all point is visited for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { // if a point is not visited if (need_visit[i][j] != 0) { return false; } } } return true; } bool isInBoundary(int r, int c) { return r >= 0 && r < row && c >= 0 && c < col && map[r][c] >= 0; } bool isSameType(Point &cur, Point &next, int cur_type) { if (map[cur.first][cur.second] == map[next.first][next.second]) { return true; } // if next is a general point if (map[next.first][next.second] == 0) { return true; } // if next point follows the same pattern if (map[cur.first][cur.second] == 0 && map[next.first][next.second] == cur_type) { return true; } return false; } bool isEdgeConfilct(Point &a, Point &b) { for (pair<Point, Point> &p : link) { // if the edge has already existed if (p.first == a && p.second == b || p.first == b && p.second == a) { return true; } // if the cross edge existed Point c(a.first, b.second), d(b.first, a.second); if (p.first == c && p.second == d || p.first == d && p.second == c) { return true; } } return false; } bool isEndPoint(Point &p) { if (isInBoundary(p.first, p.second)) { return end_point[p.first][p.second] > 0; } return false; } bool find(Point cur_point, int cur_type, bool is_begin = false) { // if ends with an terminate point if (isEndPoint(cur_point) && !is_begin) { return find(Point(-1, -1), -1); } // if no terminate point is selected, then select one if (cur_point.first == -1 && cur_point.second == -1) { cur_point = findEndPoint(); // if no terminate point is found if (cur_point.first == -1 && cur_point.second == -1) { // if all visited, solution found, else backtrace return judgeAllVisited(); } // if find a end point else { res.push_back(cur_point); need_visit[cur_point.first][cur_point.second]--; if (find(cur_point, map[cur_point.first][cur_point.second], true)) { return true; } // if there's no solution on current situation, recover the state else { res.pop_back(); need_visit[cur_point.first][cur_point.second]++; return false; } } } // select the current point int cur_row = cur_point.first; int cur_col = cur_point.second; // choose from eight directions for (int offset_row = -1; offset_row <= 1; offset_row++) { for (int offset_col = -1; offset_col <= 1; offset_col++) { int next_row = cur_row + offset_row; int next_col = cur_col + offset_col; // next point is not the current point and the next point not exceed boundary if (!(offset_row == 0 && offset_col == 0) && isInBoundary(next_row, next_col)) { Point next_point = Point(next_row, next_col); // if next point is of same type and is not visited if (need_visit[next_row][next_col] > 0 && isSameType(cur_point, next_point, cur_type)) { // if the edge is not conflict if (!isEdgeConfilct(cur_point, next_point)) { link.push_back(pair<Point, Point>(cur_point, next_point)); res.push_back(next_point); need_visit[next_point.first][next_point.second]--; // test next step if (find(next_point, cur_type)) { return true; } // if next step fails else { link.pop_back(); res.pop_back(); need_visit[next_point.first][next_point.second]++; } } } } } } // if all directions fail return false; } void foramat_result() { vector<Point> tmp; bool is_startp = true; for (int i = 0; i < (int)res.size(); i++) { tmp.push_back(res[i]); if (end_point[res[i].first][res[i].second]) { if (!is_startp) { final_res.push_back(tmp); tmp.clear(); } is_startp ^= 1; } } } void output() { ofstream os("out.txt"); for (vector<Point> &vec : final_res) { os << '(' << vec[0].first + 1 << ", " << vec[0].second + 1 << ')' << endl; for (int i = 0; i < (int)vec.size() - 1; i++) { int cur_row = vec[i].first, cur_col = vec[i].second; int next_row = vec[i + 1].first, next_col = vec[i + 1].second; int r = next_row - cur_row + 1, c = next_col - cur_col + 1; string symbol[3][3] = { "↖", "↑", "↗", "←", "", "→", "↙", "↓", "↘"}; os << symbol[r][c] << " "; } os << endl; } os.close(); } int main(void) { init(); find(Point(-1, -1), -1, true); foramat_result(); output(); return 0; } ``` 写代码的时候主要遇到两个问题。 第一个是判断起点终点问题。当一个图形遍历完后要开始下一个图形的遍历,我在调用函数时把当前结点改为非法结点来判断是否需要重新分配起点,但是后面马上有一个逻辑判断是否到了终点,到了就重新分配起点。问题就在这里,在逻辑上起点和终点是等价的,可以交换的,从起点到终点和从终点到起点是等效的,当分配一个起点的时候,递归进入下一层的时候马上就会判定到了终点,然后又重新分配起点。 所以解决方法就是强行在递归调用的时候加一个标签判断是否是新分配的结点。如果是新分配的结点就不当成终点,也就不再分配起点了。 第二个是判断同类型图形的问题。这个问题主要发生在正八边形的时候。对于正八边形而言,所有到它的结点都能成立,但是从正八边形出来的图形就不一定了,从正八边形出来的图形必须和起点的图形相匹配,因此递归调用的时候需要知道当前序列的起点是哪种类型的图形,根据这个判断从正八边形出来的图形到底是那个。 总之花了大概半天的时间写出来了,还是比较高兴的。主要是可以拿全成就,有A-Z一共26个成就,感觉还是不错的233. ### 代码的使用方法 1. 编译源代码 2. 编写输入文件,文件命名为`in.txt` 文件编写规则: 第一行, 写行数和列数,用空格隔开 从第二行起,为每个图形编写符号,符号之间用空格隔开,编写符号及规则如下: 3. 运行程序,得到out.txt |图形|表示方法|备注| |:-----:|:------:|:------:| |空|?|如果某一格没有图形,用问号表示| |一般图形|小写字母a到z|一般图形,如三角形、正方形、菱形| |端点图形|大写字母A到Z|相同的图形大写字母和小写字母匹配| |正八边形|数字2到4|正八边形有几个孔就是几| 示例: ``` 4 3 ? A B c C 2 C 3 2 B c A ``` 意思是棋盘有4行3列, 第一行第一列没有图形,第一行第二列和第四行第三列是同一个图形,而且都是端点。第一行第三列和第四行第一列是另外一种图形,而且都是端点,第二行第一列第二列、第三行第一列、第四行第二列又是另外一种图形,其中第二行第二列和第三行第一列是端点。最后第二行第三列和第三行第二列和第三行第三列是数字,分别代表有2、3、2个孔的正八边形。 最后根据out.txt来得到走的序列路径。 [1]: https://store.steampowered.com/app/266010/LYNE/ [2]: https://lh4.ggpht.com/bdr5fWHTqNBz26TMe6Eyuh1jou-Qt2QpH92PT-ERz3I5i01DXZgzo9WV2q2g5nt8XA=h900

Read More